Non-Redundant Graph Neural Networks with Improved Expressiveness
Authors:
Preprint
Abstract
Message passing graph neural networks iteratively compute node embeddings by aggregating messages from all neighbors. This procedure can be viewed as a neural variant of the Weisfeiler-Leman method, which limits their expressive power. Moreover, oversmoothing and oversquashing restrict the number of layers these networks can effectively utilize. The repeated exchange and encoding of identical information in message passing amplifies oversquashing. We propose a novel aggregation scheme based on neighborhood trees, which allows for controlling the redundancy by pruning branches of the unfolding trees underlying standard message passing. We prove that reducing redundancy improves expressivity and experimentally show that it alleviates oversquashing. We investigate the interaction between redundancy in message passing and redundancy in computation and propose a compact representation of neighborhood trees, from which we compute node and graph embeddings via a neural tree canonization technique. Our method is provably more expressive than the Weisfeiler-Leman method, less susceptible to oversquashing than message passing neural networks, and provides high classification accuracy on widely-used benchmark datasets.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Approximating the Graph Edit Distance with Compact Neighborhood Representations2024
- Theory of graph neural networks: representation and learning2023
- Towards Deeper Graph Neural Networks2020
- SPAGAN: Shortest Path Graph Attention Network2019
- Computational Capabilities of Graph Neural NetworksIEEE Transactions on Neural Networks, 2009
- Algorithms and Data Structures2008
- Extensions of marginalized graph kernels2004