Non-backtracking Graph Neural Networks

• URL: http://arxiv.org/abs/2310.07430v2
• Date: Wed, 25 Sep 2024 11:19:47 GMT
• Title: Non-backtracking Graph Neural Networks
• Abstract summary: We propose a non-backtracking graph neural network (NBA-GNN) that updates a message without incorporating the message from the previously visited node. We theoretically investigate how NBA-GNN alleviates the over-squashing of GNNs, and establish the impressive performance of non-backtracking updates for block recovery.
• Score: 28.206751149328216
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The celebrated message-passing updates for graph neural networks allow representing large-scale graphs with local and computationally tractable updates. However, the updates suffer from backtracking, i.e., a message flowing through the same edge twice and revisiting the previously visited node. Since the number of message flows increases exponentially with the number of updates, the redundancy in local updates prevents the graph neural network from accurately recognizing a particular message flow relevant for downstream tasks. In this work, we propose to resolve such a redundancy issue via the non-backtracking graph neural network (NBA-GNN) that updates a message without incorporating the message from the previously visited node. We theoretically investigate how NBA-GNN alleviates the over-squashing of GNNs, and establish a connection between NBA-GNN and the impressive performance of non-backtracking updates for stochastic block model recovery. Furthermore, we empirically verify the effectiveness of our NBA-GNN on the long-range graph benchmark and transductive node classification problems.

Related papers

• Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks [21.49824162847618]
  Graph Neural Networks (GNNs) suffer from Oversquashing, which occurs when tasks require long-range interactions.<n>We propose an efficient model-agnostic framework that asynchronously updates node features, unlike traditional synchronous message passing GNNs.<n>Our framework is applied to six standard graph datasets and two long-range datasets to perform graph classification.
  arXiv  Detail & Related papers  (2025-09-08T15:03:05Z)
• Channel-Attentive Graph Neural Networks [0.0]
  Graph Neural Networks (GNNs) set the state-of-the-art in representation learning for graph-structured data. Message-passing mechanism used in most models suffers from over-smoothing as a GNN's depth increases. This study proposes an adaptive channel-wise message-passing approach to alleviate the over-smoothing.
  arXiv  Detail & Related papers  (2025-03-01T18:00:41Z)
• Towards Dynamic Message Passing on Graphs [104.06474765596687]
  We propose a novel dynamic message-passing mechanism for graph neural networks (GNNs) It projects graph nodes and learnable pseudo nodes into a common space with measurable spatial relations between them. With nodes moving in the space, their evolving relations facilitate flexible pathway construction for a dynamic message-passing process.
  arXiv  Detail & Related papers  (2024-10-31T07:20:40Z)
• STAG: Enabling Low Latency and Low Staleness of GNN-based Services with Dynamic Graphs [20.94927463359297]
  We propose STAG, a GNN serving framework that enables low latency and low staleness of GNN-based services. Experimental results show that STAG accelerates the update phase by 1.3x90.1x, and greatly reduces staleness time with a slight increase in response latency.
  arXiv  Detail & Related papers  (2023-09-27T05:15:02Z)
• Is Rewiring Actually Helpful in Graph Neural Networks? [11.52174067809364]
  We propose an evaluation setting based on message-passing models that do not require training to compute node and graph representations. We perform a systematic experimental comparison on real-world node and graph classification tasks, showing that rewiring the underlying graph rarely does confer a practical benefit for message-passing.
  arXiv  Detail & Related papers  (2023-05-31T10:12:23Z)
• Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction [23.545059901853815]
  Graph Neural Networks (GNNs) have been widely applied to various fields for learning over graphstructured data. We propose Neighborhood Overlap-aware Graph Neural Networks (Neo-GNNs) that learn useful structural features from an adjacency overlapped neighborhoods for link prediction.
  arXiv  Detail & Related papers  (2022-06-09T01:43:49Z)
• Very Deep Graph Neural Networks Via Noise Regularisation [57.450532911995516]
  Graph Neural Networks (GNNs) perform learned message passing over an input graph. We train a deep GNN with up to 100 message passing steps and achieve several state-of-the-art results.
  arXiv  Detail & Related papers  (2021-06-15T08:50:10Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  We consider the problem of learning a graphon neural network (WNN) by training GNNs on graphs sampled Bernoulli from the graphon. Inspired by these results, we propose an algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training.
  arXiv  Detail & Related papers  (2021-06-07T15:05:59Z)
• Binary Graph Neural Networks [69.51765073772226]
  Graph Neural Networks (GNNs) have emerged as a powerful and flexible framework for representation learning on irregular data. In this paper, we present and evaluate different strategies for the binarization of graph neural networks. We show that through careful design of the models, and control of the training process, binary graph neural networks can be trained at only a moderate cost in accuracy on challenging benchmarks.
  arXiv  Detail & Related papers  (2020-12-31T18:48:58Z)
• Overcoming Catastrophic Forgetting in Graph Neural Networks [50.900153089330175]
  Catastrophic forgetting refers to the tendency that a neural network "forgets" the previous learned knowledge upon learning new tasks. We propose a novel scheme dedicated to overcoming this problem and hence strengthen continual learning in graph neural networks (GNNs) At the heart of our approach is a generic module, termed as topology-aware weight preserving(TWP)
  arXiv  Detail & Related papers  (2020-12-10T22:30:25Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  Graph Neural Networks (GNNs) have risen to prominence in learning representations for graph structured data. In this work, we establish mathematically that the aggregation processes in a group of representative GNN models can be regarded as solving a graph denoising problem. We instantiate a novel GNN model, ADA-UGNN, derived from UGNN, to handle graphs with adaptive smoothness across nodes.
  arXiv  Detail & Related papers  (2020-10-05T04:57:18Z)
• Graph Convolutional Neural Networks with Node Transition Probability-based Message Passing and DropNode Regularization [32.260055351563324]
  Graph convolutional neural networks (GCNNs) have received much attention recently, owing to their capability in handling graph-structured data. This work presents a new method to improve the message passing process based on node transition probabilities. We also propose a novel regularization method termed DropNode to address the over-fitting and over-smoothing issues simultaneously.
  arXiv  Detail & Related papers  (2020-08-28T10:51:03Z)

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.