Research map / Graph learning / GNN architectures

Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing

NeurIPS 2026 · Graph learning › GNN architectures · approach: Graph rewiring and scalable message passing · 0 citations (OpenAlex)

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 four axioms characterizing k-range graph tasks and the TRIP/GRIP constructions using stable-distribution features, plus a per-range MLE oracle, and audits LRGB, LRIM, GLoRa, and ECHO.

Problem

Existing long-range graph benchmarks (LRGB, LRIM, GLoRa, ECHO) are not verifiably long-ranged on arbitrary graphs, so claims that over-squashing mitigations improve long-range modeling are unverified.

Approach

Define a k-range task via four axioms (predictability, tightness, strict k-range, topology-invariance) and construct TRIP targets as f-stable aggregates of i.i.d. node features over the exact k-hop boundary, so any graph becomes a provably k-range task with graph-independent marginal entropy; GRIP composes multiple ranges and yields a closed-form per-range MLE lower bound.

Key results

• On TRIP-instantiated graphs, per-range Spearman correlation between minimum balanced-Forman edge curvature and GNN MSE stays within |rho| < 0.4, indicating curvature is not predictive of error.
• On TRIP-instantiated ECHO topologies, PHDGN and SWAN remain meaningful learners at k=4 while GCN, GIN, GCNII, GraphCON, ADGN and GRIT saturate at MSE 1.0 (constant-mean baseline).
• A range-9 classifier attains at least about 70% accuracy on GLoRa-15 since about 35% of instances are resolvable with hops at most 9.

Surprising findings

• Balanced-Forman curvature is uncorrelated with GNN error on TRIP tasks, supporting a topological vs computational bottleneck distinction.
• PHDGN's advantage on TRIP-instantiated ECHO topologies is absent on the original ECHO tasks, suggesting that original ECHO gaps are not purely due to long-rangedness.

Limitations

• TRIP assumes i.i.d. node features, which enforces low feature homophily and excludes correlated real-world features.
• Empirical range certification is limited to ranges up to about 4 for some models, and the post-hoc range measure averages across ranges and can underestimate range.
• Cross-graph comparisons are confounded when boundary sizes vary (e.g. SDRF rewired graphs with mostly empty boundaries).

Experimental setup

Datasets: LRGB LRIM GLoRa ECHO TRIP-instantiated ECHO topologies (charge, synth) expected-degree random graphs

Benchmarks: TRIP-instantiated cycles TRIP-instantiated expected-degree graphs with SDRF TRIP-instantiated ECHO charge and synth topologies ECHO sssp, eccentricity, charge (audit) GLoRa (audit)

Metrics: test MSE post-hoc Jacobian range Spearman correlation between minimum edge curvature and MSE

Baselines: GCN GIN GCNII GraphCON ADGN GRIT SWAN PHDGN

Builds on: Long Range Graph Benchmark Stochastic Discrete Ricci Flow Jacobian-based range measure ECHO LRIM

Closest papers by meaning

• On Measuring Long-Range Interactions in Graph Neural Networks (ICML 2025 · similarity 0.89)
• Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective (NeurIPS 2026 · similarity 0.87)
• Effects of Dropout on Performance in Long-range Graph Learning Tasks (NeurIPS 2025 · similarity 0.86)
• The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited (ICLR 2025 · similarity 0.86)
• Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching (ICML 2025 · similarity 0.86)
• Delaunay Graph: Addressing Over-Squashing and Over-Smoothing Using Delaunay Triangulation (ICML 2024 · similarity 0.86)