How Powerful are Graph Neural Networks?

图神经网络究竟有多强？

Keyulu Xu Thanks:  Equal contribution. Thanks:  Work partially performed while in Tokyo, visiting Prof. Ken-ichi Kawarabayashi. Affiliation:  MIT Email:  keyulu@mit.edu    Weihua Hu 1 1 footnotemark: 1 Thanks:  Work partially performed while at RIKEN AIP and University of Tokyo. Affiliation:  Stanford University Email:  weihuahu@stanford.edu    Jure Leskovec Affiliation:  Stanford University Email:  jure@cs.stanford.edu    Stefanie Jegelka Affiliation:  MIT Email:  stefje@mit.edu

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 achieves state-of-the-art performance.

图神经网络（GNN）是图表示学习的有效框架。GNN 采用邻域聚合：节点表示向量通过递归聚合并变换其邻居的表示得到。已有许多 GNN 变体在节点与图分类上达到当时最优。尽管 GNN 深刻改变了图表示学习，对其表示性质与局限的理解仍有限。本文提出理论框架，分析 GNN 捕捉不同图结构的表达能力。结果刻画了图卷积网络、GraphSAGE 等流行变体的判别力，并表明它们无法学会区分某些简单图结构。随后我们给出一种简单结构，可证明在 GNN 类中表达能力最强，并与 Weisfeiler-Lehman 图同构检验同等有力。我们在多个图分类基准上验证理论，并展示该模型达到当时最优表现。

1 Introduction

1 引言

Learning with graph structured data, such as molecules, social, biological, and financial networks, requires effective representation of their graph structure (Hamilton et al. 2017b). Recently, there has been a surge of interest in Graph Neural Network (GNN) approaches for representation learning of graphs (Li et al. 2016; Hamilton et al. 2017a; Kipf & Welling 2017; Velickovic et al. 2018; Xu et al. 2018). GNNs broadly follow a recursive neighborhood aggregation (or message passing) scheme, where each node aggregates feature vectors of its neighbors to compute its new feature vector (Xu et al. 2018; Gilmer et al. 2017). After $k$ iterations of aggregation, a node is represented by its transformed feature vector, which captures the structural information within the node’s $k$-hop neighborhood. The representation of an entire graph can then be obtained through pooling (Ying et al. 2018), for example, by summing the representation vectors of all nodes in the graph.

在分子、社交、生物与金融网络等图结构数据上学习，需要有效表示其图结构（Hamilton et al. 2017b）。近年图神经网络（GNN）表示学习迅速升温（Li et al. 2016；Hamilton et al. 2017a；Kipf & Welling 2017；Velickovic et al. 2018；Xu et al. 2018）。GNN 大体遵循递归邻域聚合（或消息传递）：每个节点聚合邻居特征向量以计算新特征（Xu et al. 2018；Gilmer et al. 2017）。聚合 $k$ 轮后，节点由其变换后的特征向量表示，刻画其 $k$ 跳邻域内的结构信息。整图表示可通过池化得到（Ying et al. 2018），例如对所有节点表示求和。

Many GNN variants with different neighborhood aggregation and graph-level pooling schemes have been proposed (Scarselli et al. 2009b; Battaglia et al. 2016; Defferrard et al. 2016; Duvenaud et al. 2015; Hamilton et al. 2017a; Kearnes et al. 2016; Kipf & Welling 2017; Li et al. 2016; Velickovic et al. 2018; Santoro et al. 2017; Xu et al. 2018; Santoro et al. 2018; Verma & Zhang 2018; Ying et al. 2018; Zhang et al. 2018). Empirically, these GNNs have achieved state-of-the-art performance in many tasks such as node classification, link prediction, and graph classification. However, the design of new GNNs is mostly based on empirical intuition, heuristics, and experimental trial-and-error. There is little theoretical understanding of the properties and limitations of GNNs, and formal analysis of GNNs’ representational capacity is limited.

已有大量带不同邻域聚合与图级池化方案的 GNN 变体（Scarselli et al. 2009b；Battaglia et al. 2016；Defferrard et al. 2016；Duvenaud et al. 2015；Hamilton et al. 2017a；Kearnes et al. 2016；Kipf & Welling 2017；Li et al. 2016；Velickovic et al. 2018；Santoro et al. 2017；Xu et al. 2018；Santoro et al. 2018；Verma & Zhang 2018；Ying et al. 2018；Zhang et al. 2018）。经验上它们在节点分类、链接预测与图分类等任务上表现优异。但新 GNN 的设计多靠直觉、启发式与试错，对其性质与局限的理论理解很少，对表示能力的形式分析也有限。

Here, we present a theoretical framework for analyzing the representational power of GNNs. We formally characterize how expressive different GNN variants are in learning to represent and distinguish between different graph structures. Our framework is inspired by the close connection between GNNs and the Weisfeiler-Lehman (WL) graph isomorphism test (Weisfeiler & Lehman 1968), a powerful test known to distinguish a broad class of graphs (Babai & Kucera 1979). Similar to GNNs, the WL test iteratively updates a given node’s feature vector by aggregating feature vectors of its network neighbors. What makes the WL test so powerful is its injective aggregation update that maps different node neighborhoods to different feature vectors. Our key insight is that a GNN can have as large discriminative power as the WL test if the GNN’s aggregation scheme is highly expressive and can model injective functions.

本文提出分析 GNN 表示能力的理论框架，形式刻画不同变体在学习表示并区分图结构上的表达力。框架受 GNN 与 Weisfeiler-Lehman（WL）图同构检验（Weisfeiler & Lehman 1968）密切联系启发——该检验能区分一大类图（Babai & Kucera 1979）。与 GNN 类似，WL 通过聚合网络邻居的特征向量迭代更新节点特征；其强大之处在于注入式聚合更新，把不同节点邻域映到不同特征向量。关键洞见是：若 GNN 的聚合方案足够富有表达力、能建模注入函数，则其判别力可与 WL 检验相当。

To mathematically formalize the above insight, our framework first represents the set of feature vectors of a given node’s neighbors as a multiset, i.e., a set with possibly repeating elements. Then, the neighbor aggregation in GNNs can be thought of as an aggregation function over the multiset. Hence, to have strong representational power, a GNN must be able to aggregate different multisets into different representations. We rigorously study several variants of multiset functions and theoretically characterize their discriminative power, i.e., how well different aggregation functions can distinguish different multisets. The more discriminative the multiset function is, the more powerful the representational power of the underlying GNN.

为把上述洞见数学化，框架先把某节点邻居的特征向量集合视为多重集（可有重复元素的集合）。于是 GNN 的邻居聚合可看作多重集上的聚合函数。要有强表示能力，GNN 必须能把不同多重集聚合成不同表示。我们严格研究若干多重集函数变体，理论刻画其判别力，即不同聚合函数区分不同多重集的能力。多重集函数越具判别力，底层 GNN 的表示能力越强。

Our main results are summarized as follows:

主要结果概括如下：

• 1. We show that GNNs are at most as powerful as the WL test in distinguishing graph structures.

• 1. 我们证明：在区分图结构上，GNN 至多与 WL 检验同样有力。

• 2. We establish conditions on the neighbor aggregation and graph readout functions under which the resulting GNN is as powerful as the WL test.

• 2. 我们给出邻居聚合与图读出函数的条件，使所得 GNN 与 WL 检验同等有力。

• 3. We identify graph structures that cannot be distinguished by popular GNN variants, such as GCN (Kipf & Welling 2017) and GraphSAGE (Hamilton et al. 2017a), and we precisely characterize the kinds of graph structures such GNN-based models can capture.

• 3. 我们指出 GCN（Kipf & Welling 2017）、GraphSAGE（Hamilton et al. 2017a）等流行变体无法区分的图结构，并精确刻画这类 GNN 能捕捉的结构种类。

• 4. We develop a simple neural architecture, Graph Isomorphism Network (GIN), and show that its discriminative/representational power is equal to the power of the WL test.

• 4. 我们提出简单结构 图同构网络（GIN），并证明其判别/表示能力与 WL 检验相等。

We validate our theory via experiments on graph classification datasets, where the expressive power of GNNs is crucial to capture graph structures. In particular, we compare the performance of GNNs with various aggregation functions. Our results confirm that the most powerful GNN by our theory, i.e., Graph Isomorphism Network (GIN), also empirically has high representational power as it almost perfectly fits the training data, whereas the less powerful GNN variants often severely underfit the training data. In addition, the representationally more powerful GNNs outperform the others by test set accuracy and achieve state-of-the-art performance on many graph classification benchmarks.

我们在图分类数据集上验证理论——此处 GNN 的表达力对捕捉图结构至关重要。特别地，比较不同聚合函数的 GNN：结果确认按理论最强的图同构网络（GIN）经验上也有高表示能力，几乎完美拟合训练数据；较弱变体则常严重欠拟合。此外，表示更强的 GNN 在测试准确率上优于其他，并在多个图分类基准上达到当时最优。

2 Preliminaries

2 预备知识

We begin by summarizing some of the most common GNN models and, along the way, introduce our notation. Let $G=\left(V,E\right)$ denote a graph with node feature vectors $X_{v}$ for $v\in V$. There are two tasks of interest: (1) Node classification, where each node $v\in V$ has an associated label $y_{v}$ and the goal is to learn a representation vector $h_{v}$ of $v$ such that $v$’s label can be predicted as $y_{v}=f(h_{v})$; (2) Graph classification, where, given a set of graphs $\{G_{1},...,G_{N}\}\subseteq\mathcal{G}$ and their labels $\{y_{1},...,y_{N}\}\subseteq\mathcal{Y}$, we aim to learn a representation vector $h_{G}$ that helps predict the label of an entire graph, $y_{G}=g(h_{G})$.

先概括若干常见 GNN 模型并引入记号。设 $G=\left(V,E\right)$ 为图，节点特征为 $X_{v}$（$v\in V$）。关注两类任务：(1) 节点分类：每个 $v\in V$ 有标签 $y_{v}$，目标是学习表示 $h_{v}$ 使 $y_{v}=f(h_{v})$；(2) 图分类：给定图集 $\{G_{1},...,G_{N}\}\subseteq\mathcal{G}$ 与标签 $\{y_{1},...,y_{N}\}\subseteq\mathcal{Y}$，学习整图表示 $h_{G}$，使 $y_{G}=g(h_{G})$。

Graph Neural Networks. GNNs use the graph structure and node features $X_{v}$ to learn a representation vector of a node, $h_{v}$, or the entire graph, $h_{G}$. Modern GNNs follow a neighborhood aggregation strategy, where we iteratively update the representation of a node by aggregating representations of its neighbors. After $k$ iterations of aggregation, a node’s representation captures the structural information within its $k$-hop network neighborhood. Formally, the $k$-th layer of a GNN is

图神经网络。 GNN 利用图结构与节点特征 $X_{v}$ 学习节点表示 $h_{v}$ 或整图表示 $h_{G}$。现代 GNN 采用邻域聚合：迭代地通过聚合邻居表示来更新节点表示。$k$ 轮后，节点表示捕捉其 $k$ 跳邻域的结构信息。形式上，GNN 第 $k$ 层为

$$\displaystyle a_{v}^{(k)} \\ \displaystyle=\text{AGGREGATE}^{(k)}\left(\left\{h_{u}^{(k-1)}:u\in\mathcal{N}(v)\right\}\right),\quad h_{v}^{(k)}=\text{COMBINE}^{(k)}\left(h_{v}^{(k-1)},a_{v}^{(k)}\right), \tag{2.1}$$

where $h_{v}^{(k)}$ is the feature vector of node $v$ at the $k$-th iteration/layer. We initialize $h_{v}^{(0)}=X_{v}$, and $\mathcal{N}(v)$ is a set of nodes adjacent to $v$. The choice of AGGREGATE${}^{(k)}(\cdot)$ and COMBINE${}^{(k)}(\cdot)$ in GNNs is crucial. A number of architectures for AGGREGATE have been proposed. In the pooling variant of GraphSAGE (Hamilton et al. 2017a), AGGREGATE has been formulated as

其中 $h_{v}^{(k)}$ 为第 $k$ 轮/层节点 $v$ 的特征向量。初始化 $h_{v}^{(0)}=X_{v}$，$\mathcal{N}(v)$ 为 $v$ 的邻接节点集。AGGREGATE${}^{(k)}(\cdot)$ 与 COMBINE${}^{(k)}(\cdot)$ 的选择至关重要。已有多种 AGGREGATE 结构；在 GraphSAGE 的池化变体（Hamilton et al. 2017a）中，AGGREGATE 写为

$$\displaystyle a_{v}^{(k)}={\rm MAX}\left(\left\{{\rm ReLU}\left(W\cdot h_{u}^{(k-1)}\right),\ \forall u\in\mathcal{N}(v)\right\}\right), \tag{2.2}$$

where $W$ is a learnable matrix, and MAX represents an element-wise max-pooling. The COMBINE step could be a concatenation followed by a linear mapping $W\cdot\left[h_{v}^{(k-1)},a_{v}^{(k)}\right]$ as in GraphSAGE. In Graph Convolutional Networks (GCN) (Kipf & Welling 2017), the element-wise mean pooling is used instead, and the AGGREGATE and COMBINE steps are integrated as follows:

其中 $W$ 可学习，MAX 为逐元素最大池化。COMBINE 可以是拼接后再线性映射 $W\cdot\left[h_{v}^{(k-1)},a_{v}^{(k)}\right]$，如 GraphSAGE。图卷积网络（GCN，Kipf & Welling 2017）改用逐元素均值池化，并把 AGGREGATE 与 COMBINE 合写为：

$$\displaystyle h_{v}^{(k)}={\rm ReLU}\left(W\cdot{\rm MEAN}\left\{h_{u}^{(k-1)},\ \forall u\in\mathcal{N}(v)\cup\{v\}\right\}\right). \tag{2.3}$$

Many other GNNs can be represented similarly to Eq. 2.1 (Xu et al. 2018; Gilmer et al. 2017).

许多其他 GNN 也可类似写成式 2.1（Xu et al. 2018；Gilmer et al. 2017）。

For node classification, the node representation $h_{v}^{(K)}$ of the final iteration is used for prediction. For graph classification, the READOUT function aggregates node features from the final iteration to obtain the entire graph’s representation $h_{G}$:

节点分类使用最后一轮的节点表示 $h_{v}^{(K)}$ 做预测。图分类则用 READOUT 聚合最后一轮节点特征，得到整图表示 $h_{G}$：

$$\displaystyle h_{G}={\rm READOUT}\big(\big\{h_{v}^{(K)}\ \big|\ v\in G\big\}\big). \tag{2.4}$$

READOUT can be a simple permutation invariant function such as summation or a more sophisticated graph-level pooling function (Ying et al. 2018; Zhang et al. 2018).

READOUT 可以是求和等简单置换不变函数，或更复杂的图级池化（Ying et al. 2018；Zhang et al. 2018）。

Weisfeiler-Lehman test. The graph isomorphism problem asks whether two graphs are topologically identical. This is a challenging problem: no polynomial-time algorithm is known for it yet (Garey 1979; Garey & Johnson 2002; Babai 2016). Apart from some corner cases (Cai et al. 1992), the Weisfeiler-Lehman (WL) test of graph isomorphism (Weisfeiler & Lehman 1968) is an effective and computationally efficient test that distinguishes a broad class of graphs (Babai & Kucera 1979). Its 1-dimensional form, “naïve vertex refinement”, is analogous to neighbor aggregation in GNNs. The WL test iteratively (1) aggregates the labels of nodes and their neighborhoods, and (2) hashes the aggregated labels into unique new labels. The algorithm decides that two graphs are non-isomorphic if at some iteration the labels of the nodes between the two graphs differ.

Weisfeiler-Lehman 检验。 图同构问题问两图在拓扑上是否相同，颇具挑战：尚无已知的多项式时间算法（Garey 1979；Garey & Johnson 2002；Babai 2016）。除若干边例外（Cai et al. 1992），Weisfeiler-Lehman（WL）图同构检验（Weisfeiler & Lehman 1968）能高效区分一大类图（Babai & Kucera 1979）。其一维形式“朴素顶点细化”类似于 GNN 的邻居聚合：WL 迭代地 (1) 聚合节点及其邻域的标签，(2) 把聚合标签散列成唯一新标签；若某轮两图节点标签集合不同，则判定非同构。

Based on the WL test, Shervashidze et al. 2011 proposed the WL subtree kernel that measures the similarity between graphs. The kernel uses the counts of node labels at different iterations of the WL test as the feature vector of a graph. Intuitively, a node’s label at the $k$-th iteration of WL test represents a subtree structure of height $k$ rooted at the node (Figure 1). Thus, the graph features considered by the WL subtree kernel are essentially counts of different rooted subtrees in the graph.

基于 WL，Shervashidze et al. 2011 提出 WL 子树核度量图相似度：以 WL 各轮节点标签计数作为图特征向量。直观上，第 $k$ 轮节点标签表示以该节点为根、高度为 $k$ 的子树结构（图 1）。因而 WL 子树核考虑的图特征本质上是图中不同有根子树的计数。

3 Theoretical framework: overview

3 理论框架概览

Figure 1: An overview of our theoretical framework. Middle panel: rooted subtree structures (at the blue node) that the WL test uses to distinguish different graphs. Right panel: if a GNN’s aggregation function captures the full multiset of node neighbors, the GNN can capture the rooted subtrees in a recursive manner and be as powerful as the WL test.

图 1：理论框架概览。 中图：WL 检验用来区分不同图的有根子树结构（蓝色节点处）。右图：若 GNN 的聚合函数能捕捉邻居节点的完整多重集，则可递归捕捉有根子树，并与 WL 检验同等有力。

We start with an overview of our framework for analyzing the expressive power of GNNs. Figure 1 illustrates our idea. A GNN recursively updates each node’s feature vector to capture the network structure and features of other nodes around it, i.e., its rooted subtree structures (Figure 1). Throughout the paper, we assume node input features are from a countable universe. For finite graphs, node feature vectors at deeper layers of any fixed model are also from a countable universe. For notational simplicity, we can assign each feature vector a unique label in $\{a,b,c\ldots\}$. Then, feature vectors of a set of neighboring nodes form a multiset (Figure 1): the same element can appear multiple times since different nodes can have identical feature vectors.

先概述分析 GNN 表达能力的框架。图 1 示意我们的想法：GNN 递归更新每个节点的特征向量，以捕捉其周围网络结构与其他节点特征，即有根子树结构（图 1）。全文假设节点输入特征来自可数全域；对有限图，任意固定模型更深一层的节点特征也来自可数全域。为记号简便，可为每个特征向量在 $\{a,b,c\ldots\}$ 中赋唯一标签。于是一组邻居节点的特征向量构成多重集（图 1）：同一元素可多次出现，因为不同节点可有相同特征。

Definition 1(Multiset).

A multiset is a generalized concept of a set that allows multiple instances for its elements. More formally, a multiset is a 2-tuple $X=(S,m)$ where $S$ is the underlying set of $X$ that is formed from its distinct elements, and $m:S\rightarrow\mathbb{N}_{\geq 1}$ gives the multiplicity of the elements.

定义 1（多重集）。

多重集是允许元素重复出现的集合推广。形式地，多重集是二元组 $X=(S,m)$，其中 $S$ 是由不同元素构成的底层集合，$m:S\rightarrow\mathbb{N}_{\geq 1}$ 给出元素的重数。

To study the representational power of a GNN, we analyze when a GNN maps two nodes to the same location in the embedding space. Intuitively, a maximally powerful GNN maps two nodes to the same location only if they have identical subtree structures with identical features on the corresponding nodes. Since subtree structures are defined recursively via node neighborhoods (Figure 1), we can reduce our analysis to the question whether a GNN maps two neighborhoods (i.e., two multisets) to the same embedding or representation. A maximally powerful GNN would never map two different neighborhoods, i.e., multisets of feature vectors, to the same representation. This means its aggregation scheme must be injective. Thus, we abstract a GNN’s aggregation scheme as a class of functions over multisets that their neural networks can represent, and analyze whether they are able to represent injective multiset functions.

为研究 GNN 的表示能力，我们分析何时两个节点被映到嵌入空间同一位置。直观上，最强 GNN 仅当两节点具有相同子树结构且对应节点特征相同时，才映到同一位置。由于子树结构经由节点邻域递归定义（图 1），分析可归结为：GNN 是否把两个邻域（即两个多重集）映到同一嵌入。最强 GNN 绝不会把两个不同邻域（特征向量多重集）映到同一表示，因而其聚合方案必须注入。于是我们把 GNN 聚合抽象为神经网络可表示的一类多重集函数，并分析它们能否表示注入的多重集函数。

Next, we use this reasoning to develop a maximally powerful GNN. In Section 5, we study popular GNN variants and see that their aggregation schemes are inherently not injective and thus less powerful, but that they can capture other interesting properties of graphs.

接下来据此构造最强 GNN。第 5 节研究流行变体，会看到其聚合本质不注入因而更弱，但仍能捕捉图的其他有趣性质。

4 Building powerful graph neural networks

4 构建强有力的图神经网络

First, we characterize the maximum representational capacity of a general class of GNN-based models. Ideally, a maximally powerful GNN could distinguish different graph structures by mapping them to different representations in the embedding space. This ability to map any two different graphs to different embeddings, however, implies solving the challenging graph isomorphism problem. That is, we want isomorphic graphs to be mapped to the same representation and non-isomorphic ones to different representations. In our analysis, we characterize the representational capacity of GNNs via a slightly weaker criterion: a powerful heuristic called Weisfeiler-Lehman (WL) graph isomorphism test, that is known to work well in general, with a few exceptions, e.g., regular graphs (Cai et al. 1992; Douglas 2011; Evdokimov & Ponomarenko 1999).

首先刻画一类通用 GNN 模型的最大表示能力。理想情况下，最强 GNN 应能把不同图结构映到嵌入空间中的不同表示。但“任意两不同图映到不同嵌入”意味着解决困难的图同构问题：同构图应同表示，非同构图应不同表示。分析中我们用稍弱、但通常很管用的启发式——Weisfeiler-Lehman（WL）图同构检验——来刻画表示能力；该检验总体表现好，但对正则图等有例外（Cai et al. 1992；Douglas 2011；Evdokimov & Ponomarenko 1999）。

Lemma 2.

Let $G_{1}$ and $G_{2}$ be any two non-isomorphic graphs. If a graph neural network $\mathcal{A}:\mathcal{G}\rightarrow\mathbb{R}^{d}$ maps $G_{1}$ and $G_{2}$ to different embeddings, the Weisfeiler-Lehman graph isomorphism test also decides $G_{1}$ and $G_{2}$ are not isomorphic.

引理 2。

设 $G_{1}$、$G_{2}$ 为任意两非同构图。若图神经网络 $\mathcal{A}:\mathcal{G}\rightarrow\mathbb{R}^{d}$ 把 $G_{1}$、$G_{2}$ 映到不同嵌入，则 Weisfeiler-Lehman 图同构检验也会判定二者非同构。

Proofs of all Lemmas and Theorems can be found in the Appendix. Hence, any aggregation-based GNN is at most as powerful as the WL test in distinguishing different graphs. A natural follow-up question is whether there exist GNNs that are, in principle, as powerful as the WL test? Our answer, in Theorem 3, is yes: if the neighbor aggregation and graph-level readout functions are injective, then the resulting GNN is as powerful as the WL test.

全部引理与定理的证明见附录。因此，任何基于聚合的 GNN 在区分不同图上至多与 WL 检验同等有力。自然的后续问题是：是否存在原则上与 WL 同等有力的 GNN？定理 3 给出肯定答案：若邻居聚合与图级读出函数均为注入，则所得 GNN 与 WL 检验同等有力。

Theorem 3.

Let $\mathcal{A}:\mathcal{G}\rightarrow\mathbb{R}^{d}$ be a GNN. With a sufficient number of GNN layers, $\mathcal{A}$ maps any graphs $G_{1}$ and $G_{2}$ that the Weisfeiler-Lehman test of isomorphism decides as non-isomorphic, to different embeddings if the following conditions hold:

定理 3。

设 $\mathcal{A}:\mathcal{G}\rightarrow\mathbb{R}^{d}$ 为 GNN。在层数足够时，$\mathcal{A}$ 把 Weisfeiler-Lehman 同构检验判定为非同构的任意图 $G_{1}$、$G_{2}$ 映到不同嵌入，若满足：

• a) $\mathcal{A}$aggregates and updates node features iteratively with $$h_{v}^{(k)}=\phi\left(h_{v}^{(k-1)},f\left(\left\{h_{u}^{(k-1)}:u\in\mathcal{N}(v)\right\}\right)\right),$$ where the functions$f$, which operates on multisets, and$\phi$are injective.

• a) $\mathcal{A}$按 $$h_{v}^{(k)}=\phi\left(h_{v}^{(k-1)},f\left(\left\{h_{u}^{(k-1)}:u\in\mathcal{N}(v)\right\}\right)\right),$$ 迭代聚合并更新节点特征，其中作用在多重集上的$f$以及$\phi$均为注入。

• b) $\mathcal{A}$’s graph-level readout, which operates on the multiset of node features$\left\{h_{v}^{(k)}\right\}$, is injective.

• b) $\mathcal{A}$的图级读出作用在节点特征多重集$\left\{h_{v}^{(k)}\right\}$上，且为注入。

We prove Theorem 3 in the appendix. For countable sets, injectiveness well characterizes whether a function preserves the distinctness of inputs. Uncountable sets, where node features are continuous, need some further considerations. In addition, it would be interesting to characterize how close together the learned features lie in a function’s image. We leave these questions for future work, and focus on the case where input node features are from a countable set (that can be a subset of an uncountable set such as $\mathbb{R}^{n}$).

定理 3 的证明见附录。对可数集，注入性很好刻画函数是否保持输入的可区分性。特征连续的不可数集还需额外考虑；此外，刻画学到的特征在像中有多“挤”也很有趣。这些问题留待未来，本文聚焦输入节点特征来自可数集（可为 $\mathbb{R}^{n}$ 等不可数集的子集）的情形。

Lemma 4.

Assume the input feature space $\mathcal{X}$ is countable. Let $g^{(k)}$ be the function parameterized by a GNN’s $k$-th layer for $k=1,...,L$, where $g^{(1)}$ is defined on multisets $X\subset\mathcal{X}$ of bounded size. The range of $g^{(k)}$, i.e., the space of node hidden features $h_{v}^{(k)}$, is also countable for all $k=1,...,L$.

引理 4。

假设输入特征空间 $\mathcal{X}$ 可数。设 $g^{(k)}$ 为 GNN 第 $k$ 层所参数化的函数（$k=1,...,L$），其中 $g^{(1)}$ 定义在有界大小的多重集 $X\subset\mathcal{X}$ 上。则对所有 $k=1,...,L$，$g^{(k)}$ 的值域（即节点隐特征 $h_{v}^{(k)}$ 的空间）也可数。

Here, it is also worth discussing an important benefit of GNNs beyond distinguishing different graphs, that is, capturing similarity of graph structures. Note that node feature vectors in the WL test are essentially one-hot encodings and thus cannot capture the similarity between subtrees. In contrast, a GNN satisfying the criteria in Theorem 3 generalizes the WL test by learning to embed the subtrees to low-dimensional space. This enables GNNs to not only discriminate different structures, but also to learn to map similar graph structures to similar embeddings and capture dependencies between graph structures. Capturing structural similarity of the node labels is shown to be helpful for generalization particularly when the co-occurrence of subtrees is sparse across different graphs or there are noisy edges and node features (Yanardag & Vishwanathan 2015).

这里也值得讨论 GNN 相对“仅区分不同图”的另一重要收益：捕捉图结构相似度。WL 检验中的节点特征本质上是 one-hot，无法刻画子树相似度。满足定理 3 条件的 GNN 则通过学习把子树嵌入低维空间来推广 WL：既能判别不同结构，也能把相似图结构映到相近嵌入并捕捉结构依赖。当不同图上子树共现稀疏，或边与节点特征有噪声时，捕捉节点标签的结构相似度有助于泛化（Yanardag & Vishwanathan 2015）。

4.1 Graph Isomorphism Network (GIN)

4.1 图同构网络（GIN）

Having developed conditions for a maximally powerful GNN, we next develop a simple architecture, Graph Isomorphism Network (GIN), that provably satisfies the conditions in Theorem 3. This model generalizes the WL test and hence achieves maximum discriminative power among GNNs.

在给出最强 GNN 的条件后，我们构造简单结构 图同构网络（GIN），可证明满足定理 3。该模型推广 WL 检验，从而在 GNN 中达到最大判别力。

To model injective multiset functions for the neighbor aggregation, we develop a theory of “deep multisets”, i.e., parameterizing universal multiset functions with neural networks. Our next lemma states that sum aggregators can represent injective, in fact, universal functions over multisets.

为给邻居聚合建模注入多重集函数，我们发展“深度多重集”理论，即用神经网络参数化通用多重集函数。下一条引理指出：求和聚合器可以表示注入的——事实上是通用的——多重集函数。

Lemma 5.

Assume $\mathcal{X}$ is countable. There exists a function $f:\mathcal{X}\rightarrow\mathbb{R}^{n}$ so that $h(X)=\sum_{x\in X}f(x)$ is unique for each multiset $X\subset\mathcal{X}$ of bounded size. Moreover, any multiset function $g$ can be decomposed as $g\left(X\right)=\phi\left(\sum_{x\in X}f(x)\right)$ for some function $\phi$.

引理 5。

假设 $\mathcal{X}$ 可数。存在函数 $f:\mathcal{X}\rightarrow\mathbb{R}^{n}$，使 $h(X)=\sum_{x\in X}f(x)$ 对有界大小的每个多重集 $X\subset\mathcal{X}$ 都唯一。并且，任意多重集函数 $g$ 可分解为 $g\left(X\right)=\phi\left(\sum_{x\in X}f(x)\right)$（对某个 $\phi$）。

We prove Lemma 5 in the appendix. The proof extends the setting in (Zaheer et al. 2017) from sets to multisets. An important distinction between deep multisets and sets is that certain popular injective set functions, such as the mean aggregator, are not injective multiset functions. With the mechanism for modeling universal multiset functions in Lemma 5 as a building block, we can conceive aggregation schemes that can represent universal functions over a node and the multiset of its neighbors, and thus will satisfy the injectiveness condition (a) in Theorem 3. Our next corollary provides a simple and concrete formulation among many such aggregation schemes.

引理 5 证明见附录；证明把 Zaheer et al. 2017 的集合设定扩展到多重集。深度多重集与集合的重要区别是：某些流行的注入集合函数（如均值聚合）并不是注入的多重集函数。以引理 5 的通用多重集机制为构件，可设想能表示“节点及其邻居多重集”上通用函数的聚合方案，从而满足定理 3 的注入条件 (a)。下一条推论给出众多此类方案中一个简单具体的形式。

Corollary 6.

Assume $\mathcal{X}$ is countable. There exists a function $f:\mathcal{X}\rightarrow\mathbb{R}^{n}$ so that for infinitely many choices of $\epsilon$, including all irrational numbers, $h(c,X)=(1+\epsilon)\cdot f(c)+\sum_{x\in X}f(x)$ is unique for each pair $(c,X)$, where $c\in\mathcal{X}$ and $X\subset\mathcal{X}$ is a multiset of bounded size. Moreover, any function $g$ over such pairs can be decomposed as $g\left(c,X\right)=\varphi\left(\left(1+\epsilon\right)\cdot f(c)+\sum_{x\in X}f(x)\right)$ for some function $\varphi$.

推论 6。

假设 $\mathcal{X}$ 可数。存在函数 $f:\mathcal{X}\rightarrow\mathbb{R}^{n}$，使得对无穷多 $\epsilon$（包括全部无理数），$h(c,X)=(1+\epsilon)\cdot f(c)+\sum_{x\in X}f(x)$ 对每个对 $(c,X)$ 唯一，其中 $c\in\mathcal{X}$，$X\subset\mathcal{X}$ 为有界大小多重集。并且，任意定义在此类对上的函数 $g$ 可分解为 $g\left(c,X\right)=\varphi\left(\left(1+\epsilon\right)\cdot f(c)+\sum_{x\in X}f(x)\right)$（对某个 $\varphi$）。

We can use multi-layer perceptrons (MLPs) to model and learn $f$ and $\varphi$ in Corollary 6, thanks to the universal approximation theorem (Hornik et al. 1989; Hornik 1991). In practice, we model $f^{(k+1)}\circ\varphi^{(k)}$ with one MLP, because MLPs can represent the composition of functions. In the first iteration, we do not need MLPs before summation if input features are one-hot encodings as their summation alone is injective. We can make $\epsilon$ a learnable parameter or a fixed scalar. Then, GIN updates node representations as

由通用逼近定理（Hornik et al. 1989；Hornik 1991），可用多层感知机（MLP）建模并学习推论 6 中的 $f$ 与 $\varphi$。实践中用一个 MLP 建模 $f^{(k+1)}\circ\varphi^{(k)}$，因为 MLP 能表示函数复合。第一轮若输入特征为 one-hot，求和本身已注入，求和前不必再接 MLP。$\epsilon$ 可设为可学习参数或固定标量。于是 GIN 更新节点表示为

$$\displaystyle h_{v}^{(k)}={\rm MLP}^{(k)}\left(\left(1+\epsilon^{(k)}\right)\cdot h_{v}^{(k-1)}+\sum\nolimits_{u\in\mathcal{N}(v)}h_{u}^{(k-1)}\right). \tag{4.1}$$

Generally, there may exist many other powerful GNNs. GIN is one such example among many maximally powerful GNNs, while being simple.

一般而言可能存在许多其他强 GNN；GIN 是其中满足最强条件且形式简单的一例。

4.2 Graph-level readout of GIN

4.2 GIN 的图级读出

Node embeddings learned by GIN can be directly used for tasks like node classification and link prediction. For graph classification tasks we propose the following “readout” function that, given embeddings of individual nodes, produces the embedding of the entire graph.

GIN 学到的节点嵌入可直接用于节点分类、链接预测等。对图分类，我们提出如下“读出”：由各节点嵌入得到整图嵌入。

An important aspect of the graph-level readout is that node representations, corresponding to subtree structures, get more refined and global as the number of iterations increases. A sufficient number of iterations is key to achieving good discriminative power. Yet, features from earlier iterations may sometimes generalize better. To consider all structural information, we use information from all depths/iterations of the model. We achieve this by an architecture similar to Jumping Knowledge Networks (Xu et al. 2018), where we replace Eq. 2.4 with graph representations concatenated across all iterations/layers of GIN:

图级读出的要点是：对应子树结构的节点表示随迭代加深而更精细、更全局。足够轮数是获得良好判别力的关键；但较早轮次的特征有时泛化更好。为纳入全部结构信息，我们使用模型所有深度/轮次的信息，采用类似 Jumping Knowledge Networks（Xu et al. 2018）的结构，把式 2.4 换成跨 GIN 所有轮次/层 拼接的图表示：

$$\displaystyle h_{G}={\rm CONCAT}\Big({\rm READOUT}\Big(\left\{h_{v}^{(k)}|v\in G\right\}\Big)\ \big|\ k=0,1,\ldots,K\Big). \tag{4.2}$$

By Theorem 3 and Corollary 6, if GIN replaces READOUT in Eq. 4.2 with summing all node features from the same iterations (we do not need an extra MLP before summation for the same reason as in Eq. 4.1), it provably generalizes the WL test and the WL subtree kernel.

由定理 3 与推论 6，若把式 4.2 中的 READOUT 换成对同一轮所有节点特征求和（与式 4.1 同理，求和前不必再加 MLP），则 GIN 可证明推广了 WL 检验与 WL 子树核。

5 Less powerful but still interesting GNNs

5 较弱但仍有意思的 GNN

Figure 2: Ranking by expressive power for sum, mean and max aggregators over a multiset. Left panel shows the input multiset, i.e., the network neighborhood to be aggregated. The next three panels illustrate the aspects of the multiset a given aggregator is able to capture: sum captures the full multiset, mean captures the proportion/distribution of elements of a given type, and the max aggregator ignores multiplicities (reduces the multiset to a simple set).

图 2：对多重集上 sum、mean、max 聚合器按表达能力排序。 左图为输入多重集（待聚合的网络邻域）。随后三图分别示意各聚合器能捕捉的多重集侧面：sum 捕捉完整多重集，mean 捕捉某类元素的比例/分布，max 忽略重数（把多重集压成普通集合）。

(a) Mean and Max both fail

(a) 均值与最大值均失败

Next, we study GNNs that do not satisfy the conditions in Theorem 3, including GCN (Kipf & Welling 2017) and GraphSAGE (Hamilton et al. 2017a). We conduct ablation studies on two aspects of the aggregator in Eq. 4.1: (1) 1-layer perceptrons instead of MLPs and (2) mean or max-pooling instead of the sum. We will see that these GNN variants get confused by surprisingly simple graphs and are less powerful than the WL test. Nonetheless, models with mean aggregators like GCN perform well for node classification tasks. To better understand this, we precisely characterize what different GNN variants can and cannot capture about a graph and discuss the implications for learning with graphs.

接着研究不满足定理 3 条件的 GNN，包括 GCN（Kipf & Welling 2017）与 GraphSAGE（Hamilton et al. 2017a）。对式 4.1 聚合器做两方面消融：(1) 用 1 层感知机代替 MLP；(2) 用均值或最大池化代替求和。会看到这些变体会被出奇简单的图迷惑，弱于 WL 检验。尽管如此，带均值聚合的模型（如 GCN）在节点分类上表现好。为更好理解，我们精确刻画不同变体能/不能捕捉图的哪些方面，并讨论对图学习的含义。

5.1 1-layer perceptrons are not sufficient

5.1 一层感知机不够

The function $f$ in Lemma 5 helps map distinct multisets to unique embeddings. It can be parameterized by an MLP by the universal approximation theorem (Hornik 1991). Nonetheless, many existing GNNs instead use a 1-layer perceptron $\sigma\circ W$ (Duvenaud et al. 2015; Kipf & Welling 2017; Zhang et al. 2018), a linear mapping followed by a non-linear activation function such as a ReLU. Such 1-layer mappings are examples of Generalized Linear Models (Nelder & Wedderburn 1972). Therefore, we are interested in understanding whether 1-layer perceptrons are enough for graph learning. Lemma 7 suggests that there are indeed network neighborhoods (multisets) that models with 1-layer perceptrons can never distinguish.

引理 5 中的函数 $f$ 帮助把不同多重集映到唯一嵌入；由通用逼近定理（Hornik 1991）可用 MLP 参数化。但许多已有 GNN 改用 1 层感知机 $\sigma\circ W$（Duvenaud et al. 2015；Kipf & Welling 2017；Zhang et al. 2018），即线性映射加 ReLU 等非线性。这类 1 层映射是广义线性模型的例子（Nelder & Wedderburn 1972）。因此我们关心：图学习是否一层感知机就够？引理 7 表明：确实存在带一层感知机的模型永远无法区分的网络邻域（多重集）。

Lemma 7.

There exist finite multisets $X_{1}\neq X_{2}$ so that for any linear mapping $W$, $\sum\nolimits_{x\in X_{1}}{\rm ReLU}\left(Wx\right)=\sum\nolimits_{x\in X_{2}}{\rm ReLU}\left(Wx\right).$

引理 7。

存在有限多重集 $X_{1}\neq X_{2}$，使得对任意线性映射 $W$，有 $\sum\nolimits_{x\in X_{1}}{\rm ReLU}\left(Wx\right)=\sum\nolimits_{x\in X_{2}}{\rm ReLU}\left(Wx\right)。$

The main idea of the proof for Lemma 7 is that 1-layer perceptrons can behave much like linear mappings, so the GNN layers degenerate into simply summing over neighborhood features. Our proof builds on the fact that the bias term is lacking in the linear mapping. With the bias term and sufficiently large output dimensionality, 1-layer perceptrons might be able to distinguish different multisets. Nonetheless, unlike models using MLPs, the 1-layer perceptron (even with the bias term) is not a universal approximator of multiset functions. Consequently, even if GNNs with 1-layer perceptrons can embed different graphs to different locations to some degree, such embeddings may not adequately capture structural similarity, and can be difficult for simple classifiers, e.g., linear classifiers, to fit. In Section 7, we will empirically see that GNNs with $1$-layer perceptrons, when applied to graph classification, sometimes severely underfit training data and often perform worse than GNNs with MLPs in terms of test accuracy.

引理 7 证明的核心是：1 层感知机可表现得酷似线性映射，从而使 GNN 层退化成对邻域特征简单求和。证明利用了线性映射缺少偏置项这一点。若有偏置且输出维足够大，1 层感知机或许能区分不同多重集；但即便有偏置，它也不是多重集函数的通用逼近器，这与使用 MLP 的模型不同。因此，即使带 1 层感知机的 GNN 能在一定程度上把不同图映到不同位置，这类嵌入也可能不足以刻画结构相似度，且难以被线性分类器等简单分类器拟合。第 7 节将经验看到：用于图分类时，带 1 层感知机的 GNN 有时严重欠拟合训练数据，测试准确率也常弱于带 MLP 的 GNN。

5.2 Structures that confuse mean and max-pooling

5.2 迷惑均值与最大池化的结构

What happens if we replace the sum in $h\left(X\right)=\sum_{x\in X}f(x)$ with mean or max-pooling as in GCN and GraphSAGE? Mean and max-pooling aggregators are still well-defined multiset functions because they are permutation invariant. But, they are not injective. Figure 2 ranks the three aggregators by their representational power, and Figure 3 illustrates pairs of structures that the mean and max-pooling aggregators fail to distinguish. Here, node colors denote different node features, and we assume the GNNs aggregate neighbors first before combining them with the central node labeled as $v$ and $v^{\prime}$.

若把 $h\left(X\right)=\sum_{x\in X}f(x)$ 中的求和换成 GCN、GraphSAGE 中的均值或最大池化会怎样？均值与最大池化仍是良定的多重集函数（置换不变），但不是注入。图 2 按表示能力给三种聚合器排序；图 3 给出均值与最大池化无法区分的结构对。节点颜色表示不同节点特征；并假设 GNN 先聚合邻居，再与中心节点（标为 $v$、$v^{\prime}$）结合。

In Figure 3(a), every node has the same feature $a$ and $f(a)$ is the same across all nodes (for any function $f$). When performing neighborhood aggregation, the mean or maximum over $f(a)$ remains $f(a)$ and, by induction, we always obtain the same node representation everywhere. Thus, in this case mean and max-pooling aggregators fail to capture any structural information. In contrast, the sum aggregator distinguishes the structures because $2\cdot f(a)$ and $3\cdot f(a)$ give different values. The same argument can be applied to any unlabeled graph. If node degrees instead of a constant value is used as node input features, in principle, mean can recover sum, but max-pooling cannot.

在图 3(a) 中，每个节点特征都是 $a$，对任意 $f$ 有相同的 $f(a)$。邻域聚合时，对 $f(a)$ 取均值或最大仍是 $f(a)$，归纳可知处处得到相同节点表示。于是均值与最大池化捕捉不到任何结构信息。相反，求和聚合可以区分，因为 $2\cdot f(a)$ 与 $3\cdot f(a)$ 不同。同一论证适用于任意无标签图。若用节点度数而非常数作输入特征，均值原则上可恢复求和，但最大池化不行。

Fig. 3(a) suggests that mean and max have trouble distinguishing graphs with nodes that have repeating features. Let $h_{{\rm color}}$ ($r$ for red, $g$ for green) denote node features transformed by $f$. Fig. 3(b) shows that maximum over the neighborhood of the blue nodes $v$ and $v^{\prime}$ yields $\max\left(h_{\text{g}},h_{\text{r}}\right)$ and $\max\left(h_{\text{g}},h_{\text{r}},h_{\text{r}}\right)$, which collapse to the same representation (even though the corresponding graph structures are different). Thus, max-pooling fails to distinguish them. In contrast, the sum aggregator still works because $\frac{1}{2}\left(h_{\text{g}}+h_{\text{r}}\right)$ and $\frac{1}{3}\left(h_{\text{g}}+h_{\text{r}}+h_{\text{r}}\right)$ are in general not equivalent. Similarly, in Fig. 3(c), both mean and max fail as $\frac{1}{2}\left(h_{\text{g}}+h_{\text{r}}\right)=\frac{1}{4}\left(h_{\text{g}}+h_{\text{g}}+h_{\text{r}}+h_{\text{r}}\right)$.

图 3(a) 表明：当节点特征重复时，均值与最大值难以区分图。设 $h_{{\rm color}}$（$r$ 红、$g$ 绿）为经 $f$ 变换后的节点特征。图 3(b) 显示：蓝节点 $v$ 与 $v^{\prime}$ 邻域上的最大值分别是 $\max\left(h_{\text{g}},h_{\text{r}}\right)$ 与 $\max\left(h_{\text{g}},h_{\text{r}},h_{\text{r}}\right)$，会塌成同一表示（尽管图结构不同），故最大池化失败。求和仍有效，因为 $\frac{1}{2}\left(h_{\text{g}}+h_{\text{r}}\right)$ 与 $\frac{1}{3}\left(h_{\text{g}}+h_{\text{r}}+h_{\text{r}}\right)$ 一般不等价。类似地，图 3(c) 中均值与最大值都失败，因 $\frac{1}{2}\left(h_{\text{g}}+h_{\text{r}}\right)=\frac{1}{4}\left(h_{\text{g}}+h_{\text{g}}+h_{\text{r}}+h_{\text{r}}\right)$。

5.3 Mean learns distributions

5.3 均值学习分布

To characterize the class of multisets that the mean aggregator can distinguish, consider the example $X_{1}=(S,m)$ and $X_{2}=(S,k\cdot m)$, where $X_{1}$ and $X_{2}$ have the same set of distinct elements, but $X_{2}$ contains $k$ copies of each element of $X_{1}$. Any mean aggregator maps $X_{1}$ and $X_{2}$ to the same embedding, because it simply takes averages over individual element features. Thus, the mean captures the distribution (proportions) of elements in a multiset, but not the exact multiset.

为刻画均值聚合器能区分的多重集类，考虑 $X_{1}=(S,m)$ 与 $X_{2}=(S,k\cdot m)$：二者有相同的不同元素集合，但 $X_{2}$ 含 $X_{1}$ 每个元素的 $k$ 份拷贝。任何均值聚合器把 $X_{1}$、$X_{2}$ 映到同一嵌入，因为它只对元素特征取平均。因此均值捕捉多重集中元素的分布（比例），而非精确多重集。

Corollary 8.

Assume $\mathcal{X}$ is countable. There exists a function $f:\mathcal{X}\rightarrow\mathbb{R}^{n}$ so that for $h(X)=\frac{1}{|X|}\sum_{x\in X}f(x)$, $h(X_{1})=h(X_{2})$ if and only if multisets $X_{1}$ and $X_{2}$ have the same distribution. That is, assuming $|X_{2}|\geq|X_{1}|$, we have $X_{1}=(S,m)$ and $X_{2}=(S,k\cdot m)$ for some $k\in\mathbb{N}_{\geq 1}$.

推论 8。

假设 $\mathcal{X}$ 可数。存在函数 $f:\mathcal{X}\rightarrow\mathbb{R}^{n}$，使得对 $h(X)=\frac{1}{|X|}\sum_{x\in X}f(x)$，$h(X_{1})=h(X_{2})$ 当且仅当多重集 $X_{1}$、$X_{2}$ 有相同分布。亦即，在 $|X_{2}|\geq|X_{1}|$ 时，有 $X_{1}=(S,m)$、$X_{2}=(S,k\cdot m)$（某个 $k\in\mathbb{N}_{\geq 1}$）。

The mean aggregator may perform well if, for the task, the statistical and distributional information in the graph is more important than the exact structure. Moreover, when node features are diverse and rarely repeat, the mean aggregator is as powerful as the sum aggregator. This may explain why, despite the limitations identified in Section 5.2, GNNs with mean aggregators are effective for node classification tasks, such as classifying article subjects and community detection, where node features are rich and the distribution of the neighborhood features provides a strong signal for the task.

若任务更看重图中的统计与分布信息而非精确结构，均值聚合可能表现好。此外，当节点特征多样、很少重复时，均值与求和同等有力。这或可解释：尽管有第 5.2 节的局限，带均值聚合的 GNN 在节点分类（如文章主题分类、社区发现）上仍然有效——节点特征丰富，邻域特征分布对任务信号很强。

5.4 Max-pooling learns sets with distinct elements

5.4 最大池化学习不同元素构成的集合

The examples in Figure 3 illustrate that max-pooling considers multiple nodes with the same feature as only one node (i.e., treats a multiset as a set). Max-pooling captures neither the exact structure nor the distribution. However, it may be suitable for tasks where it is important to identify representative elements or the “skeleton”, rather than to distinguish the exact structure or distribution. Qi et al. 2017 empirically show that the max-pooling aggregator learns to identify the skeleton of a 3D point cloud and that it is robust to noise and outliers. For completeness, the next corollary shows that the max-pooling aggregator captures the underlying set of a multiset.

图 3 的例子说明：最大池化把多个同特征节点视为一个节点（即把多重集当集合）。它既不捕捉精确结构，也不捕捉分布。但对需要识别代表性元素或“骨架”、而非区分精确结构/分布的任务，它可能合适。Qi et al. 2017 经验表明，最大池化聚合能学会识别 3D 点云骨架，并对噪声与离群点稳健。为完整起见，下一条推论说明最大池化捕捉多重集的底层集合。

Corollary 9.

Assume $\mathcal{X}$ is countable. Then there exists a function $f:\mathcal{X}\rightarrow\mathbb{R}^{\infty}$ so that for $h(X)=\max_{x\in X}f(x)$, $h(X_{1})=h(X_{2})$ if and only if $X_{1}$ and $X_{2}$ have the same underlying set.

推论 9。

假设 $\mathcal{X}$ 可数。则存在函数 $f:\mathcal{X}\rightarrow\mathbb{R}^{\infty}$，使得对 $h(X)=\max_{x\in X}f(x)$，$h(X_{1})=h(X_{2})$ 当且仅当 $X_{1}$、$X_{2}$ 有相同底层集合。

5.5 Remarks on other aggregators

5.5 对其余聚合器的备注

There are other non-standard neighbor aggregation schemes that we do not cover, e.g., weighted average via attention (Velickovic et al. 2018) and LSTM pooling (Hamilton et al. 2017a; Murphy et al. 2018). We emphasize that our theoretical framework is general enough to characterize the representaional power of any aggregation-based GNNs. In the future, it would be interesting to apply our framework to analyze and understand other aggregation schemes.

还有本文未覆盖的非标准邻居聚合，例如经注意力的加权平均（Velickovic et al. 2018）与 LSTM 池化（Hamilton et al. 2017a；Murphy et al. 2018）。需要强调：本理论框架足够一般，可刻画任意基于聚合的 GNN 的表示能力。未来有趣的是用它分析并理解其他聚合方案。

6 Other related work

6 其他相关工作

Despite the empirical success of GNNs, there has been relatively little work that mathematically studies their properties. An exception to this is the work of Scarselli et al. 2009a who shows that the perhaps earliest GNN model (Scarselli et al. 2009b) can approximate measurable functions in probability. Lei et al. 2017 show that their proposed architecture lies in the RKHS of graph kernels, but do not study explicitly which graphs it can distinguish. Each of these works focuses on a specific architecture and do not easily generalize to multple architectures. In contrast, our results above provide a general framework for analyzing and characterizing the expressive power of a broad class of GNNs. Recently, many GNN-based architectures have been proposed, including sum aggregation and MLP encoding (Battaglia et al. 2016; Scarselli et al. 2009b; Duvenaud et al. 2015), and most without theoretical derivation. In contrast to many prior GNN architectures, our Graph Isomorphism Network (GIN) is theoretically motivated, simple yet powerful.

尽管 GNN 经验成功，对其性质的数学研究相对较少。例外包括 Scarselli et al. 2009a：表明或许最早的 GNN 模型（Scarselli et al. 2009b）能在概率意义下逼近可测函数；Lei et al. 2017 表明其结构落在图核的 RKHS 中，但未显式研究能区分哪些图。这些工作多针对特定结构，不易推广到多种结构。相比之下，上文结果为分析一大类 GNN 的表达能力提供了一般框架。近年还提出许多 GNN 结构，包括求和聚合与 MLP 编码（Battaglia et al. 2016；Scarselli et al. 2009b；Duvenaud et al. 2015），多数缺少理论推导。与许多先前结构不同，图同构网络（GIN）有理论动机，简单却有力。

7 Experiments

7 实验

We evaluate and compare the training and test performance of GIN and less powerful GNN variants.[^1] Training set performance allows us to compare different GNN models based on their representational power and test set performance quantifies generalization ability.

我们评测并比较 GIN 与较弱 GNN 变体的训练与测试表现。[^1] 训练集表现用来按表示能力比较不同 GNN；测试集表现量化泛化。

Datasets. We use 9 graph classification benchmarks: 4 bioinformatics datasets (MUTAG, PTC, NCI1, PROTEINS) and 5 social network datasets (COLLAB, IMDB-BINARY, IMDB-MULTI, REDDIT-BINARY and REDDIT-MULTI5K) (Yanardag & Vishwanathan 2015). Importantly, our goal here is not to allow the models to rely on the input node features but mainly learn from the network structure. Thus, in the bioinformatic graphs, the nodes have categorical input features but in the social networks, they have no features. For social networks we create node features as follows: for the REDDIT datasets, we set all node feature vectors to be the same (thus, features here are uninformative); for the other social graphs, we use one-hot encodings of node degrees. Dataset statistics are summarized in Table 1, and more details of the data can be found in Appendix I.

数据集。 使用 9 个图分类基准：4 个生物信息数据集（MUTAG、PTC、NCI1、PROTEINS）与 5 个社交网络数据集（COLLAB、IMDB-BINARY、IMDB-MULTI、REDDIT-BINARY、REDDIT-MULTI5K）（Yanardag & Vishwanathan 2015）。此处目标不是让模型依赖输入节点特征，而主要从图结构学习。因此生物信息图的节点有类别输入特征，社交网络则无特征。社交网络按如下造特征：REDDIT 上所有节点特征相同（因而无信息）；其余社交图用节点度数的 one-hot。数据统计见表 1，细节见附录 I。

Models and configurations. We evaluate GINs (Eqs. 4.1 and 4.2) and the less powerful GNN variants. Under the GIN framework, we consider two variants: (1) a GIN that learns $\epsilon$ in Eq. 4.1 by gradient descent, which we call GIN-$\epsilon$, and (2) a simpler (slightly less powerful)[^2] GIN, where $\epsilon$ in Eq. 4.1 is fixed to 0, which we call GIN-0. As we will see, GIN-0 shows strong empirical performance: not only does GIN-0 fit training data equally well as GIN-$\epsilon$, it also demonstrates good generalization, slightly but consistently outperforming GIN-$\epsilon$ in terms of test accuracy. For the less powerful GNN variants, we consider architectures that replace the sum in the GIN-0 aggregation with mean or max-pooling[^3], or replace MLPs with 1-layer perceptrons, i.e., a linear mapping followed by ReLU. In Figure 4 and Table 1, a model is named by the aggregator/perceptron it uses. Here mean–1-layer and max–1-layer correspond to GCN and GraphSAGE, respectively, up to minor architecture modifications. We apply the same graph-level readout (READOUT in Eq. 4.2) for GINs and all the GNN variants, specifically, sum readout on bioinformatics datasets and mean readout on social datasets due to better test performance.

模型与配置。 评测 GIN（式 4.1、4.2）与较弱变体。在 GIN 框架下考虑两种：(1) 用梯度下降学习式 4.1 中 $\epsilon$ 的 GIN-$\epsilon$；(2) 将 $\epsilon$ 固定为 0 的更简单（略弱）[^2] GIN-0。后文可见 GIN-0 经验很强：拟合训练不逊于 GIN-$\epsilon$，测试准确率还略高且更稳。较弱变体包括：把 GIN-0 聚合中的求和换成均值或最大池化[^3]，或把 MLP 换成 1 层感知机（线性映射加 ReLU）。图 4 与表 1 中模型按所用聚合/感知机命名；mean–1-layer 与 max–1-layer 分别近似对应 GCN 与 GraphSAGE（有少量结构差别）。GIN 与全部变体使用相同图级读出（式 4.2 的 READOUT）：生物信息集用求和读出，社交集用均值读出（测试更好）。

Following (Yanardag & Vishwanathan 2015; Niepert et al. 2016), we perform 10-fold cross-validation with LIB-SVM (Chang & Lin 2011). We report the average and standard deviation of validation accuracies across the 10 folds within the cross-validation. For all configurations, 5 GNN layers (including the input layer) are applied, and all MLPs have $2$ layers. Batch normalization (Ioffe & Szegedy 2015) is applied on every hidden layer. We use the Adam optimizer (Kingma & Ba 2015) with initial learning rate $0.01$ and decay the learning rate by $0.5$ every 50 epochs. The hyper-parameters we tune for each dataset are: (1) the number of hidden units $\in\{16,32\}$ for bioinformatics graphs and $64$ for social graphs; (2) the batch size $\in\{32,128\}$; (3) the dropout ratio $\in\{0,0.5\}$ after the dense layer (Srivastava et al. 2014); (4) the number of epochs, i.e., a single epoch with the best cross-validation accuracy averaged over the 10 folds was selected. Note that due to the small dataset sizes, an alternative setting, where hyper-parameter selection is done using a validation set, is extremely unstable, e.g., for MUTAG, the validation set only contains 18 data points. We also report the training accuracy of different GNNs, where all the hyper-parameters were fixed across the datasets: 5 GNN layers (including the input layer), hidden units of size 64, minibatch of size 128, and 0.5 dropout ratio. For comparison, the training accuracy of the WL subtree kernel is reported, where we set the number of iterations to 4, which is comparable to the 5 GNN layers.

沿用 Yanardag & Vishwanathan 2015、Niepert et al. 2016，用 LIB-SVM（Chang & Lin 2011）做 10 折交叉验证，报告 10 折验证准确率的均值与标准差。所有配置使用 5 层 GNN（含输入层），MLP 均为 2 层；每隐层加 BatchNorm（Ioffe & Szegedy 2015）。优化器用 Adam（Kingma & Ba 2015），初始学习率 $0.01$，每 50 个 epoch 衰减 $0.5$。各数据集调参：(1) 隐单元数，生物信息 $\in\{16,32\}$，社交为 $64$；(2) 批大小 $\in\{32,128\}$；(3) 全连接层后 dropout $\in\{0,0.5\}$（Srivastava et al. 2014）；(4) epoch 数，取 10 折平均交叉验证准确率最高的单个 epoch。因数据规模小，用独立验证集选参极不稳定（如 MUTAG 验证仅 18 条）。另报训练准确率：超参跨集合固定为 5 层、隐单元 64、minibatch 128、dropout 0.5。对照还报 WL 子树核的训练准确率，迭代设为 4，与 5 层 GNN 可比。

Baselines. We compare the GNNs above with a number of state-of-the-art baselines for graph classification: (1) the WL subtree kernel (Shervashidze et al. 2011), where $C$-SVM (Chang & Lin 2011) was used as a classifier; the hyper-parameters we tune are $C$ of the SVM and the number of WL iterations $\in\{1,2,\ldots,6\}$; (2) state-of-the-art deep learning architectures, i.e., Diffusion-convolutional neural networks (DCNN) (Atwood & Towsley 2016), PATCHY-SAN (Niepert et al. 2016) and Deep Graph CNN (DGCNN) (Zhang et al. 2018); (3) Anonymous Walk Embeddings (AWL) (Ivanov & Burnaev 2018). For the deep learning methods and AWL, we report the accuracies reported in the original papers.

基线。 与若干图分类 SotA 对照：(1) WL 子树核（Shervashidze et al. 2011）+ $C$-SVM，调 $C$ 与 WL 迭代数 $\in\{1,2,\ldots,6\}$；(2) 深度结构：DCNN（Atwood & Towsley 2016）、PATCHY-SAN（Niepert et al. 2016）、DGCNN（Zhang et al. 2018）；(3) Anonymous Walk Embeddings（AWL，Ivanov & Burnaev 2018）。深度方法与 AWL 直接引用原论文准确率。

Figure 4: Training set performance of GINs, less powerful GNN variants, and the WL subtree kernel.

图 4：GIN、较弱 GNN 变体与 WL 子树核的训练集表现。

Datasets IMDB-B IMDB-M RDT-B RDT-M5K COLLAB MUTAG PROTEINS PTC NCI1 Datasets # graphs 1000 1500 2000 5000 5000 188 1113 344 4110 # classes 2 3 2 5 3 2 2 2 2 Avg # nodes 19.8 13.0 429.6 508.5 74.5 17.9 39.1 25.5 29.8 Baselines WL subtree 73.8 $\pm$ 3.9 50.9 $\pm$ 3.8 81.0 $\pm$ 3.1 52.5 $\pm$ 2.1 78.9 $\pm$ 1.9 90.4 $\pm$ 5.7 75.0 $\pm$ 3.1 59.9 $\pm$ 4.3 86.0 $\pm$ 1.8 ∗ DCNN 49.1 33.5 – – 52.1 67.0 61.3 56.6 62.6 PatchySan 71.0 $\pm$ 2.2 45.2 $\pm$ 2.8 86.3 $\pm$ 1.6 49.1 $\pm$ 0.7 72.6 $\pm$ 2.2 92.6 $\pm$ 4.2 ∗ 75.9 $\pm$ 2.8 60.0 $\pm$ 4.8 78.6 $\pm$ 1.9 DGCNN 70.0 47.8 – – 73.7 85.8 75.5 58.6 74.4 AWL 74.5 $\pm$ 5.9 51.5 $\pm$ 3.6 87.9 $\pm$ 2.5 54.7 $\pm$ 2.9 73.9 $\pm$ 1.9 87.9 $\pm$ 9.8 – – – GNN variants Sum–MLP (GIN-0) 75.1 $\pm$ 5.1 52.3 $\pm$ 2.8 92.4 $\pm$ 2.5 57.5 $\pm$ 1.5 80.2 $\pm$ 1.9 89.4 $\pm$ 5.6 76.2 $\pm$ 2.8 64.6 $\pm$ 7.0 82.7 $\pm$ 1.7 Sum–MLP (GIN-$\epsilon$) 74.3 $\pm$ 5.1 52.1 $\pm$ 3.6 92.2 $\pm$ 2.3 57.0 $\pm$ 1.7 80.1 $\pm$ 1.9 89.0 $\pm$ 6.0 75.9 $\pm$ 3.8 63.7 $\pm$ 8.2 82.7 $\pm$ 1.6 Sum–1-Layer 74.1 $\pm$ 5.0 52.2 $\pm$ 2.4 90.0 $\pm$ 2.7 55.1 $\pm$ 1.6 80.6 $\pm$ 1.9 90.0 $\pm$ 8.8 76.2 $\pm$ 2.6 63.1 $\pm$ 5.7 82.0 $\pm$ 1.5 Mean–MLP 73.7 $\pm$ 3.7 52.3 $\pm$ 3.1 50.0 $\pm$ 0.0 20.0 $\pm$ 0.0 79.2 $\pm$ 2.3 83.5 $\pm$ 6.3 75.5 $\pm$ 3.4 66.6 $\pm$ 6.9 80.9 $\pm$ 1.8 Mean–1-Layer (GCN) 74.0 $\pm$ 3.4 51.9 $\pm$ 3.8 50.0 $\pm$ 0.0 20.0 $\pm$ 0.0 79.0 $\pm$ 1.8 85.6 $\pm$ 5.8 76.0 $\pm$ 3.2 64.2 $\pm$ 4.3 80.2 $\pm$ 2.0 Max–MLP 73.2 $\pm$ 5.8 51.1 $\pm$ 3.6 – – – 84.0 $\pm$ 6.1 76.0 $\pm$ 3.2 64.6 $\pm$ 10.2 77.8 $\pm$ 1.3 Max–1-Layer (GraphSAGE) 72.3 $\pm$ 5.3 50.9 $\pm$ 2.2 – – – 85.1 $\pm$ 7.6 75.9 $\pm$ 3.2 63.9 $\pm$ 7.7 77.7 $\pm$ 1.5

Datasets

Baselines

GNN variants

Table 1: Test set classification accuracies (%). The best-performing GNNs are highlighted with boldface. On datasets where GINs’ accuracy is not strictly the highest among GNN variants, we see that GINs are still comparable to the best GNN because a paired t-test at significance level 10% does not distinguish GINs from the best; thus, GINs are also highlighted with boldface. If a baseline performs significantly better than all GNNs, we highlight it with boldface and asterisk.

数据集	IMDB-B	IMDB-M	RDT-B	RDT-M5K	COLLAB	MUTAG	PROTEINS	PTC	NCI1
# graphs	1000	1500	2000	5000	5000	188	1113	344	4110
# classes	2	3	2	5	3	2	2	2	2
Avg # nodes	19.8	13.0	429.6	508.5	74.5	17.9	39.1	25.5	29.8
基线
WL subtree	73.8 $\pm$ 3.9	50.9 $\pm$ 3.8	81.0 $\pm$ 3.1	52.5 $\pm$ 2.1	78.9 $\pm$ 1.9	90.4 $\pm$ 5.7	75.0 $\pm$ 3.1	59.9 $\pm$ 4.3	86.0 $\pm$ 1.8 ∗
DCNN	49.1	33.5	–	–	52.1	67.0	61.3	56.6	62.6
PatchySan	71.0 $\pm$ 2.2	45.2 $\pm$ 2.8	86.3 $\pm$ 1.6	49.1 $\pm$ 0.7	72.6 $\pm$ 2.2	92.6 $\pm$ 4.2 ∗	75.9 $\pm$ 2.8	60.0 $\pm$ 4.8	78.6 $\pm$ 1.9
DGCNN	70.0	47.8	–	–	73.7	85.8	75.5	58.6	74.4
AWL	74.5 $\pm$ 5.9	51.5 $\pm$ 3.6	87.9 $\pm$ 2.5	54.7 $\pm$ 2.9	73.9 $\pm$ 1.9	87.9 $\pm$ 9.8	–	–	–
GNN 变体
Sum–MLP (GIN-0)	75.1 $\pm$ 5.1	52.3 $\pm$ 2.8	92.4 $\pm$ 2.5	57.5 $\pm$ 1.5	80.2 $\pm$ 1.9	89.4 $\pm$ 5.6	76.2 $\pm$ 2.8	64.6 $\pm$ 7.0	82.7 $\pm$ 1.7
Sum–MLP (GIN-$\epsilon$)	74.3 $\pm$ 5.1	52.1 $\pm$ 3.6	92.2 $\pm$ 2.3	57.0 $\pm$ 1.7	80.1 $\pm$ 1.9	89.0 $\pm$ 6.0	75.9 $\pm$ 3.8	63.7 $\pm$ 8.2	82.7 $\pm$ 1.6
Sum–1-Layer	74.1 $\pm$ 5.0	52.2 $\pm$ 2.4	90.0 $\pm$ 2.7	55.1 $\pm$ 1.6	80.6 $\pm$ 1.9	90.0 $\pm$ 8.8	76.2 $\pm$ 2.6	63.1 $\pm$ 5.7	82.0 $\pm$ 1.5
Mean–MLP	73.7 $\pm$ 3.7	52.3 $\pm$ 3.1	50.0 $\pm$ 0.0	20.0 $\pm$ 0.0	79.2 $\pm$ 2.3	83.5 $\pm$ 6.3	75.5 $\pm$ 3.4	66.6 $\pm$ 6.9	80.9 $\pm$ 1.8
Mean–1-Layer (GCN)	74.0 $\pm$ 3.4	51.9 $\pm$ 3.8	50.0 $\pm$ 0.0	20.0 $\pm$ 0.0	79.0 $\pm$ 1.8	85.6 $\pm$ 5.8	76.0 $\pm$ 3.2	64.2 $\pm$ 4.3	80.2 $\pm$ 2.0
Max–MLP	73.2 $\pm$ 5.8	51.1 $\pm$ 3.6	–	–	–	84.0 $\pm$ 6.1	76.0 $\pm$ 3.2	64.6 $\pm$ 10.2	77.8 $\pm$ 1.3
Max–1-Layer (GraphSAGE)	72.3 $\pm$ 5.3	50.9 $\pm$ 2.2	–	–	–	85.1 $\pm$ 7.6	75.9 $\pm$ 3.2	63.9 $\pm$ 7.7	77.7 $\pm$ 1.5

表 1：测试集分类准确率（%）。 表现最好的 GNN 加粗。若 GIN 并非严格最高，但在 10% 显著性的配对 t 检验下与最佳 GNN 无区别，亦加粗。若某基线显著优于全部 GNN，则加粗并标星号。

7.1 Results

7.1 结果

Training set performance. We validate our theoretical analysis of the representational power of GNNs by comparing their training accuracies. Models with higher representational power should have higher training set accuracy. Figure 4 shows training curves of GINs and less powerful GNN variants with the same hyper-parameter settings. First, both the theoretically most powerful GNN, i.e. GIN-$\epsilon$ and GIN-0, are able to almost perfectly fit all the training sets. In our experiments, explicit learning of $\epsilon$ in GIN-$\epsilon$ yields no gain in fitting training data compared to fixing $\epsilon$ to 0 as in GIN-0. In comparison, the GNN variants using mean/max pooling or 1-layer perceptrons severely underfit on many datasets. In particular, the training accuracy patterns align with our ranking by the models’ representational power: GNN variants with MLPs tend to have higher training accuracies than those with 1-layer perceptrons, and GNNs with sum aggregators tend to fit the training sets better than those with mean and max-pooling aggregators.

训练集表现。 通过比较训练准确率验证关于 GNN 表示能力的理论分析：表示能力更强的模型应有更高训练准确率。图 4 在相同超参下给出 GIN 与较弱变体的训练曲线。首先，理论上最强的 GIN-$\epsilon$ 与 GIN-0 几乎能完美拟合全部训练集；显式学习 $\epsilon$ 相对固定为 0 并无额外拟合收益。相比之下，使用均值/最大池化或 1 层感知机的变体在多个数据集上严重欠拟合。训练准确率排序与按表示能力的理论排序一致：带 MLP 的变体往往高于 1 层感知机；带求和聚合的往往比均值、最大池化更好拟合。

On our datasets, training accuracies of the GNNs never exceed those of the WL subtree kernel. This is expected because GNNs generally have lower discriminative power than the WL test. For example, on IMDBBINARY, none of the models can perfectly fit the training set, and the GNNs achieve at most the same training accuracy as the WL kernel. This pattern aligns with our result that the WL test provides an upper bound for the representational capacity of the aggregation-based GNNs. However, the WL kernel is not able to learn how to combine node features, which might be quite informative for a given prediction task as we will see next.

在我们的数据上，GNN 训练准确率从未超过 WL 子树核。这符合预期：GNN 的判别力一般低于 WL 检验。例如在 IMDB-BINARY 上，没有模型能完美拟合，GNN 至多达到与 WL 核相同的训练准确率。这与“WL 检验给出基于聚合的 GNN 表示能力上界”一致。但 WL 核无法学习如何组合节点特征，而这对预测任务可能很有信息量，如下文所示。

Test set performance. Next, we compare test accuracies. Although our theoretical results do not directly speak about the generalization ability of GNNs, it is reasonable to expect that GNNs with strong expressive power can accurately capture graph structures of interest and thus generalize well. Table 1 compares test accuracies of GINs (Sum–MLP), other GNN variants, as well as the state-of-the-art baselines.

测试集表现。 理论结果并不直接谈论泛化，但可合理预期：表达力强的 GNN 更能准确捕捉感兴趣的图结构，从而泛化更好。表 1 比较 GIN（Sum–MLP）、其他变体与 SotA 基线的测试准确率。

First, GINs, especially GIN-0, outperform (or achieve comparable performance as) the less powerful GNN variants on all the 9 datasets, achieving state-of-the-art performance. GINs shine on the social network datasets, which contain a relatively large number of training graphs. For the Reddit datasets, all nodes share the same scalar as node feature. Here, GINs and sum-aggregation GNNs accurately capture the graph structure and significantly outperform other models. Mean-aggregation GNNs, however, fail to capture any structures of the unlabeled graphs (as predicted in Section 5.2) and do not perform better than random guessing. Even if node degrees are provided as input features, mean-based GNNs perform much worse than sum-based GNNs (the accuracy of the GNN with mean–MLP aggregation is 71.2$\pm$4.6% on REDDIT-BINARY and 41.3$\pm$2.1% on REDDIT-MULTI5K). Comparing GINs (GIN-0 and GIN-$\epsilon$), we observe that GIN-0 slightly but consistently outperforms GIN-$\epsilon$. Since both models fit training data equally well, the better generalization of GIN-0 may be explained by its simplicity compared to GIN-$\epsilon$.

首先，GIN（尤其 GIN-0）在全部 9 个数据集上优于或可比于较弱变体，达到当时最优。社交网络数据训练图较多，GIN 尤为突出。REDDIT 上所有节点共用同一标量特征时，GIN 与求和聚合 GNN 能准确捕捉结构并显著超过其他模型；均值聚合则无法捕捉无标签图的任何结构（与第 5.2 节一致），表现不优于随机猜测。即便提供节点度数作输入，均值类 GNN 仍远弱于求和类（mean–MLP 在 REDDIT-BINARY 约 71.2$\pm$4.6%，在 REDDIT-MULTI5K 约 41.3$\pm$2.1%）。比较 GIN-0 与 GIN-$\epsilon$，前者略高且更稳；二者拟合训练相当，更好泛化或可用结构更简单解释。

8 Conclusion

8 结论

In this paper, we developed theoretical foundations for reasoning about the expressive power of GNNs, and proved tight bounds on the representational capacity of popular GNN variants. We also designed a provably maximally powerful GNN under the neighborhood aggregation framework. An interesting direction for future work is to go beyond neighborhood aggregation (or message passing) in order to pursue possibly even more powerful architectures for learning with graphs. To complete the picture, it would also be interesting to understand and improve the generalization properties of GNNs as well as better understand their optimization landscape.

本文为推理 GNN 表达能力建立理论基础，并对流行变体的表示能力给出紧界；同时在邻域聚合框架下设计了可证明最强的 GNN。未来有趣方向是超越邻域聚合（或消息传递），追求可能更强的图学习结构。为补全图景，理解并改进 GNN 的泛化与优化景观同样重要。

Acknowledgments

This research was supported by NSF CAREER award 1553284, a DARPA D3M award and DARPA DSO’s Lagrange program under grant FA86501827838. This research was also supported in part by NSF, ARO MURI, Boeing, Huawei, Stanford Data Science Initiative, and Chan Zuckerberg Biohub. Weihua Hu was supported by Funai Overseas Scholarship. We thank Prof. Ken-ichi Kawarabayashi and Prof. Masashi Sugiyama for supporting this research with computing resources and providing great advice. We thank Tomohiro Sonobe and Kento Nozawa for managing servers. We thank Rex Ying and William Hamilton for helpful feedback. We thank Simon S. Du, Yasuo Tabei, Chengtao Li, and Jingling Li for helpful discussions and positive comments.

致谢

本工作获 NSF CAREER award 1553284、DARPA D3M 以及 DARPA DSO Lagrange 项目（FA86501827838）支持；亦获 NSF、ARO MURI、Boeing、Huawei、Stanford Data Science Initiative 与 Chan Zuckerberg Biohub 部分支持。Weihua Hu 获 Funai Overseas Scholarship 资助。感谢 Ken-ichi Kawarabayashi 与 Masashi Sugiyama 教授提供算力与建议；感谢 Tomohiro Sonobe 与 Kento Nozawa 维护服务器；感谢 Rex Ying、William Hamilton 的反馈，以及 Simon S. Du、Yasuo Tabei、Chengtao Li、Jingling Li 的讨论与鼓励。

References

参考文献

Atwood & Towsley (2016) James Atwood and Don Towsley. Diffusion-convolutional neural networks. In Advances in Neural Information Processing Systems (NIPS) , pp. 1993–2001, 2016.

Babai (2016) László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pp. 684–697. ACM, 2016.

Babai & Kucera (1979) László Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In Foundations of Computer Science, 1979., 20th Annual Symposium on , pp. 39–46. IEEE, 1979.

Battaglia et al. (2016) Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in Neural Information Processing Systems (NIPS) , pp. 4502–4510, 2016.

Cai et al. (1992) Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica , 12(4):389–410, 1992.

Chang & Lin (2011) Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST) , 2(3):27, 2011.

Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems (NIPS) , pp. 3844–3852, 2016.

Douglas (2011) Brendan L Douglas. The weisfeiler-lehman method and graph isomorphism testing. arXiv preprint arXiv:1101.5211 , 2011.

Duvenaud et al. (2015) David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. pp. 2224–2232, 2015.

Evdokimov & Ponomarenko (1999) Sergei Evdokimov and Ilia Ponomarenko. Isomorphism of coloured graphs with slowly increasing multiplicity of jordan blocks. Combinatorica , 19(3):321–333, 1999.

Garey (1979) Michael R Garey. A guide to the theory of np-completeness. Computers and intractability , 1979.

Garey & Johnson (2002) Michael R Garey and David S Johnson. Computers and intractability , volume 29. wh freeman New York, 2002.

Gilmer et al. (2017) Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML) , pp. 1273–1272, 2017.

Hamilton et al. (2017a) William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NIPS) , pp. 1025–1035, 2017a.

Hamilton et al. (2017b) William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin , 40(3):52–74, 2017b.

Hornik (1991) Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks , 4(2):251–257, 1991.

Hornik et al. (1989) Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks , 2(5):359–366, 1989.

Ioffe & Szegedy (2015) Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML) , pp. 448–456, 2015.

Ivanov & Burnaev (2018) Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International Conference on Machine Learning (ICML) , pp. 2191–2200, 2018.

Kearnes et al. (2016) Steven Kearnes, Kevin McCloskey, Marc Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer-aided molecular design , 30(8):595–608, 2016.

Kingma & Ba (2015) Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR) , 2015.

Kipf & Welling (2017) Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR) , 2017.

Lei et al. (2017) Tao Lei, Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Deriving neural architectures from sequence and graph kernels. pp. 2024–2033, 2017.

Li et al. (2016) Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR) , 2016.

Murphy et al. (2018) Ryan L Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs. arXiv preprint arXiv:1811.01900 , 2018.

Nelder & Wedderburn (1972) J. A. Nelder and R. W. M. Wedderburn. Generalized linear models. Journal of the Royal Statistical Society, Series A, General , 135:370–384, 1972.

Niepert et al. (2016) Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International Conference on Machine Learning (ICML) , pp. 2014–2023, 2016.

Qi et al. (2017) Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. Proc. Computer Vision and Pattern Recognition (CVPR), IEEE , 1(2):4, 2017.

Santoro et al. (2017) Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. In Advances in neural information processing systems , pp. 4967–4976, 2017.

Santoro et al. (2018) Adam Santoro, Felix Hill, David Barrett, Ari Morcos, and Timothy Lillicrap. Measuring abstract reasoning in neural networks. In International Conference on Machine Learning , pp. 4477–4486, 2018.

Scarselli et al. (2009a) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. Computational capabilities of graph neural networks. IEEE Transactions on Neural Networks , 20(1):81–102, 2009a.

Scarselli et al. (2009b) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks , 20(1):61–80, 2009b.

Shervashidze et al. (2011) Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research , 12(Sep):2539–2561, 2011.

Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research , 15(1):1929–1958, 2014.

Velickovic et al. (2018) Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR) , 2018.

Verma & Zhang (2018) Saurabh Verma and Zhi-Li Zhang. Graph capsule convolutional neural networks. arXiv preprint arXiv:1805.08090 , 2018.

Weisfeiler & Lehman (1968) Boris Weisfeiler and AA Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia , 2(9):12–16, 1968.

Xu et al. (2018) Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning (ICML) , pp. 5453–5462, 2018.

Yanardag & Vishwanathan (2015) Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pp. 1365–1374. ACM, 2015.

Ying et al. (2018) Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems (NIPS) , 2018.

Zaheer et al. (2017) Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems , pp. 3391–3401, 2017.

Zhang et al. (2018) Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI Conference on Artificial Intelligence , pp. 4438–4445, 2018.

Appendix A Proof for Lemma 2

附录 A 引理 2 的证明

Proof.

Suppose after $k$ iterations, a graph neural network $\mathcal{A}$ has $\mathcal{A}(G_{1})\neq\mathcal{A}(G_{2})$ but the WL test cannot decide $G_{1}$ and $G_{2}$ are non-isomorphic. It follows that from iteration $0$ to $k$ in the WL test, $G_{1}$ and $G_{2}$ always have the same collection of node labels. In particular, because $G_{1}$ and $G_{2}$ have the same WL node labels for iteration $i$ and $i+1$ for any $i=0,...,k-1$, $G_{1}$ and $G_{2}$ have the same collection, i.e. multiset, of WL node labels $\left\{l_{v}^{(i)}\right\}$ as well as the same collection of node neighborhoods $\left\{\left(l_{v}^{(i)},\left\{l_{u}^{(i)}:u\in\mathcal{N}(v)\right\}\right)\right\}$. Otherwise, the WL test would have obtained different collections of node labels at iteration $i+1$ for $G_{1}$ and $G_{2}$ as different multisets get unique new labels.

证明。

假设经过 $k$ 轮后，图神经网络 $\mathcal{A}$ 有 $\mathcal{A}(G_{1})\neq\mathcal{A}(G_{2})$，但 WL 检验无法判定 $G_{1}$、$G_{2}$ 非同构。则 WL 从第 0 轮到第 $k$ 轮，$G_{1}$ 与 $G_{2}$ 始终有相同的节点标签集合。特别地，对任意 $i=0,...,k-1$，因第 $i$ 与第 $i+1$ 轮 WL 节点标签集合相同，$G_{1}$ 与 $G_{2}$ 有相同的 WL 节点标签多重集 $\left\{l_{v}^{(i)}\right\}$，以及相同的节点邻域集合 $\left\{\left(l_{v}^{(i)},\left\{l_{u}^{(i)}:u\in\mathcal{N}(v)\right\}\right)\right\}$。否则 WL 会在第 $i+1$ 轮因不同多重集得到不同的新标签集合。

The WL test always relabels different multisets of neighboring nodes into different new labels. We show that on the same graph $G=G_{1}$ or $G_{2}$, if WL node labels $l_{v}^{(i)}=l_{u}^{(i)}$, we always have GNN node features $h_{v}^{(i)}=h_{u}^{(i)}$ for any iteration $i$. This apparently holds for $i=0$ because WL and GNN starts with the same node features. Suppose this holds for iteration $j$, if for any $u,v$, $l_{v}^{(j+1)}=l_{u}^{(j+1)}$, then it must be the case that

WL 检验总是把不同的邻居多重集重新标成不同新标签。我们证明：在同一图 $G=G_{1}$ 或 $G_{2}$ 上，若 $l_{v}^{(i)}=l_{u}^{(i)}$，则对任意轮次 $i$ 都有 GNN 节点特征 $h_{v}^{(i)}=h_{u}^{(i)}$。$i=0$ 显然成立，因为 WL 与 GNN 从相同节点特征起步。假设第 $j$ 轮成立，则若对任意 $u,v$ 有 $l_{v}^{(j+1)}=l_{u}^{(j+1)}$，必有

$$\left(l_{v}^{(j)},\left\{l_{w}^{(j)}:w\in\mathcal{N}(v)\right\}\right)=\left(l_{u}^{(j)},\left\{l_{w}^{(j)}:w\in\mathcal{N}(u)\right\}\right)$$

By our assumption on iteration $j$, we must have

由第 $j$ 轮假设，必有

$$\left(h_{v}^{(j)},\left\{h_{w}^{(j)}:w\in\mathcal{N}(v)\right\}\right)=\left(h_{u}^{(j)},\left\{h_{w}^{(j)}:w\in\mathcal{N}(u)\right\}\right)$$

In the aggregation process of the GNN, the same AGGREGATE and COMBINE are applied. The same input, i.e. neighborhood features, generates the same output. Thus, $h_{v}^{(j+1)}=h_{u}^{(j+1)}$. By induction, if WL node labels $l_{v}^{(i)}=l_{u}^{(i)}$, we always have GNN node features $h_{v}^{(i)}=h_{u}^{(i)}$ for any iteration $i$. This creates a valid mapping $\phi$ such that $h_{v}^{(i)}=\phi(l_{v}^{(i)})$ for any $v\in G$. It follows from $G_{1}$ and $G_{2}$ have the same multiset of WL neighborhood labels that $G_{1}$ and $G_{2}$ also have the same collection of GNN neighborhood features

GNN 聚合中使用相同的 AGGREGATE 与 COMBINE，相同输入（邻域特征）产生相同输出，故 $h_{v}^{(j+1)}=h_{u}^{(j+1)}$。归纳可知：若 $l_{v}^{(i)}=l_{u}^{(i)}$，则对任意 $i$ 有 $h_{v}^{(i)}=h_{u}^{(i)}$。由此得到合法映射 $\phi$，使对任意 $v\in G$ 有 $h_{v}^{(i)}=\phi(l_{v}^{(i)})$。由 $G_{1}$、$G_{2}$ 有相同的 WL 邻域标签多重集，它们也有相同的 GNN 邻域特征集合

$$\left\{\left(h_{v}^{(i)},\left\{h_{u}^{(i)}:u\in\mathcal{N}(v)\right\}\right)\right\}=\left\{\left(\phi(l_{v}^{(i)}),\left\{\phi(l_{u}^{(i)}):u\in\mathcal{N}(v)\right\}\right)\right\}$$

Thus, $\left\{h_{v}^{(i+1)}\right\}$ are the same. In particular, we have the same collection of GNN node features $\left\{h_{v}^{(k)}\right\}$ for $G_{1}$ and $G_{2}$. Because the graph level readout function is permutation invariant with respect to the collection of node features, $\mathcal{A}(G_{1})=\mathcal{A}(G_{2})$. Hence we have reached a contradiction. ∎

因而 $\left\{h_{v}^{(i+1)}\right\}$ 相同。特别地，$G_{1}$、$G_{2}$ 有相同的 GNN 节点特征集合 $\left\{h_{v}^{(k)}\right\}$。图级读出对节点特征集合置换不变，故 $\mathcal{A}(G_{1})=\mathcal{A}(G_{2})$，矛盾。∎

Appendix B Proof for Theorem 3

附录 B 定理 3 的证明

Proof.

Let $\mathcal{A}$ be a graph neural network where the condition holds. Let $G_{1}$, $G_{2}$ be any graphs which the WL test decides as non-isomorphic at iteration $K$. Because the graph-level readout function is injective, i.e., it maps distinct multiset of node features into unique embeddings, it sufficies to show that $\mathcal{A}$’s neighborhood aggregation process, with sufficient iterations, embeds $G_{1}$ and $G_{2}$ into different multisets of node features. Let us assume $\mathcal{A}$ updates node representations as

证明。

设 $\mathcal{A}$ 为满足条件的图神经网络。设 $G_{1}$、$G_{2}$ 为 WL 在第 $K$ 轮判定为非同构的任意图。因图级读出注入（把不同节点特征多重集映到唯一嵌入），只需证明：在足够轮次下，$\mathcal{A}$ 的邻域聚合把 $G_{1}$、$G_{2}$ 嵌入为不同的节点特征多重集。设 $\mathcal{A}$ 按