Learning Long Range Dependencies on Graphs via Random Walks

• URL: http://arxiv.org/abs/2406.03386v2
• Date: Mon, 07 Oct 2024 14:01:11 GMT
• Title: Learning Long Range Dependencies on Graphs via Random Walks
• Authors: Dexiong Chen, Till Hendrik Schulz, Karsten Borgwardt,
• Abstract summary: Message-passing graph neural networks (GNNs) excel at capturing local relationships but struggle with long-range dependencies in graphs. graph transformers (GTs) enable global information exchange but often oversimplify the graph structure by representing graphs as sets of fixed-length vectors. This work introduces a novel architecture that overcomes the shortcomings of both approaches by combining the long-range information of random walks with local message passing.
• Score: 6.7864586321550595
• License:
• Abstract: Message-passing graph neural networks (GNNs) excel at capturing local relationships but struggle with long-range dependencies in graphs. In contrast, graph transformers (GTs) enable global information exchange but often oversimplify the graph structure by representing graphs as sets of fixed-length vectors. This work introduces a novel architecture that overcomes the shortcomings of both approaches by combining the long-range information of random walks with local message passing. By treating random walks as sequences, our architecture leverages recent advances in sequence models to effectively capture long-range dependencies within these walks. Based on this concept, we propose a framework that offers (1) more expressive graph representations through random walk sequences, (2) the ability to utilize any sequence model for capturing long-range dependencies, and (3) the flexibility by integrating various GNN and GT architectures. Our experimental evaluations demonstrate that our approach achieves significant performance improvements on 19 graph and node benchmark datasets, notably outperforming existing methods by up to 13\% on the PascalVoc-SP and COCO-SP datasets. The code is available at https://github.com/BorgwardtLab/NeuralWalker.

Related papers

• What Can We Learn from State Space Models for Machine Learning on Graphs? [11.38076877943004]
  We propose Graph State Space Convolution (GSSC) as a principled extension of State Space Models (SSMs) to graph-structured data. By leveraging global permutation-equivariant set aggregation and factorizable graph kernels, GSSC preserves all three advantages of SSMs. Our findings highlight the potential of GSSC as a powerful and scalable model for graph machine learning.
  arXiv  Detail & Related papers  (2024-06-09T15:03:36Z)
• 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)
• Sparsity exploitation via discovering graphical models in multi-variate time-series forecasting [1.2762298148425795]
  We propose a decoupled training method, which includes a graph generating module and a GNNs forecasting module. First, we use Graphical Lasso (or GraphLASSO) to directly exploit the sparsity pattern from data to build graph structures. Second, we fit these graph structures and the input data into a Graph Convolutional Recurrent Network (GCRN) to train a forecasting model.
  arXiv  Detail & Related papers  (2023-06-29T16:48:00Z)
• Towards Better Dynamic Graph Learning: New Architecture and Unified Library [29.625205125350313]
  DyGFormer is a Transformer-based architecture for dynamic graph learning. DyGLib is a unified library with standard training pipelines and coding interfaces.
  arXiv  Detail & Related papers  (2023-03-23T05:27:32Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  Modelling long-range dependencies is critical for scene understanding tasks in computer vision. A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2022-09-20T14:41:37Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data. We present a novel Graph Matching based GNN Pre-Training framework, called GMPT. The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
  arXiv  Detail & Related papers  (2022-03-03T09:53:53Z)
• Representing Long-Range Context for Graph Neural Networks with Global Attention [37.212747564546156]
  We propose the use of Transformer-based self-attention to learn long-range pairwise relationships. Our method, which we call GraphTrans, applies a permutation-invariant Transformer module after a standard GNN module. Our results suggest that purely-learning-based approaches without graph structure may be suitable for learning high-level, long-range relationships on graphs.
  arXiv  Detail & Related papers  (2022-01-21T18:16:21Z)
• Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks [91.65637773358347]
  We propose a general graph neural network framework designed specifically for multivariate time series data. Our approach automatically extracts the uni-directed relations among variables through a graph learning module. Our proposed model outperforms the state-of-the-art baseline methods on 3 of 4 benchmark datasets.
  arXiv  Detail & Related papers  (2020-05-24T04:02:18Z)
• Gated Graph Recurrent Neural Networks [176.3960927323358]
  We introduce Graph Recurrent Neural Networks (GRNNs) as a general learning framework for graph processes. To address the problem of vanishing gradients, we put forward GRNNs with three different gating mechanisms: time, node and edge gates. The numerical results also show that GRNNs outperform GNNs and RNNs, highlighting the importance of taking both the temporal and graph structures of a graph process into account.
  arXiv  Detail & Related papers  (2020-02-03T22:35:14Z)

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.