On Graph Neural Networks versus Graph-Augmented MLPs
On Graph Neural Networks versus Graph-Augmented MLPs
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Lei Chen;Zhengdao Chen;Joan Bruna
中科院分区：
文献类型：
--
作者：
Lei Chen;Zhengdao Chen;Joan Bruna
从表达能力的角度来看，这项工作将多层图神经网络（GNN）与我们称为图增强多层感知器（GA-MLP）的简化替代方案进行了比较，后者首先使用图上的某些多跳运算符来增强节点特征，然后以节点方式应用 MLP。从图同构测试的角度来看，我们从理论上和数值上表明，具有合适算子的 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.