Metric Indexing for Graph Similarity Search

Franka Bause, David B. Blumenthal, Erich Schubert, Nils M. Kriege

Graph-structured data is fundamental to numerous domains, ranging from bioinformatics and chemical informatics to social network analysis. Determining the similarity between two graphs is a core operation in these fields, typically quantified by the Graph Edit Distance (GED). GED measures the minimum cost required to transform one graph into another through a sequence of edit operations: vertex/edge insertions, deletions, and substitutions.

Despite its utility, computing GED is an NP-hard problem, making direct comparisons in large databases computationally prohibitive. While various "filter-verification" frameworks have been proposed to accelerate this process, most are restricted to uniform edit costs and categorical labels. This paper introduces a novel multi-stage framework designed to handle arbitrary metric edit costs, enabling efficient similarity searches even for graphs with complex, continuous attributes.

The Filter-Verification Pipeline

The core contribution of this work is a sophisticated multi-stage pipeline that prunes the search space by orders of magnitude before resorting to expensive exact solvers.

The multi-stage filter-verification pipeline for graph similarity search.

The pipeline consists of three primary stages:

  1. Metric Indexing (The First Filter): The authors utilize a lower bound called BRANCH. A critical property of BRANCH is that it satisfies the triangle inequality, making it a pseudo-metric. This allows the use of established metric indexing structures, such as Vantage Point Trees (vp-trees) and Cover Trees. By indexing the database using this lower bound, the system can bypass large portions of the dataset that are mathematically guaranteed to fall outside the search radius.
  2. Upper Bound Pruning: For graphs that pass the initial metric filter, the system calculates two upper bounds: BranchUB and a refined version, BranchRUB, which employs local search. If a graph's upper bound is within the search threshold, it is immediately identified as a match, avoiding further computation.
  3. Exact Verification: Only a small fraction of candidate graphs—those whose lower bound is below the threshold but whose upper bound is above it—are passed to an exact GED solver like BSS_GED or BLPF2-V.

Handling Arbitrary Metric Costs

A significant limitation of prior research is the reliance on uniform costs (e.g., every edit costs 1). In real-world applications, such as comparing molecules with 3D coordinates, a small change in position should incur a lower cost than a large one. The proposed framework addresses this by supporting arbitrary metric edit costs.

Definitions of vertex and edge edit costs supported by the framework.

By formalizing costs for substitutions, deletions, and insertions as shown above, the framework can handle continuous attributes and non-uniform labels. The BRANCH lower bound remains effective in these scenarios, bridging the gap between complex graph theory and efficient metric space indexing.

Experimental Evaluation and Insights

The researchers evaluated the framework across diverse benchmarks from the TUDataset collection, including categorical datasets (MUTAG, PTC_FM) and those with continuous attributes (Fingerprint, Letter, Cuneiform). To test scalability, they used the QM9 dataset, containing over 129,000 organic molecules.

Key findings include:

  • Scalability: On the QM9 dataset, metric indexing reduced filtering time by several orders of magnitude compared to traditional linear scans.
  • Pruning Efficiency: The BranchRUB upper bound proved remarkably tight, often identifying nearly all results and leaving very few candidates for the final NP-hard verification step.
  • Index Performance: While both vp-trees and Cover Trees were effective, Cover Trees demonstrated superior performance during the indexing phase, making them better suited for dynamic environments.

Conclusion

By leveraging the triangle inequality of the BRANCH lower bound, this research successfully applies decades of metric indexing expertise to the challenge of graph similarity search. The resulting framework provides a scalable, flexible solution for searching large graph databases with complex attributes and non-uniform costs, significantly advancing the state-of-the-art in graph-based data retrieval.

Summary updated

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 $$\mathsf {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.
BibTeX
@inproceedings{bause2021metric,
  author = {Franka Bause and David B. Blumenthal and Erich Schubert and Nils M. Kriege},
  title = {{Metric Indexing for Graph Similarity Search}},
  booktitle = {SISAP},
  year = {2021},
  doi = {10.1007/978-3-030-89657-7\_24},
}
Figure