Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement
Overview
Overall Novelty Assessment
The paper introduces City-Networks, a large-scale transductive dataset derived from real-world road networks, and proposes a Jacobian-based metric to quantify long-range dependencies in graph neural networks. It resides in the 'Formal Characterization and Metrics' leaf under 'Theoretical Foundations and Measurement', sharing this space with only one sibling paper. This leaf is notably sparse, containing just two works focused on principled measurement of long-range interactions, suggesting the paper enters a relatively underpopulated research direction within the broader taxonomy of fifty papers across thirty-six topics.
The taxonomy reveals that most activity concentrates in 'Architecture Design and Enhancement' (nine subcategories, twenty-one papers) and 'Domain Applications' (eight subcategories, twenty-four papers), while 'Theoretical Foundations and Measurement' contains only two subcategories with three papers total. The sibling work 'Random Walks Dependencies' also develops formal metrics, but the taxonomy's scope notes clarify that this leaf excludes empirical benchmarking without theoretical grounding and architectural solutions. Neighboring leaves like 'Fundamental Limitations Analysis' examine over-smoothing and over-squashing, while 'Benchmark Datasets and Tasks' focuses on curated evaluation protocols—both adjacent but distinct from the formal metric development emphasized here.
Among thirty candidates examined via semantic search and citation expansion, none were found to clearly refute any of the three contributions. For the City-Networks dataset contribution, ten candidates were reviewed with zero refutable overlaps; the Jacobian-based measurement similarly examined ten candidates with no prior work providing the same formulation; and the theoretical justifications reviewed ten candidates without encountering overlapping analyses. This suggests that within the limited search scope, the specific combination of large-scale transductive road network data, eccentricity-based annotation, and Jacobian-derived metrics appears distinct from existing benchmarking and measurement efforts.
The analysis covers top-thirty semantic matches and does not constitute an exhaustive literature review. While the sparse taxonomy leaf and absence of refutable candidates within this scope indicate novelty in formal measurement design, the broader field's emphasis on architectural solutions and domain applications means the practical impact of these metrics will depend on adoption by the architecture-focused community. The theoretical grounding and dataset scale appear substantive, though the limited search cannot rule out related work in adjacent measurement frameworks or alternative benchmark designs.
Taxonomy
Research Landscape Overview
Claimed Contributions
The authors propose a new dataset consisting of four large-scale city road networks (Paris, Shanghai, Los Angeles, London) with over 100,000 nodes and diameters up to 400. The dataset is annotated based on local node eccentricities to create a classification task that inherently requires information from distant nodes, addressing the gap in existing benchmarks that focus on small graphs for inductive tasks.
The authors introduce a measurement that quantifies per-hop influence of a focal node's neighbors on its prediction by computing the aggregated l1-norm of the Jacobian from a trained model at each hop. This provides a principled way to measure and compare the level of long-rangeness across different datasets and models, going beyond empirical performance comparisons.
The authors establish theoretical foundations by linking the rate of over-smoothing to algebraic connectivity and network diameter, showing that graphs with large diameters and low maximum degrees are more resilient to over-smoothing. They also analyze influence score dilution in grid-like graphs to justify their choice of aggregating influence scores using summation rather than mean.
Core Task Comparisons
Comparisons with papers in the same taxonomy category
[2] On Measuring Long-Range Interactions in Graph Neural Networks PDF
Contribution Analysis
Detailed comparisons for each claimed contribution
City-Networks: a large-scale transductive learning dataset with long-range dependencies
The authors propose a new dataset consisting of four large-scale city road networks (Paris, Shanghai, Los Angeles, London) with over 100,000 nodes and diameters up to 400. The dataset is annotated based on local node eccentricities to create a classification task that inherently requires information from distant nodes, addressing the gap in existing benchmarks that focus on small graphs for inductive tasks.
[70] An end-to-end attention-based approach for learning on graphs PDF
[71] InterpGNN: Understand and improve generalization ability of transdutive GNNs through the lens of interplay between train and test nodes PDF
[72] Geom-gcn: Geometric graph convolutional networks PDF
[73] Hierarchical message-passing graph neural networks PDF
[74] Handling over-smoothing and over-squashing in graph convolution with maximization operation PDF
[75] Long-Range Neural Atom Learning for Molecular Graphs PDF
[76] Multi-view graph-based text representations for imbalanced classification PDF
[77] Center weighted convolution and GraphSAGE cooperative network for hyperspectral image classification PDF
[78] Learning graph neural networks with positive and unlabeled nodes PDF
[79] LD2: Scalable heterophilous graph neural network with decoupled embeddings PDF
A generic Jacobian-based measurement for quantifying long-range dependencies
The authors introduce a measurement that quantifies per-hop influence of a focal node's neighbors on its prediction by computing the aggregated l1-norm of the Jacobian from a trained model at each hop. This provides a principled way to measure and compare the level of long-rangeness across different datasets and models, going beyond empirical performance comparisons.
[12] Spatio-Spectral Graph Neural Networks PDF
[61] Unleashing the power of high-pass filtering in continuous graph neural networks PDF
[62] Monotone operator theory-inspired message passing for learning long-range interaction on graphs PDF
[63] Incorporating sequential and geometric structure into deep neural networks PDF
[64] Implicit graph neural networks: A monotone operator viewpoint PDF
[65] Dynamic Jacobi graph and trend-aware flow attention convolutional network for traffic forecasting PDF
[66] Neural Rough-Conditioned Switching Models for Generative Regime Inference PDF
[67] Adapting Single-Image Editing Models for Long-Horizon Video with Temporal Consistency Guarantees PDF
[68] Learning Causality for Longitudinal Data PDF
[69] Adaptation and Regularization of Deep Neural Networks Under Temporal Smoothness Assumption PDF
Theoretical justifications for dataset design and measurement based on over-smoothing and influence score dilution
The authors establish theoretical foundations by linking the rate of over-smoothing to algebraic connectivity and network diameter, showing that graphs with large diameters and low maximum degrees are more resilient to over-smoothing. They also analyze influence score dilution in grid-like graphs to justify their choice of aggregating influence scores using summation rather than mean.