TL;DR
This paper tackles the computationally expensive problem of calculating graph edit distance (GED), a crucial metric for graph similarity. They introduce novel polynomial-time methods to compute upper and lower bounds for GED, enabling efficient approximate graph search algorithms (APPFULL and APPSUB) that significantly outperform exact methods on large graph databases.
What Problem Does This Paper Address?
Graph edit distance (GED) is a widely accepted measure for determining the similarity between graphs, with applications ranging from pattern recognition to bioinformatics. However, computing the exact GED is an NP-hard problem, making it computationally infeasible for large graphs commonly found in real-world databases. This computational bottleneck limits the practical application of GED in large-scale graph search scenarios. The paper aims to bridge this gap by developing efficient methods to approximate GED, thereby enabling scalable graph search.
Methods
The core innovation of this paper lies in the introduction of "star representations" for graph structures. A star structure captures the local neighborhood of a vertex. By transforming graphs into multisets of these star structures, the authors devise three novel methods to compute polynomial-time bounds for GED:
- Lower Bound ($L_m$): This bound is derived from a mapping distance calculated using bipartite graph matching on the star representations. The Hungarian algorithm is employed for this matching.
- Upper Bounds ($\tau$ and $p$):
- $\tau$ is a simpler upper bound derived from the star edit distance.
- $p$ is a refined upper bound obtained through an iterative refinement process on the bipartite graph mapping, aiming to improve the approximation.
These bounds are then integrated into two approximate graph search algorithms:
- APPFULL: For approximate full graph search, it uses the bounds ($L_m$, $\tau$, and $p$) in a tiered filtering approach to quickly discard dissimilar graphs before resorting to expensive exact GED computation.
- APPSUB: For approximate subgraph search, it adapts the star representation and bounds to handle subgraph isomorphism, offering an alternative to methods like edge relaxation.
Datasets
The paper evaluates their methods using two types of datasets:
- Real Dataset: The AIDS antivirus compound dataset, a publicly available dataset commonly used in graph mining research.
- Synthetic Datasets: Generated using a graph data generator (Kuramochi and Karypis), allowing for controlled experiments on scalability with varying numbers of graphs and graph sizes.
Key Insights and Ideas
- Star Representation as a Bridge: The novel "star representation" effectively decomposes complex graph structures into manageable local neighborhoods, making GED approximation tractable.
- Tiered Filtering for Efficiency: The APPFULL algorithm's multi-level filtering strategy, starting with the cheapest bound ($L_m$) and progressing to more expensive ones ($\tau$, $p$), is crucial for its efficiency. This avoids costly exact GED computations for most graphs.
- GED for Subgraph Search: Adapting GED for subgraph search (without vertex relabeling) provides a more robust similarity measure compared to methods like edge relaxation, which might miss visually similar graphs.
- Scalability is Key: The NP-hard nature of exact GED necessitates approximation. The proposed bounds and algorithms demonstrate significant speedups (orders of magnitude) while maintaining reasonable accuracy, making them practical for large-scale applications.
Key Results
- Significant Speedup: The proposed bounding algorithms ($L_m$, $\tau$, $p$) are over 10,000 times faster than exact GED computation (ACT) on small graphs.
- Tighter Bounds: The upper bound $p$ is shown to be tighter than the simpler upper bound $\tau$, and $L_m$ provides a good lower bound.
- Effective Graph Search: APPFULL and APPSUB significantly reduce the number of expensive exact GED computations required for graph search tasks. APPFULL, in particular, requires a negligible runtime for approximate search compared to exact computation.
- Scalability: The bounding algorithms exhibit good scalability with respect to both the number of graphs and the size of graphs on both synthetic and real datasets.
- Comparison to BLP: While the BLP lower bound is slightly tighter, the proposed $L_m$ is 1000-10,000 times faster. The proposed upper bound $p$ is also tighter than the BLP upper bound.
Limitations and Future Work
- Directed Graphs: The current work focuses on undirected graphs. The authors mention that their algorithms can be easily extended to directed graphs by redefining the star structure and edit distance accordingly.
- Local Optimality of $p$: The iterative refinement approach for computing $p$ is guaranteed to find a local optimum, not necessarily a global one. The authors note that in practice, it performs well and converges quickly.
- Theoretical vs. Practical Performance: While theoretical complexities are analyzed, the paper emphasizes the practical performance gains observed in experiments.
- Further Optimization: The paper suggests that further research could explore more sophisticated methods for computing the mapping distance and refining the upper bounds.
Summary updated