Asynchronous Neural Networks for Learning in Graphs
This addresses a fundamental bottleneck in graph learning for researchers and practitioners, offering a novel approach to improve model expressiveness and performance.
The paper tackles the problem of oversmoothing and limited expressiveness in graph neural networks by introducing asynchronous message passing (AMP), a new paradigm that allows nodes to react individually to neighbor messages, and demonstrates that AMP can theoretically distinguish any pair of graphs and performs well on graph classification benchmarks.
This paper studies asynchronous message passing (AMP), a new paradigm for applying neural network based learning to graphs. Existing graph neural networks use the synchronous distributed computing model and aggregate their neighbors in each round, which causes problems such as oversmoothing and limits their expressiveness. On the other hand, AMP is based on the asynchronous model, where nodes react to messages of their neighbors individually. We prove that (i) AMP can simulate synchronous GNNs and that (ii) AMP can theoretically distinguish any pair of graphs. We experimentally validate AMP's expressiveness. Further, we show that AMP might be better suited to propagate messages over large distances in graphs and performs well on several graph classification benchmarks.