Research map / Graph learning / GNN architectures
Locality-Aware Graph Rewiring in GNNs
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 LASER, a locality-aware sequential graph rewiring framework that adds sparse, distance-constrained edges across multiple snapshots, prioritized by a walk-count connectivity measure, to mitigate over-squashing in GNNs.
Problem
Graph rewiring to mitigate over-squashing in MPNNs typically either densifies the graph (spatial methods, breaking sparsity) or adds long-range edges that destroy locality (spectral methods); no method satisfies connectivity, locality, and sparsity simultaneously.
Approach
Instead of one rewired graph, build a sequence of snapshots where the ℓ-th snapshot adds edges only between nodes at shortest-path distance ℓ+1, selecting a fraction ρ of them with the lowest k-step walk-count connectivity score, and aggregate each snapshot as a separate relation (multi-relational GNN view).
Key results
- On Peptides-func, LASER reaches 0.6440 test AP versus 0.5930 for no rewiring and 0.6012 for BORF, the best baseline.
- On TUDatasets, LASER attains the best mean rank of 1.37 across six datasets, with first place on IMDB-BINARY, MUTAG, ENZYMES, PROTEINS and COLLAB.
- LASER rewires a 100k-node, million-edge graph in about 2 hours, whereas FOSR and SDRF did not finish within 24 hours.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply LASER rewiring instead of the strongest reported baseline | GCN · Peptides-func | Average Precision (AP): 0.6012$\pm$0.0031 -> 0.6440$\pm$0.0010 | Helped |
| apply LASER rewiring instead of the strongest reported baseline | GCN · Peptides-struct | Mean Absolute Error (MAE): 0.3078$\pm$0.0026 -> 0.3043$\pm$0.0019 | Helped |
| apply LASER rewiring instead of the strongest reported baseline | GCN · PCQM-Contact | Mean Reciprocal Rank (MRR): 0.3007$\pm$0.0022 -> 0.3275$\pm$0.0011 | Helped |
| apply LASER rewiring instead of the strongest reported baseline | GCN · REDDIT-BINARY | accuracy: 85.930$\pm$2.793 -> 85.458$\pm$2.827 | No clear effect |
| apply LASER rewiring instead of the strongest reported baseline | GCN · IMDB-BINARY | accuracy: 64.280$\pm$1.990 -> 64.333$\pm$3.298 | No clear effect |
| apply LASER rewiring instead of the strongest reported baseline | GCN · MUTAG | accuracy: 81.684$\pm$7.964 -> 82.204$\pm$6.728 | No clear effect |
| apply LASER rewiring instead of the strongest reported baseline | GCN · ENZYMES | accuracy: 30.567$\pm$6.188 -> 34.333$\pm$6.936 | Helped |
| apply LASER rewiring instead of the strongest reported baseline | GCN · PROTEINS | accuracy: 72.714$\pm$2.946 -> 74.381$\pm$3.443 | Helped |
| apply LASER rewiring instead of the strongest reported baseline | GCN · COLLAB | accuracy: 70.222$\pm$2.571 -> 70.923$\pm$2.538 | No clear effect |
| sample edges randomly instead of prioritizing the lowest connectivity scores (ablation) | LASER, L=3, ρ=0.1 on Peptides · Peptides-func | Average Precision (AP): 0.6414$\pm$0.0020 -> 0.4796$\pm$0.0067 | Hurt |
| sample edges randomly instead of prioritizing the lowest connectivity scores (ablation) | LASER, L=3, ρ=0.1 on Peptides · Peptides-struct | Mean Absolute Error (MAE): 0.3119$\pm$0.0005 -> 0.3382$\pm$0.0019 | Hurt |
| use node ID to break ties rather than sample uniformly among tied nodes (ablation) | LASER on Peptides · Peptides-func | Average Precision (AP): 0.6447$\pm$0.0033 -> 0.6385$\pm$0.0048 | Hurt |
Surprising findings
- Spectral rewirings such as FOSR can hurt performance when relational models are not used, with GCN-FOSR-R reaching only 0.4629 AP on Peptides-func versus 0.5930 for plain GCN.
- The authors note that the TUDatasets baselines are of questionable quality, with high variance and a plain GCN and R-GCN without rewiring reporting inconsistent accuracies on MUTAG.
Limitations
- Only one instance of the general paradigm (LASER-GCN) with simple connectivity and locality measures is explored.
- The TUDatasets used are small, featureless in several cases, and show high variance, so conclusions there are tentative.
- Improvements are hard to attribute with certainty to over-squashing rather than other effects, as the authors acknowledge.
Experimental setup
Datasets: Peptides-func Peptides-struct PCQM-Contact REDDIT-BINARY IMDB-BINARY MUTAG ENZYMES PROTEINS COLLAB
Benchmarks: Peptides-func Peptides-struct PCQM-Contact REDDIT-BINARY IMDB-BINARY MUTAG ENZYMES PROTEINS COLLAB
Metrics: Average Precision Mean Absolute Error Mean Reciprocal Rank accuracy mean rank effective resistance Frobenius norm of distance matrix difference
Baselines: None SDRF GTR FOSR BORF DiffWire
Builds on: R-GCN FOSR GTR SDRF BORF
Closest papers by meaning
- GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring (ICLR 2025 · similarity 0.92)
- The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited (ICLR 2025 · similarity 0.92)
- Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.91)
- PANDA: Expanded Width-Aware Message Passing Beyond Rewiring (ICML 2024 · similarity 0.91)
- Probabilistic Graph Rewiring via Virtual Nodes (NeurIPS 2024 · similarity 0.91)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.90)
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.