一、GIN [2019]

《How powerful are graph neural networks?》

1. 对图结构数据的学习需要有效地对图结构进行表示。最近，对图表示学习（graph representation learning）的图神经网络（Graph Neural Network: GNN）引起了人们的广泛兴趣。GNN 遵循递归邻域聚合方案，其中每个节点聚合其邻居的representation 向量从而计算节点的新的 representation 。

   已经有很多 GNN 的变体，它们采用不同的邻域聚合方法、graph-level 池化方法。从实验上看，这些 GNN 变体在很多任务（如节点分类、链接预测、图分类）中都达到了 SOTA 性能。但是，新的 GNN 的设计主要基于经验直觉（empirical intuition）、启发式（heuristics）、以及实验性（experimental）的反复试验。

   人们对 GNN 的性质和局限性的理论了解很少，对 GNN 的表达容量（representational capacity）的理论分析也很有限。论文 《How powerful are graph neural networks?》 提出了一个用于分析GNN 表达能力（representational power）的理论框架。作者正式刻画了不同 GNN 变体在学习表达（represent）和区分（distinguish）不同图结构上的表达能力（expressive）。

   论文的灵感主要来自于GNN 和 Weisfeiler-Lehman:WL 图同构检验（graph isomorphism test）之间的紧密联系。WL-test 是一种强大的、用于区分同构图的检验。类似于 GNN，WL-test 通过聚合其网络邻域的特征向量来迭代更新给定节点的特征向量。WL-test 如此强大的原因在于它的单射聚合更新（injective aggregation update），这可以将不同的节点邻域映射到不同的特征向量。

   单射函数：假设 $f$$f$ 是集合 $\mathbb{A}$$\mathbb A$ 到集合 $\mathbb{B}$$\mathbb B$ 的映射。如果所有 $x,y\in \mathbb{A}$$x,y\in \mathbb A$ 且 $x\ne y$$x\ne y$ 都有 $f(x)\ne f(y)$$f(x) \ne f(y)$ ，则称 $f$$f$ 是 从 $\mathbb{A}$$\mathbb A$ 到 $\mathbb{B}$$\mathbb B$ 的单射。

   论文的主要洞察是：如果 GNN 的聚合方案具有很高的表达能力（expressive）并且建模单射函数（injective function），那么 GNN 可以具有与 WL-test 一样强大的判别力（discriminative power）。

   为了从数学上形式化该洞察，论文的框架首先将给定节点的邻居的特征向量集合表示为 multiset，即可能包含重复元素的集合。可以将 GNN 中的邻域聚合视为 multiset 上的聚合函数（aggregation function over the multiset）。因此，为了具有强大的表征能力 ，GNN 必须能够将不同的 multiset 聚合为不同的representation。论文严格研究了multiset 函数的几种变体，并从理论上刻画了它们的判别能力，即不同的聚合函数如何区分不同的multiset。multiset 函数的判别力越强，则底层GNN 的表征能力就越强。然后论文设计出一种简单的架构 Graph Isomorphism Network: GIN，该架构被证明是 GNN 中最具表达能力的，并且和 WL-test 一样强大。

   论文在图分类数据集上进行实验来验证该理论，其中GNN 的表达能力对于捕获图结构至关重要。具体而言，作者比较了使用各种聚合函数的 GNN 的性能。实验结果证明了最强大的 GNN（即作者提出的 GIN）在实验中也具有很高的表征能力，因为它几乎完美拟合训练数据。而能力更弱的 GNN 变体通常对于训练数据严重欠拟合（underfit）。此外，GIN 在测试集上的准确率也超过了其它GNN 变体，并在图分类 benchmark上达到了 SOTA 性能。

   论文的主要贡献：

   • 证明GNN 在区分图结构方面最多和 WL-test 一样强大。

   • 给出邻域聚合函数和图readout 函数在什么条件下所得的 GNN 和 WL-test 一样强大。

   • 识别那些无法被主流的GNN 变体（如 GCN,GraphSAGE）判别的图结构，然后刻画这些 GNN-based 模型能够捕获的图结构。

   • 设计了一个简单的神经网络架构，即 Graph Isomorphism Network: GIN，并证明了其判别能力/表征能力等于 WL-test 。

2. 相关工作：尽管 GNN 在经验上取得成功，但是在数学上研究GNN 特性的工作很少。

   • 《Computational capabilities of graph neural networks》 表明：早期的 GNN 模型在概率上逼近测度函数。

   • 《Deriving neural architectures fromsequence and graph kernels》 表明：该论文提出的架构位于graph kernel 的 PKHS 中，但没有明确研究该架构可以区分哪些图。

   这些工作中的每一个都专注于特定的体系结构，并且不容易推广到多种体系结构。相反，我们的研究为分析和刻画一系列GNN 模型的表征能力提供了一个通用框架。

   另外，近期提出了一些基于 GNN 的体系结构大多数没有理论推导。与此相比，我们的 GIN 是有理论推导的，而且简单、强大。

1.1 GNN 模型

1. 我们首先总结一些常见的 GNN 模型。

2. 令图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V, \mathcal E)$ ，其中：

   • $\mathcal{V}=\{v_1,v_2,\cdots \}$$\mathcal V=\{v_1,v_2,\cdots\}$ 为节点集合。

   • $\mathcal{E}=\{e_{i,j}\}$$\mathcal E=\{e_{i,j}\}$ 为边集合，$e_{i,j}$$e_{i,j}$ 表示节点 $(v_i,v_j)$$(v_i,v_j)$ 之间的边。

   • 每个节点 $v\in \mathcal{V}$$v\in \mathcal V$ 关联一个节点特征向量 ${\overrightarrow{\mathbf{x}}}_v\in {\mathbb{R}}^d$$\mathbf{\vec x}_v\in \mathbb R^d$，其中 $d$$d$ 为特征向量维度。

   通常我们关心图上的两类任务：

   • 节点分类任务：每个节点 $v\in \mathcal{V}$$v\in \mathcal V$ 关联一个标签 $y_v\in \mathbb{R}$$y_v\in \mathbb R$ ，任务目标是学习节点 $v$$v$ 的一个representation 向量 ${\overrightarrow{\mathbf{h}}}_v$$\mathbf{\vec h}_v$ ，使得节点 $v$$v$ 的标签能够通过 $y_v=f\left({\overrightarrow{\mathbf{h}}}_v\right)$$y_v = f\left(\mathbf{\vec h}_v\right)$ 来预测。

   • 图分类任务：给定一组图 $\{{\mathcal{G}}_1,\cdots ,{\mathcal{G}}_N\}\subseteq \mathbb{G}$$\{\mathcal G_1,\cdots,\mathcal G_N\}\sube \mathbb G$ ，以及每个图的标签 $\{y_1,\cdots ,y_N\}\subseteq \mathcal{Y}$$\{y_1,\cdots,y_N\}\sube \mathcal Y$ ，任务目标是学习图 ${\mathcal{G}}_i$$\mathcal G_i$ 的一个representation 向量 ${\overrightarrow{\mathbf{h}}}_{{\mathcal{G}}_i}$$\mathbf{\vec h}_{\mathcal G_i}$ ，使得图 ${\mathcal{G}}_i$$\mathcal G_i$ 的标签能够通过 $y_i=g\left({\overrightarrow{\mathbf{h}}}_{{\mathcal{G}}_i}\right)$$y_i = g\left(\mathbf{\vec h}_{\mathcal G_i}\right)$ 来预测。

3. GNN 利用图结构和节点特征 ${\overrightarrow{\mathbf{x}}}_v$$\mathbf{\vec x}_v$ 来学习节点的representation 向量 ${\overrightarrow{\mathbf{h}}}_v$$\mathbf{\vec h}_v$ ，或者学习整个图的representation 向量 ${\overrightarrow{\mathbf{h}}}_{\mathcal{G}}$$\mathbf{\vec h}_{\mathcal G}$ 。

   现代 GNN 使用邻域聚合策略，在该策略中我们通过聚合邻域的representation 来迭代更新节点的 representation 。在经过 $k$$k$ 次迭代聚合之后，节点的representation 将捕获其 k-hop 邻域内的结构信息。

   以数学公式来讲，GNN 的第 $k$$k$ 层为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{a}}}_v^{(k)}={\text{AGG}}^{(k)}\left(\{{\overrightarrow{\mathbf{h}}}_u^{(k-1)},u\in {\mathcal{N}}_v\}\right)\\ {\overrightarrow{\mathbf{h}}}_v^{(k)}={\text{COMB}}^{(k)}({\overrightarrow{\mathbf{h}}}_v^{(k-1)},{\overrightarrow{\mathbf{a}}}_v^{(k)})\end{array}$$

   其中：

   • ${\overrightarrow{\mathbf{h}}}_v^{(k)}$$\mathbf{\vec h}_v^{(k)}$ 为节点 $v$$v$ 在第 $k$$k$ 层的 representation。另外 ${\overrightarrow{\mathbf{h}}}_v^{(0)}$$\mathbf{\vec h}_v^{(0)}$ 初始化为 ${\overrightarrow{\mathbf{x}}}_v$$\mathbf{\vec x}_v$ ，即 ${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{x}}}_v$$\mathbf{\vec h}_v^{(0)} =\mathbf{\vec x}_v$ 。

   • ${\mathcal{N}}_v$$\mathcal N_v$ 为节点 $v$$v$ 的直接邻居节点集合。

   • ${\text{AGG}}^{(k)}(\cdot )$$\text{AGG}^{(k)}(\cdot)$ 为第 $k$$k$ 层的聚合函数，${\text{COMB}}^{(k)}(\cdot )$$\text{COMB}^{(k)}(\cdot)$ 为第 $k$$k$ 层的拼接函数。

4. ${\text{AGG}}^{(k)}(\cdot ),{\text{COMB}}^{(k)}(\cdot )$$\text{AGG}^{(k)}(\cdot), \text{COMB}^{(k)}(\cdot)$ 的选择至关重要。已经提出了很多聚合函数：

   • 在 GraphSAGE 的最大池化变体中，聚合函数为：

     $${\overrightarrow{\mathbf{a}}}_v^{(k)}=max\left(\{\text{relu}\left({\mathbf{W}}_{\text{pool}}{\overrightarrow{\mathbf{h}}}_u^{(k-1)}\right),u\in {\mathcal{N}}_v\}\right)$$

     其中：

     • ${\mathbf{W}}_{\text{pool}}$$\mathbf W_{\text{pool}}$ 为可学习的参数矩阵，它是跨节点、跨层共享。

     • $max(\cdot )$$\max(\cdot)$ 为逐元素的最大池化。

     • $\text{relu}(\cdot )$$\text{relu}(\cdot)$ 为 relu 非线性激活函数。

     而 GraphSAGE 中的拼接函数为简单的向量拼接：

     $${\overrightarrow{\mathbf{h}}}_v^{(k)}={\mathbf{W}}^{(k)}[{\overrightarrow{\mathbf{h}}}_v^{(k-1)},{\overrightarrow{\mathbf{a}}}_v^{(k)}]$$

     其中 [,] 表示向量拼接，${\mathbf{W}}^{(k)}$$\mathbf W^{(k)}$ 为可学习的参数矩阵。

   • 在 Graph Convolutional Networks: GCN 中，聚合函数采用逐元素的均值池化。此时聚合函数、拼接函数整合在一起：

     $${\overrightarrow{\mathbf{h}}}_v^{(k)}=\text{relu}\left({\mathbf{W}}^{(k)}\text{MEAN}\left(\{{\overrightarrow{\mathbf{h}}}_u^{(k-1)},u\in {\mathcal{N}}_v\cup \{v\}\}\right)\right)$$

     其中 MEAN(.) 为逐元素的均值池化，${\mathbf{W}}^{(k)}$$\mathbf W^{(k)}$ 为可学习的参数矩阵。

5. 对于节点分类任务，节点 $v$$v$ 最后一层的representation ${\overrightarrow{\mathbf{h}}}_v^{(K)}$$\mathbf{\vec h}_v^{(K)}$ 就是节点 $v$$v$ 的 representation。

   对于图分类任务，READOUT 函数聚合所有节点最后一层的 representation 从而得到整个图的 representation ${\overrightarrow{\mathbf{h}}}_{\mathcal{G}}$$\mathbf{\vec h}_{\mathcal G}$ ：

   $${\overrightarrow{\mathbf{h}}}_{\mathcal{G}}=\text{READOUT}\left(\{{\overrightarrow{\mathbf{h}}}_v^{(K)},v\in \mathcal{V}\}\right)$$

   READOUT 函数可以是简单的排列不变函数（permutation invariant function），例如求和函数；也可以是更复杂的graph-level 池化函数。

1.2 WL-test

1. 图同构问题 （graph isomorphism problem）是判断两个图在拓扑结构上是否相同。这是一个具有挑战性的问题，尚不知道多项式时间（polynomial-time）的算法。

   除了某些极端情况之外，图同构的 Weisfeiler-Lehman(WL) test 是一种有效且计算效率高的算法，可用于各种类型的图。它的一维形式是 naïve vertex refinement ，它类似于 GNN 中的邻域聚合。

2. 在 WL-test 过程中，每个节点都分配一个label。注意：这里的 label 和分类任务中的label 不同，这里的 label 更多的表示“属性”， 而不是“监督信息”。

3. WL-test 对节点邻域进行反复迭代，最终根据两个图之间的节点label 是否完全相同，从而判断两个图是否同构的。

   WL-test 迭代过程如下：

   • 聚合节点及其邻域的 label 。

   • 将聚合后的label 经过哈希函数得到不同的、新的label ，即 relabel 。

   如下图所示：

   • 首先将图中每个节点初始化为 label = 1 。

   • 然后经过三轮迭代，最终：

     • 图1 具有 1 个label = 8、2 个 label = 7、2 个 label = 9 。

     • 图 2 具有1 个label = 8、2 个 label = 7、2 个 label = 9 。

     因此我们不排除图1 和图 2 同构的可能性。

   下图的哈希函数为：

   {1,1}   --> 2
   {1,1,1} --> 3
   {2,3}   --> 4
   {3,3}   --> 5
   {2,2,3} --> 6
   {4,6}   --> 7
   {6,6}   --> 8
   {4,5,6} --> 9
   

   注意：这里的 label 集合需要根据label 大小排序，并且每次哈希之后都需要分配一个新的 label 。

   

4. 《Weisfeiler-lehman graph kernels》 根据 WL-test 提出了 WL subtree kernel 来衡量两个图的相似性。核函数利用 WL tet 的不同迭代中使用的节点label 数作为图的特征向量。

   直观地讲，WL test 第 $k$$k$ 次迭代中节点 label 代表了以该节点为根的、高度为 $k$$k$ 的子树结构。因此 WL subtree kernel 考虑的图特征本质上是不同根子树的计数。

   如下图所示为一棵高度 $h=1$$h=1$ 的 WL subtree 。 这里 label = 8 的节点代表一棵高度为 1 的 subtree 模式，其中subtree 根节点的 label 为 2、包含label=3 和 label=5 的邻居节点。

   

1.3 模型

1. 我们首先概述我们的框架，下图说明了我们的思想：GNN 递归更新每个节点的representation 向量，从而捕获网络结构和邻域节点的representation ，即它的 rooted subtree 结构。

   在整篇论文中，我们假设：

   • 节点输入特征来自于可数的范围（countable universe）。

   • 模型的任何layer 的 representation 也是来自可数的范围。

   通常浮点数是不可数的，而整数是可数的。我们可以将浮点数离散化为整数，从而使得数值可数。

   为便于说明，我们为每个representation vector （输入特征向量是第0 层的 representation vector）分配唯一的 label，label 范围在 $\{a,b,c,\cdots \}$$\{a,b,c,\cdots\}$ 。即对于任意 ${\overrightarrow{\mathbf{h}}}_i^{(k)}\in {\mathbb{R}}^{d_k}$$\mathbf{\vec h}_i^{(k)}\in \mathbb R^{d_k}$ ，都为它分配一个 label $l\left({\overrightarrow{\mathbf{h}}}_i^{(k)}\right)\in \{a,b,c,\cdots \}$$l\left(\mathbf{\vec h}_i^{(k)}\right)\in \{a,b,c,\cdots\}$ ，其中 $l(\cdot )$$l(\cdot)$ 函数为双射函数。

   然后节点的邻域节点 representation vector 就构成一个 multiset ：由于不同的节点可以具有相同的 representation 向量，因此同一个 label 可以在 multiset 中出现多次。

   下图中：

   • 左图：一个图结构的数据。

   • 中图：rooted subtree 结构，用于在 WL test 中区分不同的图。

   • 右图：如果 GNN 聚合函数捕获节点邻域的 full multiset，则 GNN 能够以递归的方式捕获 rooted subtree 结构，从而和 WL test 一样强大。

   

2. multiset 定义：multiset 是 set 概念的推广，它允许包含相同的多个元素。正式地讲，，multiset 是一个 2-tuple $X=(S,m)$$X =( S,m)$ ，其中：

   • $S$$S$ 为底层的set ，它包含唯一（distinct）的元素。

   • $m:S\to {\mathbb{N}}_{\ge 1}$$m:S\rightarrow \mathbb N_{\ge 1}$ 给出这些元素的重复数量（multiplicity）。

3. 为研究 GNN 的表征能力，我们分析GNN 何时将两个节点映射到 embedding 空间中的相同位置。

   直观地看，能力强大的 GNN 仅在两个节点具有相同subtree 结构、且subtree 上相应节点具有相同特征的情况下才将两个节点映射到相同的位置。

   由于 subtree 结构是通过节点邻域递归定义的，因此我们可以将分析简化为：GNN 是否将两个邻域（即两个multiset）映射到相同的 embedding 或 representation 。

   能力强大的 GNN 绝对不会将两个不同的邻域（即representation 向量的 multiset）映射到相同的representation。这意味着聚合函数必须是单射函数。因此我们将 GNN 的聚合函数抽象为神经网络可以表示的、multiset 上的函数，并分析它们能否表示multiset 上的单射函数。

   接下来我们使用这种思路来设计能力最强的 GIN。最后我们研究了主流的 GNN 变体，发现它们的聚合函数本质上不是单射的因此能力较弱，但是它们能够捕获图的其它有趣的特性。

1.3.1 定理

1. 我们首先刻画 GNN-based 通用模型的最大表征能力。

   • 理想情况下，能力最强大的 GNN 可以通过将不同的图结构映射到 embedding 空间中不同的representation 来区分它们。这种将任意两个不同的图映射到不同 embedding 的能力意味着解决具有挑战性的图同构问题。即，我们希望将同构图映射到相同的 representation，将非同构图映射到不同的 representation 。

   • 在我们的分析中，我们通过一个稍弱的准则来刻画 GNN 的表征能力：一种强大（powerful）的、启发式（heuristic）的、称作 Weisfeiler-Lehman(WL) 的图同构测试（graph isomorphism test）。

     WL-test 通常工作良好，但是也有一些例外，如正规图（regular graph）。正规图是图中每个节点的 degree 都相同。如：立方体包含四个节点，每个节点的 degree 为 3，记作 4k3 。

2. 引理2 ：令 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1,\mathcal G_2$ 为任意两个非同构图（non-isomorphic graph）。如果一个图神经网络 $\mathcal{A}:\mathcal{G}\to {\mathbb{R}}^d$$\mathcal A:\mathcal G\rightarrow \mathbb R^d$ 将 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1,\mathcal G_2$ 映射到不同的 embedding，则 WL-test 也会判定 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1,\mathcal G_2$ 是非同构的。

   证明：这里采用反证法。

   假设经过 $k$$k$ 轮迭代之后，图神经网络 $\mathcal{A}$$\mathcal A$ 满足 $\mathcal{A}({\mathcal{G}}_1)\ne \mathcal{A}({\mathcal{G}}_2)$$\mathcal A(\mathcal G_1)\ne \mathcal A(\mathcal G_2)$ ，但是 WL-test 无法区分 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1,\mathcal G_2$ 是非同构的。这意味着在 WL-test 中从迭代0 到迭代 $k$$k$ ，${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1,\mathcal G_2$ 的节点 label collection 都相同。

   具体而言，${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1,\mathcal G_2$ 在第 $i$$i$ 轮迭代都具有相同的 label multiset $\left\{l_v^{(i)}\right\}$$\left\{l_v^{(i)}\right\}$、以及相同的节点邻域label 集合 $\left\{(l_v^{(i)},\{l_w^{(i)},w\in {\mathcal{N}}_v\})\right\}$$\left\{\left(l_v^{(i)},\left\{l_w^{(i)},w\in \mathcal N_v\right\}\right)\right\}$ 。其中 $l_v^{(i)}$$l_v^{(i)}$ 为节点 $v$$v$ 在 WL-test 第$i$$i$ 轮迭代中的 label 。否则WL-test 在第 $i+1$$i+1$ 轮迭代将具有不同的节点 label collection 从而区分出 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1, \mathcal G_2$ 是非同构的。

   现在我们证明：如果 $l_v^{(i)}=l_u^{(i)}$$l_v^{(i)} = l_u^{(i)}$，则有 ${\overrightarrow{\mathbf{h}}}_v^{(i)}={\overrightarrow{\mathbf{h}}}_u^{(i)}$$\mathbf{\vec h}_v^{(i)} = \mathbf{\vec h}_u^{(i)}$ ，其中 $v\in {\mathcal{G}}_1,u\in {\mathcal{G}}_2$$v\in \mathcal G_1,u\in \mathcal G_2$ 。我们用数学归纳法证明：

   • 当 $i=0$$i=0$ 时，结论显然成立。因为 WL-test 和 GNN 都使用节点的特征向量来初始化。如前所述，对于任意 ${\overrightarrow{\mathbf{h}}}_v^{(0)}\in {\mathbb{R}}^d$$\mathbf{\vec h}_v^{(0)}\in \mathbb R^{d }$ ，都为它分配一个 label $l_v^{(0)}=l\left({\overrightarrow{\mathbf{h}}}_v^{(0)}\right)\in \{a,b,c,\cdots \}$$l_v^{(0)} = l\left(\mathbf{\vec h}_v^{(0)}\right)\in \{a,b,c,\cdots\}$ ，其中 $l(\cdot )$$l(\cdot)$ 函数为双射函数。因此如果 $l_v^{(0)}=l_u^{(0)}$$l_v^{(0)} = l_u^{(0)}$ 则有 ${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{h}}}_u^{(0)}$$\mathbf{\vec h}_v^{(0)} = \mathbf{\vec h}_u^{(0)}$ 。

   • 假设对于第 $j$$j$ 次迭代成立。

   • 考虑第 $j+1$$j+1$ 次迭代：如果对于 $v\in {\mathcal{G}}_1,u\in {\mathcal{G}}_2$$v\in \mathcal G_1,u\in \mathcal G_2$ 有 $l_v^{(j+1)}=l_u^{(j+1)}$$l_v^{(j+1)} = l_u^{(j+1)}$ ，则有：

     $$(l_v^{(j)},\{l_w^{(j)},w\in {\mathcal{N}}_v\})=(l_u^{(j)},\{l_w^{(j)},w\in {\mathcal{N}}_u\})$$

     根据第 $j$$j$ 次迭代的假设，我们有：

     $$({\overrightarrow{\mathbf{h}}}_v^{(j)},\{{\overrightarrow{\mathbf{h}}}_w^{(j)},w\in {\mathcal{N}}_v\})=({\overrightarrow{\mathbf{h}}}_u^{(j)},\{{\overrightarrow{\mathbf{h}}}_w^{(j)},w\in {\mathcal{N}}_u\})$$

     由于两个图 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1, \mathcal G_2$ 采用同一个神经网络 $\mathcal{A}$$\mathcal A$ 来计算，因此它们使用相同的AGGREGATE 函数和 COMBINE 函数。因此相同的输入（如邻域特征）产生相同的输出。因此有：

     $${\overrightarrow{\mathbf{h}}}_v^{(j+1)}={\overrightarrow{\mathbf{h}}}_u^{(j+1)}$$

     因此第 $j+1$$j+1$ 次迭代成立。

   因此如果 WL-test 节点 label 满足 $l_v^{(i)}=l_u^{(i)}$$l_v^{(i)} = l_u^{(i)}$，则有 ${\overrightarrow{\mathbf{h}}}_v^{(i)}={\overrightarrow{\mathbf{h}}}_u^{(i)}$$\mathbf{\vec h}_v^{(i)} = \mathbf{\vec h}_u^{(i)}$ 对于任意迭代轮次 $i$$i$ 成立。因此对于 ${\mathcal{G}}_1$$\mathcal G_1$ 和 ${\mathcal{G}}_2$$\mathcal G_2$ ，它们具有相同的节点representation 集合 $\left\{{\overrightarrow{\mathbf{h}}}_v^{(k)}\right\}=\left\{{\overrightarrow{\mathbf{h}}}_u^{(k)}\right\}$$\left\{\mathbf{\vec h}_v^{(k)}\right\}=\left\{\mathbf{\vec h}_u^{(k)}\right\}$ 。由于 graph-level readout 函数对于节点representation 集合是排列不变的（permutation invariant），因此有 $\mathcal{A}({\mathcal{G}}_1)=\mathcal{A}({\mathcal{G}}_2)$$\mathcal A(\mathcal G_1) = \mathcal A(\mathcal G_2)$ ，矛盾。

3. 根据引理2，任何基于聚合的 GNN 在区分不同图结构方面最多和 WL-test 一样强大。

   一个自然的问题是：是否存在和 WL-test 一样强大的 GNN？在定理3 中，我们将证明：如果邻域聚合函数和 graph-level readout 函数是单射的，则得到的 GNN 和 WL-test 一样强大。

4. 定理3：令 $\mathcal{A}:\mathcal{G}\to {\mathbb{R}}^d$$\mathcal A:\mathcal G\rightarrow \mathbb R^d$ 为一个 GNN。在具有足够数量 GNN 层的条件下，如果满足以下条件，则 $\mathcal{A}$$\mathcal A$ 将 WL-test 判定为非同构的两个图 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1,\mathcal G_2$ 映射到不同的 embedding ：

   • $\mathcal{A}$$\mathcal A$ 通过以下方程递归地聚合和更新节点representation：

     $${\overrightarrow{\mathbf{h}}}_v^{(k)}=\varphi ({\overrightarrow{\mathbf{h}}}_v^{(k-1)},f\left(\{{\overrightarrow{\mathbf{h}}}_u^{(k-1)},u\in {\mathcal{N}}_v\}\right))$$

     其中 $f(\cdot )$$f(\cdot)$ 函数、$\varphi (\cdot )$$\phi(\cdot)$ 函数都是单射函数。且 $f(\cdot )$$f(\cdot)$ 作用在 multiset 上。

   • $\mathcal{A}$$\mathcal A$ 的 graph-level readout 函数是单射函数。其中 readout 函数作用在节点embedding multiset $\left\{{\overrightarrow{\mathbf{h}}}_v^{(k)}\right\}$$\left\{\mathbf{\vec h}_v^{(k)}\right\}$ 上。

   证明：令 $\mathcal{A}$$\mathcal A$ 是满足条件的图神经网络。令 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1, \mathcal G_2$ 为任意两个图，其中 WL-test 在 $K$$K$ 次迭代后判定它们是非同构的。

   我们假设 $\mathcal{A}$$\mathcal A$ 更新节点的 representation 为：

   $${\overrightarrow{\mathbf{h}}}_v^{(k)}=\varphi ({\overrightarrow{\mathbf{h}}}_v^{(k-1)},f\left(\{{\overrightarrow{\mathbf{h}}}_u^{(k-1)},u\in {\mathcal{N}}_v\}\right))$$

   其中 $f(\cdot ),\varphi (\cdot )$$f(\cdot),\phi(\cdot)$ 都是单射函数。

   假设 WL-test 应用一个预定义的单射函数 $g(\cdot )$$g(\cdot)$ 来更新节点 label：

   $$l_v^{(k)}=g(l_v^{(k-1)},\{l_u^{(k-1)},u\in {\mathcal{N}}_v\})$$

   其中 $g(\cdot )$$g(\cdot)$ 不是从数据中学习，而是预定义的。

   接下来我们通过数学归纳法证明：对于任意迭代轮次 $k$$k$ ，存在一个单射函数 ${\phi }^{(k)}$$\varphi^{(k)}$ ，使得 ${\overrightarrow{\mathbf{h}}}_v^{(k)}={\phi }^{(k)}\left(l_v^{(k)}\right)$$\mathbf{\vec h}_v^{(k)} = \varphi^{(k)}\left(l_v^{(k)}\right)$ 。

   • 当 $k=0$$k=0$ 时结论显然成立。因为 WL-test 和 GNN 都使用节点的特征向量来初始化。如前所述，对于任意 ${\overrightarrow{\mathbf{h}}}_v^{(0)}\in {\mathbb{R}}^d$$\mathbf{\vec h}_v^{(0)}\in \mathbb R^{d }$ ，都为它分配一个 label $l_v^{(0)}=l\left({\overrightarrow{\mathbf{h}}}_v^{(0)}\right)\in \{a,b,c,\cdots \}$$l_v^{(0)} = l\left(\mathbf{\vec h}_v^{(0)}\right)\in \{a,b,c,\cdots\}$ ，其中 $l(\cdot )$$l(\cdot)$ 函数为双射函数。因此如果 $l_v^{(0)}=l_u^{(0)}$$l_v^{(0)} = l_u^{(0)}$ 则有 ${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{h}}}_u^{(0)}$$\mathbf{\vec h}_v^{(0)} = \mathbf{\vec h}_u^{(0)}$ 。此时 ${\phi }^{(0)}=l^{-1}$$\varphi^{(0)}=l^{-1}$ ，即 $l(\cdot )$$l(\cdot)$ 这个双射函数的反函数。

   • 假设对于 $k-1$$k-1$ 时也成立。

   • 现在考虑第 $k$$k$ 次迭代。根据：

     $${\overrightarrow{\mathbf{h}}}_v^{(k)}=\varphi ({\phi }^{(k-1)}\left(l_v^{(k-1)}\right),f\left(\{{\phi }^{(k-1)}\left(l_u^{(k-1)}\right),u\in {\mathcal{N}}_v\}\right))$$

     由于单射函数的复合函数也是单射函数，因此存在某个单射函数 ${\psi }^{(k-1)}$$\psi^{(k-1)}$ ，使得：

     $${\overrightarrow{\mathbf{h}}}_v^{(k)}={\psi }^{(k-1)}(l_v^{(k-1)},\{l_u^{(k-1)},u\in {\mathcal{N}}_v\})$$

     则有：

     $${\overrightarrow{\mathbf{h}}}_v^{(k)}={\psi }^{(k-1)}\circ g^{-1}g(l_v^{(k-1)},\{l_u^{(k-1)},u\in {\mathcal{N}}_v\})={\psi }^{(k-1)}\circ g^{-1}\left(l_v^{(k)}\right)$$

     因此复合函数 ${\phi }^{(k)}={\psi }^{(k-1)}\circ g^{-1}$$\varphi^{(k)} = \psi^{(k-1)}\circ g^{-1}$ 就是我们想要的单射函数。因此第 $k$$k$ 轮迭代成立。

   因此对于任意迭代轮次 $k$$k$ ，总是存在单射函数 $\phi$$\varphi$ 使得 ${\overrightarrow{\mathbf{h}}}_v^{(k)}={\phi }^{(k)}\left(l_v^{(k)}\right)$$\mathbf{\vec h}_v^{(k)} = \varphi^{(k)}\left(l_v^{(k)}\right)$ 。

   经过 $K$$K$ 次迭代之后，WL-test 判定 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1, \mathcal G_2$ 是非同构的，这意味着 ${\mathcal{G}}_1$$\mathcal G_1$ 和 ${\mathcal{G}}_2$$\mathcal G_2$ 的 label multiset $\left\{l_v^{(K)}\right\}$$\left\{l_v^{(K)}\right\}$ 不同。则由于函数 ${\phi }^{(K)}$$\varphi^{(K)}$ 的单射性（injectivity）， ${\mathcal{G}}_1$$\mathcal G_1$ 和 ${\mathcal{G}}_2$$\mathcal G_2$ 的节点 embedding 集合 $\left\{{\overrightarrow{\mathbf{h}}}_v^{(K)}\right\}=\left\{{\phi }^{(K)}\left(l_v^{(K)}\right)\right\}$$\left\{\mathbf{\vec h}_v^{(K)}\right\}= \left\{\varphi^{(K)} \left(l_v^{(K)}\right)\right\}$ 也是不同的。

5. 对于可数集，单射性（injectiveness）很好地描述了一个函数是否保持输入的唯一性（distinctness）。节点输入特征是连续的不可数集则需要进一步考虑。

   此外，刻画学到的 representation 在 embedding 空间中的邻近程度（如果两个 embedding 不相等的话）也很有意义。我们将这些问题留待以后的工作，本文重点放在输入节点特征来自可数集的情况，并仅考虑输出 representation 相等/不等的情况。

6. 引理 4 ：假设输入特征空间 $\mathcal{X}$$\mathcal X$ 是可数的。令 $g^{(k)}(\cdot )$$g^{(k)}(\cdot)$ 为GNN 第 $k$$k$ 层可学习的函数， $k=1,\cdots ,L$$k=1,\cdots,L$ 。且 $g^{(1)}$$g^{(1)}$ 是定义在 size 有界的multiset $X\subset \mathcal{X}$$X\sub \mathcal X$ 上的函数。则 $g^{(k)}(\cdot )$$g^{(k)}(\cdot)$ 的输出空间（即节点 representation ${\overrightarrow{\mathbf{h}}}_v^{(k)}$$\mathbf{\vec h}_v^{(k)}$）也是可数的。

   证明：证明之前我们先给出一个众所周知的结论，然后将其简化：对于任意 $k\in \mathbb{N}$$k\in \mathbb N$ ，${\mathbb{N}}^k$$\mathbb N^k$ 是可数的。即：有限个可数集的笛卡尔积是可数的。我们观察到 $\mathbb{N}\times \mathbb{N}$$\mathbb N\times \mathbb N$ 是可数的，因为从归纳中可以清楚地得到证明。为了表明 $\mathbb{N}\times \mathbb{N}$$\mathbb N\times \mathbb N$ 是可数的，我们构造了一个双射函数 $\varphi$$\phi$ 从 $\mathbb{N}\times \mathbb{N}\to \mathbb{N}$$\mathbb N\times \mathbb N\rightarrow \mathbb N$ ：

   $$\varphi (a,b)=2^{a-1}\times (2b-1)$$

   现在回到我们的的引理证明。如果我们可以证明在可数集上的、size 有限的 multiset 上定义的任何函数 $g(\cdot )$$g(\cdot)$ 的值域（range）也是可数的，则对于任意 $g^{(k)}(\cdot )$$g^{(k)}(\cdot)$ 上述引理成立。

   现在我们的目标是证明 $g(\cdot )$$g(\cdot)$ 的值域是可数的。

   首先，因为 $g(\cdot )$$g(\cdot)$ 是神经网络layer 定义良好（well-defined）的函数，因此很明显 $g(X)\to X$$g(X) \rightarrow X$ 的映射是单射函数。这足以表明所有的 multiset $X\subset \mathcal{X}$$X\sub \mathcal X$ 是可数的。

   由于两个可数集的并集也是可数的，因此 ${\mathcal{X}}^{\prime }=\mathcal{X}\cup \{e\}$$\mathcal X^\prime = \mathcal X\cup\{e\}$ 也是可数的，其中 $e$$e$ 为 dummy 元素且不在 $\mathcal{X}$$\mathcal X$ 中。

   正如 ${\mathbb{N}}^k$$\mathbb N^k$ 是可数的，则 ${\mathcal{X}}^{\prime k}$$\mathcal X^{\prime \;k}$ 也是可数的。则存在一个单射函数，对于某个 $k\in \mathbb{N}$$k\in \mathbb N$ ，它将 $\mathcal{X}$$\mathcal X$ 中的 multiset 的集合映射到 ${\mathcal{X}}^{\prime k}$$\mathcal X^{\prime\; k}$ 。 我们如下构建这个单射函数：

   • 由于 $\mathcal{X}$$\mathcal X$ 是可数的，因此存在一个映射 $Z:\mathcal{X}\to \mathbb{N}$$Z:\mathcal X\rightarrow \mathbb N$ 使得将 $x\in \mathcal{X}$$x\in \mathcal X$ 映射到自然数。

   • 我们对于 $x\in X$$x\in X$ 中所有元素按照 $z(x)$$z(x)$ 排序，假设结果为 $x_1,\cdots ,x_n$$x_1,\cdots,x_n$ ，其中 $n=|X|$$n=|X|$ 。

   • 由于 multiset $X$$X$ 是size 有界，则存在 $k\in \mathbb{N}$$k\in \mathbb N$ ，使得 $|X|<k$$|X|\lt k$ 对于所有 $X$$X$ 成立。然后我们定义 $h(\cdot )$$h(\cdot)$ 为：

     $$h(X)=(x_1,x_2,\cdots ,x_n,e,e,\cdots )$$

     其中最后 $k-n$$k-n$ 个元素填充 dummy element $e$$e$ 。

   显然 $h(\cdot )$$h(\cdot)$ 是单射函数，因为对于任意 size 有界的 multiset $X$$X$ 和 $Y$$Y$，仅当 $X=Y$$X=Y$ 时 $h(X)=h(Y)$$h(X) = h(Y)$ 。因此 $g(\cdot )$$g(\cdot)$ 的值域是可数的。

7. 这里还值得讨论 GNN 在图结构判别能力上的一个重要优点，即：捕获图结构的相似性。

   • WL-test 中的节点特征向量本质上是one-hot 编码，因此无法捕获 subtree 之间的相似性。

   • 相反，满足定理3 条件的 GNN 将 subtree 嵌入到低维空间来推广WL-test。这使得 GNN 不仅可以区分不同的结构，还可以学习将相似的图结构映射到相似的 embedding 从而捕获不同图结构之间的依赖关系。

     捕获node label 的结构相似性有助于泛化（generalization），尤其是当subtree 的共现（co-occurrence）很稀疏时、或者存在边噪音和/或节点特征噪音时。

1.3.2 GIN

1. 在研究出能力最强的 GNN 的条件之后，我们接下来将设计一种简单的架构，即图同构网络 （Graph Isomorphism Network: GIN）。可以证明GIN 满足定理3 中的条件。

   GIN 将 WL-test 推广从而实现了 GNN 的最大判别力。

2. 为建模用于邻居聚合的 multiset 单射函数，我们研究了一种 deep multiset 理论，即：使用神经网络对 multiset 函数进行参数化。

   我们的下一个引理指出：sum 聚合实际上可以表示为 multiset 上的通用单射函数。

3. 引理5：假设输入特征空间 $\mathcal{X}$$\mathcal X$ 是可数的。存在一个函数 $f:\mathcal{X}\to {\mathbb{R}}^n$$f:\mathcal X\rightarrow \mathbb R^n$ ，使得 $h(X)=\sum _{x\in X}f(x)$$h(X) = \sum_{ x\in X} f(x)$ 对于每个有界size 的 multiset $X\subset \mathcal{X}$$X\sub \mathcal X$ 是唯一的（unique）。进一步地，任何 multiset 函数 $g(\cdot )$$g(\cdot)$ 可以分解为： $g(X)=\varphi (\sum _{x\in X}f(x))$$g(X) = \phi\left(\sum_{x\in X} f(x)\right)$ ，其中 $\varphi (\cdot )$$\phi(\cdot)$ 为某个函数。

   证明：我们首先证明存在一个映射 $f$$f$ ，使得 $h(X)=\sum _{x\in X}f(x)$$h(X) = \sum_{x\in X} f(x)$ 对于每个有界size 的 multiset $X$$X$ 是唯一的 。

   由于 $\mathcal{X}$$\mathcal X$ 是可数的，因此存在一个映射 $Z:\mathcal{X}\to \mathbb{N}$$Z:\mathcal X\rightarrow \mathbb N$ 使得将 $x\in \mathcal{X}$$x\in \mathcal X$ 映射到自然数。因为 multiset $X$$X$ 的基（cardinality）是有界的，则存在自然数 $N\in \mathbb{N}$$N\in \mathbb N$ 使得对于所有 $X$$X$ 都有 $|X|<N$$|X|\lt N$ 成立。因此我们可以选择 $f$$f$ 为：$f(x)=N^{-Z(x)}$$f(x) = N^{-Z(x)}$ 。 可以将这个 $f$$f$ 视为 one-hot 向量或 N-digit 数字的压缩表示。因此 $h(X)=\sum _{x\in X}f(x)$$h(X) = \sum_{x\in X} f(x )$ 为 multiset 的单射函数。

   $\varphi (\sum _{x\in X}f(x))$$\phi\left(\sum_{x\in X} f(x)\right)$ 是排列不变的 （permutation invariant），因此它是定义良好的 （well-defined）的multiset 函数。对于任意 multiset 函数 $g(\cdot )$$g(\cdot)$ ，我们可以通过让 $\varphi (\sum _{x\in X}f(x))=g(X)$$\phi\left(\sum_{x\in X} f(x)\right)=g(X)$ 来构建这样的 $\varphi$$\phi$ 。现在这样的 $\varphi$$\phi$ 是定义良好的，因为 $h(X)=\sum _{x\in X}f(x)$$h(X) = \sum_{x\in X} f(x )$ 是单射函数。

4. 引理5 将 《Deep sets》中的结论从 set 扩展到 multiset 。deep multiset 和 deep set 之间的重要区别是：某些流行的 set 单射函数 （如均值聚合）不再是 multiset 单射函数。

   通过将引理5 中的通用 multiset 函数建模机制作为构建块 （building block），我们可以设想一个聚合方案，该方案可以表示单个节点及其邻域的 multiset 上的通用函数，因此满足定理3 中的第一个条件。

   我们的下一个推论是在所有这些聚合方案中选择一个简单而具体的形式。

5. 推论6：假设 $\mathcal{X}$$\mathcal X$ 是可数的。存在一个函数 $f:\mathcal{X}\to {\mathbb{R}}^n$$f:\mathcal X\rightarrow \mathbb R^n$ ，使得无限多的选择 $ϵ$$\epsilon$ （包括无理数），$h(c,X)=(1+ϵ)\times f(c)+\sum _{x\in X}f(x)$$h(c,X) = (1+\epsilon)\times f(c) + \sum_{x\in X}f(x)$ 对于每个pair 对 $(c,X)$$(c,X)$ 都是唯一的（unique），其中 $c\in \mathcal{X}$$c\in \mathcal X$ ， 有界size 的 multiset $X\subset \mathcal{X}$$X\sub \mathcal X$ 。更进一步地，任何定义在这种 pair 上的函数 $g(\cdot )$$g(\cdot)$ 可以分解为： $g(c,X)=\phi ((1+ϵ)\times f(c)+\sum _{x\in X}f(x))$$g(c,X) = \varphi\left((1+\epsilon)\times f(c)+ \sum_{x\in X} f(x)\right)$ ，其中 $\phi (\cdot )$$\varphi(\cdot)$ 为某个函数。

   证明：接着推论5 的证明过程，我们考虑 $f(x)=N^{-Z(x)}$$f(x) = N^{-Z(x)}$ ，其中 $N$$N$ 和 $Z$$Z$ 的定义延续推论 5 。

   令 $h(c,X)=(1+ϵ)\times f(c)+\sum _{x\in X}f(x)$$h(c,X)=(1+\epsilon)\times f(c) + \sum_{x\in X}f(x)$ 。我们的目标是当 $ϵ$$\epsilon$ 是一个无理数时，对于任意 $(c^{\prime },X^{\prime })\ne (c,X)$$(c^\prime,X^\prime)\ne (c,X)$ 有 $h(x,X)\ne h(c^{\prime },X^{\prime })$$h(x,X)\ne h(c^\prime,X^\prime)$ 成立，其中 $c,c^{\prime }\in \mathcal{X}$$c,c^\prime \in\mathcal X$ ， $X,X^{\prime }\subset \mathcal{X}$$X,X^\prime \sub \mathcal X$ 。

   我们用反证法证明。

   对于任意 $(c,X)$$(c,X)$ ，假设存在 $(c^{\prime },X^{\prime })$$(c^\prime,X^\prime)$ 使得 $(c^{\prime },X^{\prime })\ne (c,X)$$(c^\prime,X^\prime)\ne (c,X)$ 但是 $h(x,X)=h(c^{\prime },X^{\prime })$$h(x,X)= h(c^\prime,X^\prime)$ 成立。考虑以下两种情况：

   • $c^{\prime }=c,X^{\prime }\ne X$$c^\prime=c,X^\prime\ne X$ ：

     此时$h(c,X)=h(c^{\prime },X^{\prime })$$h(c,X)= h(c^\prime,X^\prime)$ 意味着 $\sum _{x\in X}f(x)=\sum _{x\in X^{\prime }}f(x)$$\sum_{x\in X}f(x) = \sum_{x\in X^\prime} f(x)$ 。

     根据推论5 该等式不成立，因为 $f(x)=N^{-Z(x)}$$f(x) = N^{-Z(x)}$ 以及 $X^{\prime }\ne X$$X^\prime\ne X$ 意味着 $\sum _{x\in X}f(x)\ne \sum _{x\in X^{\prime }}f(x)$$\sum_{x\in X}f(x) \ne \sum_{x\in X^\prime} f(x)$。因此矛盾。

   • $c^{\prime }\ne c$$c^\prime\ne c$ ：

     我们重写 $h(c,X)=h(c^{\prime },X^{\prime })$$h(c,X) = h(c^\prime,X^\prime)$ 为：

     $$ϵ\times (f(c)-f(c^{\prime }))=(f(c^{\prime })+\sum _{x\in X^{\prime }}f(x))-(f(c)+\sum _{x\in X}f(x))$$

     因为 $ϵ$$\epsilon$ 是一个无理数，而 $f(c)-f(c^{\prime })$$f(c)-f(c^\prime)$ 是一个非零的有理数，因此上式左侧为一个无理数。由于有限个有理数的和还是有理数，因此上式右侧为有理数。因此上式不成立，矛盾。

   对于定义在 $(c,X)$$(c,X)$ 上的任意函数 $g(\cdot )$$g(\cdot)$ ，我们可以通过 $\phi ((1+ϵ)\times f(c)+\sum _{x\in X}f(x))=g(c,X)$$\varphi\left((1+\epsilon)\times f(c)+ \sum_{x\in X} f(x)\right) =g(c,X)$ 来构建这样的 $\phi$$\varphi$ 。

   注意：这样的 $\phi$$\varphi$ 是定义良好的（well-defined），因为 $h(c,X)=(1+ϵ)\times f(c)+\sum _{x\in X}f(x)$$h(c,X) = (1+\epsilon)\times f(c)+ \sum_{x\in X} f(x)$ 是单射函数。

6. 由于通用逼近定理（universal approximation theorem），我们可以使用多层感知机 （multi-layer perceptrons:MLPs）来建模和学习推论6 中的函数 $f$$f$ 和 $\phi$$\varphi$ 。

   实际上我们使用一个 MLP 来建模 $f^{(k+1)}\circ {\phi }^{(k)}$$f^{(k+1)}\circ\varphi^{(k)}$ ，因为MLPs 可以表示组合函数。

   • 在第一轮迭代中，如果输入特征是 one-hot 编码，则在求和之前不需要 MLP ，因为它们的求和本身就是单射的。

     即：

     $${\overrightarrow{\mathbf{h}}}_v^{(1)}=(1+{ϵ}^{(1)})\times {\overrightarrow{\mathbf{x}}}_v^{(0)}+\sum _{u\in {\mathcal{N}}_v}{\overrightarrow{\mathbf{x}}}_u^{(0)}$$

   • 我们将 $ϵ$$\epsilon$ 作为一个可学习的参数或者一个固定的标量。然后 GIN 的节点representation 更新方程为：

   $${\overrightarrow{\mathbf{h}}}_v^{(k)}={\text{MLP}}^{(k)}((1+{ϵ}^{(k)})\times {\overrightarrow{\mathbf{h}}}_v^{(k-1)}+\sum _{u\in {\mathcal{N}}_v}{\overrightarrow{\mathbf{h}}}_u^{(k-1)}),k\ne 1$$

   通常而言，可能存在很多其它强大的 GNN。GIN 是这些能力强大的 GNN 中的一个简单的例子。

7. GIN 学到的节点 embedding 可以直接用于诸如节点分类、链接预测之类的任务。对于图分类任务，我们提出以下 readout 函数，该函数可以在给定每个节点embedding 的情况下生成整个图的 embedding 。

   关于graph-level readout 函数的一个重要方面是：对应于 subtree 结构的 node embedding 随着迭代次数的增加而越来越精细化（refine）和全局化（global）。足够数量的迭代是获得良好判别力的关键，但是早期迭代的representation 可能会泛化能力更好。

   为了考虑所有结构信息，我们使用来自模型所有深度的信息。我们通过类似于 Jumping Knowledge Networks 的架构来实现这一点。在该架构体系中，我们将 GIN 所有层的 representation 拼接在一起：

   $${\overrightarrow{\mathbf{h}}}_{\mathcal{G}}=\text{CONCAT}(\text{READOUT}\left(\{{\overrightarrow{\mathbf{h}}}_v^{(k)},v\in \mathcal{V}\}\right),k=0,1,\cdots ,K)$$

   通过定理3 和推论6，如果 GIN 使用求和函数（求和针对相同迭代轮次中所有节点的 representation 进行）替代了上式中的 READOUT （因为求和本身就是单射函数，因此在求和之前不必添加额外的 MLP ），它就可证明地（provably）推广了 WL-test 和 WL subtree kernel 。

1.4 Less Powerfull GNN

1. 现在我们研究不满足定理3 中条件的 GNN，包括 GCN、GraphSAGE。另外，我们对 GIN 的聚合器的两个方面进行消融研究：

   • 单层感知机代替多层感知机MLP 。

   • 均值池化或最大池化代替求和。

   我们将看到：这些 GNN 变体无法区分很简单的图，并且比 WL-test 能力更差。尽管如此，具有均值聚合的模型（如 GCN）在节点分类任务中仍然表现良好。为了更好地理解这一点，我们精确地刻画了哪些 GNN 变体可以捕获或无法捕获图结构，并讨论了图学习的意义。

1.4.1 单层感知机

1. 引理 5 中的函数 $f(\cdot )$$f(\cdot)$ 帮助将不同的 multiset 映射到唯一的 embedding 。

   MLP 可以通过通用逼近定理对 $f(\cdot )$$f(\cdot)$ 进行参数化，然而许多现有的 GNN 改为使用单层感知机 $\sigma \circ \mathbf{W}$$\sigma\circ \mathbf W$：先使用一个线性映射，然后接一个非线性激活函数（如 relu）。这种单层映射是广义线性模型（Generalized Linear Models）的示例。

   因此，我们有兴趣了解单层感知机是否足以进行图学习。引理7 表明：确实存在使用单层感知机的图模型永远无法区分的网络邻域（multiset ）。

2. 引理7：存在有限size 的 multiset $X_1\ne X_2$$X_1\ne X_2$ ，使得任意线性映射 $W$$W$ ，有：

   $$\sum _{\mathbf{x}\in X_1}\text{relu}\left(Wx\right)=\sum _{\mathbf{x}\in X_2}\text{relu}\left(Wx\right)$$

   证明：考虑示例 $X_1=\{1,1,1,1,1\}$$X_1=\{1,1,1,1,1\}$ 以及 $X_2=\{2,3\}$$X_2=\{2,3\}$，即两个不同的 、包含正数的multiset，但是它们的sum 结果相同。我们将使用 ReLU 的同质性（homogeneity）。

   令 $W$$W$ 为任意一个线性映射，它将 $x\in X_1,X_2$$x\in X_1,X_2$ 映射到 $\mathbb{R}$$\mathbb R$ 。显然，由于 $X_1,X_2$$X_1,X_2$ 中的元素都为正数：

   • 如果 $W>0$$W\gt 0$ ，则 $Wx>0,x\in X_1\cup X_2$$Wx\gt 0, x\in X_1\cup X_2$ 。此时 $\text{relu}(Wx)=Wx$$\text{relu}(Wx) = Wx$ ，$\sum _{\mathbf{x}\in X_1}\text{relu}\left(Wx\right)=\sum _{\mathbf{x}\in X_2}\text{relu}\left(Wx\right)$$\sum_{\mathbf{x}\in X_1}\text{relu}\left(W x \right) = \sum_{\mathbf{x}\in X_2}\text{relu}\left(Wx \right)$ 。

   • 如果 $W<0$$W\lt 0$ ，则 $Wx<0,x\in X_1\cup X_2$$Wx\lt 0, x\in X_1\cup X_2$ 。此时 $\text{relu}(Wx)=0$$\text{relu}(Wx) =0$ 。$\sum _{\mathbf{x}\in X_1}\text{relu}\left(Wx\right)=\sum _{\mathbf{x}\in X_2}\text{relu}\left(Wx\right)$$\sum_{\mathbf{x}\in X_1}\text{relu}\left(W x \right) = \sum_{\mathbf{x}\in X_2}\text{relu}\left(Wx \right)$ 。

   • 如果 $W=0$$W=0$，则 $Wx=0,x\in X_1\cup X_2$$Wx=0,x\in X_1\cup X_2$ 。此时 $\text{relu}(Wx)=0$$\text{relu}(Wx) =0$ 。$\sum _{\mathbf{x}\in X_1}\text{relu}\left(Wx\right)=\sum _{\mathbf{x}\in X_2}\text{relu}\left(Wx\right)$$\sum_{\mathbf{x}\in X_1}\text{relu}\left(W x \right) = \sum_{\mathbf{x}\in X_2}\text{relu}\left(Wx \right)$ 。

   因此得到：$\sum _{\mathbf{x}\in X_1}\text{relu}\left(Wx\right)=\sum _{\mathbf{x}\in X_2}\text{relu}\left(Wx\right)$$\sum_{\mathbf{x}\in X_1}\text{relu}\left(W x \right) = \sum_{\mathbf{x}\in X_2}\text{relu}\left(Wx \right)$ 。

3. 引理7 的证明的主要思想是：单层感知机的行为和线性映射非常相似。因此 GNN 层退化为简单地对邻域特征进行求和。我们的证明基于以下事实：线性映射中缺少偏置项。使用偏置项和足够大的输出维度，单层感知机可能区分不同的 multiset。

   尽管如此，和使用 MLP 的模型不同，单层感知机（即使带有偏置项）也不是 multiset 函数的通用逼近器。因此，即使具有单层感知机的 GNN 可以在不同程度上将不同的图嵌入到不同的位置，此类embedding 也可能无法充分捕获结构相似性，并且可能难以拟合简单的分类器（如线性分类器）。

   在实验中，我们观察到带单层感知机的 GNN 应用于图分类时，有时对于训练数据严重欠拟合（underfit）。并且在测试集准确率方面要比带 MLP 的 GNN 更差。

1.4.2 均值池化和最大池化

1. 如果我们把 $h(X)=\sum _{x\in X}f(x)$$h(X) = \sum_{x\in X} f(x)$ 中的求和替换为均值池化或最大池化，就像 GCN、GraphSAGE 中的那样，结果会如何？

   均值池化和最大池化仍然是 multiset 上定义良好的函数，因为它们是排列不变的（permutation invariant）。但是，它们不是单射函数。

   下图按照表征能力对这三种聚合器（sum/mean/max 聚合器）进行排名（rank）。左图给出了输入的 multiset，即待聚合的网络邻域。后面的三幅图说明了给定的聚合器能够捕获 multiset 的哪个方面：

   • sum 捕获了完整的multiset。

   • mean 捕获了给定类型的元素的比例/分布。

   • max 忽略了多重性（multiplicity），将multiset 简化为简单的 set 。

   

2. 下图说明了 mean 池化和 max 池化无法区分的一对图结构。这里节点颜色表示不同的节点特征，我们假设 GNN 首先将邻域聚合在一起，然后再将它们与标记为 $v$$v$ 和 $v^{\prime }$$v^\prime$ 的中心节点结合（combine）在一起。

   在两个图之间，节点 $v$$v$ 和 $v^{\prime }$$v^\prime$ 获得相同的 embedding，即使它们的图结构是不同的。如前所述：sum 捕获了完整的multiset；mean 捕获了给定类型的元素的比例/分布；max 忽略了多重性 （multiplicity），将multiset 简化为简单的 set 。

   • 图 (a) 给出均值池化和最大池化都无法区分的图。这表明：均值池化和最大池化无法区分所有节点特征都相同的图。

   • 图 (b) 给出最大池化无法区分的图。令 $h_r$$h_r$ 和 $h_g$$h_g$ （r 表示红色、g 表示绿色） 为 $f(\cdot )$$f(\cdot)$ 转换得到的节点特征。该结果表明：在蓝色节点 $v$$v$ 和 $v^{\prime }$$v^\prime$ 邻域上的max 池化：$max(h_g,h_r)$$\max(h_g,h_r)$、$max(h_g,h_r,h_r)$$\max(h_g,h_r,h_r)$ 将坍缩（collapse）到相同的 representation（即使对应的图结构不同）。因此最大池化也无法区分它们。

     相反，均值池化是有效的，因为 $\frac{1}{2}(h_g+h_r)$$\frac 12(h_g+h_r)$ 和 $\frac{1}{3}(h_g+h_r+h_r)$$\frac 13(h_g+h_r+h_r)$ 通常不相等。

   • 图(c) 给出均值池化和最大池化都无法区分的图。这表明：均值池化和最大池化无法区分节点特征分布相同的图。因为：

     $$\begin{array}{c}\frac{1}{2}(h_g+h_r)=\frac{1}{4}(h_g+h_g+h_r+h_r)\\ max(h_g,h_r)=max(h_g,h_g,h_r,h_r)\end{array}$$

     

a. 均值池化

1. 为了刻画均值聚合器能够区分的 multiset 类型，考虑两个multiset ：$X_1=(S,m)$$X_1=(S,m)$ 以及 $X_2=(S,k\times m)$$X_2=(S,k\times m)$ ，其中 $X_1$$X_1$ 和 $X_2$$X_2$ 具有相同（distinct）的元素，但是 $X_2$$X_2$ 中每个元素的数量都是 $X_1$$X_1$ 中数量的 $k$$k$ 倍。任何均值聚合器都将 $X_1$$X_1$ 和 $X_2$$X_2$ 映射到相同的 embedding，因为均值聚合器只是对各元素特征取均值。

   因此，均值聚合器捕获的是multiset 中元素的分布（比例），而不是捕获确切的 multiset 本身。

2. 推论8：假设 $\mathcal{X}$$\mathcal X$ 是可数的。则存在函数 $f:\mathcal{X}\to {\mathbb{R}}^n$$f:\mathcal X\rightarrow \mathbb R^n$ ，使得对于 $h(X)=\frac{1}{|X|}\sum _{x\in X}f(x)$$h(X) = \frac{1}{|X|}\sum_{x\in X}f(x)$ ，当且仅当 $X_1$$X_1$ 和 $X_2$$X_2$ 有相同的分布时有 $h(X_1)=h(X_2)$$h(X_1) = h(X_2)$ 成立。即，假设 $|X_2|\ge |X_1|$$|X_2|\ge |X_1|$，我们有：$X_1=(S,m)$$X_1=(S,m)$ 以及 $X_2=(S,k\times m)$$X_2=(S,k\times m)$ ，其中 $k$$k$ 为某个大于1 的整数。

   证明：假设 multiset $X_1,X_2$$X_1,X_2$ 有相同的分布，不失一般性我们假设 $X_1=(S,m),X_2=(S,k\times m)$$X_1=(S,m),X_2=(S,k\times m)$ ，其中 $k$$k$ 为某个大于等于1 的正整数。即 $X_1,X_2$$X_1,X_2$ 有相同的底层set，并且 $X_2$$X_2$ 中元素的multiplicity 为 $X_1$$X_1$ 中的 $k$$k$ 倍。然后我们有：

   $$|X_2|=k|X_1|,\sum _{x\in X_2}f(x)=k\times \sum _{x\in X_1}f(x)$$

   因此有：

   $$\frac{1}{|X_2|}\sum _{x\in X_2}f(x)=\frac{1}{|X_1|}\sum _{x\in X_1}f(x)$$

   现在我们证明存在一个函数 $f(\cdot )$$f(\cdot)$ ，使得 $\frac{1}{|X|}\sum _{x\in X}f(x)$$\frac{1}{|X|}\sum_{x\in X}f(x)$ 对于分布相等（distributionally equivalent）的 $X$$X$ 而言是unique 的。由于 $\mathcal{X}$$\mathcal X$ 是可数的，因此存在映射 $Z:\mathcal{X}\to \mathbb{N}$$Z:\mathcal X\rightarrow \mathbb N$ ，它从 $x\in \mathcal{X}$$x\in\mathcal X$ 映射到自然数。因为multiset $X$$X$ 的基cardinality 是有界的，因此存在一个数 $N\in \mathbb{N}$$N\in \mathbb N$ ，使得 $|X|<N$$|X|\lt N$ 对于所有 $X$$X$ 成立。则满足条件的 $f(\cdot )$$f(\cdot)$ 的一个例子是 $f(x)=N^{-2Z(x)}$$f(x) = N^{-2Z(x)}$ 。

3. 如果某个任务中，图的统计信息和分布信息比确切结构更重要，则对于该任务使用均值聚合器可能会表现良好。

   此外，当节点特征多种多样（diverse），且很少重复时，均值聚合器的能力几乎和 sum 聚合器一样强大。这可以解释为什么尽管存在限制（只能捕获 multiset 中元素的分布、而不是捕获确切的 multiset 本身），但是具有均值聚合器的 GNN 对于节点特征丰富的节点分类任务（如文章主题分类和社区检测）有效，因为邻域特征分布足以为任务提供强有力的信号。

b. 最大池化

1. 最大池化将多个具有相同特征的节点视为仅一个节点（即，将 multiset 视为一个简单的 set）。

   最大池化无法捕获确切的结构或分布。但是，它可能适合于需要识别代表性元素或者骨架（skeleton），而不适合需要区分确切结构或分布的任务。

   实验表明：最大池化聚合器学会了识别3D 点云的骨架，并对噪声和离群点具有鲁棒性。为了完整起见，下一个推论表明最大池化聚合器捕获了 multiset 底层的 set 。

2. 推论9：假设 $\mathcal{X}$$\mathcal X$ 是可数的，则存在一个函数 $f:\mathcal{X}\to {\mathbb{R}}^{\mathrm{\infty }}$$f:\mathcal X\rightarrow \mathbb R^\infty$ ，使得对于 $h(X)=\underset{x\in X}{max}f(x)$$h(X) = \max_{x\in X}f(x)$ ，当且仅当 $X_1$$X_1$ 和 $X_2$$X_2$ 具有相同的底层set 有 $h(X_1)=h(X_2)$$h(X_1)=h(X_2)$ 成立。

   证明：假设 multiset $X_1$$X_1$ 和 $X_2$$X_2$ 有相同的底层set $S$$S$ ，我们有：

   $$\underset{x\in X_1}{max}f(x)=\underset{x\in S}{max}f(x)=\underset{x\in X_2}{max}f(x)$$

   现在我们证明存在一个映射 $f(\cdot )$$f(\cdot)$，使得 $\underset{x\in X}{max}f(x)$$\max_{x\in X}f(x)$ 对于具有相同底层 set 的 $X$$X$ 而言是 unique 的。由于 $\mathcal{X}$$\mathcal X$ 是可数的，因此存在映射 $Z:\mathcal{X}\to \mathbb{N}$$Z:\mathcal X\rightarrow \mathbb N$ ，它从 $x\in \mathcal{X}$$x\in\mathcal X$ 映射到自然数。因此这种 $f:\mathcal{X}\to {\mathbb{R}}^{\mathrm{\infty }}$$f:\mathcal X\rightarrow \mathbb R^{\infty}$ 函数的定义为：

   $$\begin{array}{c}{f}_i(x)=\{\begin{array}{ll}1,& i=Z(x)\\ 0,& \text{else}\end{array}\end{array}$$

   其中 $f_i(x)$$f_i(x)$ 为 $f(x)$$f(x)$ 的第 $i$$i$ 个坐标。这样的 $f$$f$ 本质上将 multiset 映射到它的 one-hot embedding 。

1.4.3 其它聚合器

1. 我们还没有覆盖到其它非标准的邻域聚合方案，如通过attention 加权平均的聚合器、 LSTM 池化聚合器。我们强调，我们的理论框架足以通用从而刻画任何基于聚合的 GNN 的表征能力。未来我们会研究应用我们的框架来分析和理解其它聚合方案。

1.5 实验

1. 我们评估和对比了 GIN 以及能力较弱的 GNN 变体的训练和测试性能。

   • 训练集上的性能比较让我们能够对比不同 GNN 模型的表征能力。

   • 测试集上的性能比较让我们能够对比不同 GNN 模型的泛化能力。

2. 数据集：我们使用9 种图分类benchmark 数据集，包括4 个生物信息学数据集（MUTAG, PTC, NCI1, PROTEINS）、5 个社交网络数据集（COLLAB, IMDB-BINARY, IMDB-MULTI, REDDITBINARY and REDDIT-MULTI5K） 。

   • 社交网络数据集：

     • IMDB-BINARY 和 IMDB-MULTI 是电影协作（collaboration）数据集。

       每个图对应于演员的协作图，节点代表演员。如果两个演员出现在同一部电影中，则节点之间存在边。

       每个图都来自于预先指定的电影流派（genre），任务的目标是对图的流派进行分类。

     • REDDIT-BINARY 和 REDDIT-MULTI5K 是平衡的数据集。

       每个图对应于一个在线讨论话题（thread），节点对应于用户。如果一个用户评论了另一个用户的帖子，则两个节点之间存在一条边。

       任务的目标是将每个图分类到对应的社区。

     • COLLAB 是一个科学协作（collaboration）数据集，它来自3 个公共协作数据集，即 High Energy Physics, Condensed Matter Physics, Astro Physics 。

       每个图对应于来自每个领域的不同研究人员的协作网络。任务的目标是将每个图分类到所属的领域。

   • 生物学数据集：

     • MUTAG 是包含 188 个诱变（mutagenic）的芳香族（aromatic）和异芳香族（heteroaromatic）硝基化合物（nitro compound）的数据集，具有 7 个类别。

     • PROTEINS 数据集中，节点是二级结构元素 （secondary structure elements:SSEs），如果两个节点在氨基酸序列或3D 空间中是邻居，则两个节点之间存在边。它具有3 个类别，分别代表螺旋（helix）、片（sheet）、弯（turn）。

     • PTC 是包含344 种化合物的数据集，给出了针对雄性和雌性老鼠的致癌性，具有 19 个类别。

     • NCL1 是美国国家癌症研究所公开的数据集，是化学化合物平衡数据集的子集（balanced datasets of chemical compounds）。这些化合物经过筛选具有抑制一组人类癌细胞系生长的能力，具有 37 个类别。

   重要的是，我们的目标不是让模型依赖于节点的特征，而是主要从网络结构中学习。因此：在生物信息图中，节点具有离散 （categorical）的输入特征；而在社交网络中，节点没有特征。对于社交网络，我们按照如下方式创建节点特征：

   • 对于 REDDIT 数据集，我们将所有节点特征向量设置为相同。因此这里特征向量不带任何有效信息。

   • 对于其它社交网络，我们使用节点 degree 的 one-hot 编码作为节点特征向量。因此这里的特征向量仅包含结构信息。

   下表给出了数据集的统计信息。

   

3. baseline 方法：

   • WL sbuntree kernel，其中使用 C-SVM 来作为分类器。

     SVM 的超参数 C 以及WL 迭代次数通过超参数调优得到，其中迭代次数从{1,2,3,4,5,6} 之中选择。

   • STOA 深度学习架构，如 Diffusionconvolutional neural networks: DCNN、PATCHY-SAN、Deep Graph CNN: DGCNN。

   • Anonymous Walk Embeddings: AWL。

   对于深度学习方法和 AWL，我们报告其原始论文中的准确率。

4. 实验配置：我们评估 GIN 和能力较弱的 GNN 变体。

   • 在 GIN 框架下，我们考虑两种变体：

     • 一种是通过梯度下降来学习 $ϵ$$\epsilon$ ，我们称之为 $\text{GIN-}ϵ$$\text{GIN-}\epsilon$ 。

     • 另一种是固定 $ϵ=0$$\epsilon=0$，我们称之为 GIN-0 。

       $ϵ=0$$\epsilon=0$ 时，GIN 的邻域聚合就是 sum 池化（不包含当前节点自身）。

     正如我们将看到的，GIN-0 将表现出强大的实验性能：GIN-0 不仅与$\text{GIN-}ϵ$$\text{GIN-}\epsilon$ 一样拟合训练集，它也表现出良好的泛化能力：在测试准确率上稍微并持续地优于 $\text{GIN-}ϵ$$\text{GIN-}\epsilon$ 。

   • 对于能力较弱的GNN 变体，我们考虑使用均值池化或最大池化替代GIN-0 中的 sum聚合，或者使用单层感知机来代替 GIN-0 中的多层感知机。

     这些变体根据使用的聚合器、感知器来命名。如 mean-1-layer 对应于GCN、max-1-layer 对应于 GraphSAGE，尽管有一些小的体系架构修改。

   对于 GIN 和所有的 GNN 变体，我们使用相同的 graph-level readout 函数。具体而言，由于更好的测试性能，生物信息学数据集的 readout 采用sum 函数，而社交网络数据集的 readout 采用 mean 函数。

   我们使用 LIB-SVM 执行 10-fold 交叉验证，并报告 10-fold 交叉验证中验证集准确率的均值和标准差。

   对于所有配置（ configurations）：

   • 我们使用5 层 GNN layer（包含输入层），并且 MLP 都有 2 层（它不算在 5 层 GNN内）。

   • 我们对于每个 hidden layer 应用 batch normalization。

   • 我们使用初始学习率为 0.01 的 Adam 学习器，并且每 50 个 epoch 进行学习率衰减 0.5 。

   超参数是针对每个数据集进行调优的：

   • 对于生物学数据集，隐层维度为16 或 32；对于社交网络数据集，隐层维度为64 。

   • batch size 为32 或 128 。

   • dropout 在 dense 层后，dropout 比例为0 或 0.5 。

   • epoch 数量通过 10-fold 交叉验证来确定。

   注意：由于数据集规模较小，因此使用验证集进行超参数选择极其不稳定。例如对于 MUTAG，验证集仅包含 18 个数据点。因此上述有很多超参数是我们人工调优的。

   我们也报告了不同 GNN 的训练准确率。其中所有的超参数在所有数据集上都是固定的（调优之后）：5 层 GNN layer（包括输入层）、hidden 维度为 64、batch size = 128、dropout 比例为 0.5 。

   为进行比较，我们也报告了 WL subtree kernel 的准确率，其中迭代数量为 4 。这和 5 GNN layer 相当。

1.5.1 训练准确率

1. 通过比较 GNN 的训练准确率，我们验证了我们关于表征能力的理论分析。具有较高表达能力的模型应该具有较高的训练准确率。下图给出了具有相同超参数设置的 GIN 和能力较弱的 GNN 变体的训练曲线。

   • 首先，$\text{GIN-}ϵ$$\text{GIN-}\epsilon$ 和 $\text{GIN-0}$$\text{GIN-0}$ 都是理论上最强大的 GNN，它们都可以几乎完美地拟合训练集。

     在我们的实验中，在拟合训练数据集这个方面 ，显式学习 $ϵ$$\epsilon$ 的$\text{GIN-}ϵ$$\text{GIN-}\epsilon$ 相对于将 $ϵ$$\epsilon$ 固定为 0 的 $\text{GIN-0}$$\text{GIN-0}$，并没有额外的收益。

   • 相比之下，使用均值/最大值池化聚合、或者单层感知机的 GNN 变体在很多数据集中严重欠拟合。

     具体而言，训练准确率模式和我们通过模型表征能力的排名相符：

     • 采用 MLP 的 GNN 变体要比采用单层感知机的 GNN 变体拟合训练集效果更好。

     • 采用 sum 聚合器的 GNN 变体要比采用均值/最大值池化聚合的 GNN 变体拟合训练集效果更好。

   • 在我们的数据集上，GNN 训练准确率永远不会超过 WL subtree kernel 。

     这是可以预期的，因为 GNN 的判别力通常比 WL-test 更低。例如在 IMDB-BINARY 数据集上，没有一个模型能够完美拟合训练集，而 GNN 最多可达到与 WL kernel 相同的训练准确率。

     这种模式和我们的结果一致，即 WL-test 为基于聚合的 GNN 的表征能力提供了上限。但是， WL kernel 无法学习如何组合节点特征，这对于给定的预测任务非常有用。我们接下来会看到。

   

1.5.2 测试准确率

1. 接下来我们比较测试准确率。尽管我们的理论分析并未直接提及 GIN 的泛化能力，但是可以合理地预期具有强大表达能力的 GNN 可以准确地捕获感兴趣的图结构，从而更好地泛化。

   下表给出了 GIN（Sum-MLP） 、其它GNN 变体、以及SOTA baseline 的测试准确率。表现最好的 GNN 以黑色突出显示。在有些数据集上 GIN 的准确率在所有 GNN 变体之间并非最高，但是和最佳 GNN相比 GIN 仍然具有可比的性能，因此GIN 也已黑色突出显示。如果 baseline 的性能明显高于所有 GNN，则我们用黑体和星号同时突出显示。

   结论：

   • 首先，GIN，尤其是 GIN-0，在所有 9 个数据集上均超越了（或者达到可比的）能力较弱的 GNN 变体，达到了 SOTA 性能。

   • 其次，在包含大量训练数据的社交网络数据集中，GIN 效果非常好。

     对于 Reddit 数据集，所有节点都使用相同的特征，因此模型仅能捕获图结构信息。

     • GIN 以及 sum 聚合的 GNN 准确地捕获到图结构，并且显著优于其它模型。

     • 均值聚合 GNN 无法捕获图的任何结构，并且其测试准确率和随机猜测差不多。

     对于其它社交网络数据集，虽然提供了节点degree 作为输入特征，但是基于均值聚合的 GNN 也要比基于sum 聚合的 GNN 差得多。

   • 对于 GIN-0 和 $\text{GIN-}ϵ$$\text{GIN-}\epsilon$ ，我们发现 GIN-0 稍微、但是一致地超越了 $\text{GIN-}ϵ$$\text{GIN-}\epsilon$ 。由于两者都能很好地拟合训练集，因此可以简单解释为GIN-0 相比 $\text{GIN-}ϵ$$\text{GIN-}\epsilon$ 的泛化能力更好。