Shortest Path Networks for Graph Property Prediction
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 issue, 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. Theoretically, our framework generalizes
message passing neural networks, resulting in provably more expressive models.
Empirically, we verify the capacity of a basic model of this framework on
dedicated synthetic experiments, and on real-world graph classification and
regression benchmarks, obtaining several state-of-the-art results.