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 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 that we define
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 markedly outperforms 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.

该研究通过分析分离秩、分界面上行走数等图论特征量化 GNNs 建模给定顶点子集及其补集之间交互的能力，设计了一种名为 Walk Index Sparsification (WIS) 的边稀疏化算法，用于保持 GNNs 模型在输入边被移除的情况下建模交互的能力。该算法在预测准确度上优于替代方法。

图神经网络对顶点间相互作用建模能力的研究

On the Ability of Graph Neural Networks to Model Interactions Between Vertices

Our formal understanding of the inductive bias that drives the success of
convolutional networks on computer vision tasks is limited. In particular, it
is unclear what makes hypotheses spaces born from convolution and pooling
operations so suitable for natural images. In this paper we study the ability
of convolutional networks to model correlations among regions of their input.
We theoretically analyze convolutional arithmetic circuits, and empirically
validate our findings on other types of convolutional networks as well.
Correlations are formalized through the notion of separation rank, which for a
given partition of the input, measures how far a function is from being
separable. We show that a polynomially sized deep network supports
exponentially high separation ranks for certain input partitions, while being
limited to polynomial separation ranks for others. The network's pooling
geometry effectively determines which input partitions are favored, thus serves
as a means for controlling the inductive bias. Contiguous pooling windows as
commonly employed in practice favor interleaved partitions over coarse ones,
orienting the inductive bias towards the statistics of natural images. Other
pooling schemes lead to different preferences, and this allows tailoring the
network to data that departs from the usual domain of natural imagery. In
addition to analyzing deep networks, we show that shallow ones support only
linear separation ranks, and by this gain insight into the benefit of functions
brought forth by depth - they are able to efficiently model strong correlation
under favored partitions of the input.

本文研究卷积网络对其输入区域之间相关性的建模能力，并通过理论分析和实证验证，证明深度网络的池化几何形状是控制感性偏差的一种手段，使其在输入不同类型的数据时可以适应不同的偏差方向。