GINConv

1. Weisfeiler-Lehman Test

论文名称：Weisfeiler-Lehman Graph Kernels

论文地址：https://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf

Weisfeiler-Lehman Test用于判断两个图是否同构。Weisfeiler-Lehman Test是一个迭代的过程， Algorithm 1给出简洁的算法描述。

这个算法的关键思想是对node节点赋予标签，然后对邻居节点进行升序排列，然后，将这些标签压缩产生新的标签。重复以上步骤，直到$G$和$G^{\prime }$的标签不同或者迭代次数到达$n$. Figure2 a-d描述这些步骤（需要注意的是，这两个图是非同构的，因为他们的标签在开始就不同）。
如果初始化标签不存在，开始的时候，可以初始化标签为1.

以下图的参考链接: https://davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/

2. GIN

论文名称：HOW POWERFUL ARE GRAPH NEURAL NETWORKS?

论文地址：https://arxiv.org/pdf/1810.00826.pdf

Graph Neural Networks. GNN使用图的结构和节点的特征$X_v$, 学习节点的embedding $h_v$或者整个图的embedding $h_G$。现在GNN汇总邻居节点信息和更新节点表征。在$k$迭代汇总后，当前节点 的表征就会捕捉到$k\text{-hop}$的邻居信息。GNN $k\text{-th}$ 的layer如下：
$$a_v^{(k)}={\mathrm{A}\mathrm{G}\mathrm{G}\mathrm{R}\mathrm{E}\mathrm{G}\mathrm{A}\mathrm{T}\mathrm{E}}^{(k)}\left(\left\{h_u^{(k-1)}:u\in \mathcal{N}(v)\right\}\right),h_v^{(k)}={\mathrm{C}\mathrm{O}\mathrm{M}\mathrm{B}\mathrm{I}\mathrm{N}\mathrm{E}}^{(k)}\left(h_v^{(k-1)},a_v^{(k)}\right)\text{\hspace{1em}(2.1)}$$
其中$h_v^{(k)}$代表节点$v$在$k\text{-th}$ layer的特征表示。我们初始化$h_v^{(0)}=X_v$, 其中$\mathcal{N}(v)$是节点$v$的邻居。

2.1 BUILDING POWERFUL GRAPH NEURAL NETWORKS

首先，我们描述以下GNN模型的表征能力，通常来说，一个强大的GNN模型能否将不同的图结构映射到不同的向量表征空间中。将不同的图映射到不同的向量空间，用来判别两个图是否同构图。同构图映射到相同的空间中，非同构图映射到不同的空间中。我们设计的 $GNN$具备Weisfeiler-Lehman (WL) graph isomorphism test同样的判别能力，泛化能力更高。

Lemma 2. 设$G_1$和$G_2$是两个非同构图。如果GNN $\mathcal{A}:\mathcal{G}\to {\mathbb{R}}^d$将其映射为不同到embedding，Weisfeiler-Lehman test也能判定其是非同构的。

是否存和WL test具备同等能力的GNN？我们的 回答是的，如果没满足Theorem 3，即eighbor aggregation 和 graph-level readout函数都是单射的，我们的GNN就具备和WL test同样的能力。

**Theorem 3.**设 $\mathcal{A}:\mathcal{G}\to {\mathbb{R}}^d$为一个$GNN$, 一个多层GNN。对于任何两个图$G_1$和$G_2$, Weisfeiler-Lehman test将两个图判别为非同构图。$\mathcal{A}$满足以下条件，将两个图映射到不同的embedding（也就是说，$\mathcal{A}$具备和 Weisfeiler-Lehman test同样的能力）:

a) 通过以下迭代的方式更新和汇总节点的特征：
$$h_v^{(k)}=\varphi \left(h_v^{(k-1)},f\left(\left\{h_u^{(k-1)}:u\in \mathcal{N}(v)\right\}\right)\right)$$
其中，对于函数$f$， 它是基于multisets， $\varphi$是单射函数。

b) $\mathcal{A}$是单射的，它能够作用于multiset 节点特征$\left\{h_v^{(k)}\right\}$, 是单射的。

需要注意的是GNN不仅能够判别图，而且，通过将图接否映射为低维的embedding，能够衡量不同图之间的相似性。

2.2 GRAPH ISOMORPHISM NETWORK (GIN)

我们开发简单架构GIN, 满足Theorem 3，这个模型是WL test的泛化，因此也能够对GNN进行判别。

Lemma 5. 假设$\mathcal{X}$是可枚举的。对于每个有限集 multiset $X\subset \mathcal{X}$， 存在函数$f:\mathcal{X}\to {\mathbb{R}}^n$使得$h(X)={\sum }_{x\in X}f(x)$是唯一的。甚至，对于任何一个multiset函数$g$对于某些$\varphi$可以分解为$g(X)=\varphi \left({\sum }_{x\in X}f(x)\right)$.

深度multisets和sets一个重要的区别在于它的单射性，像mean aggregator不是单射函数。我们设计聚合框架满足Theorem 3中的单射性。

Corollary 6. 假设$\mathcal{X}$是可枚举的。存在一个函数$f:\mathcal{X}\to {\mathbb{R}}^n$, 对于任意$ϵ$和pair $(c,X)$，$h(c,X)=(1+ϵ)\cdot f(c)+{\sum }_{x\in X}f(x)$是唯一的， 其中$c\in \mathcal{X}$，$X\subset \mathcal{X}$。基于pair, 对于任意一个函数$g$可以分解为$g(c,X)=\phi \left((1+ϵ)\cdot f(c)+{\sum }_{x\in X}f(x)\right)$.

在实践中，我们使用针对$f^{(k+1)}\circ {\phi }^{(k)}$我们使用同一个MLP，$ϵ$是可学习的参数，GIN表示如下：
$$h_v^{(k)}={\mathrm{MLP}}^{(k)}\left(\left(1+{ϵ}^{(k)}\right)\cdot h_v^{(k-1)}+\sum _{u\in \mathcal{N}(v)}{h}_u^{(k-1)}\right)$$
通常存在很多这样GNN, GIN只是其中比较简单的一个。

2.3 GRAPH-LEVEL READOUT OF GIN

GIN会产生node embedding，用于节点分类和链路预测。如果需要对图进行分类还需要"readout"函数，根据节点的embedding产生整个图的embedding。

graph-level readout一个重要的方面，随着迭代次数的增加，节点的表征和subtree结构的刻画能力越强，对于图的判别能力越强。当然，初始迭代中，特征的泛化能力比较好。
$$h_G=\mathrm{READOUT}\left(\left\{h_v^{(K)}\mid v\in G\right\}\right)\text{\hspace{1em}(2.4)}$$
与Eq. 2.4不同的是，GIN的图表征是指将所有迭代层的输出拼接起来:
$$h_G=\mathrm{CONCAT}\left(\mathrm{READOUT}\left(\left\{h_v^{(k)}\mid v\in G\right\}\right)\mid k=0,1,\dots ,K\right)\text{\hspace{1em}(4.2)}$$