@inproceedings{
park2023nonbacktracking,
title={Non-backtracking Graph Neural Networks},
author={Seonghyun Park and Narae Ryu and Gahee Kim and Dongyeop Woo and Se-Young Yun and Sungsoo Ahn},
booktitle={NeurIPS 2023 Workshop: New Frontiers in Graph Learning},
year={2023},
url={https://openreview.net/forum?id=cZMdiwFjCh}
}
The celebrated message-passing updates for graph neural networks allow the representation of large-scale graphs with local and computationally tractable updates. However, the local updates suffer from backtracking, i.e., a message flows through the same edge twice and revisits 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 for downstream tasks. In this work, we propose to resolve such a redundancy via the non-backtracking graph neural network (NBA-GNN) that updates a message without incorporating the message from the previously visited node. We further 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. We empirically verify the effectiveness of our NBA-GNN on long-range graph benchmark and transductive node classification problems.
Non-backtracking Graph Neural Networks
Seonghyun Park Narae Ryu Gahee Kim Dongyeop Woo Se-Young Yun Sungsoo Ahn