1. Weisfeiler-Leman算法

• 图同构： 通俗点就是两个图的特征及结构信息完全相同。具体来说就是：如果图G和图H同构，那么在G和H的顶点集间存在一个“edge-preserving"的双射函数$f$，使得“如果节点u和v在图G中相连，那么$f(u)$和$f(v)$在图H中也相连”。下图展示了两个同构图G和H：

  

• Jaccard相似度： Jaccard index，又称为Jaccard相似系数或者叫雅可比相似度系数，用来比较有限样本集之间的相似性与差异性。Jaccard系数值越大，样本相似度越高。狭义的Jaccard系数计算公式如下：

  $J(A,B)=\frac{|A\cap B|}{|A\cup B|}=\frac{|A\cap B|}{|A|+|B|-|A\cap B|}$

  当A和B都为空集时，$J(A,B)=1$；当$A=B$时，$J(A,B)=1$。

Weisfeiler-Leman(WL，威斯费勒-莱曼)是用来测试图同构的一种经典算法，可以在准多项式复杂度内判别两个图是否同构。所谓的图同构就是两个图中对应节点的特征信息和结构信息都相同，则称两个图同构。因此就需要一种高效地计算方法能将特征信息及结构位置信息映射成一个数值，我们称其为这个节点的ID。最后，两个图的相似度问题就可以转化成两个图节点集合ID的Jaccard相似度问题。

• 思路： 计算节点ID需要用到节点的特征信息和结构信息。特征信息即节点自带的Embedding，而结构信息可以通过节点的邻居来刻画，比如，如果两个节点的Embedding相同，并且他们连接了Embedding完全相同的邻居，此时我们是无法区分这两个节点的，因此这两个节点的ID相同。我们可以通过对节点ID的Hash来高效判断两个节点ID是否一致。
• Input： 一对图$G=(V,E,X)$和$H=(U,F,Y)$
• Output： 是否存在双射函数$f:V\rightarrow U$，使得$X_v=Y_{f(v)}\ \forall v\in V$，并且当且仅当$\{f(u),f(v)\in F\}$时，$\{u,v\}\in E$。

1.1 1-WL

$h_l^{(t)}(v)=HASH\Big(h_l^{(t-1)}(v),\mathcal F\Big\{h_l^{t-1}(u)|u\in N(v)\Big\}\Big)$

其中$v$表示单个节点，$\mathcal F$表示邻居$Embedding$的聚合函数，可以是简单的拼接。$h_l^{(t-1)}(v)$表示上一轮迭代中节点$v$的Embedding。$HASH$是哈希函数，也可以是其他单射函数（输入x不同，得到的f(x)一定不同）。

• 多重集

  多重集是集合概念的推广，它允许集合中元素重复出现。一个多重集可以看做是一个二元组$X=(S,m)$，其中S为在X中出现的所有元素构成的集合，$m:S\rightarrow\mathbb N_{\geq1}$表示S中每个元素出现的次数。

• 流程

  Input： 一对图$G=(V,E,X)$和$H=(U,F,Y)$

  1. $c_v^{(0)}\leftarrow Hash(X_v)\ (\forall v\in V)$

  2. $d_u^{(0)}\leftarrow Hash(Y_u)\ (\forall u\in U)$

  3. for $l=1,2,...(untill\ convergence)$

     (1) if $\{\{c_v^{(l-1)}\ |\ v\in V\}\}\neq \{\{d_u^{(l-1)}\ |\ u\in U\}\}$ then return “non-isomorphic”

     (2) $c_v^{(l)}\leftarrow Hash(c_v^{(l-1)},\{\{c_w^{(l-1)}\ |\ w\in\mathcal N_G(v)\}\})\ (\forall v\in V)$

     (3) $d_u^{(l)}\leftarrow Hash(d_u^{(l-1)},\{\{d_w^{(l-1)}\ |\ w\in\mathcal N_H(u)\}\})\ (\forall u\in U)$

  4. return “possibly isomorphic”

  1-WL一定会在$O(|V|+|U|)$迭代内终止。如果1-WL算法输出"non-isomorphic"，那么G和H一定是非同构的。但是如果1-WL输出"possibly isomorphic"，那么G和H也可能是非同构的，如下图所示：

  

• 实例

  

• 问题1：为什么1-WL返回$possibly\ isomorphic$时，两个图可能非同构的？

  因为WL用邻居来刻画图的结构信息，如果非同构图G和H中存在这样一个节点对组合：任意一个节点对中两个节点的特征相同，且邻居数量、特征都相同，那么此时1-WL算法无法区分这两个非同构图。

  

• 问题2：为什么1-WL最多迭代$O(|V|+|U|)$？

  考虑回答这个问题：为什么k-WL最多迭代$O(|V|^k+|U|^k)$次？

  因为k-WL算法中，对于有n个顶点的图最多有$n^k$种颜色类别，所以最多在$n^k$次迭代后颜色状态达到稳定，算法终止。

1.2 k-WL

1-WL算法计算过程中只考虑1个顶点，k-WL算法计算时考虑的是K个顶点组成的k-tuple。

• 流程

  Input： 一对图$G=(V,E,X)$和$H=(U,F,Y)$

  1. $c_\mathbf v^{(0)}\leftarrow Hash(G[\mathbf v])\ (\forall\mathbf v\in V^k)$

  2. $d_\mathbf u^{(0)}\leftarrow Hash(H[\mathbf u])\ (\forall\mathbf u\in U^k)$

  3. for $l=1,2,...(untill\ convergence)$

     (1) if $\{\{c_\mathbf v^{(l-1)}\ |\ \mathbf v\in V\}\}\neq \{\{d_\mathbf u^{(l-1)}\ |\ \mathbf u\in U\}\}$ then return “non-isomorphic”

     (2) $c_{\mathbf v,i}^{(l)}\leftarrow \{\{c_\mathbf w^{(l-1)}\ |\ \mathbf w\in\mathcal N_{G,i}^{k-WL}(\mathbf v)\}\}\ (\forall\mathbf v\in V^k, i\in[k])$

     (3) $c_\mathbf v^{(l)}\leftarrow Hash(c_\mathbf v^{(l-1)},c_{\mathbf v,1}^{(l)},...,c_{\mathbf v,k}^{(l)}\}\})\ (\forall\mathbf v\in V^k)$

     (4) $d_{\mathbf u,i}^{(l)}\leftarrow \{\{d_\mathbf w^{(l-1)}\ |\ \mathbf w\in\mathcal N_{H,i}^{k-WL}(\mathbf u)\}\}\ (\forall\mathbf u\in U^k, i\in[k])$

     (5) $d_\mathbf u^{(l)}\leftarrow Hash(d_\mathbf u^{(l-1)},d_{\mathbf u,1}^{(l)},...,d_{\mathbf u,k}^{(l)}\}\})\ (\forall\mathbf u\in U^k)$

  4. return “possibly isomorphic”

  其中$\mathcal N_{G,i}^{k-WL}(\mathbf v)=\{(v_1,...,v_{i-1},w,v_{i+1},...,v_k)\ |\ w\in V\}$表示k元组$\mathbf v$的i-th邻居，即用G中的其他顶点任意顶点$w$替换$\mathbf v$中的第i个顶点。对于连个k-tuple，当且仅当下面两个条件都满足时，$Hash(G[\mathbf v^1])=Hash(G[\mathbf v^2])$：

  • $\mathbf {X_{v_i^1}=X_{v_i^2}}, \forall i\in[k]$
  • 当且仅当$\{\mathbf v_i^2\,\mathbf v_j^2\}\in E,\ \forall i,j\in[k]$时，${\mathbf v_i^1,\mathbf v_j^1}\in E$

1.2 k-FWL

WL算法有很多变体形式，主要通过改变邻居信息的聚合方式来进行优化，k-FWL就是其中一种。

• 流程

  Input： 一对图$G=(V,E,X)$和$H=(U,F,Y)$

  1. $c_\mathbf v^{(0)}\leftarrow Hash(G[\mathbf v])\ (\forall\mathbf v\in V^k)$

  2. $d_\mathbf u^{(0)}\leftarrow Hash(H[\mathbf u])\ (\forall\mathbf u\in U^k)$

  3. for $l=1,2,...(untill\ convergence)$

     (1) if $\{\{c_\mathbf v^{(l-1)}\ |\ \mathbf v\in V\}\}\neq \{\{d_\mathbf u^{(l-1)}\ |\ \mathbf u\in U\}\}$ then return “non-isomorphic”

     (2) $c_{\mathbf v,w}^{(l)}\leftarrow (c_{\mathbf v[0]\leftarrow w}^{(l-1)},...,c_{\mathbf v[k]\leftarrow w}^{(l-1)})\ (\forall\mathbf v\in V^k, w\in V)$

     (3) $c_\mathbf v^{(l)}\leftarrow Hash(c_\mathbf v^{(l-1)},\{\{c_{\mathbf v,w}^{(l)}\ |\ w\in V\}\})\ (\forall\mathbf v\in V^k)$

     (4) $d_{\mathbf u,w}^{(l)}\leftarrow (d_{\mathbf u[0]\leftarrow w}^{(l-1)},...,d_{\mathbf u[k]\leftarrow w}^{(l-1)})\ (\forall\mathbf u\in U^k, w\in U)$

     (5) $d_\mathbf u^{(l)}\leftarrow Hash(d_\mathbf u^{(l-1)},\{\{d_{\mathbf u,w}^{(l)}\ |\ w\in U\}\})\ (\forall\mathbf u\in U^k)$

  4. return “possibly isomorphic”

  其中$c_{\mathbf v[i]\leftarrow w}=c(v_1,...,v_{i-1},w,v_{i+1},...,v_k)$。FWL和WL的区别在于：FWL先concate节点w替换的所有邻居，在将其与k元组$\mathbf v$进行Hash操作。$k-FWL$算法可以区分$k-WL$算法不能区分的非同构图，但是也存在$k-FWL$无法区分的非同构图。

• 问题：为什么$k-FWL$比$k-WL$要强？

  证明待定。

1.3 不同WL间的性能比较

1. 1-WL和2-WL性能一样

   证明待定。

2. 当$k\geq2$时，$k-FWL$和$(k+1)-WL$性能一样

   证明待定。

3. 当$k\geq2$时，$(k+1)-WL$一定比$k-WL$要强

   比如，1-WL不能区分下图，但是3-WL能区分。

   

证明待定。

上述结论主要根据参考文献“ Pebble games and linear equations ”中下面两条定理得到的：

• 定理1：$A\equiv_C^k B$当且仅当k-WL算法无法区分图A和图B。

• 定理2：$A\equiv_C^2 B \Leftrightarrow A\equiv_C^{<2}B$；对于$k\geq 3$，$A\equiv_C^k B\Rightarrow A\equiv_C^{<k}B\Rightarrow A\equiv_C^{k-1}B$。

（上述第二条关于FWL的结论给的参考文献和第三条结论的相同，但是没找到相关结论）

对于WL算法能区分哪些图，不能区分哪些图，学术界也做了很多研究，有一下结论：

1. 如果两个图是随机均匀获取到的，那么随着图越来越大，1-WL算法的失败率逐渐变为0。

   证明待定。

2. 当$k\geq2$时，一定存在一个大小为$O(k)$的非同构图$(G,H)$，k-WL算法输出"possibly isomorphic"。

   证明待定。

3. 1-WL算法能区分任意一对非同构树S和T。

   证明待定。

4. 任意正整数$k,n\in\mathbb Z^+$，对于有n个顶点的k正则图，1-WL算法输出结果一定是"possibly isomorphic"。

   证明待定。

5. 1-WL算法可以在准线性时间内区分出它可以区分的非同构图。

   证明待定。

2. GNNs和WL间的联系

定理： 对于任何基于消息传播的GNN模型，在图G和图H上，如果1-WL输出结果为”possibly isomorphic"，那么GNN模型的到的图嵌入$h_G$和$h_H$一定相同。（1-WL算法性能是GNN的上限）

解释： GNNs中的聚合函数和更新函数可以看做对1-WL中Hansh函数的近似。所以，要想GNNs模型拥有和1-WL一样的性能，需要想办法将GNNs中的聚合函数和更新函数变成单射函数。

2.1 GIN模型——消息传播GNNs的天花板

2.1.1 定理证明

引理：$G_1$和$G_2$是非同构图。如果通过GNN$A:\mathcal G\rightarrow\mathbb R^d$得到的图embedding是不同的，那么1-WL算法作用于这两个图上的结果一定是$non\ isomorphic$。

定理： 用$\mathcal A:\mathcal G\rightarrow\mathbb R^d$表示GNN。对于一个层数足够的GNN，如果满足下列两个条件，则对于所有1-WL算法输出为非同构的图，GNN模型得到的embedding一定不同：

• $\mathcal A$聚合和更新函数$h_v^{(k)}=\phi\Big(h_v^{(k-1},f\Big(\Big\{h_u^{(k-1)}:u\in\mathcal N(v)\Big\}\Big)\Big)$，其中$f$作用于多重集的函数，$\phi$是单射函数。
• $\mathcal A$的graph-level readout函数，即作用于节点特征集合$\{h_v^{(k)}\}$上的函数是单射的。

定理3： 假设集合$\mathcal X$是可数的。存在一个函数$f:\mathcal X\rightarrow\mathbb R^n$，对于每一个有限大小的集合$X\subset\mathcal X$，使得$h(X)=\sum_{x\in X}f(x)$是唯一的。另外存在一个多重集上的函数g，对于某种函数$ \phi $，可以按照$g(X)=$$\phi(\sum_{x\in X}f(x))$方式分解。

推论6： 假设集合$\mathcal X$是可数的。存在函数$f:\mathcal X\rightarrow\mathbb R^n$，使得$h(c,X)=(1+\epsilon)·f(c)+\sum_{x\in X}f(x)$对于所有$(c,X)$都成立，其中$\epsilon$有无数种选择（也可以是无理数），$c\in\mathcal X$，$X\subset \mathcal X$。同样地，也存在一个作用于$(c,X)$上的函数g，对于某种函数$\varphi$，可以将g分解为：$g(c,X)=\varphi((1+\epsilon)·f(c)+$$\sum_{x\in X}f(x))$。

2.1.2 聚合和更新函数

根据通用近似定理（人工神经网络可以近似任意函数），在GIN中作者用MLP来对$f^{(k+1)}\circ \varphi^{(k)}$进行建模。在第一层中，如果节点特征是one-hot编码，我们不需要使用MLP，因为对他们求和本身就是单射的。GIN中的聚合和更新算法如下：

$h_v^{(k)}=MLP^{(k)}\Big(\big(1+\epsilon\big)·h_v^{(k-1)}+\sum_{u\in\mathcal N(v)}h_u^{(k-1)}\Big)$

2.1.3 graph-level readout函数

为了考虑所有的结构信息，在计算图特征时用到了所有迭代中的节点特征。作者参考Jumping Knowledge那篇论文的架构：

$h_G=CONCAT(READOUT(\{h_v^{(k)}|v\in G\})\ |\ k=0,1,...,K)$

根据定理3和推论6，如果用求和函数代替READOUT（和第一层不需要用MLP的理由一样)，这样GIN就可证明地推广了WL-test和WL subtree kernel。

2.2 比1-WL更强的GNNs

Morris等人在2019年发表了一篇名为“ eisfeiler andlemango neural: Higher-order graph neural network ”的文章，里面基于set K-WL算法提出了一种更强大的模型k-GNNs（之所以不用k-WL是为了减少内存开销）。

2.2.1 Set k-WL算法

Set k-WL和k-WL算法不同的时：不在使用k-tuple作为基本研究对象，而是使用k-set。$[V]_k=\{S\subseteq V\ |\ |S|=k\}$表示V的一个真子集，大小为k。$\mathcal N_{V,k}^{set}(S)=\{W\in[V]_k\ |\ |W\cup V|=k-1\}$表示V的所有邻居构成的集合。set k-WL算法流程如下：

1. $c_S^{(0)}\leftarrow Hash(G[S])(\forall S\in [V]_k)$

2. $d_T^{(0)}\leftarrow Hash(H[T])(\forall T\in[U]_k)$

3. for $l=1,2,...(util\ convergence)$

   (a) if $\{\{c_S^{(l-1)}\ |\ S\in[V]_k\}\}\neq\{\{d_T^{(l-1)}\ |\ T\in[U]_k\}\}$ return “non-isomorphic”

   (b) $c_S^{(l)}\leftarrow Hash(c_S^{(l-1)},\{\{c_W^{(l-1)}\ |\ W\in\mathcal N_{V,k}^{set}(S)\}\})(\forall S\in[V]_k)$

   © $d_T^{(l)}\leftarrow Hash(d_T^{(l-1)},\{\{d_W^{(l-1)}\ |\ W\in\mathcal N_{U,k}^{set}\}\})(\forall G\in[U]_k)$

4. return “possibly isomorphic”

set 3-WL可以检测出三角形的数量（1-WL不行），因此可以区分上面几对图，但是1-WL无法区分。需要注意的是set k-WL算法是严格弱于k-WL算法的。例如3-WL算法可以区分下面两个图，但是set 3-WL区分不了，因为3-WL可以检测出4-cycles的数量：

2.2.2 k-GNNs

$\begin{aligned} h_S^{(0)}&=f^{(0)}(G[S])\\ h_S^{(k)}&=W_1^{(k)}h_S^{(k-1)}+\sum\limits_{W\in\mathcal N_{V,k}^{set}(S)}W_2^{(k)}h_W^{(k-1)} \end{aligned}$

其中$f^{(0)}(G[S])$给每个S导出的子图赋予一个特征向量。k-GNN可以看作在$G^{\bigotimes k}$上作消息传播，当且仅当$T\in\mathcal N_{V,k}^{set}(S)$时，$S\in[V]_k$和$T\in[V]_k$之间存在一条边。

定理： 对于任意图G和H，$k\geq2$，如果set k-WL输出图G和H是“non-isomorphic”，一定存在一个k-GNN计算出的图嵌入$h_G$和$h_H$是不一样的。

3. 高阶GNN

k-GNNs的一个缺点就是需要保留$O(n^k)$个embedding，花费太多内存了。Maron等人在“ provably powerful graph networks ”一文中基于$2-FWL$算法提出了一种模型，该模型只需要保留$O(n^2)$个embedding，但是拥有和3-WL一样的表现性能。下面介绍一下高阶invariant和equivariant的GNNs。

3.1 Invariance 和 Equivariance

假设$S_n$表示一个[n]上的对称群，张量$X\in\mathbb R^{n^k}$，排列$p\in S_n$，定义$(p·X)\in\mathbb R^{n^k}$为$(p·X)_{p(i_1),p(i_2),...,p(i_n)}=X_{i_1,i_2,...,i_n}$。对于一个张量$X\in\mathbb R^{n^k\times d}$和排列$p\in S_n$，我们定义$(p·X)\in\mathbb R^{n^k\times d}$为$(p·X)_{p(i_1),p(i_2),...,p(i_n),j}=X_{i_1,i_2,...,i_n,j}$。

1. Invariance

   如果对于任意$X\in\mathbb R^{n^k}$以及$p\in S_n$，如果$f(p·X)=f(X)$成立，那么称$f:\mathbb R^{n^k}\rightarrow\mathbb R$是invariant。

   如果对于任意$X\in\mathbb R^{n^k\times d}$以及$p\in S_n$，如果$f(p·X)=f(X)$成立，那么称$f:\mathbb R^{n^k\times d}\rightarrow\mathbb R^{n^l\times d'}$是invariant。

2. Equivariance

   如果对于任意$X\in\mathbb R^{n^k}$以及$p\in S_n$，如果$f(p·X)=p·f(X)$成立，那么称$f:\mathbb R^{n^k}\rightarrow\mathbb R$是equivariant。

   如果对于任意$X\in\mathbb R^{n^k\times d}$以及$p\in S_n$，如果$f(p·X)=p·f(X)$成立，那么称$f:\mathbb R^{n^k\times d}\rightarrow\mathbb R^{n^l\times d'}$是equivariant。

4. Relational Pooling

未完待续。。。

5. 参考文献