% Encoding: UTF-8
@COMMENT{BibTeX export based on data in FAU CRIS: https://cris.fau.de/}
@COMMENT{For any questions please write to cris-support@fau.de}
@inproceedings{faucris.266012676,
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.},
address = {Cham},
author = {Bause, Franka and Blumenthal, David B. and Schubert, Erich and Kriege, Nils M.},
booktitle = {Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021)},
date = {2021-09-29/2021-10-01},
doi = {10.1007/978-3-030-89657-7{\_}24},
editor = {Reyes N, Connor R, Kriege N, Kazempour D, Bartolini I, Schubert E, Chen J},
faupublication = {yes},
isbn = {978-3-030-89657-7},
pages = {323--336},
peerreviewed = {Yes},
publisher = {Springer International Publishing},
series = {Lecture Notes in Computer Science},
title = {{Metric} {Indexing} for {Graph} {Similarity} {Search}},
venue = {Dortmund},
volume = {13058},
year = {2021}
}