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 achieves state-of-the-art performance.
核心贡献 · Key contributions
建立了通过 WL 测试分析 GNN 表达能力的理论框架。 Established theoretical framework analyzing GNN expressive power via WL test.
证明了 GNN 在区分图结构方面最多与 WL 测试能力相当。 Proved GNNs are at most as powerful as WL test in distinguishing graph structures.
刻画了 GCN 和 GraphSAGE 的区分能力，表明它们在简单结构上失效。 Characterized discriminative power of GCN and GraphSAGE, showing they fail on simple structures.
开发了图同构网络（GIN），在 GNN 中具有可证明的最大表达能力。 Developed Graph Isomorphism Network (GIN) with provably maximal expressive power among GNNs.
识别了匹配 WL 测试能力的单射聚合和读出条件。 Identified conditions for injective aggregation and readout to match WL test power.