Research map / Graph learning / Graph algorithms and clustering
GraSP: Simple Yet Effective Graph Similarity Predictions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GraSP, a graph similarity predictor for GED and MCS that uses random-walk positional encodings, a gated residual RGGC GNN, and multi-scale pooling, avoiding cross-graph node interactions.
Problem
Predicting graph edit distance (GED) and maximum common subgraph (MCS) similarity between graph pairs efficiently and accurately, since exact computation is NP-hard and existing GNN methods rely on costly cross-graph node-level interactions.
Approach
Enhance node features with random-walk positional encoding (RWPE) to exceed 1-WL expressiveness, encode graphs with a ResGatedGraphConv backbone and multi-scale (attention + sum) pooling, and predict similarity from graph embeddings alone via Euclidean distance plus NTN interaction, with no cross-graph node matching.
Key results
- On AIDS700nef GED prediction, GraSP reaches P@10 0.741 vs. 0.662 for the best competitor EGSC (about 11.9% relative gain).
- On LINUX GED prediction, GraSP reduces MAE to 0.042 versus 0.080 for the best competitor ERIC.
- On PTC MCS prediction, GraSP achieves Kendall's tau 0.762 versus 0.7 for the runner-up GEDGNN; GraSP is reported as the fastest inference method on all datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GraSP instead of the strongest reported GED baseline | Graph similarity prediction · AIDS700nef, IMDBMulti, LINUX, and PTC | MAE: 0.667 $\pm$0.010 -> 0.640 $\pm$0.013; 4.397 $\pm$0.101 -> 3.966 $\pm$0.064; 0.080 $\pm$0.011 -> 0.042 $\pm$0.003; 3.743 | Helped |
| Use GraSP instead of the strongest reported MCS baseline | Graph similarity prediction · AIDS700nef, IMDBMulti, and PTC | MAE: 0.335 $\pm$0.006 -> 0.330 $\pm$0.007; 0.147 $\pm$0.012 -> 0.134 $\pm$0.018; 1.170 $\pm$0.127 -> 1.162 $\pm$0.028 | Helped |
| Use GraSP instead of ERIC | Graph similarity prediction · LINUX MCS | MAE: 0.037 $\pm$0.009 -> 0.037 $\pm$0.005 | No clear effect |
| Use RGGC instead of GIN or GCN as the backbone (ablation) | GraSP · AIDS700nef GED | MAE: 0.677 $\pm$0.013 -> 0.640 $\pm$0.013; 0.654 $\pm$0.011 -> 0.640 $\pm$0.013 | Helped |
| Add positional encoding (ablation) | GraSP · AIDS700nef GED | MAE: 0.651 $\pm$0.016 -> 0.640 $\pm$0.013 | Helped |
| Add attention pooling to summation pooling (ablation) | GraSP · AIDS700nef GED | MAE: 0.666 $\pm$0.006 -> 0.640 $\pm$0.013 | Helped |
| Add summation pooling to attention pooling (ablation) | GraSP · AIDS700nef GED | MAE: 0.662 $\pm$0.002 -> 0.640 $\pm$0.013 | Helped |
| Add NTN interaction (ablation) | GraSP · AIDS700nef GED | MAE: 0.662 $\pm$0.003 -> 0.640 $\pm$0.013 | Helped |
| Increase RWPE step size (ablation) | GraSP · AIDS700nef | MAE | Mixed |
| Increase GNN layer count or hidden dimension beyond the optimal settings (ablation) | GraSP · AIDS700nef | MAE | Hurt |
Surprising findings
- Ablation on LINUX shows removing the NTN raises MAE from 0.042 to 0.321, while on PTC removing NTN gives a lower MAE (3.367) than the full model (3.556).
Limitations
- Compared baselines' heads were modified and some methods extended to MCS by the authors, which may affect fairness of comparison.
- Ground-truth GEDs on IMDBMulti and PTC are approximations (min of Beam, Hungarian, VJ), not exact values.
- Performance on PTC MCS and some metrics is not uniformly best; on LINUX GED, NA-GSL achieves higher P@10.
Experimental setup
Datasets: AIDS700nef IMDBMulti LINUX PTC
Benchmarks: AIDS700nef IMDBMulti LINUX PTC
Metrics: MAE Spearman's rho Kendall's tau Precision@10 Precision@20
Baselines: SimGNN GraphSim GMN MGMN H2MN EGSC ERIC Greed NA-GSL GEDGNN
Builds on: SimGNN GEDGNN Greed ResGatedGraphConv RWPE
Closest papers by meaning
- Position: Graph Matching Systems Deserve Better Benchmarks (ICML 2025 · similarity 0.88)
- GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code (ICML 2025 · similarity 0.87)
- Graph Edit Distance with General Costs Using Neural Set Divergence (NeurIPS 2024 · similarity 0.86)
- Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN (NeurIPS 2025 · similarity 0.85)
- GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights (NeurIPS 2025 · similarity 0.85)
- Graph Classification via Reference Distribution Learning: Theory and Practice (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.