Graph Neural Networks (GNNs) are the state-of-the-art model for machine
learning on graph-structured data. The most popular class of GNNs operate by
exchanging information between adjacent nodes, and are known as Message Passing
Neural Networks (MPNNs). Given their widespread use, understanding the
expressive power of MPNNs is a key question. However, existing results
typically consider settings with uninformative node features. In this paper, we
provide a rigorous analysis to determine which function classes of node
features can be learned by an MPNN of a given capacity. We do so by measuring
the level of pairwise interactions between nodes that MPNNs allow for. This
measure provides a novel quantitative characterization of the so-called
over-squashing effect, which is observed to occur when a large volume of
messages is aggregated into fixed-size vectors. Using our measure, we prove
that, to guarantee sufficient communication between pairs of nodes, the
capacity of the MPNN must be large enough, depending on properties of the input
graph structure, such as commute times. For many relevant scenarios, our
analysis results in impossibility statements in practice, showing that
over-squashing hinders the expressive power of MPNNs. We validate our
theoretical findings through extensive controlled experiments and ablation
studies.

本文针对图结构数据上的机器学习所使用的最先进的模型 —— 图神经网络 (GNNs) 中的信息传递神经网络 (MPNNs) 类进行研究，分析了不同维度的节点特征在 MPNNs 中的表达能力，并通过新颖的量化特征来解释过压缩效应对 MPNNs 表达能力的影响。结果表明，对于大多数实际情况，MPNNs 的表现能力受到严重的限制。