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'.
翻译:信息传递神经网络(MPNNS)是图形神经网络的事例,它利用图图向边缘发送信息。 这种暗示性偏差导致一种被称为超压现象,即一个节点特征对远端节点所含信息不敏感。 尽管最近采用了一些方法来缓解这一问题,但人们仍缺乏对超压原因和可能解决办法的理解。在这个理论工作中,我们证明:(一) 神经网络宽度可以缓解超压现象,但代价是使整个网络更加敏感;(二) 相反,深度无法帮助缓解超压现象:(二) 反过来,深度无法帮助缓解超压现象:增加层数导致超压层以消失的梯度为主;(三) 图形表层发挥最大作用,因为高通勤时间的节点之间会发生超压现象。我们的分析提供了一个统一框架,用于研究最近为应付超压现象而采用的不同方法,并成为“绘图重新布线”下某类方法的理由。