论文标题
关于图形神经网络在顶点之间建模相互作用的能力
On the Ability of Graph Neural Networks to Model Interactions Between Vertices
论文作者
论文摘要
图神经网络（GNN）广泛用于建模表示为图的顶点的实体之间的复杂相互作用。尽管最近为理论上分析了GNN的表达能力，但仍缺乏对其建模能力的形式表征。当前的论文旨在解决这一差距。通过称为分离等级的既定度量的相互作用的形式强度，我们量化了某些GNN在给定的顶点子集及其补体之间建模相互作用的能力及其补体，即在输入顶点的给定分区的两侧。我们的结果表明，建模相互作用的能力主要取决于分区的步行索引 - 一种图理论特征，该特征由源自分区边界的步道数量定义。使用常见GNN体系结构的实验证实了这一发现。作为我们理论的实际应用，我们设计了一种名为Walk索引稀疏（WIS）的边缘稀疏算法（WIS），该算法保留了GNN在删除输入边缘时建模相互作用的能力。 WIS是简单的，计算上有效的，在我们的实验中，就诱导的预测准确性而言，替代方法明显优于替代方法。更广泛地说，它通过理论上分析它们可以建模的相互作用来展示改善GNN的潜力。
Graph neural networks (GNNs) are widely used for modeling complex interactions between entities represented as vertices of a graph. Despite recent efforts to theoretically analyze the expressive power of GNNs, a formal characterization of their ability to model interactions is lacking. The current paper aims to address this gap. Formalizing strength of interactions through an established measure known as separation rank, we quantify the ability of certain GNNs to model interaction between a given subset of vertices and its complement, i.e. between the sides of a given partition of input vertices. Our results reveal that the ability to model interaction is primarily determined by the partition's walk index -- a graph-theoretical characteristic defined by the number of walks originating from the boundary of the partition. Experiments with common GNN architectures corroborate this finding. As a practical application of our theory, we design an edge sparsification algorithm named Walk Index Sparsification (WIS), which preserves the ability of a GNN to model interactions when input edges are removed. WIS is simple, computationally efficient, and in our experiments has markedly outperformed alternative methods in terms of induced prediction accuracy. More broadly, it showcases the potential of improving GNNs by theoretically analyzing the interactions they can model.
