Abstract
GraSP (GRAph Similarity Prediction) is a streamlined GNN-based framework designed to predict graph similarity in linear time. Unlike previous state-of-the-art models that rely on computationally expensive quadratic cross-graph interactions, GraSP utilizes random walk positional encodings and a novel multi-scale pooling strategy. This approach achieves superior accuracy on Graph Edit Distance (GED) and Maximum Common Subgraph (MCS) tasks while maintaining high scalability and speed.
Introduction
Comparing the similarity between two graphs—known as Graph Similarity Computation (GSC)—is a cornerstone of tasks such as drug discovery, social network analysis, and bug detection. The two gold-standard metrics for this are Graph Edit Distance (GED), which measures the minimum cost to transform one graph into another, and Maximum Common Subgraph (MCS), which identifies the largest structure shared by both.
Calculating these metrics exactly is NP-hard. Consequently, researchers have turned to Graph Neural Networks (GNNs) to predict these values. However, most existing models rely on "cross-graph interactions," where every node in the first graph is compared to every node in the second. This creates a computational bottleneck with $O(N^2)$ complexity, making them impractical for large-scale applications. GraSP aims to prove that better results can be achieved with a simpler, linear-time architecture.
Methods
GraSP moves away from node-to-node comparisons and instead focuses on generating high-quality graph-level embeddings. Its architecture consists of four main stages:
- Enhanced Node Features: Standard GNNs are often limited by the "1-WL test," preventing them from distinguishing between certain graph structures. GraSP bypasses this by using Random Walk Positional Encoding (RWPE), which injects global topological information into each node's initial features.
- RGGC Backbone: The model employs ResGatedGraphConv (RGGC) layers. This GNN variant uses gating mechanisms to control information flow and residual connections to prevent gradient vanishing, offering more robustness than standard GCNs.
- Multi-Scale Pooling: A key innovation of GraSP is its hybrid pooling strategy. It combines Attention Pooling, which identifies "important" nodes, with Summation Pooling, which captures the overall scale of the graph. A learnable parameter allows the model to find the optimal balance between these two methods.
- Similarity Prediction: Finally, the two graph embeddings are compared using a combination of Euclidean distance and a Neural Tensor Network (NTN). This dual approach captures both geometric distance and complex relational interactions.
Experimental Results
The authors evaluated GraSP on four widely used benchmarks: AIDS700nef (chemical compounds), LINUX (Program Dependency Graphs), IMDBMulti (ego-networks), and PTC (toxicology compounds). For small graphs, exact A* algorithms provided ground truth, while high-quality combinatorial approximations (Beam, Hungarian, and VJ) were used for larger graphs.
Key Findings
- State-of-the-Art Accuracy: GraSP outperformed 10 major competitors, including SIMGNN and GMN. On the AIDS700nef dataset, it improved the Precision@10 (P@10) by 11.9% over the previous best model.
- Unmatched Efficiency: Because its complexity is linear ($O(|V|)$) rather than quadratic, GraSP is significantly faster and remains efficient as graph sizes increase.
- Superior Generalization: In "zero-shot" tests—training on small graphs and testing on much larger ones—GraSP maintained its performance better than more complex models like GREED and H2MN.
Discussion and Conclusion
The most surprising insight from this work is that explicit cross-graph node interactions, long considered necessary for high accuracy, may actually be a hindrance. By focusing on superior individual graph representations and breaking the 1-WL ceiling with RWPE, GraSP achieves higher accuracy with much lower complexity.
While the current framework focuses on node-labeled graphs, future work could extend these principles to edge-heavy tasks like knowledge graphs. GraSP serves as a powerful, efficient backbone for graph similarity and potentially other graph-related tasks such as classification or regression in drug discovery pipelines.
Summary updated