挑战泛化能力天花板！突破GNN中消息传递范式的限制

2022 年 5 月 5 日 图与推荐

“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。

来源：知乎—无知影

地址：https://zhuanlan.zhihu.com/p/507111763

编辑：人工智能前沿讲习

消息传递是图神经网络的一种范式，但近些年来研究发现消息传递GNN的表达能力欠佳，不能识别网络中的高阶结构。本文讨论一篇来自ICML2021的文章，介绍GNN如何突破被消息传递范式所限制的表达能力：

http://proceedings.mlr.press/v139/balcilar21a/balcilar21a.pdf

温馨提示：这篇文章也是有代码的哦~

https://github.com/balcilar/gnn-matlang

消息传递是什么

消息传递（Message Passing）是图神经网络的一种范式。基于消息传递范式的图神经网络（MPNN）旨在将节点的特征传播到邻居节点上，通常也会考虑添加一些权重来分配邻居之间传播特征的比例。事实上，绝大多数GNN都可以被归纳为消息传递图神经网络（MPNN）。

由此，MPNN的第

l+1

层

H^{(l+1)}

可以被表示为下面这个方程：

H^{(l+1)}=\sigma(\sum\limits_s C^{(s)} H^{(l)} W^{(l,s)})

其中，

C^{(s)} \in \mathbb{R}^{n\times n}

表示第s个卷积，定义节点特征如何传播到邻居节点上，最简单的传播方式就是直接传给邻居，即

C^{(s)}=A

；

W^{(l,s)} \in \mathbb{R}^{f_l \times f_{l+1}}

表示第s个可训练矩阵；

\sigma

表示激活函数。

根据上述方程可以看出，MPNN 可通过堆叠层数增加参数量，因而MPNN的复杂度往往是线性的。

MPNN的问题：表达能力弱

尽管消息传递范式非常流行，但这种结构的图神经网络有一个显著的问题，即表达能力弱。

一般来说，评价某个GNN的表达能力通常看这个GNN能否区别两个图是否同构。下图给出了一对同构图和一对非同构图，而表达能力强的GNN应具有区分它们的能力。

检验GNN的表达能力：WL图同构测试

表达能力强的GNN能够将两个非同构的图嵌入到特征空间中的两个不同位置，而一个能够识别所有非同构图的GNN就是一个万能逼近器，我们也可以将这种GNN描述为具有很强的泛化能力。

WL测试则是一种识别图同构的方法，因此WL测试经常被用于度量GNN的表达能力。典型的WL测试基于染色方法，且WL测试可以迭代多次，下图展示了1轮迭代的1-WL测试的过程。

相关研究表明k-WL测试是有一定规律的。当

k \geq 2

，(k+1)-WL测试的表达能力强于k-WL，但1-WL测试和2-WL测试的表达能力差不多。更重要的是，现有MPNN的表达能力都小于等于1-WL测试。

注：个人认为1-WL能够区分节点，2-WL能够区分节点对（即连边），3-WL能够区分三角模体和更高阶的网络子结构。

设计表达能力更强的MPNN

作者从图谱的角度展开分析，认为迹(trace)和元素乘(element-wise)这两种算子是让MPNN获得超过1-WL表达能力的关键。

迹：矩阵对角线的和
元素乘：矩阵元素按位置相乘

本文中，作者使用元素乘来改造MPNN。这是因为迹算子不足以区分余谱（cospectral）图，类似下面这样的：

想要直接使用元素乘是不容易的，因为使用元素乘算子区分同构需要用到邻接矩阵的高阶幂（有兴趣可以自己参考原文，这里直接给出结论），但这对于MPNN而言是困难的，因为它不能直接得到这样的高阶幂。更值得注意的是，这样的高阶幂矩阵大概率是稠密的，这使得计算所需的存储空间指数级上升。

解决这个问题的方法是通过设计特别的掩码矩阵

M

保证高阶幂矩阵的稀疏性，并保留一定长度的感受野（receptive field，指的是某个节点能关联到多远距离的邻居），如感受野长度为1的掩码矩阵

M=A+I

。

接着文章给出了一个能够满足3-WL表达能力的MPNN，名为GNNML3。相关定理表明，这个MPNN多次卷积等价于图拉普拉斯矩阵（即

L=D-A

）或邻接矩阵的高阶幂：

其中，

mlp_k

表示可训练的模型；

U \in \mathbb{R}^{n \times n}

表示图拉普拉斯矩阵的特征向量矩阵，其中的每一列都是图拉普拉斯矩阵的特征向量；

\lambda \in \mathbb{R}^n

表示图拉普拉斯矩阵的一系列特征值；

diag

函数能够生成一个矩阵，其对角线是输入的向量；

f_s \in [\lambda_{min}, \lambda_{max}], b>0

是两个超参数。

最后，作者给出了他的算法(((φ(◎ロ◎;)φ)))：

这样设计的GNN效果有多好

作者设计了一系列实验以回答下面四个问题：

多少对1-WL和3-WL等价的非同构图不能被模型区分？
给定一个图，模型能够对图中的子结构（模体）计数吗？
模型能够学习到低通、高通和带通滤波器的性质吗？
模型在下游任务中的表现怎么样？

针对第一个问题，作者在四个数据集上展开图分类任务，结果表明GNNML是最好的。这里提到的几个模型都是图神经网络中比较常见的模型啦，值得注意的是ChebNet表现竟然还不错，这是因为当两个图正则化拉普拉斯矩阵的最大特征值不同时，Cheb Net是能够区分它们的，此时的ChebNet拥有超过1-WL测试的表达能力。此外PPGN的效果也不错，但相比于GNNML的线性复杂度，PPGN的复杂度