降级但非完全无效：基于PE的可变形图神经网络

# 退化但并非完全无效：基于位置编码的可变形图神经网络
来源：https://arxiv.org/html/2609.13712
期刊：神经网络
张新亮
邮箱：[[email protected]](mailto:[email protected])
单位：河南理工大学，中国河南省焦作市，454000
通讯作者：通讯作者

###### 摘要

许多现实世界场景可以用图结构数据来表示。然而，基于一阶邻居传递消息的传统图神经网络长期以来面临几个基本矛盾：增加深度会导致过平滑，远距离依赖造成过压缩，固定邻域限制了感受野，而在异配图上，拓扑邻居则成为噪声的来源。尽管已有许多工作分别解决了这些问题，但很少有机制能同时缓解所有这些挑战。为了解决上述问题，我们提出了一种基于位置编码的可变形空间聚合模块，它能一步到位地解决所有问题。具体来说，我们在位置空间利用可变形机制来识别相关节点，以补充传统GNN的一阶邻居信息，从而使传统GNN能够适应异配场景。通过诊断实验，我们得出了几个主要发现：当前偏移量未能产生任何效果；随后，我们分析了偏移失效的原因以及为什么在偏移失效后模型性能仍然提升，并指出了未来的研究方向。基于这些诊断实验，我们精简了原始的PEBDSAM，得到了一个简化版本，我们称之为基于位置编码的空间聚合模块。此外，我们还提出了一个PEBSAM-Speed版本以适应大规模数据集。最后，我们将该模块设计为即插即用，并将其应用于GCN、GAT、GIN和GraphSAGE，在三个同配数据集和六个异配图数据集上都取得了理想的结果。

###### 关键词：

图神经网络，位置编码，可变形，诊断实验，异配图

## 1 引言

许多现实世界场景可以用图结构数据来表示，例如交通网络、分子结构和社会系统。因此，设计处理图结构数据的方法尤为重要。

早期，受卷积神经网络在自然语言处理和计算机视觉领域巨大成功的启发，Bruna等人（2013年）首次将卷积引入图结构数据，提出了基于谱的图卷积网络。当时，在空间域直接定义图卷积极其困难且具有挑战性；因此，他们通过计算图拉普拉斯矩阵L的所有特征值来处理图信号，从而在谱域定义了卷积运算。为了缓解谱GCN所需的昂贵特征分解带来的巨大计算成本，Defferrard等人（2016年）提出了ChebNet，使用切比雪夫多项式近似谱卷积核，从而避免了特征分解，并使模型复杂度与图中边的数量呈线性关系。Kipf和Welling（2017年）更进一步，对ChebNet进行了一阶近似，极大地简化了模型。从空间角度看，它只聚合一阶邻居。然而，聚合权重是固定的且不可学习。Hamilton等人（2017年）引入了GraphSAGE，通过对一阶邻居进行采样，大大降低了计算成本，使其非常适合大规模图数据集。此外，GraphSAGE引入了可学习的聚合方法，如LSTM聚合。随着Transformer的出现，LSTM的地位受到了显著冲击。Veličković等人（2018年）受Transformer中注意力机制的启发，提出了基于自注意力机制的GAT，提供了对邻居重要性的更精确评估。这些方法建立在先前工作的基础上并加以改进，不仅具有优雅简洁的公式，而且被广泛应用并在各个领域取得了显著成功。

然而，它们存在一些固有问题：

1. 1. 受限感受野：单层只有一阶邻域感受野。要扩展它，需要堆叠多层，这不仅增加了模型参数数量，还可能导致过平滑。
2. 2. 过压缩：图中拓扑距离较远的节点需要许多GNN层才能相互获取信息，且跨多条边的逐步传播会导致显著的信息损失。
3. 3. 泛化能力有限：传统GNN基于同配假设，即相连的节点往往具有相似的特征和标签。这使得它们在处理同配图时表现出色，但在异配图上通常表现不佳。

在计算机视觉领域，Dai等人（2017年）提出了可变形卷积。传统卷积核具有固定和规则的形状，在预定位置进行采样，并且拥有固定的感受野大小。这类似于当前的传统GNN：由于静态图数据中的边是预定义且不可变的，处理此类数据的GNN的单层感受野也是固定的——即仅限于一阶邻居。可变形卷积突破了固定规则网格的限制，允许模型自主决定在哪里“看”。为了赋予GNN可变形卷积的灵活性，模型架构必须能够自适应地调整边。这不仅赋予模型自适应的感受野，还允许当模型调整边时，原本在图拓扑中距离遥远的节点之间建立直接连接，从而避免过压缩。对边结构的自适应调整和重建也打破了同配假设——即如果两个节点之间存在边，它们往往具有相似的特征和类别标签。这使得模型能够应用于异配图，增强了其通用性。因此，上述问题一举得到解决。由于我们的工作仍处于早期探索阶段，设计的模块尚不完美，可以在第4节中提到的方面进行改进。同时，我们希望更多人加入这个社区，共同探索。

本文提出了PEBDSAM。具体来说，传统GNN通过结构关系聚合一阶邻居；这些信息被称为结构信息。而我们的PEBDSAM则提供空间信息。位置编码空间中的每个节点通过动态偏移量寻找新的空间相关节点，随后聚合这些新节点的特征，我们称之为空间特征。最后，模型自适应地融合结构和空间特征。空间特征中识别的新节点可能在图拓扑中相距数跳，这使得我们能够在单次聚合中遍历图中的长距离，显著缓解过压缩问题。然而，这些新节点也提供了更大、更全面的感受野，克服了一阶邻居的局限性。为了证明我们所提模型的通用性，我们在同配图和异配图上都进行了实验，我们的模型都表现出优越的性能。然而，在后续的模型诊断中，我们发现可变形机制中的偏移量在模型收敛时趋近于零，表明可变形机制失效了。我们深入分析了这一现象，揭示了其根本原因，以及我们工作的当前局限性和未来研究建议。此外，我们还分析了为什么在偏移失效后模型性能仍能提升。最后，我们报告了若干额外发现。在完成模型诊断并基于这些发现后，我们简化了所提出的PEBDSAM，并引入了一个精简模型。为了使我们的模型能够在大规模图上运行，我们进一步提出了PEBSAM-Speed。总之，我们的主要贡献如下：

1. 1. 为了解决传统GNN在异配图上性能不佳的问题，我们提出了一种结合结构信息和空间信息的新颖架构，从而使标准GNN能够应用于异配场景。
2. 2. 在图神经网络领域，位置编码的作用目前被低估；因此，我们展示了一个新的应用案例。
3. 3. 为了解决传统GNN中感受野大小固定和远距离节点过压缩的问题，我们提出了PEBDSAM，它提供空间信息以同时扩大感受野并缓解过压缩。
4. 4. 我们的框架在三个同配图和六个异配图上取得了有前景的性能。特别是在异配图上，性能提升显著，凸显了我们空间信息的优势。

我们首先在第2节回顾相关工作，然后在第3节详细阐述我们提出的方法。诊断实验和分析在第4节呈现。简化模型在第5节介绍。实验和消融研究在第6节报告，结论在第8节得出。

## 2 相关工作

### 2.1 可变形卷积

卷积神经网络已被广泛应用并在各个领域取得了显著成功。然而，受固定感受野限制的传统卷积核在建模具有多样形变的对象时存在局限性。为了解决这一限制，Dai等人（2017年）；Zhu等人（2019年）提出了可变形卷积，通过学习偏移量来突破固定感受野的约束，实现自适应感受野。该技术随后被应用于特征对齐和众多领域。受此工作启发，它被引入注意力机制，催生了可变形DETR。本工作致力于将可变形机制引入GNN，以解决传统GNN固有的缺陷，如固定感受野。

### 2.2 GNN中现有的可变形机制

Park等人（2022年）提出了可变形图卷积网络，其核心公式如下：

y_v = ∑_{u∈˜N(v)} g_deform(r_{u,v}, Δ_k(e_v)) h_u,

从公式（1）可以看出，可变形卷积的思想被引入了聚合方法中。原始论文表明，这种新颖的聚合方法优于GAT，值得称赞。然而，这个可变形公式实际上并没有扩大感受野，因为h_u保持不变，仍然只聚合一阶邻居，只是聚合权重被修改了。本质上，它们通过构建多个潜在邻居图来扩展感受野，因为对于任何给定节点，其邻居在不同潜在邻居图中是不同的。最终结果是通过注意力聚合所有邻居图得到的。

Park等人（2025年）提出了一个可变形图Transformer。其核心创新是应用NodeSort模块，该模块根据多个标准对原始图数据中的每个节点进行重新排列，从而生成几个新的有序节点特征序列。这些是一维的，类似于NLP中的token序列，然后对这些有序序列应用可变形图注意力，以实现自适应感受野。这两种方法都具有很强的通用性，并在异配和同配图上都取得了有前景的性能，令人鼓舞。然而，我们的方法与它们不同。上述两种方法都需要对图数据进行预处理——DGCN通过构建多个潜在邻居图来实现，而DGT则使用多个标准重新排列节点特征。相比之下，我们利用偏移量将可变形卷积引入PE空间，直接识别PE空间中超出一阶邻居范围的新的相关节点，从而扩大感受野并缓解过压缩。

## 3 提出的方法

### 3.1 总体架构与简要分析

图1：总体架构
所提模型架构如图1所示。最初，我们的想法是使用可变形机制来调整边；然而，在图数据集中，边的数量远超过节点的数量。由于对单条边进行操作的计算复杂度很高，必须采用某些技术。我们也进行了初步实验，显示出一些性能改进，但与最先进水平相比仍有显著差距。

图2：简化模型示意图
因此，我们提出了一个简化版本。PEBDSAM提供了更大的感受野；然而，这可能会引入不必要的噪声。处理策略如下：结构信息和空间信息可以通过门控机制进行过滤，以减少结构信息和空间信息中的噪声；同时在空间信息内部，使用注意力机制来减弱噪声节点的影响并增强相关节点的作用。对于结构信息，传统模型如GAT也可用于减少噪声节点的影响。因此，这在理论上是可行的。下面，我们将介绍本文提出的简化模型。

### 3.2 模型介绍

图3：所提PEBDSAM示意图
图3说明了所提PEBDSAM的核心模块。输入x ∈ ℝ^{N×d}（其中N是节点数，d是原始维度）首先通过公式（2）生成M个偏移量。

h_i = MLP_embed(x_i) = W_embed * x_i + b_embed ∈ ℝ^{d_h}
Δ_{i,j} = σ( MLP( h_i || PE_i ) ), j=1,...,M

其中M表示偏移量的数量。