Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement
Authors: Huidong Liang
Haitz Sáez de Ocáriz Borde
Baskaran Sripathmanathan
Michael M. Bronstein
Xiaowen Dong
Venue: ICLR 2026 Poster (2026)
Keywords: Graph Neural Networks
Long-range dependency
Primary area: learning on graphs and other geometries & topologies
TL;DR: We introduce a large-scale transductive learning dataset for testing long-range dependencies in GNNs, and propose a measurement with theoretical justifications.

Abstract: Long-range dependencies are critical for effective graph representation learning, yet most existing datasets focus on small graphs tailored to inductive tasks, offering limited insight into long-range interactions. Current evaluations primarily compare models employing global attention (e.g., graph transformers) with those using local neighborhood aggregation (e.g., message-passing neural networks) without a direct measurement of long-range dependency. In this work, we introduce $\texttt{City-Networks}$, a novel large-scale transductive learning dataset derived from real-world city road networks. This dataset features graphs with over $10^5$ nodes and significantly larger diameters than those in existing benchmarks, naturally embodying long-range information. We annotate the graphs based on local node eccentricities, ensuring that the classification task inherently requires information from distant nodes. Furthermore, we propose a generic measurement based on the Jacobians of neighbors from distant hops, offering a principled quantification of long-range dependencies. Finally, we provide theoretical justifications for both our dataset design and the proposed measurement—particularly by focusing on over-smoothing and influence score dilution—which establishes a robust foundation for further exploration of long-range interactions in graph neural networks.

Published as a conference paper at ICLR 2026
TOWARDS QUANTIFYING LONG-RANGE INTERAC- TIONS IN GRAPH MACHINE LEARNING: A LARGE GRAPH DATASET AND A MEASUREMENT
Huidong Liang"
Haitz Sáez de Ocáriz Borde*
Baskaran Sripathmanathan"
Michael Bronstein
Xiaowen Dong
University of Oxford
ABSTRACT
Long-range dependencies are critical for effective graph representation learning, yet most existing datasets focus on small graphs tailored to inductive tasks, offering limited insight into long-range interactions. Current evaluations primarily compare models employing global attention (e.g., graph transformers) with those using local neighborhood aggregation (e.g., message-passing neural networks) with- out direct measurement of long-range dependency. In this work, introduce Kity-Networkk novel large-scale transductive learning dataset derived from real-world city road networks. This dataset features graphs with over 105 nodes and significantly larger diameters than those existing benchmarks, naturally embody- ing long-range information. We annotate the graphs based on local node eccentrici- ties, ensuring that the classification task inherently requires information from distant nodes. Furthermore, we propose generic measurement based on the Jacobians of neighbors from distant hops, offering principled quantification of long aaggrangee dependencies. Finally, we provide theoretical justifications for both our dataset de- sign and the proposed measurement -aatinenntttattullrrry. by focusing on over-smoothing and influence score dilution, which establishes robust foundation for further exploration of rangerane interactions in graph neural networks. Our dataset and measurement are available on PyTorch Geometric, and the code for reproducing the experimental results be found at giggguth..com wwwp:////....eeeeereeeee/eeeeeee
Paris
Shangbai
Los Angeles
London
Figure 1: Visualizations of Nity-Networks for Paris, Shanghai, Los Angeles, and London.
INTRODUCTION
Graphs are a widely used mathematical abstraction across nearly every branch of science. They particularly effective for modeling the intricate and non-uniform interactions found in real- world data, where nodes stand in for objects and edges depict their connections. The growing recognition of the versatility of graph representations has sparked intense interest Graph Neural
"qqual contribution, contact hui dong. lianggeng.ox.c.

---

Published as a conference paper at ICLR 2026
Networks (GNNs) (Scarselli et al., 2009 Wu et al., 2021 driving innovation in deep learning for both geometric and graph-centric applications. Most GNNs, in particular variants based on a message-passing mechanism (Gilmer et al. (017)) exchange information between one-hop neighbors per layer to build node representations. While they found wide success in analysing citation and social networks (Yang et al., 201 one significant limitation concerns their capability of handling long-range dependencies, where interactions between distant nodes might be required to solve a task. Most existing datasets are not sufficient in assessing this: for instance, social networks, despite comprising thousands of nodes, often exhibit the small world effect (Watts & Strogatz, (998) with short average path lengths and high clustering coefficients. The node labels on these graphs usually possess homophilic pattern where nodes tend to connect with "similar" or "alike" others (McPherson et al. 200T), making possible to propagate sufficient information for modelling with only a few passsagg-passing layers. On the other hand, while connected nodes tend to have different properties on heterophilic graphs (Zhu et al. 2020; Ma et al. 2022), solving the tasks in those cases do not necessarily require the handling of long-range dependencies
& Errica 2025).
Recently, Long Range Graph Benchmark (LRGB) (Dwivedi et al., 2023) introduces alternative graph datasets based on super-pixels and molecules with larger diameters than those of the previous works. To justify the existence of long- rong-rangeness, the authors compare classical GNNs with Graph Transformers (GTs), which leverage global attentions over the entire graph, and associate the observed performance gaps with the presence of long-range dependencies. However, conclusions that are mainly derived from empirical comparisons may not be reliable as they can be largely influenced by hyperparameter tuning (Tönshoff' et al. 2024), leading to an ambiguous assessment of the long-range interactions. Moreover, LRGB and other synthetic long-range benchmarks (Bodnar et al. 202T Zhou et al. 2025) all focus on inductive learning tasks with relatively small graphs typically on the order of 10 to 102 nodes, while currently there is no long-range benchmark that considers large graphs with real-world topology for transductive learning. This is a critical gap in the literature since applying GT's (Rampášek et al., 2022), which are expected to better capture long-range interactions, to large graphs is significantly more challenging compared to amall-graphy inductive tasks due to the computational complexity in its positional encoding and global attention (Borde 2024).
We aim to address these limitations in this work, and our main contributions are as follows:
We propose Ci City-Networr a transductive learning dataset that consists of four large-scale city road networks with a topology distinct from those commonly found in the literature. In particular, it features grid-like large graphs with up to 500k nodes and diameters of up to 400, where the labels are annotated based on node accessibility that inherently requires long-range dependency in its calculation. To the best of our knowledge, this is the first large-graph dataset designed for testing long-range dependencies in graph representation learning.
We empirically test classical GNNs and GTs on our dataset under different model depths, and compare their behaviors to those on other common graph datasets that are short-ranged, large-scale, heterophilic, or long-range dependent. The results on our datasets, unlike those on the existing datasets, suggest that communication with neighbors from distant hops consistently improves the performance of all models, supporting the presence of long-range signals.
To quantify such long-range dependency, we further introduce a generic measurement that quantifies per-hop influence of focal node's 's neighbors on its prediction, which is estimated by the aggregated & -nomm of the Jacobian from a trained model for the task at hand at each hop around the focal node. This per-hop analysis of the task range goes beyond the concurrent work of [Bamberger et al. (2025) and provides novel insights: we observe that distant hops exert a greater influence on all baseline models our Nett-Neetwok compared to those on other commonly used graph datasets in the literature.
Finally, we theoretically justify the graph structure in our dataset from spectral perspective on over-smoothing, whose rate we link to the algebraic connectivity and diameter of the graph. In addition, we relate our proposed measurement to the concept of influence as defined in the literature, and study the dilution of mean influence score in grid-like graphs to justify our design.
Here, generic means that the metric can be applied any differentiable GNN or Graph Transformer, without requiring architectural modifications or assumptions about the model class.
2

---

Published as a conference paper at ICLR 2026
Table 1: Statistics of Cit city-Networks compared to common graph datasets, where d, C, T, diam, homo represent degree, clustering coefficient, transitivity, diameter, and homophily, respectively.
Dataset
#Nodes
#Edges
avg(d)
std(d)
mux(d)
diam
homo
Paris
114k
1834
3.2
0.8
15
0.03
0.03
0.70
Shanghai
184k
2634
2.9
1.0
8
0.04
0.04
123
0.75
Los Angeles
241A
343k
2.8
0.04
0.05
0.75
London
569k
759k
2.7
1.0
10
0.04
0.05
404
0.76
Cora
2.7k
5.34
3.9
5.2
168
0.24
0.09
19
0.81
ogbn-arxiv
169k
1.16m
13.7
68.6
13k
0.23
0.02
0.65
Amazon-Rate Rannn-atiinnn EaizonnRaatnge
24k
93k
7.6
6.0
132
0.58
0.31
46
0.38
Pasca VVC-SPP
479
1.3k
5.7
0.43
0.40
0.92
THE CITY-NETWORKS DATASET
In this section, we begin by identifying the limitations and challenges in current literature. Then, we characterize how the topology of City-Networkk differs from the existing datasets, and proceed to justify the rationale behind our long-range labeling strategy. Lastly, we explain how our dataset addresses the current limitation and discuss the new challenges brought the field.
Challenges in testing long-range dependency. To design and fairly evaluate graph datasets of long-range dependency, we need address three research challenges:
How can we generate long-rand range signals in a principled and controllable manner, so that models required to communicate with sufficiently distant neighbors of node predict its label?
2. Beyond the small graphs used in LRGB or other synthetic benchmarks, how can we design long-range signals on large real-world networks to the scalability of model?
3. How define principled measure to quantify and compare the level of long-rangeness across different datasets?
We will discuss how our proposed dataset handles the first two challenges in this section, and address the third challenge Section
2.1 LARGE-SCALE ROAD NETWORKS WITH LONG DIAMETERS
Real-world network topologies and features. As shown in Figure D our City-Networks consists of street maps in four cities: Paris, Shanghai, Los Angeles, and London, which are obtained by querying OpenStreetMap (Haklay Weber 2008) with OSMnx (Boeing 2024). particular, consider city network inclusive of all types of roads in the city (c.g., drive, bike, walk, etc.), where nodes represent road junctions with features like longitude, latitude, land use, etc.; and edges represent road segments with features like road length, speed limit, road types, etc. Next, facilitate a typical node classification task, we apply a simple neighborhood aggregation that transforms edge features into node features by averaging the features of incidental edges and then concatenating them to the features of the focal node. These new node features represent, for instance, the average speed limit around road junction or the probability of finding residential road nearby. As a result, the final dataset contains 37 node features, where we also make the graphs undirected so that they only represent connectivity between junctions, and retain the largest connected component each city. We refer readers to Appendix C. for complete list of features and our approach in dataset processing.
Large graphs with long diameters and low maximum degrees. We can observe from Table T that our datasets feature large diameters from 100 to 400, which are much longer than those of the common graphs used in the literature. particular, compared to the super-pixel graphs in P Pascalle wascalvoo-- VOC SP with typically 500 nodes, our datasets have much larger sizes ranging from 100k to 500k. Mean- while, compared to social networks such as Cora, ogbn-arxiv, and Ama 2 -n-Rat ings, our City-Net works have smaller average clustering coefficients and much lower maximum degrees. We argue that this distinct graph topology enables us to effectively design learnable long-range signals graphs, explained in the next paragraph and further justified theoretically in Section
3

---

Published as a conference paper at ICLR 2026
(a) Huangpu, Shanghai
(b) Pasadena, Los Angeles
Visualizations of node accessibility estimations based on local eccentricity in two sub- regions, where darker colors indicate smaller eccentricity values, i.e. nodes that are easier access.
Figure 2:
2.2 LONG-RANCE LABELS BASED ON URBAN ACCESSIBILITY
Based the city road networks, design real-world task that requires the handling of long range dependencies. Specifically, we aim to predict how accessible a road junction is based on its own location well neighboring characteristics of the urban landscape. This is useful task especially when it comes to evaluating urban design principles such as the 15-minute city (Abbiasov et al. 2024). To quantify accessibility, measure the distance one needs to travel from one road junction to its k-hop neighbors along road segments in the road network. By design, solving this task requires the model be able to access information within the k-hop neighborhood of each focal node and, by adjusting k, we can design long-range task as desired. Such a notion of accessibility is directly related node eccentricity E(V) in network science (Newman) 2018), which looks the maximum distance from to all other nodes in the graph G = (V,
However, using the exact eccentricity as signals not ideal for two reasons. First, we cannot control the level of long-rangeness, as eccentricity is determined by the entire graph structure and not adjustable by design. In particular, although predicting s(v) appears to require distant information based its definition, in many cases (Figure Appendix C.2) p. the underlying signal can be well
inferred by spatial features (e.g., geographical coordinates) alone. This is because nodes in the city center generally have lower eccentricity due to the grid-like topology in road networks. Second, the calculation of eccentricity requires computing all pair-wise shortest paths in the network, which is typically cost ((V)) and is hence prohibitively expensive for labeling our large-scale networks.
Node classification task based on local eccentricity. With the above consideration in mind, we propose local eccentricity measure éx (v) that only considers k-hop neighbors (u( of node when calculating the longest shortest paths with the following expressions:
E (v) = max (w, u), (u) (v)
[((e), min P(MM))
(I)
.E
where (w, u) is the weighted shortest path distance from node node u, P(v, u) is the set of all possible paths from node to node and w(e) denotes the edge weight for edge (we use road length for this particular purpose, while all other cases, the graphs are considered unweighted). To design classification task, we then split éx (v) for all nodes into 10 quantiles which we use as node labels for the classification task.
We emphasize that this local approach is introduced not only for computational efficiency, but it also brings in two important considerations. First, it creates long-range signals that extend to k-hop neighbors by design, i.e., known "ground-truthi range, hence is directly controllable and testable. Second, it ensures both graph topology and node features contribute to the modelling, avoiding the problem of high correlation between node signal with either the graph structure node features
4

---

Published as a conference paper at ICLR 2026
alone. Indeed, since k and the edge weights used to compute (v) are unknown to the model, it must integrate structural information from distant neighborhoods with their spatial information (geographic location, road type, land use, etc.) to infer the rongerange signal, which makes the task non-trivial. We provide a deeper analysis in Appendix C.3
regarding the roles of graph structure and spatial features.
Choice of the long-range level k. To assess long-range dependency, k should be sufficiently large to distinguish our setting from short-range tasks (e.g., social graphs with typical message passing around 4 hops). Thanks to the large grid-like topology with long diameters, can create long enough node signals based on different local networks. At the same time, k should also not be too large such that (i) the selected neighborhoods maintain local characteristics; and (ii) baseline models under a k-layer architecture, which captures the required information, can fit into common GPUs for fair benchmarking purposes. After experimenting with values from 8 to 32 (Figure g Appendix C.4). we design the task at k=16, which strikes balance between sufficient long-rangeness and computational efficiency. We refer readers to Appendix for a more detailed justification of our methods.
Visualizations and interpretations. As shown in equation calculating (v) naturally requires information from distant neighbors up to & hops, and it carries a practical meaning which relates to the accessibility of node in the network. As an illustration, we visualize two sub-regions from the city maps in Figure 2 with k=16. We can observe that nodes on major transportation routes such as freeways and highways tend to have larger eccentricities than those in populated areas. This is because reaching a node's 16-hop neighbors from a highway junction often requires traveling a much longer distance compared to road junctions in a downtown area. It is also clear from Figure that that significant part of the graph topology is grid-like and possibly quasi-isometric to lattice, as we will later discuss in Section 6 Note that the homophily scores, as reported in Table are reasonably high since nodes with similar & tend to cluster together.
New challenges for learning long-range dependencies. The proposed dataset presents a significant challenge for both GNNs and GTs. In general, such long-range dependencies create fundamental trade-off for graph learning: while increasing the number of layers in GNNs helps propagate information from distant hops. it also leads to issues such as wworssmootiing (Li et al. 2018 Ni
Maehara 2019 Rusch et al.) (023), over-squashing (Alon Yahav] [02T]] Topping et 2022, Di Giovanni al. 2023), ), and vanishing gradients (Arroyo et al. (025]. On the other hand, GT's which rely on attention mechanisms with quadratic computational complexity, face scalability challenges when applied to our large-scale city networks compared to learning smaller long-ranged graphs
like those in LRGB (wwivedi et al. 2023) and other synthetic benchmarks (Zhou et al. 2025
BENCHMARKS: FROM CLASSICAL GNNS TO GRAPH TRANSFORMERS
In this section, we benchmark classical GNNs and GTss at different numbers of message-passe passing layers City-Networks, and then contrast their behaviors with results other commonly used graphs to examine the long-range dependencies across datasets.
Experimental setups. We consider transductive node classification with train/validation/tsst splits of 10%/10% /80% on all -Netyy-eetrrke in which we evaluate various classical GNNs and GTss.
Specifically, we benchmark GCN (Kipf & Welling 2017). GraphSAGE (Hamilton et al. (017)) GAT /Veličković et al. 2018). and GCNII (Chen et al. (020)) for GNNs; and GraphGPS (Rampášek) al. 2022), Exphormer (Shirzad et al. 2023), and SGF (Wu al. 2023) for GTs. In addition, an MLP is also included to reflect the importance of graph topology (or lack thereof) in our task. Lastly, we fix the data split for benchmarking purposes and report the mean and standard deviation of the test accuracy over 5 runs with different random seeds.
Evaluation protocols. As a hypothesis, when a graph model is predicting on a certain node v, it will benefit from communicating with v's neighbors from distant hops if the task is wong-rnnged Following this rationale, we evaluate baseline models at different numbers of layers L = [2, 4, 8, 16). with the expectation that a larger L would lead to better performance after sufficient training. By comparison, we also evaluate the same baselines on four representative datasets from the literature: Cora, ogbn-arxiss Amazon-Roo ings, and PascalVOCe VOC-SP from LRGB, which are homophilous, large-scale, heterophilous, and long-range dependent, respectively. We then compare the behaviors of baseline models across different datasets while increasing the number of layers T..
5

---

Published as a conference paper at ICLR 2026
Paris
Shanghoi
Los Angeles
London
80
80
80
80
Test Agc
60
60
60
60
40
40
40
40
20
16
2
16
8
16
2
16
ogbn arxiv
Amazoon-Ratinn Raaions
PascalVOC-SP
80
80
80
80
Test Ace
60
60
60
40-
40-
40-
40
20
20
2
16
2
Layers
Layers
Layers
Layers
MLP
GCN
GriphSAGE
GAT
GOND
GrughGPS
Exphormer
SGFormer
Figure 3: Baseline results across datasets different number of layers L = for GraphGPS are not shown on London as it is Out-of-Memory on our 48GB GPU; the result for SGFormer on Pascalvoc-S5 is also not reported as it's not originally designed for inductive setting.
=2 12,4,8, 16). The results
For fair comparison purposes, we follow the latest GNN tuning technique from Luo al, (2024) that considers residual connection, normalization, dropout, etc. Readers are also referred Appendix D.2 for full details on our training and experimental setups.
Results. From Figure we can observe clear and consistent improvement in performance for all baselines on our City-Network as their message- saassaggppssingg depth increases from to 16. It suggests that, even with sufficient training, shallow graph model cannot outperform its deeper counterpart if does not communicate with sufficiently distant hops. This result also means that the gains from incorporating long-range information L. increases outweigh other side effects of depth. By contrast, the performance of baseline models gradually degrades as L increases on Cora and ogbn arxiv due to the locality of these tasks and depth-related issues. To elaborate on this matter, we further provide a theoretical justification for our dataset in Section where we link the rate of wver-smothhing prominent issue associated with depth) to the algebraic connectivity and network diameter of the underlying graph. On the other hand, the baseline performance remains relatively unchanged with only a slight increase on Ama monzon-ee ings and Pasca VOC-SP, which suggests that these tasks are relatively short-ranged compared to City-Networre works. To examine this hypothesis, we therefore introduce a quantitative measure of long-range dependency in the next section and compare it across datasets and baselines.
Table 2: Best baseline results (L 16) on city-Networks.
Baseline
Type
Paris
Shanghai
Los Angeles
London
MLP
25.5 + 0.4
28.4 0.6
24.1 + 0.5
27.9
ChebNet
54.1 0.2
0.2
66.5 +.5:000 0.1
61.4 + 0.4
54.7 + 0.2
GCN
53.2 0.3
62.1
5..
5.7
MPNNs
GraphSAGE
0.2
68.3
6.34
5.24+
GAT
0.3
68.0
5.3
5.3
GCNII
0.2
61.5
5.30
48.2 0.3
DropEdge
0.2
60.8 0.4
5.3
4..0
GraphGPS
52.1
63.0 0.5
59.8
OOM 49.5
GT's
Exphormer
55.1 0.8
70.2 + 0.4
63.8 + 0.6
SGFormer
52.0 0.8
64.1 + 0.3
60.1 0.7
48.3 + 0.3
For completeness, we summarize the best baseline performance and further conducte an ablation study in Appendix [D3 that (i) tests baselines under different hidden size; and (ii) fixes the model size at L 16, refrains the model from seeing beyond hop-Hl each node, then tests baselines at different H. The results are consistent with our above findings, and the potential limitation of our experiments is discussed in Appendix
Netyoks in Table 2

---

Published as a conference paper at ICLR 2026
4 A LONG-RANGE MEASUREMENT BASED ON JACOBIANS
In this section, we propose to quantify the long-range dependency of a task given a trained model. by evaluating how the influence score I(u, u) between node-pairs (Xu et al. 2022) varies with distance. The influence score measures the sensitivity of a GNN
2018
Gasteiger et al. layer at node e to where H!!)) is
the imput feature of node u using the Jacobian: [(v, u) = Σ, ( the 1th entry of node v's embedding at layer L, and Xaj is the jth entry of the input feature vector for node Unless otherwise specified, assume L refers to the last logit layer.
/ax,ss
Based on the influence score, we define the average total influence Th at hth hop as:
(v) Luum (v,
Σ (CC,u), Th N
1
Σ sum (v, h),
(2)
where (v) sum (u, h) is the total inffuence from the ttth -hop neighbors of node v, p(u, u) is the length of the shortest path between o and u (note that this is equivalent to the h-hop shell later would like to highlight that when h = 0, (u) = [Vv v) becomes the influence of the feature at node v on its output. The average total influence quantifies how much, on average, the features of nodes that h hops away affect the output at the focal node. In other words, by summing the Jacobian- -based influence scores from all h-hop neighbors and then averaging over all nodes, it provides an expected measure of the cumulative effect that distant nodes have on each node as the focal node.
discussed in Section 6). and N is the number of nodes in the network. Also,
Given equation 2
we further define the average size R of the influence-weightte receptive field as:
Ex h (v)
R N E
Σ h20 Tb)
where H is the maximum number of hops to be considered. Intuitively, one understand R as measuring how far away the average unit of influence is, since the influences from distant nodes to the target node will be proportionally stronger in long-range tasks compared to those in short-range tasks. Note that the proposed R bears similarity to the recent work of Bamberger et al. (2025): the definition of R in equation 3 ii based on the shortest path distance, which corresponds to a specific instance of the measure in |Bamberger et al. (025). However, unlike that work which focuses on an aggregated measure of the range, our work has particular focus on using the per-hop influence Th (v) as a diagnostic tool of the dependency decay, which leads to the key analysis in Figure 4 below.
Finally, we provide an analysis of the computation cost of our measurement in Appendix and
discuss its potential limitations on large dense graphs (a common challenge for Jacobian- based methods (Xu et al.) 2018 Gasteiger et al. 2022) the literature) in Appendix F
Results. We validate R and T, on City-Networks using the baselines at L = 16 layers from Section 3 Since Pascall loccalle VOC-SPP is under an inductive setting, we randomly sample 100 graphs from its testing set (more than 400k nodes in total) and report their average. The results in Table show that R consistently higher on our -Nttyooeoorr across all models compared to those on the other graph datasets, indicating a longer effective range of influence.
Table 3: Average size of the nofluence-weighte receptive field R across different datasets and models.
Model
Paris
Shanghai
L.A.
London
Cora
ogbo-arxiv
Amazon
PascalVOC
GCN
4,86
5.55
5,36
6.09
2.56
1.34
1.92
3.38
GraphSAGE
4.92
5.73
5.44
5.97
2.37
1.40
1.80
2.99
GCNII
3.62
3.64
3.68
3.66
2.76
3.5
1.79
2.60
GraphGPS
8.18
7.88
7.92
00M
2.65
OOM
6.86
7.14
Exphormer
5.71
7.06
7.15
7.90
2.84
2,80
1.43
1.42
SGFormer 3.75
4.25
4.03
4.01
3.21
1.21
2.46
NA
To better compare Th across models and datasets, we normalize it by To and report Tu/To in Figure 4 For all models, generally observe rapid influence drop at distant hops Cora and Oggn-arxitt whereas the decay is noticeably much slower on City-Networke The patterns Amazon Rngings and P Pascal VOC-SP generally fall between the above two cases with
7

---

Published as a conference paper at ICLR 2026
GCN
GraphSAGE
GCNI
10
10-3
10-1
10-1
10-3.
10
10-5
10-14
15.
10
10
15
10
CraphCPS
Exphormer
SGFormer
10P-
10-1
10-1-
10-4
10-5
-10--
10-11
10-9-
10
0
10
15
10
Hlp
Hop h
Hop
Stanghal
Los Angeies
ogbn-aindt
Amazon Sattnngs
Pesc
Figure 4:
Normalized average total influence TT/To averaged across nodes at different distances. Note that the influence calculation for GraphGPS is Out-of-Ne of-Memory on London and ogin-arxiv.
influence concentrated on the first few hops, which corroborate findings in Section 3 R and 7h are both model-dependent, the above results yield a consistent ordering across datasets: models trained Ci CyttNetewrr perform well, compared to those trained on existing datasets.
While
required to leverage information from more distant hops to
Note that the bias in the models will naturally lead to a biased estimation of the ground-truth range using the proposed measurement, and we will discuss this limitation in more detail in Appendix F In addition, we further provide results on Ring KingTransfer caasfer (Bodnar et al. 2021). synthetic experiment for testing oongraange dependency using small ring-like graphs under inductive settings in Appendix D.4] and provide results on other common heterophilic datasets in Appendix [D.5]
For the rest of the paper, we will first provide theoretical justification of the proposed dataset by linking over-smoothing to algebraic connectivity and network diameter in Section and then present the intuition behind the proposed long- long-range measurement in Section 6
5 THEORETICAL JUSTIFICATION OF TOPOLOGIES IN CITY-NETWORKS
In this section, we provide a spectral analysis of over-smoothing in GNNs to justify our dataset design. As such, main goal is not in-depth theoretical analysis, since both over-smoothing and spectral analysis of GNNs have been carried out extensively in the literature (Rusch et al. 2023 Wu et al. 2023 Oono & Suzuki 2020 Rong et al.) 2019); instead, our aim is build on top of these and derive simple results which provide a theoretical grounding of our dataset construction. The section is organized as follows. First, we review the concept of information loss in the limit of infinite GNN layers due to over-smootine wer-ssoothing, which effectively vanishes the original node features and makes representations collapse
value that is only dependent on the graph topology (Section 5.] and Appendix G.T). Next, we relate the rate at which over-smoothing happens and the eigenvalues of the normalized adjacency operator in linearized GCNs (Section 5.2p. Given that eigenvalues with larger absolute values slow down over-smoothing, we analyze how the magnitude of the eigenvalues relates to the graph topology of our datasets. This provides justification that graphs with large diameters promote bigger positive eigenvalues for the normalized adjacency operator and hence less vulnerable to over-smoothing (Theorem 5.2 and Appendix (.3).. Finally, we argue that less over-smoothing makes it possible for GNNs to capture long-range dependencies in the case of our proposed dataset. All proofs are presented in Appendix G.2
5.1 PRELIMINARIES: SPECTRAL PERSPECTIVE ON
FOR LINEAR GCNs
We begin by analyzing sver-snoothing through the lens of lincarization, following the framework established in Wu et al. (2019) to build Simple Graph Convolutional Networks (SGCs). We select this
8

---

Published as a conference paper at ICLR 2026
Table 4: The lower bound for Xw \1-1(S on different datasets.
Dataset
Paris
Shanghai
L.A.
London
Cora
arxiv
Ratings
Pascal
Lower Bound
0.4741
0.6344
0.6095
0.5921
0.0324
-0.0639
0.1224
0.4857
model because is a linearized and more interpretable version of the widely adopted GCN model, which has also been used for theoretical analysis in previous works such (Giovanni al. 2022).
Let G = (V, EE) be an undirected graph with N = |V| nodes, adjacency matrix A E RNXN and degree matrix D RNXN (D;, Σ; A1)). The normalized (augmented) adjacency operator Sadj R is defined as Sudt (I + D) - - (I + A) + D) where the original adjacency matrix and degree matrix have been augmented with self-loops. [Wu et al. (2019) discuss the spectral properties of the normalized adjacency operator, which satisfies: An = and [x1 < 1 for all i < N.
Therefore lim; (Sad)) ) üNū where üN is the eigenvector corresponding Ax. whose entries at node v are v degree(v).
Via linearization (detailed in Appendix G.T). as the number of layers tends to infinity, the graph convolution operation collapses all node features to scalar multiples of ú, resulting in complete loss of the original feature information, that is, the learned representations suffer from over-smoothing.
5.2 OVER-SMOOTHING RATE ON ALGERRAIC CONNECTIVITY, DIAMETER, AND SPARSITY
We now provide intuition about the types of graph topologies that would mitigate the over-smoothing problem. In particular, sparse graphs-thhe those lacking the amall-wordd effect commonly found in citation networks-ant graphs with large diameters tend to experience over-smoothing at slower rate. We argue that this slower rate of over-smoothing implies a higher likelihood that GNNs can learn long-range dependencies during optimization. We validate this intuition by bounding the eigenvalues of the normalized adjacency matrix using graph properties, then showing how these eigenvalues influence wer-smoothing, and thus how controlling these graph properties
reduce the likelihood
of over-smoothing. More concretely, we extend (Wu et al. 2019 Theorem 1), which only covers
A and Av, to Proposition 5.1 which prove in Appendix G.2 covering the normalized algebraic
connectivity ~ and showing that A (Satt) < x (Sad)
Proposition 5.1 (Self-loops decrease algebraic connectivity of the original graph). Assume con- nected graph G with more than two nodes. For all y > O,
AN-1 (Saa)) = 1 (D- AD- <
AN
D)-+))
(4)
This allows us to relate the second largest positive eigenvalue of Sadj to the topology of graphs in the proposed dataset, using bounds similar those in (Chung) 1997] Lemma 1.14).
Theorem 5.2 (Bound on second largest positive eigenvalue of the normalized adjacency operator).
Let dmma be the maximum degree of vertex in G, and dgam(G) the diameter of G, which must be diam(() > 4. Then
AN AN-1(Sad) 2 dmna=- dmaz
2 2
1
(5)
diam(g)
dmax
From Table we see that the lower bound in equation 5 is generally higher for our datasets; this
is because the bound is decreasing in d and increasing in diam(G), showing graphs with large diameter and low maximum degree will be more resilient to over-smoothing. We further provide the rationale behind this lower bound in Appendix G.3 as well as its relations to the Braess paradox and previous study (Jamadandi et al. 2024) regarding over-smoothing and graph sparsity Appendix G.4
THEORETICAL JUSTIFICATION OF JACOBIAN-BASE MEASUREMENT
Finally, we justify the proposed measurement for analyzing long-range interactions in GNNs, partic- ularly by comparing the mean and the sum of influence scores of neighboring nodes candidates

---

Published as a conference paper at ICLR 2026
to represent the total influence score for focal node (t). Recall that (b) = sum (v.h)
u. [v, u) as in equation 2. We first introduce definitions for the standard lattice in Eu- clidean space, h--hpp shells, and quasi-isometric graphs, and then provide a mathematical analysis of influence score dilution. Due to space limits, we provide the definitions in Appendix
Lemma 6.1 (Growth of h-hop shells in grid-like graphs). Let G = (V, F) be graph that is grid-like in D dimensions (e.g., let us presume the graphs in the proposed dataset are a subgraph of zD or quasi-isometric to it, which seems reasonable given Figure 2 and assume the node degrees are uniformly bounded. Then, there exist positive constants E and e₂ (depending on and the local geometry of G) and an integer he such that for all h 2 hu,
C₁hP-1 < (u(2)) S P2h
(6)
After having quantified the growth of the h--hop shell, one can prove the following theorem, which motivates our aggregation choice.
Theorem 6.2 (Dilution of mean aggregated influence in grid-like graphs). Suppose that for a fixed e
and for each h hg there exists a distinguished node u² E (v) with a strong influence on u, quanti-
fied by [v,, u²' ) I* > O, while for all other nodes u E (N) {u"} the influence [(V, u) is negligi- ble (i.e. zero). Define sum (v. h) EveNa()) I(U, u) = E Eu.ple I(v.u) u) and I (v. h)
I"
[VI.(o)] EueNa.to) ((V,u) u). Then, (u, 2 1", and Aman (v, S
C, hD-IT Hence, as + oc.
we have meann (v. ht) - 0, while [1,((1 ht) remains bounded below by I" This also holds for planar graphs, where D =
Corollary 6.3 (Dilution for a planar grid-like graph). The dilution of the mean aggregated influence for a planar grid-like graph (like our city networks) is proportional to n.
Corollary 6.4 (Faster dilution over aggregated h-hopp neighborhoods). Let G be a grid-like graph in D dimensions, and define the aggregated ht-hop neighborhood (or ball) of a node Ni(u). As before, suppose that within Ba (v) there exists a unique node u* with influence [[u", v) = 1' > 0 and that for all other nodes u E (v) \ {u") }. the influence is negligible (i.e. zero). Then, the mean aggregated influence is diluted a rate proportional 1/h². In particular, for a planar graph (D = 2), the dilution occurs at rate proportional to 1/h².
(v)
The analysis above formally justifies the choice in equation 2 which considers the aggregate influence of neighboring nodes Ti (v) = sum as a more reliable measure than the mean /mean which is susceptible to dilution, particularly in the case of distant neighbors. This is key to the computation receptive field in equation 3
of the average total influence in equation and the Finally, note the following:
Corollary 6.5 (The dilution problem does not affect the average total influence). Let Tv) 1sam (s,m(,, h) be the total influence from the h-hop neighborhood (v) of node v. and let Tn 1. [V] Evey (x) be the average total influence over all nodes in V. Suppose that for every v and every h there exists at least one distinguished node u" E (v) satisfying I(u, u²) 1 > 0. Then, Tn L", Vh.
Proofs are provided in Appendix J and more detailed justification of Jacobian based influence score and connections to existing literature, along with its limitations, can be found Appendix H
CONCLUSION
The main objective of our work is to provide better tools to help quantify long-range interactions in GNNs. Previous benchmarks, such as the LRGB (Dwivedi et al. (023), are introduced in the context of small graph inductive learning, using solely the performance gap between classical GNNs and GT's to support the presence of long-range signals. In this work, we introduce new large graph dataset based on city road networks, featuring long-range dependencies for transductive learning, and propose a principled measurement to quantify such dependencies. We also provide theoretical justification of both the proposed dataset and measurement, focusing on over wer-shmothing and influence score dilution. Beyond benchmarking purposes, work also holds potential for a broader impact, informing applications in urban planning and transportation by providing tools to analyze and predict accessibility within city road networks.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENT
Huidong Liang is funded by the ESRC Grand Union Doctoral Training Partnership and the Oxford- Man Institute of Quantitative Finance.
REFERENCES
T. Abbiasov, C. Heine, Sabouri, A. Salazar-Miranda, P. Santi, E. Glaeser, and C. Ratti. The 15-minute city quantified using human mobility data. Nature Human Behaviour, 8:445 455, 2024.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Adrian Arnaiz-Rodee Rodriguzd and Federico Errica. Oversmoothing," oversquashing", heterophily, long- range, and more: Demystifying common beliefss in graph machine learning. arXiv preprint 1rXi::2505.15547, 2025.
Adrián Arnaiz-Rodrgguer, Ahmed Begga, Francisco Escolano, and Nuria M Oliver. Diffwire: Inductive graph rewiring via the lovász. bound. In Learning on Graphs Conference, pp. 15-1, PMLR, 2022.
A. Arroyo, A. Gravina, B. Gutteridge, F. Barbero, C. Gallicchio, X. Dong, M. Bronstein, and P. Yandergheynst. On vanishing gradients, over-smoothing, and over-squashing in gnns: Bridging recurrent and graph learning. arXiv preprint arXiv:2502.10811 2025.
Bamberger, B. Gutteridge, le Roux, M. M. Bronstein, and X. Dong. On measuring long-range interactions in graph neural networks. In International Conference on Machine Leurning, 2025.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in neural information processing systems, 34:2625-2640, 2021.
Geoff Boeing. Modeling and analyzing urban networks and amenities with osmnx. Working paper, 2024. URL[sttps://eeoffoore htt.pp/ss..roffoooooo......oooo/
Haitz Sáez de Ocáriz Borde. Elucidating graph neural networks, transformers, and graph transformers, 02 2024.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. International conference on machine learning, pp. 1725-1735. PMLR, 2020.
Fan RK Chung. Spectral graph theory, volume 92, American Mathematical Soc., 1997.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact width, depth, and topology. In International Conference Machine Learning, pp. 7865-7885. PMLR, 2023.
EW Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271 1959.
Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark, 2023. URL
abs/2206.. 08 644
Robert W. Floyd. Algorithm 97: Shortest path. Commun. ACM, 5(6):345, 1962, ISSN 0001-0782. doi: 10.1145/367766.66810
Johannes Gasteiger, Chendi Qian, and Stephan Günnemann. Influence-based mini-batching for graph neural networks. Learning on Graphs Conference, pp. 9-1. PMLR, 2022.
Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, 2017.
11

---

Published as a conference paper at ICLR 2026
Francesco Di Giovanni, James Rowbottom, Benjamin Paul Chamberlain, Thomas Markovich, and Michael M. Bronstein. Understanding convolttonn on graphs via energies. Trans. Mach. Learn. Res., 2023, 2022. URL https: / ott.p//wwwwo..ooo.aaoaa.aaoooooa wtt.:oaaa..rr/oooouus......
Jhony H Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D Malliaros. On the trade- off between over-smoothing and over-squashing in deep graph neural networks. In Proceedings of the 32nd ACM international conference on information and knowledge management, pp. 566-576, 2023.
Aric Hagberg. Pieter Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008.
Mordechai Haklay and Patrick Weber. Openstreetmap: User-generated street maps. IEEE Pervasive computing, 7(4):12-11, 2008.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the I International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer New York, 2009, ISBN 9780387848587. http: doi. www.oogg/o..... 1000000077780 0 0885-84888-7
doi: 10.1007/972-0-337-4485311 URL
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec, Ogb-Isc: large-scale challenge for machine learning graphs. arXiv preprint arXiv:2103.09430, 2021.
Adarsh Jamadandi, Celia Rubio Madriga,, and Rebekka Burkholz. Spectral graph pruning against over-squashing and over-smoothing. Advances in Neural Information Processing Systems, 37: 10348-10379, 2024.
Thomas N Kipf and Max Welling. Sepi-super classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2019.
Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Classic gnns are strong baselines: Reassessing gnns for node classification. Advances in Neural Information Processing Systems, 37:97650-97665 976009997799--7 2024.
Yao Ma, Xiaorui Liu. Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In International Conference on Learning Representations, 2022. URL https //openrevient net Tet.:/Forrrmm
Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. A fractional graph laplacian approach to oversmoothing. Advances in Neural Information Processing Systems, 36:13022- 13063, 2023.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, 27(1):415-444, 2001.
Mark Newman, Networks. Oxford university press, 2018.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: (00..0990000000 2019.
K. Oono and Suzuki. Graph neural networks exponentially lose expressive power for node classification, In International Conference Learning Representations, 2020.
12

---

Published as a conference paper at ICLR 2026
Hongbin Pei, Bingzhe Wei, Kevin Chen Chuan Chang. Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In 8th Interaatoonal Conference on Learning Representations, ICLR 2020, 2020.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations. 2023. URL https
net/ /
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systemx, 35: 14501-14515, 2022.
Y. Rong, W. Huang. T. Xu, and Huang. DropEdge: Towards deep graph convolutional networks on node classification. In International Conference on Leurning Representations, 2019.
T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey oversmoothing in graph neural networks. arXiv preprint arXiv:2303..0990 2023.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009. doi: 10.1 10.1109/TN.2008 20000005 2005605.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning. pp. 31613-31636. PMLR, 2023.
Jasraj Singh, Keyue Jiang, Brooks Paige, and Laura Toni. Effects of dropout on performance in long-range graph learning tasks. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
Jan Tönshoff, Martin Ritzert, Fran Rosenbluth, and Martin Grohe Where did the gap go? reassessing the long-range graph benchmark. Transactions Machine Learning Research, 2024. ISSN 2835-8856.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference Learning Representations, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Duncan Watts and Steven Strogatz. Collective dynamics of 'soall-world' networks. Nature, 393(6684):440 442, 1998. ISSN 1476-4687. doi: 10.1038/30918. httptsts/tp/o....// 70.1038/3091
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. -6711. PMLR, 09-15 Jun 2019. URL mlr press v97 wu 9e. html.
Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for large-graph representations. In Advances in neural information processing systems, 2023.
Z. Wu, S. Pan, F. Chen, G. Long. C. Zhang, and P. Yu. comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1 24, 2021.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks, In International conference on machine learning, pp. 5453-5462, PMLR, 2018
13

---

Published as a conference paper at ICLR 2026
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervee sumi-superiieed learning with graph embeddings. International conference on machine learning. pp. 40-48. PMLR, 2016a.
Zhilin Yang, William w. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference International Conference on Machine Learning Volume 48, ICML'16, pp. 40-48. JogR.org, 2016b.
Dongzhuoran Zhou, Evgeny Kharlamov, and Egor V Kostylev. Glora: A benchmark to evaluate the ability to learn long-range dependencies in graphs. The Thirteenth International Conference on Learning Representations, 2025.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804 2020.
14

---

Published as a conference paper at ICLR 2026
A DATASET AND CODE AVAILABILITY
Our dataset, CitNeework and our long-range mcasurement, total influence are both pub- licly available Pylorch Geometric (PyG 2.7.0) under torch geome da tasets and sti We also open-sourced the code for dataset construction and bench- marking at https//gggaabbboommeeeeeeeeerrrt
B NETWORK STATISTICS
In this section, we explain the statistics used in Table 1 that characterize our dataset and discuss the estimation approach used when direct computation is impractical. We consider undirected graphs, =V, EV) with N V nodes and [E] edges, where each node is associated with feature vector X. E R and label yo E y from a finite class set.
Node degree. The degree deg(v) of a node represents the number of edges adjacent to it. To characterize the distribution of node degree in network, we consider its mean and standard deviation dF:
P. Σ deg(u), ok VN Σ (deg(u) - px)²
Importantly, networks of different topologies will have different degree distributions. For example, social networks often exhibit a power-law property, where a few nodes have high degrees while most nodes have relatively low degrees. As result, their degree distribution tends to follow a scale- free pattern with high degree variance of. In contrast, grid-like networks, such as city networks and super-pixel graphs, have structured layout of connections, leading to a more uniform degree distribution with lower variance.
Clustering coefficient. The clustering coefficient C, measures the tendency of a node v V to form tightly connected group based on triangles, and its average C measures the overall level of clustering:
C deg(r)(deg(u) 1)
2T.
Σ C., C C= NONN
1
(8)
DEV
where T, is the number of triangles that include node e E V. Alternatively, transitivity offers a global measure clustering with the following expressions:
number of triangles
Transilivity number of connected triples'
Intuitively, social networks tend to have high average clustering coefficient and transitivity due to their community structure with highly connected hubs and frequent triadic closures. On the other hand, our city networks exhibit a low clustering coefficient and transitivity, as their structured and sparse connectivity (e.g., forming lattices) reduces the prevalence of triangles. Note that LRGB, although being "grid-like", shows an even higher and transitivity than social networks. This is because its networks contain many triangles, as it uses semantic super-pixels as nodes with pixel borders being the edges.
Diameter
The diameter D of network is the longest shortest path between any two nodes:
max p(u, v),
(10)
u
where p(u, v) is the shortest path length from node u to node v. Note that in this case the distance unweighted for more direct comparison with other datasets. It represents the maximum com- munication delay in the network and varies significantly across different network structures. In social networks, the presence of hubs greatly reduces the average shortest path length, leading to small-world effect with relatively small diameter. In contrast, grid-like networks lack hubs, and their regular structure causes the diameter to increase more rapidly as the network size grows.
Since the exact calculation of D has an impractical computational complexity at O log(N))) the following approach to estimate the approximate diameter / of our city networks. For
15

---

Published as a conference paper at ICLR 2026
all nodes in given city, select the ones with the maximum and minimum latitude and lon- gitude, respectively: coord(e1) = latmer), coord(v2) = (... datmin), coord(u') = (longman:
(longmaxt and coord(es) between (vi, 02) and (v3, va), and take their maximum as our final diameter estimate, that is, D max (d(e1, 02), d(v3, oa)). Note that the exact diameter D will always be larger than our estimation D.
Based these, compute the shortest path
Homophily. The node homophily score (Pei et al. 2020 quantifies the tendency of nodes with the same label to be connected:
Hu Nou)) vn = voHl
Homo
(11)
[W(v)
DEV
where (w)) is the set of neighbors of node v, and ye represents the label of node A higher homophily indicates stronger preference for connections between nodes of the same class, which can significantly impact the performance of GNN models.
C DATASET DETAILS
C.I RAW FEATURE PROCESSING
This section provides additional details of the features and labels of our City-Networks.
Node and edge features. The node and edge features in our dataset are derived from real-world features provided by OpenStreetMap for both road junctions and road segments, as detailed below.
Three numerical features for the road junctions (nodes):
latitude: the latitude the current road junction.
longitude: the longitude of the current road junction.
street count: the number of connected roads in both directions.
One categorical features for the road junctions (nodes):
land use: the type of land commercial, railway, etc.
the current coordinate: residential, industrial, forest. farmland.
Two numerical features for road segments (edges):
road length: the length of the road meters.
speed limit: the speed limit on the current road in km/h.
Two binary features for road segments (edges):
one-way: if the current road can only be used in one direction by vehicles.
reversed: if the current road alternates between different directions during rush hours in the morning and evening, which is also sometimes called "tidal flow".
Two categorical features for road segments (edges):
lanes: number of lanes the current road, which takes either numerical values (e.g. 1,2,3, 3, ...), list of numerical values (e.g. [1, [2, 3), [4, .)... when the current road has different number of lanes at different segments. We treat this feature as a categorical variable during modeling.
road type: the type of the current road, with possible values being: service, residential, footway, primary, secondary, tertiary, etc.
Feature engineering. Since the categorical features land use, lanes, and road type contain many categories of only a few data points and varies across different networks, only take the top 8 categories with most entries for each categorical feature, and treat the rest as a single category other. Based on observations, in all cases. This strategy leads to 12 node features and 25 edge features after one-hot encoding. Next, facilitate typical node classification task, apply simple neighborhood aggregation that
than 90% of the network with the top categories
16

---

Published as a conference paper at ICLR 2026
transforms edge features into node features by averaging the features of incidental edges and then concatenating them to the features of the focal node. These new node features represent, for instance, the average speed limit around road junction or the probability of finding residential road nearby. As a result, the final dataset contains 37 node features after processing. Lastly, we transform the graph into undirected one by merging all edges between each pair of nodes into single edge, where the edge features are averaged using to leto__uniiiie rected (reduce= "mean") from PyG.
C.2 LONG-RANGE NODE LABELS BASED ON LOCAL ECCENTRICITY
Controllable long-range signal based on local eccentricity. As mentioned in Section 2.2 we k--opp ego-network to estimate the eccentricity of each node. Specifically, after obtaining the neighborhood (u) within & hops node v, we compute the shortest path from node & to all nodes within this neighborhood, and take the maximum as the local eccentricity (x(v):
(x( =
MENa(e) (w u), Pro u)
min Σw w(c)) TEP(U.))
(12)
where (w, u) is the weighted shortest path distance from node to node P(u, u) de- notes the set of all possible paths from node to node u, and w(e) represents the edge weight for edge e. Here, we use one of the edge features road length the edge weight w(e).
Distributions of node eccentricity estimations
2.00
Parts Shanghai
1.75
London
Density
1.25
such that the local eccentricity (v) will indi- cate the maximal traveling distance (in meters) from node u to its k-hop neighbors. Figure 5 shows the distributions of such approximation at k = 16 across different city networks, in which Paris and Shanghai i have the most skewed and uniform distributions, respectively.
1.00
0.75
0.50
0.25
0.00
10
16-hop eccentricity (km)
Importantly, this method allows
know priori that the long-range signal should be highly correlated with the hop which facilitates in task design and model benchmarking. Lastly, after obtaining the local eccentricity for all nodes, we split them into 10 quantiles as the final node labels for transductive classification.
Figure 5: Distribution of the 16-hop eccentricity for nodes each of our City-Net
Discussions more realistic estimations of accessibility. While our approach gives us clean and controllable setup to study long-range topological interactions, it inevitably neglects some of the complexities inherent in real-world transportation dynamics, in which other factors like road speed, capacity, and traffic congestion strongly influence how "accessible" one area is from another. However, we believe our frame- work can be naturally extended by using road length and speed limit to approximate travel time when defining the edge weight in the eccen- tricity from equation]] [] Here we present some preliminary results Paris under this strategy. The results in Figure 6 suggest a similar rising trend in performance as we increase the model's depth, which is consistent with our statements in the main text. We note that other travel-time proxies, such as data from the Google Maps API, may provide a closer approximation to real-world conditions. and we leave such directions for future work.
Paris
60
50-
Test Acc
40
30
20
16
# Layers
GCN
GraphSAGE
Figure 6: Results on Paris where labels are de- rived with travel time being the edge weight.
Computational cost. The exact eccentricity typically requires O(VV13) using the Floyd- Warshall algorithm (Floyd 1962). However, with local approach, the computation is at much cheaper cost
17

---

Published as a conference paper at ICLR 2026
of (([EE) | (V) using the Dijkstra's algorithm (Dijkstra, 1959), where [V] and | the average number of nodes and edges across all k-hop ego-networks. The calculation is implemented with networkx (Hagberg et al. 2008) on CPU cluster of 72 Intel Xeon @ 2.3GHz cores, which takes 3, 5, 6, and 23 hours to compute for Paris s, Shanghai, L.A. and London, respectively, when l: = 16.
C.3 THE ROLES OF GRAPH TOPOLOGY AND SPATIAL FEATURES
The importance of structural and spatial information. Our goal is to use label generation approach that incorporates long-range dependency via information from both node features and graph structures. Although the local eccentricity is based on weighted shortest-path strategy with road length being the edge weight, does not only capture a structure perspective. This is because road length naturally relates to geographical locations, road type, land use, etc., which will link the node labels to these node features. Since the edge features are removed for the transductive task, the model will not be able to directly infer the original weighted shortest-paid -atth values. Moreover, while can control the range of the task by changing the approximation hop k. this knowledge is hidden from the model. Therefore, the model needs to explore the distant neighborhood and capture both structural and spatial information to effectively infer the long-range information.
Problem of uninformative graph structures on labels. One catastrophic problem we encountered during the experiment is that, when using the exact eccentricity or a relatively larger ls for node labels, the signal becomes nearly independent of graph structures. As illustrated in Figure 7 we can observe clear correlation between the node labels and their spatial coordinates. since nodes around the city center would generally have lower eccentricity values due to the 2D grid-like topology. This means that the spatial coordinates alone are sufficient for modeling E(V), hence weakening the importance of graph structure for the prediction task. Similarly, some other labeling approaches would also lead to the same problem, such as using a single node as an anchor, then regarding its shortest path distance to other nodes as the node label.
Empirical validation. In Section we MLP on all four city networks that only uses node features such as geographical coordinates, land use, etc. The result in Figure F shows a significant performance gap between MLP and other graph models, indicating that using spatial information alone is insufficient for our task. To further show the sensitivity of the baseline models to geographic coordinates, test two GNNs (GCN and GraphSAGE) and two GTs (Exphormer and SGFormer) on Paris and Shanghai, with coordinates masked in node features. At the same time, we also test MLP on these two cities with coordinates only, and summarize the results in Table below. Compared to the original results with all spatial features, we can observe slight performance drop across both GNNs and GT's after removing the geographical coordinates, while for MIP, the results indicate that geographical coordinates alone are not sufficient for modelling our long-range signal.
Table 5: Baseline results Paris and Shanghai with all features vs. coordinates only (MLP) and coordinates masked (GNNs and GTs).
Paris
Shanghai
Model
features
coords. only masked
features
coords. only masked
MLP
25.5 1 0.4
12.5 1 0.5
28.4 0.6
15.2 + 0.7
GCN
53.2 1 0.3
51.4 1 0.4
62.1 02.1-0.2 0.2
61.3 1 0.4
GraphSAGE
54.6 + 0.2
52.3 + 0.3
68.3 + 0.5
66.5 + 0.4
Exphormer
55.1
53.5 0.4
0.4
67.4 + 0.5
SGFormer
52.0 0.8
51.3 1
64.1 1..1-00 0.3
62.8 1 0.4
Discussion on LRGB. Finally, we would like to point out that this problem also exists in LRGB, as illustrated by example graph from PascalvOC-SP in Figure However, while the learning task in P Pascallee PascalVoc-S3 VOC-SP resembles a spatial segmentation problem on the coordinates, it still requires the model to handle graph structural information for prediction due to the inductive task nature.
18

---

Published as a conference paper at ICLR 2026
(a) Huangpu, Shanghai, k 8
(b) Pasadena, Los Angeles, k
(c) Huangpu, Shanghai, k= 16
(d) Pasadena, Los Angeles, k= 16
(e) Huangpu, Shanghai, k= 32
(D Pasadena, Los Angeles, k= 32
(g) Huangpu, Shanghai, full hop
(h) Pasadena, Los Angeles, full hop
Figure 7: Visualization of local eccentricity (v) at k: [8, 16, 32] and full-hop (exact eccentricity) on two sub-regions. We can observe that in the last two cases (g) and (h), node labels become highly correlated with geographic coordinates and are hence less dependent on the graph structure.
19

---

Published as a conference paper at ICLR 2026
Original Image
PascalVOC-SP Network
Figure 8: An example graph in Pascal from LRGB (Dwivedi et al. 2023 where nodes are represented by super-pixels and their labels are annotated by semantics. Although spatial coordinates are highly correlated with node labels, the inductive nature makes the task still graph-dependent.
C.4 CHOICE OF THE LONG-RANGE LEVEL
As explained in Section 2.2 the choice of i is critical in designing the long-range signal. On one side, k should be sufficiently large to distinguish our setting from short-range datasets (e.g.. social graphs with typical message passing around hops). To further elaborate on this, fol- low the same experiment setups in Section 3 and test GCN on Paris using k = [8, 16, 32] at num lanessaysr=-2,44
16, 32). where the results are reported in Figure on the right.
We can observe that, at k 8, the model's performance quickly saturates as expected when num layers reaches 8. While at h 16 and much
Paris GCN
80
32, the performance starts to plateau deeper depth of num_layers=16. As such, 8 does not seem to an optimal choice for k, since there is still room to "extend" the range of the signal.
Test Acc
60
k
40
16
32
On the other hand, & should also remain small enough that it does not lead to the aforemen- tioned problem of uninformative graph structure during modelling. As visualized in Figure 7 the underlying signal, given its local nature, be- comes smoother as k increases from 8 to 32. At the same time, we can also see increasing correlation between signal and the spatial coordinates. In the extreme case when & equals the network diameter, é (v) becomes the exact eccentricity É(v), and the classification task resembles a "segmentation" problem on 2D plane. This also explains the marginal performance gain from num_layers=Ile to at & 32, as the signal becomes overly smoothed that information based on 16-hop neighborhood is sufficient to have good "guess" of the signal at hop 32.
20
16
# LLyers
Figure 9: Results of GCN at different numbers of
layers on Paris with k = [8, 16, 32] used for labels.
At the same time, for benchmarking purposes, we wish test GNNs and GT' with enough model depth such that they reach the source of the signal. However, found that when training GTs on our large city networks, due to the quadratic complexity their global attention mechanism, they often suffer from Out-Of- Oft-Or-Memory errors (NVIDIA-L408
when num jayers is large.
Therefore, we decided to adopt = 16 in our final dataset, which we believe achieves a balance between being sufficiently ronger and remaining practical for computation. As discussed earlier in Section [ and Section 2.2] we believe City-Network brings a new and important challenge to the literature, which calls for scalable architectures that effectively handle long-range dependency.
20

---

Published as a conference paper at ICLR 2026
D EXPERIMENTAL DETAILS
In this section, we first provide training details in our experiments, and then present an ablation study that supports main claim the long-range dependency. Lastly, summarize the best baseline results on our dataset and discuss potential limitations of our experimental settings.
D.1 BASELINES AND DATASETS FOR COMPARISON
Baselines. We consider four common GNNs: GCN (Kipf & Welling 2017). GraphSAGE (Hamilton)
et al. 2017), GAT (Veličković et al., 2018), and GCNII (Chen et al., 2020 for GNNs; and three Graph Transformers: GraphGPS (Rampášek et al. 2022). Exphormer (Shirzad et al. 2023). and SGFormer [Wu et al. 2023) the baseline models in experiments.
Datasets. We compare the bascline results on City-Networka to the following datasets that are homophilic, heterophilic, large-scale, and long-range dependent.
Cora Yang et al. 2016a is a well-known homophilic citation network, with nodes representing documents and edges representing citation links. The features of the nodes are represented as bag-of-words that captures the content of the documents, and the goal is predict the academic topic of each paper.
ogbn-arn arxiv (Hu et al. 2021p a large-scale citation network of 169k computer science papers on arXiv that were indexed by the Microsoft academic graph, in which nodes represent papers and the directed edges indicate the citations. In particular, each node has an 188dimmnnsionll feature vector derived from the word embeddings of titles and abstracts in the underlying papers. The task is to identify the primary category of each arXiv paper, that is, to classify each node into one the 40 classes.
Rat ings (Platonov et al. 2023 is heterophilic network that models Amazon product co-purchasing information, where nodes represent products and edges represent frequently co- purchased items. The goal is to predict average product ratings from five classes, with node features being the fastText embeddings of product descriptions.
Pas Pascalvoc-S$ SP an inductive dataset from LRGB (Dwivedi et al. 2023). which contains graphs derived from images. In particular, the nodes represent super-pixee and edges represent their boundaries. The labels are derived based on semantics, which makes the task similar to image segmentation.
As mentioned in Section 3 we closely follow the latest GNN tuning technique from Luo et al. (2024), which considers residual connection, batch normalization, dropout, etc., and use their code base for training classical GNNs and GT's most datasets, except for Pasca VOC-SP, where we adopt the hyperparameters reported by Tönshoff et al. (2024) and Shirzad et al. (2023).
D.2 EXPERIMENTAL SETUPS
As discussed earlier in Section 3 we consider transductive node classification with train/validdaiiontest splits of 10% 10% 880% on all four graphs in -otyyNetworse
Since goal is to investigate the presence of long-range dependency, train each model at num num__ayers=[2,, 4, 8, 16] while fixing Salden_size=128 and then check if the model's performance will positively correlate with num num_layers. All cases are repeated times, and we present their means and standard deviations. In the ablation studies below, we also investigate different choices of hidden size in [16, 32, 64, 128] following this strategy, which not only acts as hyperparameter tuning, but also shows the robustness of our conclusion to different choices of model hyperparameters.
Evaluation protocols.
Hyperparameters We run each model for 30k maximum epochs using AdamW (Loshchilov & Hutter 2019) optimizer for sufficient training. during which we record the validation accuracy every 100 epochs and save the model at the best validation epoch for final testing. Meanwhile, closely follow the latest GNN tuning technique from Luo et al. (2024), and our hyperparameter search space is summarized in 6 Note that for GTs, we do not apply positional encoding due to its
21

---

Published as a conference paper at ICLR 2026
impractical computation our large graphs (which is one of the challenges of applying GTs on large graphs), and use GCN as their internal MPNNs.
Table 6: Summary of hyperparameters and their search space.
Type
Hyper-parameter
Search range
Default
num num_layer layers hidden_size Lizee__sieee__
[, 4, 8, 16]
16
16, 32, 64, 128]
128
Model
pre_ vee_inear__a _laerr post Lost_lineer____ layer residual
0, 1, 2
0
0. 1, 2
(True, False]
True
learning rate dropout weight decay normalization
10-4 5 10-4 10-3
10-3
0.2, 0.5, 0.7]
0.2
Train
0, 10-0 5x 10-5, 10-4
10-5
[None, BatchNorm, LayerNorm]
BatchNorm
D.3 ABLATION STUDIES
Results under different hidden channel sizes. To further support our main findings, we test two classical GNN baselines: GCN (Kipf & Welling 2017) and GraphSAGE (Hamilton et al. 2017);
and two GT baselines: Exphormer (Shirzad et al. 2023) and SGFormer (Wu et al. 2023) under
different hidden h 32, 64, 128] on Paris, Shanghai, and L. A.. The results are presented
in Figure 10 where we can observe a consistent pattern with our main findings in Figure 3 the
baselines' performance improves substantially when increasing the number of layers from 2 to 16.
Paris GCN
Paris CraphSAGE
Paris Exphormer
Paris SCFormer
Teat Acc.
50
50
50
40
40
40
40
30
30
16
2
16
16
Shanghai GCN
Shanghai GraphSAGE
Shanghai Exphormer
Shanghai SGFormer
Testt Acc
60
60
60
40
40
40
40
20
20
20
20
Los Angeles LGCN
Los Angeles GraphSAGE
Los Angeles Exphormer
Los Angeles SCFormer
60
60
60
Test Anc
20-
16
Layers
Layers
Layers
# Layers
Figure 10: Ablation results under hidden size=[16, 32, 64, 128] and num lanesayyys 4, 8, 16]
Paris, Shanghai, and Los Angeles. The patterns are all consistent with our findings in Section 3
Notably, all baselines generally achieve superior performance with a larger hidden_sto sizee. However, such differences are often negligible compared to the increasing trend in model depths. With that being said, in the next section, we proceed to investigate scenarios when the model size is fixed.
Results at fix model depth with various sampling hops. As discussed earlier, one limitation of the main results Figure 3 is that the observed performance gains may be attributed to the
22

---

Published as a conference paper at ICLR 2026
Paris
Shanghoi
Los Angeles
London
80
80
80
80
Test Arc
60
60
60
60
40
40
40
OCN
GraphSAGE
-4- Exphormer
SGFormer
Figure 11: Results for fixing number of layers = 16 and setting numbers of hops H E [2, 4, 16].
Paris
Shanghai
Los Angeles
Test Acc
40-
40
40-
20
20
21
8
16
32 Layers
48
64
24
8
16
32 # Layers
48
64
21 8
16
32
48
64
# Layers
GCN
GraphSAGE
Figure 12: Results for models deeper depths L E [32, 48, 64] beyond the ground-truth range of 16 hops. For illustration purposes, we also show results at model depths of [2, 4, 8, 16).
increasing model parameters the number of layers L grows. To address this, further investigate the scenario where is fixed at 16 (i.e., keeping the model size constant), and adopt an H H-hop neighborhood sampling method introduced in GraphSAGE (Hamilton et al. 2017) that refrains the model from seeing beyond hop H. Note that the same method is also widely used in the literature for training models on large graphs
Concretely, our strategy is implemented with NeighborLoader from PyG, which recursively selects NN........ ...,,Ni NH] neighbors from node's 1st, 2nd, .... H-th hop neighborhood. Given the grid-like structure of our city networks, the size of the neighborhood does not explode with H, and we empirically found that the average size 16-hop ego-network typically around 1 nodes, which remains manageable for most GPU devices. Therefore, we sample all nodes inside the H-hop neighborhood, and use a batch_s ze of 20k (i.e., 20k seed nodes) for training and testing.
The results are presented in Figure 11 where we can observe that every baseline, architecture, shows a consistent upward trend on all four city networks. These results indicate that long-range dependency, rather than the parameter size, is the primary factor that contributes to the improvement of the model's performance.
fixed model
One may notice the trend from H to H = 16 remains relatively flat. We attribute this phe- nomenon to the overlapped subgraphs sampled from Nei beighhorLoade,, where the ego-networks of different seed nodes often share common supporting nodes. Consequently, if the number of layers L exceeds H, the model can capture information from more distant hops beyond H, rather than being limited to maximum of H as expected. This effect is further amplified when using large batch size (i.c., a large number of seed nodes) or large number of hops (i.c. large neighborhood size), as increases the chance of overlapping ego-networks. As result, the performance remains similar between these two settings. Note that this phenomenon is not a contradiction to our main claims, but rather limitation, as we can create perfect 8-hop subgraphs.
Deeper depths beyond the ground-truth range. While adopting a fixed ground-trutt truth range prevents our rangrange task from falling into unbounded "the longer the communication path, the better the model performance" setting, we additionally benchmark GNNs with depths much deeper than the ground-truth task range (16th hop) here for complete analysis of the model's behavior.
23

---

Published as a conference paper at ICLR 2026
GCN
GrapbSAGE
10"1
10"7
10-44
10-15
10
10-2.
10
30
40
50
30
40
60
Hop
Hop
Shanghal
Angeles
Figure 13: Normalized average total influence Tr, To averaged across nodes, where the underlying models are trained with 64 layers-much deeper than the ground-truth range of the task.
Table 7: Average size the influence-weighted receptive field It across datasets on GCN and GraphSAGE, where both models are trained with 64 layers with residual connections and batch norm.
Model
Paris
Shanghai
L.A.
Cora
Amazon
FascalVOc
GCN
8.61
10.21
9.64
5.17
6.51
7.06
GraphSAGE
8.34
10.72
10.54
3.74
2.78
7.62
In particular, we test GCN and GraphSAGE with depth=132, 48, 64] on Paris, Shanghai, and L.A. under the same experimental settings (GT's are not tested here due to OOM at these depths), where results are presented in Figure T2] As expected, we can observe that both GNNs, even with residual connections and batch norm enabled, start to suffer from over-smoothing when model depth exceeds ground-truth range 16.
In addition, we also show the results of our per-hop influence measurement and R in Figure 13 and Table 7 respectively, where we compare the behaviors of these two deep GNNs on our city networks to those the other common graph datasets. The results reveal consistent trend with our findings in Section that the influence scores decay at a much slower rate on our city networks compared to those the existing graph datasets in the literature. It is also worth noting that the current model depth of exceeds the diameters of those common graph benchmarks, which leads to the "cut-off"
pattern in Figure 12
D.4 RESULTS ON RINGTRANSPER
The RingTransfer (Bodnar et 2021) experiment is used for testing long-range dependency in GNNs under inductive settings with small ring-like graphs. In this section, we will analyze the behaviors of different graph models on this synthetic task using our influence metric.
Task description. Each graph in the Ring- Transfer dataset is ring of N nodes with only two nodes marked: the source node and the get node, which are placed at opposite sides of the ring (i.e., distance the diameter N/2). All nodes on the ring will have a constant feature vector except for the source node, which has one-hot encoding of its label. The task is to train a model such that the target node's representa- tion predicts the source's label, which requires the model to propagate long-range information from the source node to the target node.
RingTransfer
GCN (R=5.27)
101
GraphSAGE (R=5.21)
Exphormer (R=3.34)
/To
10a
0
2
Setups. We followed the same setups by Bod- nar et al. (2021) and adopted k=16 (i.e., a task range of 8 hops) with model depth of in our setting, as we observed a similar phenomenon in their paper that GNNs start to deteriorate after this point. Meanwhile, since the diameter of rings matches the true task range of N/2 in
Hop h
Figure 14: Influence scores RingTransfer.
24

---

Published as a conference paper at ICLR 2026
RingTransfer, there will be gradient w.r.t nodes from hops N/2. Therefore, test models at depth up to the ground-truth range in this setting. In particular, we evaluate GCN, GraphSAGE splits of 5k/1k/ 1kk graphs, where all models can achieve 100% accuracy on the testing set. We then apply our measurement on the target node only for each graph, and then report the average over the testing set.
and Exphormer with trainin/vvalidationn
Results and discussion. The results for R and per-hop influence summarized in Figure 14 As expected, we can observe a strong influence at hop 8 for GCN and GraphSAGE; while for Exphormer, as it adopts global virtual node and expander graph operations in its attention mechanism, the source node can be effectively reached within a single hop. Therefore, we observe higher influence on the first few hops compared to more distant hops since the underlying graph has been modified. In addition, we have also tested models with deeper depth of 16 layers, where the result shows similar pattern to that Figure [4] except for the O influence after hop 8 (as explained above).
While we do observe different influence patterns due to different model designs, we'd also like to point out that this is because RingTransfer is too simplistic and relies solely on long-range interactions, such that simple operations (c.g., rewiring, virtual node, etc.) will convert it into a short-range task.
D.5 MORE RESULTS ON HETEROPHILIC DATASETS
As pointed out by Arnaiz-Rodriguez & Errica 2025), the heterophilic datasets are often misused in the graph machine learning literature to eva vvaluate long-range interaction (Amaiz-Rodriguu Rodríguez et al.
2022] Maskey et al., 2023 Giraldo et al., 2023: Singh al. 2025). However, there is no empirical study that compares the range of tasks between homophilic and heterophilic graphs.
In Section and we have tested baselines and quantified their long-range influence on repre- sentative heterophilic dataset, Amazon-Rata igs. To further support our findings that heterophily does not empirically imply long-rangeness, we proceed to show more results on the following het- erophilic datasets that are commonly used in the literature: Roman - Empire (Platonov et al. 2023), Wiscons in, Texas, and Cornell (Pei et al. 2020). The results for per-hop influence and R are presented in Figure 15 and Table g respectively, where we can observe from these two diagnostics that heterophilic datasets generally exhibit a short-range pattern compared to our city networks across different models, which is consistent with the findings in our paper.
CON
GraphSAGE
GraphGPS
SGPormer
101-
10
10
10:1.
10-1
10 7-
10-9.
10--
10-4.
10-11.
10
10-2
10-7
15.
10-11
10
10
15
15
Hop
Hop h
-+- Loc. Angrues
Cora
ogtn srate
PascalVEIG SP
Amazon Hattngs
Remran- Complre
Wiscoman
Theays
Cortol
Figure 15: Normalized average total influence TM To averaged across nodes at different hops on heterophilic datasets, where results on other datasets are also presented for comparison purposes.
Table 8: Average size of the influence- influence-weighted receptive field R across heterophilic datasets and models with 16 layers, where results on other datasets are also presented for comparison purposes.
Model
L.A.
Cora
arxiv
Pasca VOC
Amazon
Romen
it sicnnnsii in
Texas
Cornel1
GCN
5.36
2.56
1.34
3.38
1.92
2.04
1.28
1.11
1.54
GraphSAGE
5.44
2.37
1.40
2.99
1.80
1.89
0.97
0.89
0.96
GraphGPS
7.92
2.65
00M
7.14
6.86
6.37
1.03
0.77
0.98
SGFormer
4.03
3.21
1.21
NA
2.46
2.33
0.14
0.24
0.17
Note that Wisconsin, Texas, and Cornell 1 are small heterophilic graphs (around 200 nodes) and all have a small diameter of 8, which explains their extreme short-range behaviors compared to other heterophilic datasets like Amazon-Ra t ngs and Roman-Empi re.
25

---

Published as a conference paper at ICLR 2026
E COMPUTATIONAL COMPLEXITY
The computation of requires calculating (v)()) for v E at h E [0, 1..., H], in which the dominant cost stems from computing the Jacobian matrix. Since the model's gradient at node will be zero for nodes beyond its Ht hop, we only need to compute the Jacobian within each node's H hhop neighborhood. This leads to computational cost of O(NNH), with Nu being the average size of H-hop ego-networks on G:
1 Σ WH(()), NH(v) (uEV H}, N VEV
NH
(13)
where d(v, u) is the length of shortest path from node v to node u. Given the large scale of our city networks, employ stochastic approximation that samples 10k nodes to further reduce the computational cost. For reference, the calculation finishes under 30 minutes for all baselines on all four City-Networks using a single NVIDIA RTX 3090 GPU with 48 AMD Ryzen 39600 60XCPU cores.
F LIMITATIONS AND FUTURE WORK
Total Influecce under model bias. Since our measurement based on the gradient of the underly- ing model, its behavior will be naturally influenced by the bias in the architecture. For example, as described in Appendix [D3] when the models' depth (num layers=66)))) is much deeper than the known task depth (k 16), we observe that Rs are generally larger than those from models with 16 layers in our city networks. Meanwhile, the per-hop influence also suggests that deeper models leverage information from distant hops beyond the ground truth range & (which makes sense since the model has no information about k, and node features beyond the kth hop may contain useful information for prediction). Therefore, the biased approximation of the ground-truth function will inevitably lead to biased estimation of the underlying task's range, even though the measurement remains a faithful description of how the model utilizes long-range information.
However, our conclusions regarding long-rangenn rangenesss across datasets are still valid, since each model is validated across different datasets under the same depth in our analysis, where all models show clear long range patterns on our city-networks compared to those on the existing benchmarks at depth=16 (Section and depth=64 (Appendix D.3).
Total Influence on large dense graphs. During our experiment, we found that on large dense graphs, especially the one with small diameters such as oogn-arxce.... aarii (V 169k, diam 25), difficult to compute our Total Influence measurement, to N as H increases. In this case, the model also happens to have complex architectures (e.g.. GraphGPS), the computation of R and Th will therefore become impractical. Meanwhile, also want to point out that this is a common challenge for all Jacobian-basee
NH in equation 13 quickly converges
analysis the literature (Xu) et al. 2018 Gasteiger et al. 2022), and it is open question for future works explore more effective methods for measuring long-range dependency on dense graphs.
Inductive setting. In the current work, we focus on testing long-range signals under transductive settings on large-scale graphs, which is largely underexplored in the literature. However, we believe it is also possible extend our method to inductive settings by sampling networks via OpenStreetMap (or similar geographic graph sources), and then defining a graph-level classification or regression task on them, e.g., urban (graph) morphology classification. We leave this direction for future explorations.
of cities" road
G PROOFS AND JUSTIFICATIONS IN SECTION 5
G. DETAILS OF LINEARIZATION
A Graph Convolutional Network (GCN) layer with input features X learnable weights ( for layer 1, and non-linear pointwise activation function a is defined as:
(1+1) (Sae) x x0
(14)
26

---

Published as a conference paper at ICLR 2026
As pointed out in Wu et al. (2019), under linearization (removal of non-linen non-linear activations), L-layer
Simple Graph Convolution (SGC) can be expressed as:
( (S 1.
II W
(15)
where (Sotz) the L-th power of the normalized adjacency operator. The result follows directly from iterative application of the linearized GCN operation.
Next, it is well known that the normalized adjacency operator Sad) admits an eigendecomposition:
Sadj ÜAÜT,
(16)
where A = diag(>i,..... Ax) with λ <... AN and U contains the corresponding eigenvectors. And, for any positive integer k, the power iteration as follows:
(Bad) ÜA"0".
(17)
where A diag(A di. x
Wu al. (2019) discuss the spectral properties of the normalized adjacency operator, which satisfies: An = I, and Aii for all i < N. Therefore, as the number of layers approaches infinity, the layer
collapse phenomenon well-documented the literature:
lim (Sadt) üN U 1++00
(18)
where ün is the eigenvector corresponding to Av. This is because as + 00, A - for N since |Ad < 1. Meanwwile, Xx= 1' for all Thus,
0
lim (Sad)) ) = ū 1+000
UT = ÜN
(19)
This ultimately leads to information loss. In the limit -> cc, the graph convolution operation collapses all node features to scalar multiples of ūn the entry of which at node v is / + degree(v), resulting in complete loss of the original feature information. In other words, the learned representa- tions suffer from over-smoothing.
G.2 PROOFS FOR THEORETICAL RESULTS SECTION 5
Lemma G.1 (Eigenvalue complementarity of normalized operators). For a connected graph, the eigenvalues Sadj and L sym exhibit the following complementarity relationship:
AN+1-i(Sad) = As (yym))
(20)
for all = 1,..., N, where N is the number of nodes in the graph, and eigenvalues (for both operators) are indexed such that a A2 S S An-
Proof of Lemma G.7 By definition, Loym I Sadj- Since both matrices symmetric, they diagonalizable with real eigenvalues. Let u be an eigenvector of Lyym with eigenvalue X; (yym) Then:
Laym u = (L + (I LI-SSai (-Saaj)uu = ( Ju + Sudj (1 (Ley)))
(21)
Therefore, u is also an cigenvector of Sadj with eigenvalue 1 - A₂ (eymm))) Since the eigenvalues are ordered in ascending order for Laym and the transformation 1 X reverses this ordering, we have
(N+1-;(Saat) = X₂ (L
This complementarity implies that when the normalized algebraic connectivity (2 sym) is small, the second largest positive eigenvalue of Sad must be close to 1. However, in context, interested in the algebraic connectivity the normalized graph Laplacian that would correspond to the normalized adjacency operator, Sadj. introduced in Section 5.1 instead that of Sajjo motivating the following:
27

---

Published as a conference paper at ICLR 2026
Proposition G.2 (Self-loops decrease algebraic connectivity of the original graph, from Section 5.2)
Assume a connected graph G with more than two nodes. For all y > 0,
AN-1 (Sudi) = AN-1 p AD AN-1 (D A) + +))+
(22)
Proof of Proposition 5.7 (scame as Proposition G Let G' be the graph 9 with self-loops added, each having weight 0. If G already contains self-loops, their weights are increased by We denote the vertex set of g' as V, with the obvious correspondence the vertices of G. Then (rI D) A) D) - so proving
L sym I A and L sym
A2 L sym) A2 (L
(23)
will prove the proposition. Note that in practice we care about the case where y = 1. We proceed as follows: we take the eigenfunction on G corresponding to Xg. lift G', and show that this yields an upper bound. Using the variational characterisation of cigenvalues in (Chung) 1997] Eq. 1.13) and the fact that edge weights (u, u) wg. (u, u) if u & v, and the degrees of vertices de + d
inf Enn((f(x) - P())))(((,,)
X2 (L
(24)
/: E.E.ev (0)df=0
Evev S(x)dg
Pick such an f attaining this infimum (i.e., the eigenvector of L sym corresponding to A2 L multiplied by D- We use this f to construct signal g on G'. Let
sym)
> (xx
g(x) f(x) Exer & +
(25)
That is, we reduce f by a constant everywhere. We have picked the constant such that
Σ g(x)dg
Σ NEV
((x + + = 0.
(26)
EVV
Since g is simply f shifted by constant,
Vx,yEV.
- ((v) f(x) (2)
(27)
Again, by the variational characterisation of eigenvalues in (Chung 1997 Eq. 1.13);
Eany (h(x)) - h(v)) 2 w(x,y)
A2 ( sym)
inf h: Evev h(z)dg'= =0 E Enng (g(x) - =(u)))
(28)
Evev h(x)2 d
Eany(f(a)) f())
(29)
Exevg(x)2 2(x)2d0''
Ezev 2
The first inequality holds because g is in the set (h: : E EzEv h(r)dg' = 0) and the infimum serves as lower bound for the function on any element of that set. The last equality follows from applying (2
We now show that Exev (())dd( Ezev f(z)ad.. This will let us bound 29 above by 24 Expanding the definition of g:
Σnla = ISOPE - ( (ES(2)
((ES(0)
(30)
Ede
Σd
Noting that E((r)dg = and df dh 47 Ef(r)de =f((x,,
Egle) - -E ; f(x)) -2 -2² 2 (2{((()))
72 2 f(x))²
(31)
Eg
Σ 5
=7 "E -22 {Σ
( (x))2
(32)
Σ d
28

---

Published as a conference paper at ICLR 2026
By the Cauchy-Schward inequality on fax and 1,
f(x) 2
f 12) = =-
fxx)
(33)
Furthermore, as G is connected, each node has degree of least 1- Vx: : dh 2 As the graph has more than two nodes, one node must have degree of at least So Σ do > nn11 +7), and therefore:
Σ g
Σ ((x)
7 7
(()))2
- [Σ/ (x))
(34)
n(1 + +7)
[f(e))
72
7 1+7
(35)
(ES())
7
(36)
1+7
>
(37)
Based on which we conclude that Evev ((x)2d²' > E Eze 2 and so by
24 and 29
22 sym) S Eann (f(x) -f())
(38)
ΣzEv g(x)
Σ Ennyy (f(z) Rw))) = Xe (L (ggy))
(39)
ΣzEV f(
Hence, (L 2gm)
Au (L sym) and by 23 the proof is complete.
Proof of Theorem 5.2 Given Lemma G.1 (correspondence between the eigenvalues of Sadj and
L gym) and Proposition 5.1 seeing that diam(g) > 4 means that the graph has more than two nodes, Lemma 1.14).
the result follows immediately from (Chung 1997
G.3 RATIONALE BEHIND THEOREM 5.2
The second largest eigenvalue of Sadj in terms of magnitude is either Ax-1 or A We explicitly consider the case when 1 As Ax-1 approaches the rate of convergence to the limiting state ü decreases exponentially with the number of layers. For any layer I, the difference from the limiting state can be expressed as:
I|(I - n T. (5
(Sadj) 2aj) = [iiig N,., X
(40)
where || I || denotes the spectral norm and the last equality follows from that the spectral norm of diagonal matrix being equal to the largest absolute value of its diagonal entries. Thus, when A is close to 1, more layers are required to achieve the same level of convergence to the limiting state. Since AN-1 < 1, taking powers of A will eventually converge to zero, but the rate of this convergence slows dramatically Av-1 approaches 1. Hence, because graphs with large diameter and low maximum degree have a lower algebraic connectivity due to reduced inter-oomponen connectivity, GNNs operating on such graphs will be less susceptible over-smoothing when processing node features.
We have focused on the case where the second largest eigenvalue by magnitude of Sadj is AN-1- The special case where it is instead X (which, in this case, must be negative) gives different regime, where it is possible for graphs with smaller diameters exhibit less wer-smoothing than those with larger diameters. Consider, for example, bipartite graph where over-smoothing occurs independently on each side of the partition, resulting in two distinct values depending on which partition the node is in, rather than convergence to multiple of un, where the node feature value would only depend on the degree.
Nevertheless, our analysis demonstrates that large diameters and sparse connectivity generally reduce the likelihood of werrssoothing.. This insight motivates our proposal of benchmark datasets with significantly larger diameters than those currently used in the literature (see Table [.. The underlying hypothesis is that reduced likelihood of over-smoothing in high-diameter sparse networks enables the possibility of GNNs learning representations that capture long-range dependencies when necessary.
29

---

Published as a conference paper at ICLR 2026
G.4 RELATIONS TO BRAESS PARADOX AND PREVIOUS WORK
Sparsity of the graph and spectral gap. Our main theoretical result in Section[]] (Theorem 5.2) suggests that the second largest eigenvalue of the normalized augmented adjacency matrix has lower bound that is increasing in graph diameter and decreasing in maximum node degree, hence the spectral gap tends to be smaller for graphs with larger diameter and smaller maximum degree. However, this tendency may not be exact as the bound is not necessarily tight, and furthermore, a smaller maximum degree does not necessarily imply a sparser graph (although the two can be generally correlated). Therefore, our result is not in contradiction with the Braess paradox, which is an interesting observation by itself.
Spectral gap and tendency of over-smoothing. Our analysis of the rate of over-smoothing is purely based on the spectral analysis that the speed convergence to a stationary point upon repeated application of matrix operator depends on the spectral gap: smaller gap generally slows down convergence in this precise sense. It is worth noting that this analysis is task-agnostic, i.c., it does not take into account node classification analysis of over-smoothing by Jamadandi et al. (2024) is, however, task-dependent, as it specifically highlights situations when pruning edges mitigate over- weo-thng of mask-beneficia signals by disconnecting nodes with different labels. Therefore, while both are meaningful, the two analyses look at over-smoothing from slightly different perspectives.
task, and furthermore distribution of node labels. The
H MOTIVATION FOR JACOBIAN-BASER INFLUENCE SCORE
We provide additional motivation behind the proposed measurement for quantifying long-rangeness in Section 4
H.1 INTUITION BEHIND JACOBIAN-BASED INFLUENCE SCORE
The Jacobian has been used in analysis of node interactions in GNNs in multiple previous works (Xu
jt al.
2018
Gasteiger et al. 2022, Di Giovanni et al. 2023). For example, it is used in Di Giovanni
et al. (2023 Theorem 4.1) to show when oqur-squashing happens in long-range interactions, and
to show how vanishing gradients occur in very deep GNNs. Influence specifically has been used to
compute a natural measure of interactions between two nodes (Xu et al.) 2018). We accordingly use aggregated influence, Equation equation to gauge how nodes at distance h affect the output the GNN at focal node, thus quantifying long-rangeness. By the definition of partial derivatives, we can understand the Jacobian as follows:
2
O oi
(X)
(001( + Sewz)
())( Di (X)
lim 5-+0
(41)
0x uj
where X is the original (unperturbed) input feature matrix, and dews is an infinitesimal perturbation in the jth component of the feature vector at node u (a standard basis vector in the node feature space). This means the more positive the Jacobian entry is, the more a positive perturbation of the features at node u and component j will increase the logits at node e and component at the final layer. In other words, the Jacobian entry being positive or negative means that the logits are pushed up or down. Given that, after applying the softmax function, the probabilities at given data point increase monotonically with the logits at that point, we can consider both positive and negative influences as actual influence and only focus on the absolute value (i.e., sensitivity rather than direction).
Monotonicity of the Softmax function. Consider the derivative of the i-th softmax probability with respect its corresponding logit:
Op: = 0z, az: E, exp(2,))
à
exp(zs)
exp(zi) E, exp(z,) exp(z;) exp(zi)
=ps(1 - -pi)
(42)
E, exp(2)))2
Observe that: p;(1 pi) > 0 0 0 < Pi < 1 and
8p: U5:
0 p: - 0 p; 1. For j # i:
Op: 0 exp(zz)
exp(zs) exp(2,)
dzj Zz, Σn exp(zn)
En exp(2x))2
=P:P;
(43)
30

---

Published as a conference paper at ICLR 2026
This proves that the softmax probabilities increase with their corresponding logits and decrease with other logits.
The above well-known fact and we do not claim novelty.
H.2 POTENTIAL LIMITATIONS: OUTPUT CANCELLATION
However, it is possible to find counterexamples in which measuring the absolute Jacobian sensitivity could be insufficient or even misleading: if positive and negative influence always cancel each other out. We find such situation can happen in unregularised linear models with heavy collinearity of features (Hastie et al. 2009 p.63) indeed, this is presented as one of the motivations ridge regression. To better understand this, we give simple model of such cancellation:
Proposition H.1 (Absolute Jacobian sensitivity may over-estimate influence). There exists a model he, where the combined effect of changes in input variables the output is zero (i.e., the sum of the partial derivatives is zero), while the sum of the absolute values of the individual partial derivatives is nonzero.
Proof of Proposition H.7 our calculation. Let input and output features be scalars X,, Iu on H, h, (nodewise binary classification where using a single logit as input to sigmoid function is possible). The influence
Consider graph with three nodes u, V, where is the focal node for
Assume the model learns the function by 2u zw and that za Tw. then following the definition in the main text:
I(u, u) = [hh and similarly for X = Tw, [(u w)
ahs 3x
@hy Oxr
Oh
(v) ((v, u) + [(u,w) w)=
+
[1|
1 2,
(44)
while h, 0. In fact,
Oh,
Oh.
+
--1
(45)
Fx.
drw
holds for all (Iu, ;.)); no -ifll-difference assumption on T, and F., is required.
This demonstrates that the sum of the absolute values of the Jacobian entries can be non-zero, when the net effect on the output zero. The key is the opposing nature of their influence, not their specific values. The example sets zi and Fae as approximately equal highlight that the output can be small (or changes to it can be small) while the individual influences are significant.
Although this a valid concern, we next show that for Message Passing Neural Networks (MPNNs), at least at initialization, such cancellation does not happen.
Definition H.2 (Message-Passing Neural Network layer). For MPNN layer I, the node feature update for is given by: x (((+) ó (!!) DuENTY) v (x.").!')) where is message function, responsible for computing interactions between neighboring nodes, + is permutation- invariant aggregation function, such as summation, mean, or max, & is an update function that integrates aggregated information into the node representation.
Definition H.3 (Smooth Hypersurface in RP) A hypersurface in H is a subset defined locally as the zero of continuously differentiable function f RDD + such that the gradient f is nonzero at almost every point where f = 0. That is, if we have equation of the form f(0) = 0. where 0 is a vector of parameters, and if ( + generically, then f 0 defines a (locally) (D di-dimensional manifold, which is a hypersurface.
Theorem H.4 (Measure-zero of exact cancellation at MPNN initialization). Consider an MPNN where the functions vé and o are parameterized by 0 and differentiable, typically modeled as Mul- tiLayer Perceptrons (MLPs). Suppose the parameters are drawn from a probability distribution that is absolutely continuous with respect to the Lebesgue measure. Then, the set of parameter configurations for which exact cancellation of Jacobian contributions occurs has Lebesgue measure
31

---

Published as a conference paper at ICLR 2026
For exact cancellation to hold assuming + Σ. the following sum must be identically zero while the individual terms remain non-zero Since té and ø are differentiable and parameterized by 0, each Jacobian term is smooth function of 0. The equation:
Proof of Theorem H.4
(
f(0) = (EN(
= 0,
(46)
ax
defines a level set of smooth functions, hypersurface (or set of lower-dimensional submanifolds) in parameter space. The solution set of a nontrivial smooth function has Lebesgue measure zero unless is identically zero across all 0, which is not the case here. Furthermore, since is drawn from an absolutely continuous distribution (such as Gaussian or uniform), the probability of exactly selecting parameter that lies on this hypersurface zero at initialization. Thus, exact cancellation of Jacobian contributions is an event of measure zero in the space of our idealized single-layer MPNN: this can naturally be extended to multiple layers. Note that in this proof we have assumed the Jacobian sum is not identically zero by construction, unlike in Proposition H. where the function was explicitly constructed to ensure cancellation.
Lastly, it worth noting an alternative perspective on interpreting influence measures derived from the sum of absolute Jacobian entries, particularly when considering potential cancellation effects as demonstrated in Proposition H.I One can indeed argue that the measure's 's utility lies precisely in its capacity to quantify the magnitude of sensitivity to inputs from individual distant nodes or pathways, irrespective of whether these influences ultimately negate one another in contributing to the final output. From this stance, focusing the of absolute values reveals the underlying structure and strength of potential long-range dependencies (the information channels themselves) that might be obscured by observing only the net effect. This interpretation, therefore, hinges on defining dependency or interaction based on the existence and intensity of these information flow pathways, rather than strictly on their final, combined impact node's prediction.
I ADDITIONAL DEFINITIONS IN SECTION
Definition I.1 (Standard lattice in P.). The standard lattice in RD, denoted by ZP, is the set of all integer-coordinate points in R:: zd = {(21, 22. 23 E Z for all = 1.....,D D). Equivalently, zP consists of all points that be written integer linear combinations of the standard basis vectors: _ {E Ze 2, E 2 where (e,,e....,,e) } is the standard basis
for D. meaning each e, is unit vector with I in the i-th position and 0 elsewhere. This lattice forms a grid-like structure in IR D with each point having exactly 2D one-hop (adjacent lattice) neighbors. For a planar graph D 2, hence, each node has total of 4 neighbors.
Definition I.2 (h-hop shells). Let g = (V, .E) be a graph with shortest- -aath distance p V V + N. The h-hop shell (or h-hop neighberhood) of node v E is defined as Nx( = (u E V plu, u) = hj. That is, NN, (v) consists of all nodes that are exactly h hops away from v.
Definition 1.3 (Quasi-isometric graphs). Let 9 = (V1, E1) and G2 (V2, E2) be two graphs equipped with shortest-pale -attstt-ttthhhhe distance functions P1 : V1 Vi + R>o and P2 1/2 x V/2 Rzo- respectively (in our case distances are in N). We say that G1 and Go are gmasi-isomert
if there exist constants À 2 1, 2 O, and D 2 O, and a function f V1 - V22 such that for all u, Vi: (pl(u,) v) e I (f), fu)) < Ap,(u, v) + C. Every node in V22 is within distance D of some f(w), i.e., Ye V2, Bu E V1 such that p2(v, (w)) < D.
J PROOFS FOR THEORETICAL RESULTS IN SECTION 6
Proof of Lemma 6 Since 9 giid in D dimensions, its structure mimics that of DD In RR.. the volume of a ball of radius h scales as h² (recall the volume of a sphere in R is 3 T Let
4
(v) = {u E V : p(v, u) < h).
(47)
denote the ball of radius h centered at c. Then for large (asymptotic bound),
[B((v) Ol.
(48)
32

---

Published as a conference paper at ICLR 2026
Since the h-hop neighborhood is the set difference
(x(e) = B,(()) \ (n))
(49)
This effectively means that the size of (1) is approximately the difference between the volume of two consecutive balls:
[Wa(2)] (v) [B)-(t))-
(50)
standard asymptotic argument implies
[W) = P(hP-1),
(51)
since we can approximate the aforementioned difference via:
(v)) - (B).1(rr] Ch e(h - 1) = Eh. - E(h. D& D
(52)
using the binomial expansion and assuming large h (we are concerned with long-range interactions), where the leading order term dominates. Intuitively, this corresponds to the surface growth of the ball, which in IR scales as h" D-1 (the area of a sphere in R is 4Th²). Thus, there exist constants
E C2
0 and integer ho such that for all h 2 ho.
e, C S Wi(('ll S 12111
(53)
Proof Theorem 6.2
Assume that within (v) there is unique node u" with a strong influence [(v, u²) 1' and that for all other nodes E (v) \ {u*}, J. the influence [(v, u) is negligible
(A R 0). Then:
The total (or sum) influence is
Sum (v,, =
E
[e,,u) 2 ((, = 1"
(54)
(0N
The mean influence given by Amean (v, h))
Σ
[(0,
1 Wi((v)
(1++
Σ
I(e,u))
1' + A [Na(v]]
(55)
[v)
(e)
Using the lower bound on (w)(
1+ E, Пー
m (v, h)
(56)
Since D-1 h do for D 2, it follows that
Imean (v, h) - 0,
(57)
while (sum(o, h) 2 Is remains non-vanishing.
Proof of Corollary 6.3 For planar graph that is grid-like (for example, a two-dimensional lattice), set D = 2. Then, (v) = 0(12-1)= @(h). Repeating the same argument as above: the total
influence satisfies (u, h) 2 _*_ The mean influence is bounded by (u, h) < [M S e, x-
1"
Hence, h 0o, Tuncan( (v, h) - O, which demonstrates that for a planar graph the dilution of the mean aggregated influence occurs at a rate proportional to 1/h.
Proof of Corollary 6.4 Since G is grid-like in D dimensions, the size of the aggregated h-hop neighborhood (the ball) grows as [v)] = (.,P). Assuming that only one node u" in (v)v) has significant influence I' while the influence of all other nodes is negligible, the total (or sum) influence
satisfies B (v, h) > I*. Thus, the mean influence over Bx(v) is 1 (v, h) 5 क( That is, there
f"
exists constant C > 0 such that B hv < follows that B mean (v. h) 0.
_
RD.. Since hD + as h + for D 2 1, it
33

---

Published as a conference paper at ICLR 2026
Proof of Corollary 6.3 For any node E V. by the distinguished node assumption (reused from Theorem 6.2) there is at least one u" E (N)v with
((r,"))21'
(58)
Since the total influence is sum nonnegative contributions, it follows that
Th(() = Σ
I(u, 2 ((,,'')
(59)
MENi(e)
Averaging over all nodes V.
Tk
1
Σ Tx( BEV
2
1 Σr=r. V NEV
(60)
This bound is independent of the size (t) of the h-hop neighborhood and hence remains valid even as (N.(v) (or the overall number of nodes) tends to infinity.
1 Σ Th
(2))2 1" Vh.
(61)
V BEV
34


Reviews:
[{"review_id": "nqcw74BuYD", "reviewer": "Reviewer_ckYP", "summary": "This paper introduces City-Networks, a new benchmark dataset designed to evaluate long-range dependency handling in graph learning models. It consists of large real-world road networks (100k–569k nodes) from four global cities and labels nodes by computing local eccentricity over large hop distances (k=16 layers). The task is transductive node classification; models must incorporate information from far-away neighborhoods to succeed.\n\nThe authors also propose a model-agnostic Jacobian-based influence measure that quantifies how much distant nodes contribute to predictions. They show deeper GNNs and graph transformers consistently improve on these datasets and provide theoretical justification linking dataset topology to reduced over-smoothing and emphasizing influence dilution in grid-like graphs.", "questions": "1. Can you please defend and answer the questions or concerns raise in **Weaknesses**?\n2. How sensitive is performance to the inclusion of geographic features (lat/long)? Can you report results where positional coordinates are removed?\n3. Can models exploit spatial coordinates alone (that is consider separately MLP with coordinates only and GNNs with coordinates masked)?\n4. What is the runtime overhead of Jacobian measurement on a single city graph?\n5. Can you please provide a Table with accuracy results you presented in Figure 3 for k=16? It will be more easier to compare the results.\n6. How would your model perform on heterephilic datasets (Texas, Wisconsin, Cornell, Roman-Empire, etc)", "limitations": "", "rating": 4, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. **Novel Benchmark Contribution**: Introduces a real-world long-range benchmark on large graphs.\n\n2. **Task Design**:\n- Long-range target signal (local eccentricity) is explicitly tied to graph distance, not just node features.\n- Sensible justification for choosing k=16 to require long-range aggregation.\n\n3. **Good Empirical Study**: Systematic layer-depth experiments show deeper message passing helps.\n\n4. **Theoretical Support**: Spectral argument connecting large diameter & low degree to slower over-smoothing.", "weaknesses": "1. **More Clarity Needed on Task Setup**:\n- Distribution of quantile labels — class imbalance?\n- Exact splits and sampling details\n\n2. **Transductive-only Setting**: Dataset is transductive; how will the ideas generalize to inductive settings?\n\n3. **Label Leakage and Spatial Bias Concerns**: Although the authors argue against pure geographical dependence, node features include latitude & longitude and spatially-derived attributes. It is not fully demonstrated that models can't rely largely on spatial features alone. Stronger evidence is needed to show that spatial coordinates alone cannot solve most of the signal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tSuTNf2f3G", "reviewer": "Reviewer_e2fb", "summary": "This work proposes a real-world, attributed, transductive benchmark consisting of four city networks, where the task is to classify each junction’s \"urban accessibility\", defined via a local eccentricity measure with radius 16. This, they argue, creates non-trivial long-range task dependencies. They also explore other radii values: smaller ones make the task too easy, while larger ones suffer from uninformativeness of the graph structure. They compare several network metrics with existing graph datasets and show that their city networks have larger diameters but are sparser and more grid-like; this mitigates over-smoothing and makes them better suited for benchmarking long ranges. They benchmark both GNNs and graph transformers and find that, on their dataset, performance consistently improves with depth, whereas on common benchmarks it typically plateaus or drops. Finally, they introduce a measure of long-range dependency that examines the layer-wise and cumulative influence of distant nodes on predictions. On their dataset, this influence is stronger and decays much more slowly than on the others.", "questions": "1. It would help to see how the influence measurement behaves on synthetic long-range tasks (1). In a setting without real-world noise and with fully controlled dependencies, does the influence become more stable across models, or do we still observe the same variability?\n2. The paper states that \"graphs with long-range dependencies are expected to have higher proportional influence between more distant nodes\", but this assumes a monotone growth of influence with distance. In practice a task could depend on radius 0 and on exactly radius R, and your global metric would average it out. Can this happen for your task, and could models overfit to intermediate radii in a way that even distorts the per-hop measurement?\n3. How does the theoretical argument about sparsity and slower over-smoothing relate to phenomena like the Braess paradox, where removing edges can increase leading eigenvalues, and to empirical findings that sparsity can reduce measured over-smoothing even when the leading eigenvalue grows (2)?\n\n(1) GLoRa: A Benchmark to Evaluate the Ability to Learn Long-Range Dependencies in Graphs. Dongzhuoran Zhou et al., ICLR 2025.\n\n(2) Spectral Graph Pruning Against Over-Squashing and Over-Smoothing. Adarsh Jamadandi et al., NeurIPS 2024.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces a transductive benchmark built from real road networks, and moves beyond the small citation-like graphs that dominate current GNN evaluations of long range tasks.\n- On their benchmark, all models improve with depth, which is not the case on most standard datasets, and is thus a good indicator that the task needs long-range interactions. They furthermore support it with theory on over-smoothing, showing why this is possible on this kind of structure.\n- Road networks are an important application area of graph learning, so a benchmark based on them is very welcome.", "weaknesses": "1. I am not fully convinced by the benefits of the proposed long-range influence metric. It does not seem strictly model-agnostic, since the influence values still depend on the trained parameters and even change across models (cf. Table 2). It mostly answers \"did this model use long-range information?\" rather than \"is this dataset inherently long-range?\"\n2. I think the limitation of this metric on dense graphs is too important to be buried in the appendix; it should be brought into the main text and discussed more lengthily and explicitly.\n3. While it is a good point to test graph transformers on large graphs for scalability, I am not sure this setting is the most revealing for getting insights. I.e. failure cases on smaller graphs are often more informative because there are fewer confounding factors. This benchmark awkwardly sits between being realistic and being revealing.\n4. The defined task is not necessarily informing about the accessibility of a city area. For instance, in practice longer and faster highways can make areas more accessible and not less. The task is still a synthetic one defined on top of a real graph structure.\n5. Fixing the ground-truth radius at 16 and mostly benchmarking models up to that depth is not entirely fair. The other tasks can make models suffer from over-smoothing from having more layers than required. Apart from a single point in Fig. 8, I would like to see more results with deeper models than the target radius.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6djsSFtvjM", "reviewer": "Reviewer_NW7j", "summary": "The paper suggests a new graph dataset that is clearly based long-range dependencies. The graphs are based on city road networks of four major cities with the target to compute the furthest distance one can travel passing 16 junctions. In addition, they provide a measurement that computes the influence of far-away nodes, highlighting that indeed the constructed graphs contain long-range dependencies.", "questions": "see weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper addresses an important open problem in graph learning as currently good benchmarks for long-range dependencies are missing even though we know (or rather assume) that long-range dependencies exist in many real-world tasks. The construction of the dataset is very clear and the provided metric improves upon the main existing alternative (Bamberger et al 2025) in terms of speed and possibly accuracy. The theoretical justification is non-trivial and makes a sound impression. The paper is well-written and easy to follow.", "weaknesses": "Not exactly strong weaknesses, but rather points that I would have liked:\n- a more detailed comparison to the metric by Bamberger et al which I did expect to be mentioned in the introduction as well (e.g. in 107 I did expect that reference)\n- a more concrete statement in 125ff that the appendix contains the exact list of features that made it into the dataset. The description in the main paper is a little to vague here for my personal taste.\n- the conclusion states that LRGB's claim for long-range is solely based on the performance gap while the paper also talks about larger (even though not large) graphs and larger diameter.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)