Recurrent Distance Filtering for Graph Representation Learning

• URL: http://arxiv.org/abs/2312.01538v3
• Date: Wed, 5 Jun 2024 14:18:59 GMT
• Title: Recurrent Distance Filtering for Graph Representation Learning
• Authors: Yuhui Ding, Antonio Orvieto, Bobby He, Thomas Hofmann,
• Abstract summary: Graph neural networks based on iterative one-hop message passing have been shown to struggle in harnessing the information from distant nodes effectively. We propose a new architecture to reconcile these challenges. Our model aggregates other nodes by their shortest distances to the target and uses a linear RNN to encode the sequence of hop representations.
• Score: 34.761926988427284
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks based on iterative one-hop message passing have been shown to struggle in harnessing the information from distant nodes effectively. Conversely, graph transformers allow each node to attend to all other nodes directly, but lack graph inductive bias and have to rely on ad-hoc positional encoding. In this paper, we propose a new architecture to reconcile these challenges. Our approach stems from the recent breakthroughs in long-range modeling provided by deep state-space models: for a given target node, our model aggregates other nodes by their shortest distances to the target and uses a linear RNN to encode the sequence of hop representations. The linear RNN is parameterized in a particular diagonal form for stable long-range signal propagation and is theoretically expressive enough to encode the neighborhood hierarchy. With no need for positional encoding, we empirically show that the performance of our model is comparable to or better than that of state-of-the-art graph transformers on various benchmarks, with a significantly reduced computational cost. Our code is open-source at https://github.com/skeletondyh/GRED.

Related papers

• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  We propose Spatio-Spectral Graph Networks (S$2$GNNs) S$2$GNNs combine spatially and spectrally parametrized graph filters. We show that S$2$GNNs vanquish over-squashing and yield strictly tighter approximation-theoretic error bounds than MPGNNs.
  arXiv  Detail & Related papers  (2024-05-29T14:28:08Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  We propose a novel heterogeneous graph neural network with sequential node representation, namely Seq-HGNN. We conduct extensive experiments on four widely used datasets from Heterogeneous Graph Benchmark (HGB) and Open Graph Benchmark (OGB)
  arXiv  Detail & Related papers  (2023-05-18T07:27:18Z)
• 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)
• Rewiring with Positional Encodings for Graph Neural Networks [37.394229290996364]
  Several recent works use positional encodings to extend receptive fields of graph neural network layers equipped with attention mechanisms. We use positional encodings to expand receptive fields to $r$-hop neighborhoods. We obtain improvements on a variety of models and datasets and reach competitive performance using traditional GNNs or graph Transformers.
  arXiv  Detail & Related papers  (2022-01-29T22:26:02Z)
• Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
  We show that in typical heterphilous graphs, the edges may be directed, and whether to treat the edges as is or simply make them undirected greatly affects the performance of the GNN models. We develop a model that adaptively learns the directionality of the graph, and exploits the underlying long-distance correlations between nodes.
  arXiv  Detail & Related papers  (2021-11-19T08:54:21Z)
• Isometric Graph Neural Networks [5.306334746787569]
  We propose a technique to learn Isometric Graph Neural Networks (IGNN) IGNN requires changing the input representation space and loss function to enable any GNN algorithm to generate representations that reflect distances between nodes. We observe a consistent and substantial improvement as high as 400% in Kendall's Tau (KT)
  arXiv  Detail & Related papers  (2020-06-16T22:51:13Z)

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.