使用K跳高斯扩散增强的图神经网络

# 使用K跳高斯扩散的增强图神经网络
来源: https://arxiv.org/html/2606.18317

###### 摘要

大多数图神经网络 (GNN) 核心依赖于图卷积，通常实现为直接（单跳）邻居之间的消息传递。在许多现实世界的图中，边可能带有噪声或定义不良，从而限制了信息传播到局部邻域。现有的扩散核，如个性化 PageRank (PPR) 和热核，通过全局传播缓解了这一问题，但仍然难以处理复杂的局部结构和远距离节点噪声。为了解决这些限制，我们提出了一种K跳高斯 (KHG) 扩散核，作为图数据的预处理模块。KHG 引入了具有高斯加权的多跳扩散，用于远程节点，在应用标准 GNN 之前平衡局部和全局信息传播。在多个基准数据集上的实验表明，KHG 显著优于传统的消息传递 GNN，以及 PPR 和热核扩散，特别是在噪声或结构复杂的图中。

索引词——图神经网络，节点分类，图分类

## 1. 引言

图神经网络 (GNN) 已成为分析图结构数据的重要工具，其应用涵盖社交网络、交通网络、分子图 [9 (https://arxiv.org/html/2606.18317#bib.bib4)]、生物网络、金融交易网络 [19 (https://arxiv.org/html/2606.18317#bib.bib6)] 和引文图 [21 (https://arxiv.org/html/2606.18317#bib.bib7)]。通过将深度学习与图数据相结合，GNN 在节点分类、图分类和链接预测方面取得了优异性能。大多数 GNN 建立在消息传递神经网络 (MPNN) 之上，后者通过聚合邻域信息来更新节点嵌入。代表性模型包括 GCN [12 (https://arxiv.org/html/2606.18317#bib.bib10)]、SGC [20 (https://arxiv.org/html/2606.18317#bib.bib3)]、ChebNet [6 (https://arxiv.org/html/2606.18317#bib.bib9)]、TAGCN [8 (https://arxiv.org/html/2606.18317#bib.bib12)] 和 JKNet [22 (https://arxiv.org/html/2606.18317#bib.bib8)]，涵盖了从频谱卷积到跳跃连接聚合的技术。虽然深度神经网络通常受益于更多层，但 GNN 在层数较多时会遭受过平滑问题 [14 (https://arxiv.org/html/2606.18317#bib.bib20)]，最佳性能通常出现在 2-4 跳范围内 [13 (https://arxiv.org/html/2606.18317#bib.bib18)]。诸如 DropEdge [16 (https://arxiv.org/html/2606.18317#bib.bib19)] 和 DropNode 等技术（受 dropout 启发 [18 (https://arxiv.org/html/2606.18317#bib.bib24)]）试图缓解此问题，但随机删除边/节点可能会破坏图结构。另一个挑战是信息瓶颈 [1 (https://arxiv.org/html/2606.18317#bib.bib22)]，即长程依赖关系难以捕获。此外，许多 GNN 假设简单的无权无向图，忽略了如自环和多重边等更丰富的结构模式。为解决这些限制，我们提出了 K跳高斯 (KHG) 扩散核，它引入了具有高斯加权的多跳扩散。此设计平衡了局部和全局传播，抑制了来自远距离节点的噪声，并与现有扩散核（如个性化 PageRank (PPR) [13 (https://arxiv.org/html/2606.18317#bib.bib18)] 和热核）相比提高了鲁棒性。

我们的主要贡献有三点：(1) 我们提出了 KHG 扩散核以缓解深度 GNN 中的过平滑和信息瓶颈问题。(2) KHG 通过高斯加权集成了多跳扩散，并且是一个模块化、即插即用的预处理组件，适用于现有 GNN。(3) 在节点和图分类基准上的广泛实验表明，它优于 PPR 和热核。

参考图注图 1：K=2 时 K跳高斯扩散过程的示意图。深蓝色节点表示扩散源，蓝色节点对应 1 跳邻域，浅蓝色节点表示 2 跳邻域。扩散后，边按其扩散权重排序，仅保留权重最高的边。对所有节点重复此过程，最后合并生成的扩散图以构建 K跳高斯扩散图。
## 2. 相关工作

不同的GNN与消息传递：在GNN中，经典模型如 GCN [12 (https://arxiv.org/html/2606.18317#bib.bib10)]、SGC [20 (https://arxiv.org/html/2606.18317#bib.bib3)] 和 ChebNet [6 (https://arxiv.org/html/2606.18317#bib.bib9)] 仅聚合 1 跳邻居，限制了长程建模，而过度的多跳扩散会导致过平滑。GraphSAGE [10 (https://arxiv.org/html/2606.18317#bib.bib29)] 是一个完整的 GNN 模型，它聚合来自 1 跳和 2 跳邻域的信息，以在计算成本和过平滑之间取得平衡。其跳数通常限制为 2，因为更大的邻域可能引入噪声并增加模型复杂性。相比之下，我们的 K跳高斯 (KHG) 扩散是一个预处理模块，而非完整的 GNN，它允许灵活选择更大的 K 跳范围来传播信息，同时通过高斯加权控制远距离节点的贡献。扩散核推广了这个思路：PPR [13 (https://arxiv.org/html/2606.18317#bib.bib18)] 使用个性化随机游走，热核则模拟热流，两者都缺乏显式的跳数控制。GRAND [4 (https://arxiv.org/html/2606.18317#bib.bib34)] 提高了灵活性，但需要迭代或采样步骤。KHG 以闭合形式实现了高效、抗噪且确定性的多跳扩散。扩散机制：在 GNN 中，信息传播是学习节点关系的关键。经典模型如 GCN [12 (https://arxiv.org/html/2606.18317#bib.bib10)]、SGC [20 (https://arxiv.org/html/2606.18317#bib.bib3)] 和 ChebNet [6 (https://arxiv.org/html/2606.18317#bib.bib9)] 依赖于 1 跳聚合，限制了长程建模，而过度的多跳扩散会导致过平滑。PPR [13 (https://arxiv.org/html/2606.18317#bib.bib18)] 和热核等方法捕获了更广泛的上下文，但缺乏显式的跳数控制。GRAND [4 (https://arxiv.org/html/2606.18317#bib.bib34)] 通过可学习或连续扩散增强了灵活性，但产生了迭代或采样开销。我们的 K跳高斯 (KHG) 扩散提供了一种闭合形式的替代方案：一个高斯衰减的多跳核，能平滑地平衡局部和全局传播，同时保持高效和抗噪性。不同的GNN与消息传递：高斯滤波是图像处理中的经典去噪技术，也广泛用于深度视觉模型 [11 (https://arxiv.org/html/2606.18317#bib.bib17)]。受图上的频谱滤波启发 [3 (https://arxiv.org/html/2606.18317#bib.bib23)]，我们将其扩展到 GNN 以控制多跳传播。在图像中，像素 (x, y) 的高斯核为 G(x,y)=1/(2πσ^2) exp(−(x^2+y^2)/(2σ^2))，其中 σ 控制平滑尺度。大的 σ 产生宽泛滤波，小的 σ 保留精细细节。类似地，在图中我们用跳距 i 替代空间距离，得到权重 w(i,σ)=exp(−i^2/(2σ^2))，它随 i 平滑衰减。这桥接了局部和全局传播：小的 σ 强制局部平滑，而大的 σ 纳入更广泛的上下文，从而缓解深度 GNN 中的过平滑问题。

参考图注图 2：K跳高斯扩散模型性能比较。
## 3. 方法

### 3.1 图归一化与转移矩阵

K跳高斯 (KHG) 扩散是一种基于高斯核的方法，能够在 GNN 中实现多跳传播，确保信息随距离平滑衰减，以缓解过平滑和噪声。输入是邻接矩阵 A∈R^(N×N)，其中若节点 i 和 j 之间存在边则 A_ij=1，否则为 0。目标是构建一个平衡局部平滑与长程依赖的扩散矩阵。关键步骤是对 A 进行归一化以获得稳定的转移矩阵 T。如果不进行归一化，度不平衡会导致传播不均匀。两种广泛使用的形式是：对称归一化：T_sym = D^(-1/2) A D^(-1/2)，其中 D_ii = Σ_j A_ij。此形式平衡了入度和出度，如 GCN [12 (https://arxiv.org/html/2606.18317#bib.bib10)]。列归一化：T_col = D^(-1) A，它均匀地将节点的信息分配给其邻居，防止低度节点的信息过度稀释。T_sym 和 T_col 都作为多跳传播的基本算子 (T^k)，随后在 KHG 扩散中与高斯权重结合。与未归一化的 A 相比，这些归一化形式保证了稳定性，并在异构图保留了结构平衡。

### 3.2 K跳高斯扩散机制

设 A∈R^(N×N) 为邻接矩阵，D=diag(d_i) 为度矩阵。我们首先形成一个归一化的转移算子 T（我们使用对称或列归一化）：T_sym = D^(-1/2) A D^(-1/2)，T_col = D^(-1) A。i 跳转移算子是 T 的 i 次幂，并满足递归关系：

T^(1) = T，T^(i) = T^(i-1) T (i≥2)，(1)

或元素形式 T_uv^(i) = Σ_k T_uk T_kv^(i-1)，它编码了 i 跳内的可达性和聚合传播。为了控制跳数影响，我们引入高斯跳权重：

w(i,σ) = exp(-i^2/(2σ^2))，i=1,...,K，(2)

其中 σ>0 是尺度，K 是最大跳数截止值。未归一化的多跳核聚合加权幂次：D̃_K = Σ_{i=1}^K w(i,σ) T^(i)。通过标量权重和 Z(σ)=Σ_{i=1}^K w(i,σ) 进行归一化，我们得到最终的扩散核：

D_K = D̃_K / Z(σ) = (Σ_{i=1}^K w(i,σ) T^(i)) / (Σ_{i=1}^K w(i,σ))。(3)

若 T = UΛU^(-1)（当 T 对称时 U 正交），则：

T^(i) = UΛ^i U^(-1)，D̃_K = U(Σ_{i=1}^K w(i,σ) Λ^i) U^(-1)，

因此 D_K 作为一个多项式频谱滤波器：

D_K = U diag(g(λ_j)) U^(-1)，g(λ) = (Σ_{i=1}^K w(i,σ) λ^i) / (Σ_{i=1}^K w(i,σ))。(4)

因此 KHG 是一个具有高斯系数的 K 次多项式滤波器。作为比较，PPR 对应几何权重 D_PPR = α Σ_{i≥0} (1-α)^i T^i = α(I-(1-α)T)^(-1)，热扩散对应阶乘/指数级数 exp(tT)=Σ_{i≥0} t^i/i! T^i。显式构建 D_K 可能会使矩阵变密；相反，可以通过递归计算 D_K X 来处理特征矩阵 X∈R^(N×d)。设 Y^(0)=X 且 Y^(i)=T Y^(i-1)，i=1,...,K，则：

D_K X = (Σ_{i=1}^K w(i,σ) Y^(i)) / (Σ_{i=1}^K w(i,σ))。(5)

这避免了存储 T^(i)，并导致简单的迭代过程：迭代 K 次稀疏乘法 Y←T Y，累积 w(i,σ) Y 并除以 Z(σ)。当在特征级别实现时（稀疏 T）。显式矩阵构建在最坏情况下可能导致存储密集化为 O(N^2)。实践中使用稀疏累积和可选的逐行 top-m 稀疏化以保持 D_K 稀疏。参数语义直观：小的 σ 将质量集中在低阶幂次上（局部平滑），大的 σ 将质量分布到各跳（更多全局聚合）；K 限制最大传播深度。

## 4. 实验

表 1：不同扩散机制下GNN模型在各数据集上的性能对比### 4.1 数据集与基线

在我们的实验中，我们评估了所提出的 K跳高斯 (KHG) 扩散与一系列代表性 GNN 基线的比较，包括 GCN [12 (https://arxiv.org/html/2606.18317#bib.bib10)]、SGC [20 (https://arxiv.org/html/2606.18317#bib.bib3)]、ChebNet [6 (https://arxiv.org/html/2606.18317#bib.bib9)]、TAGCN [8 (https://arxiv.org/html/2606.18317#bib.bib12)]、JKNet [22 (https://arxiv.org/html/2606.18317#bib.bib8)]，以及高级扩散方法 GRAND [4 (https://arxiv.org/html/2606.18317#bib.bib34)]。对于节点分类，我们使用了三个基准引文网络：Cora、CiteSeer、Pubmed [15 (https://arxiv.org/html/2606.18317#bib.bib31)] 和 Chameleon [17 (https://arxiv.org/html/2606.18317#bib.bib27)]。对于图分类，我们考虑了三个分子和蛋白质数据集：ENZYMES [2 (https://arxiv.org/html/2606.18317#bib.bib28)]、MUTAG [5 (https://arxiv.org/html/2606.18317#bib.bib30)] 和 PROTEINS [7 (https://arxiv.org/html/2606.18317#bib.bib32)]。没有官方划分的数据集（例如 Chameleon、ENZYMES、MUTAG、PROTEINS）使用固定的随机种子 42 按 7:2:1 比例随机分为训练/验证/测试集，以确保可重复性。每个实验重复多次，结果以 95% 置信区间报告，以确保稳定性和鲁棒性。

### 4.2 性能对比

表 I 报告了四种扩散机制（无、PPR、热核、KHG）在三个节点分类数据集（Cora、CiteSeer、Chameleon）和三个图分类数据集（MUTAG、ENZYMES、PROTEINS）上与五种 GNN 模型（GCN、SGC、ChebNet、TAGCN、JKNet）结合的结果。总体而言，KHG 始终优于其他核。例如，在 Cora 上，GCN+KHG 达到了 82.0%，超过了无（80.8%）和 PPR/热核。在 Chameleon 上，ChebNet+KHG 达到了 48.9%，比无高出 3.7%。在图分类中，改进更大：ChebNet+KHG 在 MUTAG 上达到了 93.0%，比无高出 7.9%；GCN+KHG 在 ENZYMES 上提高了 5.0%。这些结果表明，高斯加权有效地增强了稀疏图和复杂图中的鲁棒性。K 的选择强烈影响性能。对于较小、稀疏的图（Cora、MUTAG），小 K（<10）是最优的；而对于更密集或异质的图（Chameleon、ENZYMES），中等 K（>10）通过捕获更多全局信息而不引入过多噪声，产生更好的准确率。这一趋势凸显了 KHG 对不同图规模和结构的适应性。

参考图注图 3：σ 对准确率的影响（Cora 数据集，固定 K）。效率。与依赖于迭代幂级数或矩阵指数化的 PPR 和热核不同，KHG 是一个闭合形式的预处理步骤。在 PubMed（19000 节点，88000 边，500 维特征）上，