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

• URL: http://arxiv.org/abs/2503.09008v1
• Date: Wed, 12 Mar 2025 02:51:17 GMT
• 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,
• Abstract summary: Long-range dependencies are critical for effective graph representation learning.<n>Most existing datasets focus on small graphs tailored to inductive tasks, offering limited insight into long-range interactions.<n>We introduce City-Networks, a novel large-scale transductive learning dataset derived from real-world city roads.
• Score: 10.124564216461858
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 City-Networks, a novel large-scale transductive learning dataset derived from real-world city roads. 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 using an eccentricity-based approach, ensuring that the classification task inherently requires information from distant nodes. Furthermore, we propose a model-agnostic 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.

Related papers

• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs)<n>This framework provides a standardized setting to evaluate GNNs across diverse datasets.<n>We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• Multi-Scene Generalized Trajectory Global Graph Solver with Composite Nodes for Multiple Object Tracking [61.69892497726235]
  Composite Node Message Passing Network (CoNo-Link) is a framework for modeling ultra-long frames information for association. In addition to the previous method of treating objects as nodes, the network innovatively treats object trajectories as nodes for information interaction. Our model can learn better predictions on longer-time scales by adding composite nodes.
  arXiv  Detail & Related papers  (2023-12-14T14:00:30Z)
• MGNNI: Multiscale Graph Neural Networks with Implicit Layers [53.75421430520501]
  implicit graph neural networks (GNNs) have been proposed to capture long-range dependencies in underlying graphs. We introduce and justify two weaknesses of implicit GNNs: the constrained expressiveness due to their limited effective range for capturing long-range dependencies, and their lack of ability to capture multiscale information on graphs at multiple resolutions. We propose a multiscale graph neural network with implicit layers (MGNNI) which is able to model multiscale structures on graphs and has an expanded effective range for capturing long-range dependencies.
  arXiv  Detail & Related papers  (2022-10-15T18:18:55Z)
• Affinity-Aware Graph Networks [9.888383815189176]
  Graph Neural Networks (GNNs) have emerged as a powerful technique for learning on relational data. We explore the use of affinity measures as features in graph neural networks. We propose message passing networks based on these features and evaluate their performance on a variety of node and graph property prediction tasks.
  arXiv  Detail & Related papers  (2022-06-23T18:51:35Z)
• Long-term Spatio-temporal Forecasting via Dynamic Multiple-Graph Attention [20.52864145999387]
  Long-term tensor-temporal forecasting (LSTF) makes use of long-term dependency between spatial and temporal domains, contextual information, and inherent pattern in the data. We propose new graph models to represent the contextual information of each node and the long-term parking revealed-temporal data dependency structure. Our proposed approaches significantly improve the performance of existing graph neural network models in LSTF prediction tasks.
  arXiv  Detail & Related papers  (2022-04-23T06:51:37Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Dimensionality Reduction Meets Message Passing for Graph Node Embeddings [0.0]
  We propose PCAPass, a method which combines Principal Component Analysis (PCA) and message passing for generating node embeddings in an unsupervised manner. We show empirically that this approach provides competitive performance compared to popular GNNs on node classification benchmarks. Our research demonstrates that applying dimensionality reduction with message passing and skip connections is a promising mechanism for aggregating long-range dependencies in graph structured data.
  arXiv  Detail & Related papers  (2022-02-01T13:39:00Z)
• Hierarchical graph neural nets can capture long-range interactions [8.067880298298185]
  We study hierarchical message passing models that leverage a multi-resolution representation of a given graph. This facilitates learning of features that span large receptive fields without loss of local information. We introduce Hierarchical Graph Net (HGNet), which for any two connected nodes guarantees existence of message-passing paths of at most logarithmic length.
  arXiv  Detail & Related papers  (2021-07-15T16:24:22Z)
• Learning Graph Neural Networks with Positive and Unlabeled Nodes [34.903471348798725]
  Graph neural networks (GNNs) are important tools for transductive learning tasks, such as node classification in graphs. Most GNN models aggregate information from short distances in each round, and fail to capture long distance relationship in graphs. In this paper, we propose a novel graph neural network framework, long-short distance aggregation networks (LSDAN) to overcome these limitations.
  arXiv  Detail & Related papers  (2021-03-08T11:43:37Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Several recent studies attribute this performance deterioration to the over-smoothing issue. We propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields.
  arXiv  Detail & Related papers  (2020-07-18T01:11:14Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.