HOW POWERFUL ARE GRAPH NEURAL NETWORKS? abstract。

Summary

GNN 作为一种有效的图表示学习框架近年来越来越受到人们的重视，通常来说，GNN 通过在相邻节点间迭代传播和聚合特征。许多 GNN 的变体也获得了 sota 结果，不论是在节点分类任务还是图分类任务中。

但是，尽管 GNNs 革命化地改变了图表示学习领域，但是对齐表示特征和局限性的理解仍然很有限。

因此，我们提出了一种理论框架，来分析 GNNs 学习不同图结构的能力。

主要的贡献如下：

  • 展示了 GNNs 在区分图结构方面极限性能是能够与 WL test 媲美的（GNNs are at most as powerful the WL test）
  • 测试并获得了 GNN 性能接近 WL test 时，GNN 在 邻居节点聚合 和 图读出 操作函数的条件
  • 发现流行的 GNN 变体，如 GCN/GraphSAGE 等，不能够区分简单的图结构，并且精确地总结了他们能够区分的图结构
  • 提出了一种简单的神经网络结构，图同构网络（Graph Isomorphism Network, GIN），并且测试表明图结构的分类和区别能力与 WL test 相同

Less Powerful But Still Interesting GNNs

  • 单层感知机无法很好地学习图结构，特别是在图分类任务，通常会欠拟合
  • Mean 和 Max-Pooling 不擅长学习的结构，如下图3所示
  • Mean 聚合器主要学习分布特征
  • Max-Pooling 主要学习代表特征或者缩略图特征，不适合用于区分具体结构和分布特征

structure