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

Computer Science > Machine Learning arXiv:2503.09008 (cs) [Submitted on 12 Mar 2025 (v1), last revised 28 Mar 2026 (this version, v3)] Title: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 Bronstein, Xiaowen Dong View a PDF of the paper titled Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement, by Huidong Liang and 4 other authors 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....