Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement

View PDF HTML (experimental)

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.

Comments: Published as a conference paper at ICLR 2026

Subjects:

Machine Learning (cs.LG); Artificial Intelligence (cs.AI)

Cite as: arXiv:2503.09008 [cs.LG]

(or arXiv:2503.09008v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2503.09008

arXiv-issued DOI via DataCite

Submission history

From: Huidong Liang [view email] [v1] Wed, 12 Mar 2025 02:51:17 UTC (5,432 KB) [v2] Fri, 3 Oct 2025 08:31:45 UTC (4,345 KB) [v3] Sat, 28 Mar 2026 13:34:41 UTC (5,614 KB)