自适应互补增强修复异质性下基于粗化的GNN训练

# 基于自适应互补增强的异质性图粗化GNN训练修复方法 来源: https://arxiv.org/html/2607.21885

Jian Yang  
中国人民大学信息学院, 北京, 中国  
Xukun Wang  
中国科学院数学与系统科学研究院, 北京, 中国  
Zixiao Wang  
穆罕默德·本·扎耶德人工智能大学, 阿布扎比, 阿联酋  
Shangsong Liang  
中山大学计算机学院, 广州, 中国  
Yifan Chen† (mailto:[email protected])  
香港浸会大学计算机科学系, 香港特别行政区, 中国  

###### 摘要

基于粗化的图神经网络（GNN）训练，即在粗化图上而非原始大图上进行训练，已成为将GNN扩展到大规模图的一种有前景的方向。然而，以往的工作几乎只在同质性图上进行评估，而更具挑战性的异质性设置尚未得到充分探索。我们通过实证和理论分析表明，现有的基于粗化的训练方法在异质性图上会出现显著的性能下降，这是因为粗化过程中不可避免地丢失了图信息。为解决这一问题，我们提出**自适应互补增强（ACE）**，这是一种即插即用、模型无关的策略，旨在重新整合粗化过程中丢弃的信息：ACE学习一个投影器用于重构原始节点特征，并应用**各向异性结构正则化**来嵌入局部异质性。我们进一步采用**同方差不确定性加权**来自适应地平衡主粗化图训练损失与全图辅助损失（使用由异质性感知投影器重构的增强节点特征）的组合训练目标。大量实验表明，ACE在异质性基准测试上取得了持续的性能提升，同时在同质性图上以最小的计算开销保持了有竞争力的结果。代码可在GitHub仓库获取：https://github.com/vasile-paskardlgm/ACE。

## 1 引言

图神经网络（GNN）已成为从图信号中捕获结构信息的强大工具，在广泛的结构化和基于图的应用中表现卓越（Wu et al., [2022]）。然而，随着现实世界的图扩展到数百万节点和数十亿边，主流传播算法的计算复杂度导致训练成本高昂（Zhou et al., [2022]）。为此，研究者提出了多种可扩展训练策略，包括**以模型为中心**的图采样（Serafini and Guan, [2021]）和**以数据为中心**的图约简（Hashemi et al., [2024]）。在以数据为中心的方法中，**图粗化**已成为一种广泛采用的范式（Huang et al., [2021], Kumar et al., 2023b, Kataria et al., 2024, Xia et al., 2025, Dickens et al., 2024）。通过在缩减后的图上训练GNN，并对原始规模进行预测，这些方法实现了显著的效率提升。与**图浓缩**（Jin et al., [2022]）不同，粗化是**模型无关**的，允许一个粗化图支持广泛的GNN架构系列（Huang et al., [2021], Kataria et al., 2024）。尽管取得了实证成功，现有粗化方法几乎完全针对**同质性图**开发，使得更具挑战性的**异质性图**（与**异构图**不同；Wang et al. 2023）在很大程度上未被探索（Gong et al., [2024]）。在同质性图中，相邻节点倾向于共享相似的标签或特征，而这一假设在异质性图中不成立；在此类图中，邻居通常具有不同的标签或表示。我们的初步分析（在第2.2节）表明，与全图训练相比，基于粗化的训练在异质性图上的性能下降更为明显，而在同质性图上的下降则显著较小。我们尝试通过互信息的视角解释这一差异，表明图异质性显著加剧了通过粗化训练的模型与在全图上训练的模型之间的**互信息差距**。这些结果表明，异质性对基于粗化的训练构成了根本性挑战。

为此，本文提出**自适应互补增强（ACE）**，这是一种即插即用、模型无关的框架，用于增强异质性下的基于粗化的GNN训练。ACE的核心原理是通过一种异质性感知的辅助损失，重新整合粗化过程中丢弃的图信息。具体而言，ACE首先学习一个精细化的**投影器**，用于利用平均化超节点特征重构原始节点特征；该学习过程进一步通过**各向异性结构正则化**（参见公式(3.2.1)）来识别异质性。该正则化源自各向异性图扩散，并主要适用于监督式GNN训练设置（Chamberlain et al., [2021], Elhag et al., [2022]）；在此，我们将其制定为一种无监督数据增强机制，将局部异质性嵌入到重构特征以及投影器中。由此得到的投影器将粗化图上的GNN预测提升回全图尺度，以定义相对于全图标签的辅助损失。为进一步稳定训练，我们采用**同方差不确定性**（Kendall et al., [2018]）自适应地权衡辅助目标与主粗化损失。ACE的模块化特性使其能够无缝集成到现有流程中，我们的实证研究验证了其持续的性能提升。总之，我们的主要贡献如下：

- **我们发现**了基于粗化的GNN训练中的异质性挑战，并提供了实证证据和理论解释，突出这一未被充分探索的局限性。
- **我们提出了自适应互补增强（ACE）**，这是一种即插即用、模型无关的方法，通过异质性感知的辅助损失增强基于粗化的训练。
- **我们进行了大量实验**，在大规模异质性和同质性基准测试上证明ACE以显著的优势持续改善了粗化训练。

## 2 预备知识与挑战

我们首先介绍关键符号和背景知识，然后通过实证和理论分析识别现有粗化训练中的异质性挑战。

### 2.1 符号与预备知识

##### 符号。
设 \(\mathcal{G} = (A, X)\) 表示一个图，其中 \(A \in \{0,1\}^{n \times n}\) 表示邻接矩阵，\(X \in \mathbb{R}^{n \times d}\) 是节点特征/信号。归一化图拉普拉斯矩阵定义为 \(L = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\)（Chung, [1997]），其中 \(I\) 是单位矩阵，\(D\) 是度矩阵。此外，我们记 \(Y \in \{0,1\}^{n \times c}\) 为独热编码的标签矩阵，其中 \(c\) 是节点类别数。关于图粗化，我们遵循先前文献（Liu et al., [2018], Chen et al., 2022a），令 \(\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_{n'}\) 为节点集的一个划分，包含 \(n' < n\) 个不相交的簇，每个簇对应粗化图中的一个**超节点**。划分矩阵 \(P \in \{0,1\}^{n' \times n}\) 满足：若节点 \(v_j \in \mathcal{C}_i\)，则 \(P_{i,j}=1\)。粗化图 \(\mathcal{G}' = (A', X')\) 由下式给出：
\[
A' = P A P^T, \quad X' = C^{-1} P X, \quad Y' = C^{-1} P Y,
\]
其中 \(C = \text{diag}(|\mathcal{C}_1|, |\mathcal{C}_2|, \dots, |\mathcal{C}_{n'}|)\)。

##### 基于粗化的GNN训练。
遵循先前工作（例如，Huang et al., [2021], Xia et al., [2025]），粗化训练旨在通过在粗化图 \(\mathcal{G}'\) 上训练来提高效率，同时力求保留与在全图 \(\mathcal{G}\) 上训练的模型相当的下游性能。形式上，这一范式可定义如下：

###### 定义 2.1（基于粗化的GNN训练）。
设 \(f(; \Theta)\) 表示一个具有参数集 \(\Theta\) 和 softmax 输出层的 GNN。基于粗化的 GNN 训练最小化粗化图上的任务损失：
\[
\mathcal{L}(f(A', X'; \Theta), Y'),
\]
该损失作为原始图损失的代理目标：
\[
\mathcal{L}(f(A, X; \Theta), Y).
\]
本文中，我们聚焦于**节点分类**任务，其中 \(\mathcal{L}\) 实例化为**交叉熵**损失，遵循先前研究（Huang et al., [2021], Kumar et al., 2023b, Kataria et al., 2024, Xia et al., [2025]）。

##### 异质性图。
异质性图——与**异构图**不同（Wang et al., [2023]）——已成为现代节点分类研究的核心焦点（Zheng et al., [2024], Gong et al., [2024]）。与同质性图（其中相邻节点通常共享相似标签或属性）不同，异质性图连接不相似的节点，违反了消息传递 GNN 背后的关键假设，并常常加剧**过度平滑**效应（Rusch et al., [2023], Yan et al., [2022]）。此类结构常见于现实世界网络（例如，金融、通信和某些分子图），并对 GNN 架构提出了独特挑战（Lim et al., [2021], Platonov et al., [2023]）。尽管异质性至关重要，但它在基于粗化的 GNN 训练中的影响在很大程度上尚未得到检验，这留下了本文将要探索的一个显著空白。

##### 图上的 Dirichlet 能量。
设 \(E\) 为图 \(\mathcal{G}\) 的边集。节点特征 \(X\) 的 Dirichlet 能量通常定义为：
\[
\mathcal{E}(\mathcal{G}) = \frac{1}{2} \sum_{(i,j) \in E} A_{ij} \left\| \frac{X_i}{\sqrt{D_{ii}}} - \frac{X_j}{\sqrt{D_{jj}}} \right\|_2^2 = \text{trace}(X^\top L X). \tag{1}
\]
Dirichlet 能量是图上平滑性的基本描述符，对于理解图上的扩散、传播和卷积行为至关重要（Giovanni et al., [2023], Han et al., [2023]）。这一概念与上述关键现象密切相关：异质性（标签信号具有高 Dirichlet 能量）（Maskey et al., [2023]）和过度平滑（重复的图传播将节点表示的能量推向零）（Cai and Wang, [2020]）。

### 2.2 异质性挑战

##### 经验观察。
我们考察现有基于粗化的 GNN 训练方法在异质性下的表现。具体来说，我们评估了三种代表性方法——SCAL（Huang et al., [2021]）、FGC（Kumar et al., 2023b）和 SGBGC（Xia et al., [2025]）——采用 10% 的粗化比率，覆盖大规模异质性图（Genius、Gamers、Wiki（Lim et al., [2021]））和同质性图（Ogbn-arxiv、Ogbn-products（Hu et al., [2020]））。实验使用三种骨干 GNN：GCN（Kipf and Welling, [2017]）、LINKX（Lim et al., [2021]）和 GloGNN（Li et al., [2022]），其中后两者是专门为异质性设置设计的。完整细节见第 4.1 节。

**表 1：异质性对基于粗化的训练的影响。** “-” 表示全图训练，\(\Delta \downarrow\) 表示每个数据集上粗化训练相对于全图训练的平均性能下降。

| 骨干      | GCN                          | LINKX                          | GloGNN                         | \(\Delta \downarrow\) |
|-----------|------------------------------|--------------------------------|--------------------------------|-----------------------|
| 方法      | -    | SCAL | FGC  | SGBGC | -    | SCAL | FGC  | SGBGC | -    | SCAL | FGC  | SGBGC |                       |
| Genius    | 87.42 | 67.47 | 70.13 | 71.22 | 90.77 | 60.62 | 65.49 | 62.68 | 90.66 | 59.47 | 63.81 | 67.33 | 26.26                |
| Gamers    | 62.18 | 47.39 | 40.14 | 44.62 | 66.06 | 50.13 | 42.48 | 47.60 | 66.19 | 46.28 | 45.92 | 47.15 | 19.07                |
| Pokec     | 75.45 | 50.44 | 53.81 | 55.48 | 82.04 | 56.48 | 57.63 | 54.18 | 83.00 | 61.58 | 66.91 | 63.77 | 22.35                |
| Arxiv     | 71.74 | 63.42 | 65.52 | 64.12 | 69.54 | 57.71 | 59.38 | 61.55 | 72.68 | 57.09 | 61.73 | 61.24 | 7.79                 |
| Products  | 75.64 | 68.37 | 71.28 | 71.96 | 74.59 | 62.49 | 67.52 | 64.93 | 77.48 | 66.53 | 70.46 | 69.11 | 6.50                 |

表 1 的结果揭示了一个显著趋势：**所有**基于粗化的方法在异质性图上的性能下降都远大于同质性图——通常大约**四倍**——而且这在所有骨干模型（包括专门处理异质性的架构 LINKX 和 GloGNN）上都是一致的。值得注意的是，这些面向异质性的模型甚至表现出更大的性能下降，表明困难并非来自模型本身，而是来自异质性设置下基于粗化的训练的**更根本的局限性**。支持这一观察的更多实证结果见第 4 节的主要实验和附录 D.4。

##### 理论解释。
异质性图上的实证结果揭示了在粗化图与全图上训练的模型之间存在显著且一致的性能差距，表明性能下降源于粗化过程本身。受此观察启发，我们从信息论角度研究异质性挑战，以理解这种差距是如何以及为何产生的。

设 \(\mathcal{G} \setminus \mathcal{G}'\) 表示粗化过程中**丢弃的图信息**，包括超节点内部的结构细节（如图 1 所示）。利用这一概念，