Abstract
Subgraph matching is a fundamental operation for querying graph-structured data. Due to potential errors and noises in real-world graph data, exact subgraph matching is sometimes inappropriate in practice. In this paper we consider an approximate subgraph matching model that allows missing edges. Based on this model, approximate subgraph matching finds all occurrences of a given query graph in a database graph, allowing missing edges. A straightforward approach is to first generate query subgraphs of a given query graph by deleting edges and then perform exact subgraph matching for each query subgraph. In this paper we propose a sharing-based approach to approximate subgraph matching, called SASUM. Our method is based on the fact that query subgraphs are highly overlapped. Due to this overlapping nature of query subgraphs, the matches of a query subgraph can be computed from the matches of a smaller query subgraph, which results in reducing the number of query subgraphs that require expensive exact subgraph matching. Our method uses a lattice framework to identify sharing opportunities between query subgraphs. To further reduce the number of graphs that need exact subgraph matching, SASUM generates small base graphs that are shared by query subgraphs and chooses the minimum number of base graphs whose matches are used to derive the matching results of all query subgraphs. A comprehensive set of experiments shows that our approach outperforms the state-of-the-art approach by orders of magnitude in terms of query execution time.
Introduction
Finding a specific pattern within a massive network—such as a specific protein interaction in a biological database or a fraudulent transaction pattern in a financial web—is a classic computational challenge known as subgraph matching. In its exact form, the goal is to find all instances of a small query graph $Q$ within a large database graph $G$. However, real-world data is often noisy or incomplete. For instance, in Protein-Protein Interaction (PPI) networks, many edges may be missing due to experimental limitations. Consequently, exact matching often fails to find relevant patterns, necessitating approximate subgraph matching.
The Challenge of Approximate Matching
Approximate subgraph matching allows for a user-defined number of missing edges, denoted by a threshold $\theta$. A common strategy to solve this is to generate all possible subgraphs of $Q$ formed by deleting up to $\theta$ edges and then perform exact matching for each variation. However, as $\theta$ increases, the number of these variations explodes combinatorially. Since exact subgraph matching is an NP-complete problem, searching for hundreds or thousands of variations individually becomes computationally prohibitive.
The SASUM Approach: Exploiting Redundancy
The core innovation of SASUM (Sharing-based approach to Approximate SUbgraph Matching) is the realization that these query variations are not independent; they are highly redundant.
The Lattice Framework
SASUM organizes all possible query subgraphs into a "query lattice." In this structure, if one subgraph is contained within another, their results can be shared. If a match for a larger pattern is found, it inherently contains matches for all its smaller sub-patterns. This hierarchical organization allows the system to identify sharing opportunities systematically.
Base Graphs and Seed Selection
To further optimize, SASUM "prunes" edges to create even smaller base graphs—tiny structural building blocks shared by multiple query variations. The problem then becomes: what is the smallest set of these base graphs we need to search for to reconstruct every required approximate match? SASUM treats this as a "Set Cover" problem and employs a greedy algorithm to select a minimal set of seed graphs.
Filter and Extend
Once the seeds are matched against the database using an exact matching engine, SASUM uses a "filter and extend" approach. It efficiently derives the matches for all other subgraphs in the lattice by extending the results obtained from the seeds, rather than starting every search from scratch.
Experimental Evaluation
The authors evaluated SASUM against SAPPER, the previous state-of-the-art, using several datasets:
- Synthetic Datasets: Scalability tests with up to 10,000 vertices and varying edge densities.
- Human Protein Interaction Network (PPIN): A real-world biological graph (10,527 vertices, 40,903 edges).
- Collaboration Network: A social graph of authors (5,241 vertices, 14,484 edges).
Key Results
The experiments demonstrated that SASUM outperformed SAPPER by orders of magnitude in query execution time. Specifically, SASUM consistently reduced the number of required exact subgraph matching executions by more than 50%. Interestingly, as the error threshold $\theta$ increases—making the problem harder for traditional methods—the efficiency of SASUM actually improves because the increased number of subgraphs provides even more opportunities for structural sharing.
Conclusion
SASUM transforms the combinatorial explosion of approximate subgraph matching from a burden into an asset. By exploiting structural overlaps through a lattice framework and optimizing seed selection via a set-cover strategy, it significantly reduces the overhead of expensive isomorphism tests. Future work may involve extending this sharing logic to directed graphs or distributed frameworks to handle web-scale graphs with billions of edges.
Summary updated