Metric Indexing for Graph Similarity Search
Bause F, Blumenthal DB, Schubert E, Kriege NM (2021)
Publication Type: Conference contribution, Conference Contribution
Publication year: 2021
Publisher: Springer International Publishing
Series: Lecture Notes in Computer Science
City/Town: Cham
Book Volume: 13058
Pages Range: 323--336
Conference Proceedings Title: Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021)
Event location: Dortmund
ISBN: 978-3-030-89657-7
DOI: 10.1007/978-3-030-89657-7_24
Abstract
Finding the graphs that are most similar to a query graph in a large database is a common task with various applications. A widely-used similarity measure is the graph edit distance, which provides an intuitive notion of similarity and naturally supports graphs with vertex and edge attributes. Since its computation is {\$}{\$}{\backslash}mathsf {\{}NP{\}}{\$}{\$}NP-hard, techniques for accelerating similarity search have been studied extensively. However, index-based approaches for this are almost exclusively designed for graphs with categorical vertex and edge labels and uniform edit costs. We propose a filter-verification framework for similarity search, which supports non-uniform edit costs for graphs with arbitrary attributes. We employ an expensive lower bound obtained by solving an optimal assignment problem. This filter distance satisfies the triangle inequality, making it suitable for acceleration by metric indexing. In subsequent stages, assignment-based upper bounds are used to avoid further exact distance computations. Our extensive experimental evaluation shows that a significant runtime advantage over both a linear scan and state-of-the-art methods is achieved.
Authors with CRIS profile
Involved external institutions
Austria (AT)How to cite
APA:
Bause, F., Blumenthal, D.B., Schubert, E., & Kriege, N.M. (2021). Metric Indexing for Graph Similarity Search. In Reyes N, Connor R, Kriege N, Kazempour D, Bartolini I, Schubert E, Chen J (Eds.), Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021) (pp. 323--336). Dortmund, DE: Cham: Springer International Publishing.
MLA:
Bause, Franka, et al. "Metric Indexing for Graph Similarity Search." Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021), Dortmund Ed. Reyes N, Connor R, Kriege N, Kazempour D, Bartolini I, Schubert E, Chen J, Cham: Springer International Publishing, 2021. 323--336.
BibTeX: Download