Titel
EmbAssi: embedding assignment costs for similarity search in large graph databases
Autor*in
Abstract
The graph edit distance is an intuitive measure to quantify the dissimilarity of graphs, but its computation is NP-hard and challenging in practice. We introduce methods for answering nearest neighbor and range queries regarding this distance efficiently for large databases with up to millions of graphs. We build on the filter-verification paradigm, where lower and upper bounds are used to reduce the number of exact computations of the graph edit distance. Highly effective bounds for this involve solving a linear assignment problem for each graph in the database, which is prohibitive in massive datasets. Index-based approaches typically provide only weak bounds leading to high computational costs verification. In this work, we derive novel lower bounds for efficient filtering from restricted assignment problems, where the cost function is a tree metric. This special case allows embedding the costs of optimal assignments isometrically into ℓ1 space, rendering efficient indexing possible. We propose several lower bounds of the graph edit distance obtained from tree metrics reflecting the edit costs, which are combined for effective filtering. Our method termed EmbAssi can be integrated into existing filter-verification pipelines as a fast and effective pre-filtering step. Empirically we show that for many real-world graphs our lower bounds are already close to the exact graph edit distance, while our index construction and search scales to very large databases.
Stichwort
Graph edit distanceSimilarity searchIndex
Objekt-Typ
Sprache
Englisch [eng]
Persistent identifier
Erschienen in
Titel
Data Mining and Knowledge Discovery
Band
36
Ausgabe
5
ISSN
1384-5810
Erscheinungsdatum
2022
Seitenanfang
1728
Seitenende
1755
Publication
Springer Science and Business Media LLC
Projekt
Kod / Identifikator
VRG19-009
Erscheinungsdatum
2022
Zugänglichkeit
Rechte
Rechteangabe
© The Author(s) 2022
Universität Wien | Universitätsring 1 | 1010 Wien | T
+43-1-4277-0