ICML 2024｜全新图卷积！Mila和华为提出CKGConv：连续卷积核的图卷积网络

近年来，基于Transformer的图模型(图Transformer，graph Transformer)成为了一个备受关注的研究方向。有别于传统的基于信息传递机制(Message-passing)的图神经网络(简称MPNN)，图Transformer通过全局注意力机制来聚合全图的所有其他节点的信息，因此它能有效克服MPNNs的过度挤压(over-squashing), 过度平滑(over-smoothing)，以及有限的表征能力(上界为于1阶WL算法)。得益于图Transformer的设计，在对结构信息要求较高的图任务中（如[1], [2])，图Transformer的表现有着对MPNNs极大的优势 [3, 4]。

近年来，在视觉领域，不少研究者在质疑注意力机制和Transformer是不是唯一的“正确解”。不基于注意力机制的卷积网络(Convolution Networks, 简称ConvNet)，是否能够于达到Transformer一样的性能。

同样的，在图学习领域有不少研究者也在思考，是否能够不通过注意力机制来拓展MPNNs。不基于注意力机制的图卷积网络(Graph ConvNet[^1])，真的就一定不如图Transformer吗？注意力机制真的就那么重要吗？

在ICML2024上，来自麦吉尔大学， Mila魁北克人工智能研究所以及华为诺亚方舟实验室的研究者发表了一个基于连续卷积核(continuous kernel)的全新图卷积算子(图连续卷积CKGConv)，基于此算子的纯图卷积网络(CKGCN)在多个图任务中同样能够达到媲美SOTA图Transformer的性能。作者通过探索实验说明注意力机制并不是发展图神经网络唯一路径，强大的图卷积网络同样拥有其自身的优势。

论文@PMLR: https://proceedings.mlr.press/v235/ma24k.html

代码@github: https://github.com/networkslab/CKGConv

1. 突破信息传递限制的图卷积 CKGConv

定义欧几里得空间(如图像，序列等)上的卷积(Convolution)算子，实际上是利用一个查找表(Lookup Table)来存储卷积核的系数。卷积核中一个位置对应一个可学习的参数。

但由于图结构的不规则性以及排列不变性，大多数基于MPNNs的图卷积只会有一个或两个可学习参数，所有领域中的点共享一个可学习参数(在考虑一个通道的情况下)。这个性质大大限制的普通图卷积，继而导致了过度平滑(所有领域的点共享一个参数)，过度挤压(只能聚合来自相邻的点的信息)。为了克服传统图卷积的缺点，受欧几里得空间里的正则坐标系(canonical coordinates)的启发，作者提出两点改进：

1. 使用(相对/绝对)图位置编码(PE)来定义图的伪坐标系(pseudo-coordinates)，使得图卷积可以定义在连续化的伪坐标系上，而不是受限于离散的图结构上 (图结构空间上是不存在正则坐标系的)。
2. 由于伪坐标的不规则性，常规卷积中的Lookup Table同样并不适用，作者希望借助神经网络的泛化性能来克服此问题。因此作者将卷积核视为一个由相对位置映射到卷积系数的连续函数，并且重参数(reparameterize)卷积核为一个神经网络(即continuous kernel [7]).

基于这两点，我们可以很灵活的定义图卷积运算：给图上点的信号函数(node signal, 也称作点的表征) ，CKGConv的运算为

p 其中卷积后的信号函数 和 是可学习的权重矩阵和偏置向量; 为逐项乘积; 为伪坐标系定义下的相对位置编码; 是一个基于 MLP (多层感知器) 的卷积核函数。 是定义的图卷积支撑集(即卷积核覆盖的区域)。

‍作者使用了来自于GRIT[4]的随机游走概率编码RRWP来定义伪坐标系。在仅使用图连续卷积CKGConv、不使用任何注意力机制的情况下，提出的图连续卷积网络CKGCN能够在多个图任务重，达到和目前性能最好的图Transformer(如GraphGPS[3], GRIT[4])相当的表现。

2. CKGConv的性质

2.1 不局限于特定的图位置编码

为了说明CKGConv并不局限于使用RRWP，作者也尝试了其他几种常见的图位置编码PE(如电阻距离RD[5], 最短路径距离SPD[6])来定义图的伪坐标系，CKGCN也能达到接近SOTA图模型的表现。这说明CKGConv的灵活性，并不局限于某种特定的PE。

2.2 灵活的卷积核大小

得益于神经网络的泛化性能，CKGConv的卷积核函数可以支持任意定义的卷积核大小。同注意力机制一样，CKGConv也可以支持可变大小的全局图卷积运算。除此之外，作者也验证了CKGConv可以支持非全局的卷积运算，并且进行了对比实验。实验结果说明，当卷积核大小达到一定阈值后，CKGConv也可以达到和全局卷积相当的表现。这说明CKGConv具有后续拓展到更大的图数据的灵活性。

2.3 和图Transformer相当的结构表征能力

基于广义距离-WL框架[5]，作者也从理论上证明CKGConv可以拥有和图Transformer相当的结构表征能力。其表征能力介于1-WL与3-WL之间。

3. CKGConv和注意力机制的对比

注意力机制能够基于输入内容来改变权重大小，但是代价是需要Softmax来稳定输出的数值，这使得注意力系数必须是非负的。与注意力机制不同，CKGConv的权重仅基于输入的图结构，因此其不会由于输入点的信号变化而变化；由于不需要额外稳定数值输出，因此CKGConv的卷积核是可以同时有正负的系数。作者的对卷积核的可视化也证明了这点。

作者还做了消融实验，如果强加类似注意力矩阵(attention matrix)的限制于CKGConv的卷积核(kernel)的系数，即卷积核系数非负且加和为一，则CKGCN的性能会受到一定的影响。

4. 同时有正负卷积核系数的优势

作者同时也用两个小示例来展示同时有正负的系数的卷积核的优势。

4.1 CKGConv能够抵抗过度平滑问题

如图，作者考虑一个例子：相邻的点有不一样的图信号。作者分别训练2层/6层的图卷积网络(GCN [8])和图连续卷积网络 (CKGCN)来重构图上的点信号。在该实验中，作者去除了所有残差连接和标准化层：2层的GCN和CKGCN都可以100%的重构点信号；但是6层的GCN就无法重构点信号，展现的过度平滑导致的问题；但是6层的CKGCN依然能够100%重构点信号，显示它能够抵抗过度平滑问题。

4.2 CKGConv能够检测异配(heterophily)图信号

大部分图神经网络(GNNs)都较为擅长处理同配图(homophily)，即图中相连的节点更倾向于拥有相似的特征或标签。由于大部分GNNs都等价于低通滤波(Low-pass filter)，因此它们对于异配(heterophily)图信号的处理能力相对较弱。

受计算机视觉中的边缘检测(edge detection^2)启发，作者设计一个小实验去说明CKGConv具有检测周边信号变化较大的点的能力，即检测异配信号的能力。

如图，作者考虑一个例子：基于点信号(左)，图中的点能够自然分成两个簇(cluster)，任务是找到处于簇边缘的点(即，相邻的点有不一样的信号)。

在只考虑只有一个单通道的滤波(即卷积核)的情况下，CKGConv的表现远好于图卷积网络的卷积(GCNConv)。对CKGConv的卷积强加上Softmax或者Softplus来强制卷积系数非负，均会导致CKGConv检测边缘点的能力下降。这充分说明同时拥有正负卷积系数的重要之处。

5. 结合CKGConv和注意力机制？

作者还做了一个小试验，尝试结合CKGConv和图注意力机制。作者分别训练多个CKGCN和图Transformer(GRIT)，并对他们进行集成(ensemble)。作者发现GRIT和CKGCN的集成比起同一模型的集成，在ZINC上得到更好的表现。这可能启示CKGCN和GRIT学习到的信息可能是互补的。因此，如何结合CKGConv和注意力机制可能是未来的研究方向。

结论

1. 现有图卷积网络的缺陷大多数是由于图卷积(包括由其拓展的其他MPNNs)定义于离散且排列不变的图结构上。构造符合排列不变的图伪坐标系(pseudo-coordinate)可以拓展图卷积的定义，克服大部分现有图卷积的缺陷（即，过度挤压， 过度平滑，以及表征能力上界为于1-WL，处理异配图能力限制等)。
2. 使用pseudo-coordinate并不局限于使用注意力机制，利用连续卷积核(continuous kernel)可以构造出强大的图卷积(CKGConv)，可以在理论上和实征上达到于SOTA图Transformer相当的性能。
3. 结合连续图卷积(CKGConv)和注意力机制有构造出更强图模型的潜力。

参考文献

• [1] Dwivedi, Vijay Prakash, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2022. “Benchmarking Graph Neural Networks.” Journal of Machine Learning Research.
• [2] Dwivedi, Vijay Prakash, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. 2022. “Long Range Graph Benchmark.” In Adv. Neural Inf. Process. Syst. Track Datasets Benchmarks.
• [3] Rampášek, Ladislav, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. 2022. “Recipe for a General, Powerful, Scalable Graph Transformer.” In Adv. Neural Inf. Process. Syst.
• [4] Ma, Liheng, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K. Dokania, Mark Coates, Philip H.S. Torr, and Ser-Nam Lim. 2023. “Graph Inductive Biases in Transformers without Message Passing.” In Proc. Int. Conf. Mach. Learn.
• [5] Zhang, Bohang, Shengjie Luo, Liwei Wang, and Di He. 2023. “Rethinking the Expressive Power of GNNs via Graph Biconnectivity.” In Proc. Int. Conf. Learn. Represent.
• [6] Ying, Chengxuan, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. 2021. “Do Transformers Really Perform Badly for Graph Representation?” In Adv. Neural Inf. Process. Syst.
• [7] Romero, David W., Anna Kuzina, Erik J. Bekkers, Jakub Mikolaj Tomczak, and Mark Hoogendoorn. 2022. “CKConv: Continuous Kernel Convolution For Sequential Data.” In Proc. Int. Conf. Learn. Represent.
• [8] Kipf, Thomas N., and Max Welling. 2017. “Semi-Supervised Classification with Graph Convolutional Networks.” In Proc. Int. Conf. Learn. Represent.

[^1]: 图卷积网络不一定局限为MPNNs， MPNNs也不一定局限于图卷积网络。

[^2]: 边缘检测中的边缘(edge)与图数据中的边(edge)的定义并不相同。边缘检测的目的是标识数字图像中亮度变化明显的点。

公众号后台回复“数据集”获取100+深度学习各方向资源整理