On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology
This theoretical work addresses a fundamental bottleneck in graph neural networks for researchers, providing a unified framework to analyze and justify methods like graph rewiring, but it is incremental as it builds on existing understanding.
The authors tackled the problem of over-squashing in Message Passing Neural Networks, proving that width can mitigate it at the cost of increased sensitivity, depth cannot help due to vanishing gradients, and graph topology is the key factor, with over-squashing occurring between nodes at high commute time.
Message Passing Neural Networks (MPNNs) are instances of Graph Neural Networks that leverage the graph to send messages over the edges. This inductive bias leads to a phenomenon known as over-squashing, where a node feature is insensitive to information contained at distant nodes. Despite recent methods introduced to mitigate this issue, an understanding of the causes for over-squashing and of possible solutions are lacking. In this theoretical work, we prove that: (i) Neural network width can mitigate over-squashing, but at the cost of making the whole network more sensitive; (ii) Conversely, depth cannot help mitigate over-squashing: increasing the number of layers leads to over-squashing being dominated by vanishing gradients; (iii) The graph topology plays the greatest role, since over-squashing occurs between nodes at high commute (access) time. Our analysis provides a unified framework to study different recent methods introduced to cope with over-squashing and serves as a justification for a class of methods that fall under graph rewiring.