近年来，基于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
)的启发，作者提出两点改进：
-
使用(相对/绝对)图位置编码(PE)来定义图的伪坐标系
(pseudo-coordinates)，使得图卷积可以定义在连续化的伪坐标系上，而不是受限于离散的图结构上 (图结构空间上是不存在正则坐标系的)。
-
由于伪坐标的不规则性，常规卷积中的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检测边缘点的能力下降。这充分说明同时拥有正负卷积系数的重要之处。
