How Powerful are Graph Neural Networks?
Keyulu Xu MIT、Weihua Hu Stanford University、Jure Leskovec Stanford University、Stefanie Jegelka MIT Equal contribution.Work partially performed while in Tokyo, visiting Prof. Ken-ichi Kawarabayashi.Work partially performed while at RIKEN AIP and University of Tokyo.
Abstract
Graph Neural Networks (GNNs) are an effective framework for representation learning of graphs. GNNs follow a neighborhood aggregation scheme, where the representation vector of a node is computed by recursively aggregating and transforming representation vectors of its neighboring nodes. Many GNN variants have been proposed and have achieved state-of-the-art results on both node and graph classification tasks. However, despite GNNs revolutionizing graph representation learning, there is limited understanding of their representational properties and limitations. Here, we present a theoretical framework for analyzing the expressive power of GNNs to capture different graph structures. Our results characterize the discriminative power of popular GNN variants, such as Graph Convolutional Networks and GraphSAGE, and show that they cannot learn to distinguish certain simple graph structures. We then develop a simple architecture that is provably the most expressive among the class of GNNs and is as powerful as the Weisfeiler-Lehman graph isomorphism test. We empirically validate our theoretical findings on a number of graph classification benchmarks, and demonstrate that our model achieve
中文速览
图神经网络（GNN）虽然在节点分类、图分类等任务上成绩亮眼，但学界对它"到底能区分哪些图结构、又在哪里失效"几乎没有严格的理论解释。这项工作把GNN的邻域聚合过程与经典的Weisfeiler-Lehman（WL）图同构测试联系起来，证明了任何基于聚合的GNN在区分图结构方面至多与WL测试等强，并给出了使GNN恰好达到这一上界的充要条件——聚合函数必须对"多重集"（multiset）保持单射性。基于此，作者设计了一种称为图同构网络（Graph Isomorphism Network，GIN）的简单架构，在理论上与WL测试等价，并在多个图分类基准上达到了当时最优性能，同时实验还揭示了GCN、GraphSAGE等流行变体因使用均值或最大值聚合而无法区分某些简单图结构的根本原因。这项工作首次为GNN的表达能力划定了清晰的理论边界，为设计更强大的图学习模型提供了坚实的理论基础。
原文 arXiv:1810.00826;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1810.00826v3