Shortest Path Networks for Graph Property Prediction

Ralph Abboud, Radoslav Dimitrov, Ismail Ilkan Ceylan
Proceedings of the First Learning on Graphs Conference, PMLR 198:5:1-5:25, 2022.

Abstract

Most graph neural network models rely on a particular message passing paradigm, where the idea is to iteratively propagate node representations of a graph to each node in the direct neighborhood. While very prominent, this paradigm leads to information propagation bottlenecks, as information is repeatedly compressed at intermediary node representations, which causes loss of information, making it practically impossible to gather meaningful signals from distant nodes. To address this, we propose shortest path message passing neural networks, where the node representations of a graph are propagated to each node in the shortest path neighborhoods. In this setting, nodes can directly communicate between each other even if they are not neighbors, breaking the information bottleneck and hence leading to more adequately learned representations. Our framework generalizes message passing neural networks, resulting in a class of more expressive models, including some recent state-of-the-art models. We verify the capacity of a basic model of this framework on dedicated synthetic experiments, and on real-world graph classification and regression benchmarks, and obtain state-of-the art results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v198-abboud22a, title = {Shortest Path Networks for Graph Property Prediction}, author = {Abboud, Ralph and Dimitrov, Radoslav and Ceylan, Ismail Ilkan}, booktitle = {Proceedings of the First Learning on Graphs Conference}, pages = {5:1--5:25}, year = {2022}, editor = {Rieck, Bastian and Pascanu, Razvan}, volume = {198}, series = {Proceedings of Machine Learning Research}, month = {09--12 Dec}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v198/abboud22a/abboud22a.pdf}, url = {https://proceedings.mlr.press/v198/abboud22a.html}, abstract = {Most graph neural network models rely on a particular message passing paradigm, where the idea is to iteratively propagate node representations of a graph to each node in the direct neighborhood. While very prominent, this paradigm leads to information propagation bottlenecks, as information is repeatedly compressed at intermediary node representations, which causes loss of information, making it practically impossible to gather meaningful signals from distant nodes. To address this, we propose shortest path message passing neural networks, where the node representations of a graph are propagated to each node in the shortest path neighborhoods. In this setting, nodes can directly communicate between each other even if they are not neighbors, breaking the information bottleneck and hence leading to more adequately learned representations. Our framework generalizes message passing neural networks, resulting in a class of more expressive models, including some recent state-of-the-art models. We verify the capacity of a basic model of this framework on dedicated synthetic experiments, and on real-world graph classification and regression benchmarks, and obtain state-of-the art results.} }
Endnote
%0 Conference Paper %T Shortest Path Networks for Graph Property Prediction %A Ralph Abboud %A Radoslav Dimitrov %A Ismail Ilkan Ceylan %B Proceedings of the First Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2022 %E Bastian Rieck %E Razvan Pascanu %F pmlr-v198-abboud22a %I PMLR %P 5:1--5:25 %U https://proceedings.mlr.press/v198/abboud22a.html %V 198 %X Most graph neural network models rely on a particular message passing paradigm, where the idea is to iteratively propagate node representations of a graph to each node in the direct neighborhood. While very prominent, this paradigm leads to information propagation bottlenecks, as information is repeatedly compressed at intermediary node representations, which causes loss of information, making it practically impossible to gather meaningful signals from distant nodes. To address this, we propose shortest path message passing neural networks, where the node representations of a graph are propagated to each node in the shortest path neighborhoods. In this setting, nodes can directly communicate between each other even if they are not neighbors, breaking the information bottleneck and hence leading to more adequately learned representations. Our framework generalizes message passing neural networks, resulting in a class of more expressive models, including some recent state-of-the-art models. We verify the capacity of a basic model of this framework on dedicated synthetic experiments, and on real-world graph classification and regression benchmarks, and obtain state-of-the art results.
APA
Abboud, R., Dimitrov, R. & Ceylan, I.I.. (2022). Shortest Path Networks for Graph Property Prediction. Proceedings of the First Learning on Graphs Conference, in Proceedings of Machine Learning Research 198:5:1-5:25 Available from https://proceedings.mlr.press/v198/abboud22a.html.

Related Material