论文标题
在图形神经网络上与图形增强的MLP
On Graph Neural Networks versus Graph-Augmented MLPs
论文作者
论文摘要
从表达能力的角度来看，这项工作将多层图神经网络（GNN）与简化的替代方案进行了比较，我们称之为图形启动的多层求解器（GA-MLP），首先增强节点的特征，并在图上使用某些多跳动操作员，然后在Node-Wise-Wise-Wise Wise-Wise-Wise-Wise-Wise-Wise Wise-Wise-Wise-Wise中应用。从图形同构测试的角度来看，我们从理论和数字上表明具有合适算子的GA-MLP几乎可以区分所有非同构图，就像Weifeiler-Lehman（WL）测试一样。但是，通过将它们视为节点级函数并检查它们在根系上诱导的等效类，我们证明了GA-MLP和GNN之间的表达能力分离，可以深入成长。特别是与GNN不同，GA-MLP无法计算归因步行的数量。我们还通过社区检测实验证明，与具有更高灵活性的GNN相比，GA-MLP可以受其选择的操作员家族的选择限制。
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.
