Irregular message passing networks

The graph neural network (GNN) is a widely adopted technique to process graph-structured data. Despite its pervasiveness, the exact reasons for the message aggregator's effectiveness are still poorly understood. The popular belief is that this effectiveness stems from optimizing edge weights to improve the local fusion of node information. In this study, we demonstrate that such propagation weight optimization has a limited contribution to the success of message passing. Instead, we find that any normalized random attention (or edge weights) can have a similar and, sometime, even stronger effect. We refer to these randomly initialized propagations as irregular message passing. Experiments conducted on our random edge weight and random attention models verified the positive impact of weight randomness, uncovering the importance of the topology itself in achieving superior results for message iterations. Our code is available at https://github.com/Eigenworld/RAN. (c) 2022 Published by Elsevier B.V.

Automated summary

The effectiveness of the message aggregator in graph neural networks is not primarily due to the optimization of edge weights, but rather can be achieved through randomized attention. This finding emphasizes the importance of the network topology in achieving superior performance for message passing iterations.