Research map / Graph learning / GNN architectures
On Measuring Long-Range Interactions in Graph Neural Networks
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.
Formalizes long-range interactions in graph tasks by deriving a unique, axiomatically grounded range measure (Jacobian- and Hessian-based) and uses it to validate synthetic tasks and critically assess LRGB models.
Problem
x
Approach
Derive a range measure from four/five axiomatic properties (locality, unit interaction, additivity, homogeneity, normalized additivity) that yields the expected graph distance over the absolute Jacobian (node-level) or Hessian (graph-level) influence distribution, applicable to any differentiable GNN or task at node, graph, and dataset granularity.
Key results
- On VOCSuperpixels, MPNNs reach a final SPD range of about 2-3 hops while GPS and GT reach about 10, with range correlating positively with performance.
- On PeptidesFunc and PeptidesStruct, MPNNs maintain a range of about 1 hop and perform similarly well, suggesting these tasks are inherently local.
- Trained linear GCNs with residual connections approach the true task range (1.33 for 5-hop task) as depth and training progress, with lower MSE for deeper models.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use higher-range architectures, including global-attention models, rather than MPNNs | VOCSuperpixels models · VOCSuperpixels | performance | Helped |
| Use global attention, increasing model range relative to GCN | VOCSuperpixels models · VOCSuperpixels validation | SPD range: 2.32 ± 0.098 -> 9.15 ± 0.525 | Helped |
| Add a virtual node to GCN | VOCSuperpixels models · VOCSuperpixels | performance | Helped |
| Add a virtual node to GCN | Peptides models · Peptides-func and Peptides-struct | performance | No clear effect |
| Use higher-range models such as GPS or GT instead of MPNNs | Peptides models · Peptides-func and Peptides-struct | performance | Hurt |
| Add a virtual node to GCN | GCN on heterophilic tasks · Amazon-Ratings and Roman-Empire | performance | No clear effect |
| Use local Transformer-style attention instead of standard GCN message passing | Local GT · Amazon-Ratings and Roman-Empire | performance | Helped |
| Add GeLU nonlinearity to the synthetic k-Power GCN (ablation) | Synthetic node-level k-Power task · Synthetic k-Power | range | No clear effect |
| Add a virtual node to the synthetic GCN (ablation) | Synthetic node-level k-Power task · Synthetic k-Power | range | Mixed |
| Add a virtual node to the synthetic GCN (ablation) | Synthetic graph-level k-Power model · Synthetic graph-level k-Power | range | Mixed |
| Reduce the Peptides differentiable atom encoding from 174 dimensions to 31 (ablation) | Peptides models · Peptides-func and Peptides-struct | performance | No clear effect |
Surprising findings
- PeptidesFunc and PeptidesStruct appear largely local: GT and GPS, despite larger ranges, perform worst on PeptidesFunc, and range does not improve MPNN performance.
- On Cora and heterophilic datasets, graph transformers can learn short-range behavior matching GCN range, and virtual nodes increase range without performance gains.
Limitations
- Range of a real-world trained model only approximates task range when validation error is near zero; otherwise it is a heuristic correlated with performance.
- Peptides datasets contain disconnected graphs, complicating SPD-based diameter and range computation.
- Hessian-based graph-level range is not yet evaluated on real-world benchmarks due to computational cost.
Experimental setup
Datasets: VOCSuperpixels PeptidesFunc PeptidesStruct Cora Amazon-Ratings Roman-Empire
Benchmarks: VOCSuperpixels PeptidesFunc PeptidesStruct Cora Amazon-Ratings Roman-Empire
Metrics: range (normalized SPD / resistance) F1 score average precision mean absolute error MSE
Baselines: GCN GINE GatedGCN GPS GT GCN+VN
Builds on: influence functions mixing measure problem radius LRGB
Closest papers by meaning
- Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing (NeurIPS 2026 · similarity 0.89)
- Learning Long Range Dependencies on Graphs via Random Walks (ICLR 2025 · similarity 0.89)
- Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks (NeurIPS 2025 · similarity 0.88)
- Long Range Propagation on Continuous-Time Dynamic Graphs (ICML 2024 · similarity 0.88)
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.87)
- Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching (ICML 2025 · similarity 0.87)
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.