From the perspective of expressive power, this work compares multi-layer
Graph Neural Networks (GNNs) with a simplified alternative that we call
Graph-Augmented Multi-Layer Perceptrons (GA-MLPs), which first augments node
features with certain multi-hop operators on the graph and then applies an MLP
in a node-wise fashion. From the perspective of graph isomorphism testing, we
show both theoretically and numerically that GA-MLPs with suitable operators
can distinguish almost all non-isomorphic graphs, just like the
Weifeiler-Lehman (WL) test. However, by viewing them as node-level functions
and examining the equivalence classes they induce on rooted graphs, we prove a
separation in expressive power between GA-MLPs and GNNs that grows
exponentially in depth. In particular, unlike GNNs, GA-MLPs are unable to count
the number of attributed walks. We also demonstrate via community detection
experiments that GA-MLPs can be limited by their choice of operator family, as
compared to GNNs with higher flexibility in learning.

本文比较了多层图神经网络和一种被称为图增强多层感知器的简化替代品之间的表现，其中后者首先通过图上的某些多跳算子增强节点特征，然后以节点方式应用 MLP；并证明了 GA-MLP 具备适当算子的情况下，能像 Weifeiler-Lehman（WL）测试一样，理论和数值上能够区分几乎所有非同构图，但是 GA-MLP 与 GNN 之间在表达能力方面的差距随着深度呈指数增长，并且 GA-MLP 不能计算属性步行的数量，表明 GA-MLP 受其操作符族的选择限制比拥有更高学习灵活性的 GNN 更为受限，这在社区检测实验中也得到了证明。