Graph Unitary Message Passing
This addresses oversquashing in GNNs for graph learning applications, but appears incremental as it builds on unitary RNN concepts.
The paper tackles the oversquashing problem in Graph Neural Networks (GNNs) by proposing Graph Unitary Message Passing (GUMP), which uses a unitary adjacency matrix for message passing, and shows effectiveness in improving performance on various graph learning tasks.
Message passing mechanism contributes to the success of GNNs in various applications, but also brings the oversquashing problem. Recent works combat oversquashing by improving the graph spectrums with rewiring techniques, disrupting the structural bias in graphs, and having limited improvement on oversquashing in terms of oversquashing measure. Motivated by unitary RNN, we propose Graph Unitary Message Passing (GUMP) to alleviate oversquashing in GNNs by applying unitary adjacency matrix for message passing. To design GUMP, a transformation is first proposed to make general graphs have unitary adjacency matrix and keep its structural bias. Then, unitary adjacency matrix is obtained with a unitary projection algorithm, which is implemented by utilizing the intrinsic structure of unitary adjacency matrix and allows GUMP to be permutation-equivariant. Experimental results show the effectiveness of GUMP in improving the performance on various graph learning tasks.