GwAC: GNNs With Asynchronous Communication

Lukas Faber, Roger Wattenhofer
Proceedings of the Second Learning on Graphs Conference, PMLR 231:8:1-8:20, 2024.

Abstract

This paper studies the relation between Graph Neural Networks and Distributed Computing Models to propose a new framework for Learning in Graphs. Current Graph Neural Networks (GNNs) are closely related to the synchronous model from distributed computing. Nodes operate in rounds and receive neighborhood information aggregated and at the same time. Our new framework, on the other hand, proposes GNNs with Asynchronous Communication: Every message is received individually and at potentially different times. We prove this framework must be at least as expressive as the existing synchronous framwork. We further analyze GwAC theoretically and practically with regard to several GNN problems: Expressiveness beyond 1-Weisfeiler Lehman (1WL), Underreaching, and Oversmoothing. GwAC shows promising improvements for all problems. We finish with a practical study on how to implement GwAC GNNs efficiently.

Cite this Paper

BibTeX
@InProceedings{pmlr-v231-faber24a, title = {GwAC: GNNs With Asynchronous Communication}, author = {Faber, Lukas and Wattenhofer, Roger}, booktitle = {Proceedings of the Second Learning on Graphs Conference}, pages = {8:1--8:20}, year = {2024}, editor = {Villar, Soledad and Chamberlain, Benjamin}, volume = {231}, series = {Proceedings of Machine Learning Research}, month = {27--30 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v231/faber24a/faber24a.pdf}, url = {https://proceedings.mlr.press/v231/faber24a.html}, abstract = {This paper studies the relation between Graph Neural Networks and Distributed Computing Models to propose a new framework for Learning in Graphs. Current Graph Neural Networks (GNNs) are closely related to the synchronous model from distributed computing. Nodes operate in rounds and receive neighborhood information aggregated and at the same time. Our new framework, on the other hand, proposes GNNs with Asynchronous Communication: Every message is received individually and at potentially different times. We prove this framework must be at least as expressive as the existing synchronous framwork. We further analyze GwAC theoretically and practically with regard to several GNN problems: Expressiveness beyond 1-Weisfeiler Lehman (1WL), Underreaching, and Oversmoothing. GwAC shows promising improvements for all problems. We finish with a practical study on how to implement GwAC GNNs efficiently.} }
Endnote
%0 Conference Paper %T GwAC: GNNs With Asynchronous Communication %A Lukas Faber %A Roger Wattenhofer %B Proceedings of the Second Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2024 %E Soledad Villar %E Benjamin Chamberlain %F pmlr-v231-faber24a %I PMLR %P 8:1--8:20 %U https://proceedings.mlr.press/v231/faber24a.html %V 231 %X This paper studies the relation between Graph Neural Networks and Distributed Computing Models to propose a new framework for Learning in Graphs. Current Graph Neural Networks (GNNs) are closely related to the synchronous model from distributed computing. Nodes operate in rounds and receive neighborhood information aggregated and at the same time. Our new framework, on the other hand, proposes GNNs with Asynchronous Communication: Every message is received individually and at potentially different times. We prove this framework must be at least as expressive as the existing synchronous framwork. We further analyze GwAC theoretically and practically with regard to several GNN problems: Expressiveness beyond 1-Weisfeiler Lehman (1WL), Underreaching, and Oversmoothing. GwAC shows promising improvements for all problems. We finish with a practical study on how to implement GwAC GNNs efficiently.
APA
Faber, L. & Wattenhofer, R.. (2024). GwAC: GNNs With Asynchronous Communication. Proceedings of the Second Learning on Graphs Conference, in Proceedings of Machine Learning Research 231:8:1-8:20 Available from https://proceedings.mlr.press/v231/faber24a.html.

Related Material