Search papers, labs, and topics across Lattice.
This paper introduces a formal framework with four verifiable axioms (Predictability, Tightness, Strictly $k$-Range, and Topology-Invariance) to rigorously define and construct genuinely long-range graph benchmarks for Graph Neural Networks (GNNs). The authors then propose TRIP and GRIP, constructive procedures that generate such benchmarks from arbitrary graphs, providing a per-range lower bound on test error via a closed-form oracle. Auditing existing benchmarks reveals their limitations, and experiments on GRIP-instantiated topologies decouple curvature from GNN performance, highlighting computational bottlenecks.
Most "long-range" GNN benchmarks fail to actually test long-range interactions, but a new framework provides provably long-ranged tasks and a per-range error oracle.
Empirical claims about the connection between over-squashing and long-range interactions in GNNs, can only be trusted if the benchmarks used to validate them genuinely require long-range interactions. The de-facto standard, the Long Range Graph Benchmark, has been repeatedly shown to be saturated by tuned short-range models, with existing synthetic alternatives being tied to specific topologies. As such, there is a lack of principled certificate of long-rangedness on arbitrary graphs. This state reflects the absence of a precise characterization of long-ranged benchmarks. We address this fundamental gap by introducing four verifiable axioms: Predictability, Tightness, Strictly $k$-Range, and Topology-Invariance, that any task claiming to test $k$-hop interactions must satisfy. We formally prove that violating any one of them admits failure modes that undermine conclusions drawn from the task. Based on these axioms, we introduce TRIP (Truly Ranged Interactions Problem) and its generalisation GRIP (Generally Ranged Interactions Problem), constructive procedures that turn any graph into a provably long-ranged task by drawing features from stable distributions. Moreover, by construction, GRIP admits a closed-form, per-range Maximum-Likelihood oracle that yields the first a priori per-range lower bound on test error available on any benchmark. Using our framework, we: (i) audit 4 common long-range benchmarks and identify their failures modes with respect to our axioms; (ii) on TRIP-instantiated topologies, we find a popular notion of curvature is uncorrelated with GNN performance, supporting topological-vs-computational bottleneck distinction; and (iii) we show that a novel benchmark's over-squashing measures factors beyond pure long-rangedness. Code to use the framework and reproduce experiments is released https://github.com/ferranhernandezc/graph-grip.
