基于角色感知聚类的异构图压缩

# 基于角色感知聚类的异构图压缩
来源：https://arxiv.org/html/2607.03097
###### 摘要

异构图神经网络（HGNNs）在建模包含多种节点和关系类型的复杂系统方面表现出了显著的有效性，但其在大型异构图上进行训练在计算上代价高昂。尽管图压缩方法能够有效提升大规模图上的学习效率，但现有的压缩流程主要针对同构图设计，且通常依赖计算昂贵的梯度匹配或双层优化范式，使其在异构场景下不切实际。为解决这些局限，我们提出 HGC-RC，一个简单而有效的角色感知异构图压缩框架。具体来说，HGC-RC 首先通过轻量传播提取语义增强的节点嵌入。然后引入一种角色感知的混合聚类策略：对有标签的目标节点进行类别分区聚类以保持类分布，对非目标节点进行无监督按类型聚类以保留关键的跨类型连接性。最后，基于得到的聚类分配，高效重构一个紧凑的异构图。大量实验表明，HGC-RC 优于最先进的基线方法，为在不牺牲任务性能的前提下加速大型异构图上 HGNN 的训练提供了实用途径。

## I 引言

异构图广泛应用于模拟现实场景中的复杂关系系统，例如学术网络、推荐系统和知识驱动平台 [90 (https://arxiv.org/html/2607.03097#bib.bib114),58 (https://arxiv.org/html/2607.03097#bib.bib124),41 (https://arxiv.org/html/2607.03097#bib.bib128),29 (https://arxiv.org/html/2607.03097#bib.bib129),19 (https://arxiv.org/html/2607.03097#bib.bib142),55 (https://arxiv.org/html/2607.03097#bib.bib150)]。在异构模型兴起之前，标准图神经网络（GNNs）[34 (https://arxiv.org/html/2607.03097#bib.bib1),59 (https://arxiv.org/html/2607.03097#bib.bib2),21 (https://arxiv.org/html/2607.03097#bib.bib19),7 (https://arxiv.org/html/2607.03097#bib.bib21),96 (https://arxiv.org/html/2607.03097#bib.bib24),95 (https://arxiv.org/html/2607.03097#bib.bib106),24 (https://arxiv.org/html/2607.03097#bib.bib123),4 (https://arxiv.org/html/2607.03097#bib.bib146),38 (https://arxiv.org/html/2607.03097#bib.bib151)] 在同构图表示学习方面展现出了巨大潜力。通过显式刻画多种节点和关系类型，异构图比同构图提供了更丰富的语义信息。为有效建模此类异构交互，异构图神经网络（HGNNs）[64 (https://arxiv.org/html/2607.03097#bib.bib102),63 (https://arxiv.org/html/2607.03097#bib.bib103),25 (https://arxiv.org/html/2607.03097#bib.bib120),67 (https://arxiv.org/html/2607.03097#bib.bib11),97 (https://arxiv.org/html/2607.03097#bib.bib44),14 (https://arxiv.org/html/2607.03097#bib.bib45),27 (https://arxiv.org/html/2607.03097#bib.bib43),85 (https://arxiv.org/html/2607.03097#bib.bib14),62 (https://arxiv.org/html/2607.03097#bib.bib108),43 (https://arxiv.org/html/2607.03097#bib.bib126),84 (https://arxiv.org/html/2607.03097#bib.bib135),76 (https://arxiv.org/html/2607.03097#bib.bib138),1 (https://arxiv.org/html/2607.03097#bib.bib152)] 在多个领域取得了强劲性能，包括交通网络 [94 (https://arxiv.org/html/2607.03097#bib.bib100),53 (https://arxiv.org/html/2607.03097#bib.bib117),92 (https://arxiv.org/html/2607.03097#bib.bib115),80 (https://arxiv.org/html/2607.03097#bib.bib130),42 (https://arxiv.org/html/2607.03097#bib.bib131),78 (https://arxiv.org/html/2607.03097#bib.bib137),28 (https://arxiv.org/html/2607.03097#bib.bib139),9 (https://arxiv.org/html/2607.03097#bib.bib149),56 (https://arxiv.org/html/2607.03097#bib.bib153)]、生物学 [3 (https://arxiv.org/html/2607.03097#bib.bib121),22 (https://arxiv.org/html/2607.03097#bib.bib104),35 (https://arxiv.org/html/2607.03097#bib.bib134),83 (https://arxiv.org/html/2607.03097#bib.bib136),13 (https://arxiv.org/html/2607.03097#bib.bib141),49 (https://arxiv.org/html/2607.03097#bib.bib145),73 (https://arxiv.org/html/2607.03097#bib.bib127),47 (https://arxiv.org/html/2607.03097#bib.bib154)]、关系数据库 [75 (https://arxiv.org/html/2607.03097#bib.bib118),52 (https://arxiv.org/html/2607.03097#bib.bib119),36 (https://arxiv.org/html/2607.03097#bib.bib101),72 (https://arxiv.org/html/2607.03097#bib.bib116),89 (https://arxiv.org/html/2607.03097#bib.bib111),39 (https://arxiv.org/html/2607.03097#bib.bib140),71 (https://arxiv.org/html/2607.03097#bib.bib148),74 (https://arxiv.org/html/2607.03097#bib.bib155)]，以及新兴应用如事件检测、链接预测和疾病预后 [10 (https://arxiv.org/html/2607.03097#bib.bib91),102 (https://arxiv.org/html/2607.03097#bib.bib92),12 (https://arxiv.org/html/2607.03097#bib.bib95),99 (https://arxiv.org/html/2607.03097#bib.bib96),77 (https://arxiv.org/html/2607.03097#bib.bib93),98 (https://arxiv.org/html/2607.03097#bib.bib94),65 (https://arxiv.org/html/2607.03097#bib.bib132),26 (https://arxiv.org/html/2607.03097#bib.bib147),8 (https://arxiv.org/html/2607.03097#bib.bib156)]。尽管表达能力强大，但在大型异构图上训练 HGNNs 仍然代价高昂，原因在于重复的关系感知传播、高维语义特征以及邻居扩展。

*图压缩*（GC）通过构建紧凑图同时保留下游效用，已成为加速 GNN 训练的一种有前景的范式 [33 (https://arxiv.org/html/2607.03097#bib.bib53),37 (https://arxiv.org/html/2607.03097#bib.bib105),87 (https://arxiv.org/html/2607.03097#bib.bib109),91 (https://arxiv.org/html/2607.03097#bib.bib110),51 (https://arxiv.org/html/2607.03097#bib.bib125),48 (https://arxiv.org/html/2607.03097#bib.bib144),54 (https://arxiv.org/html/2607.03097#bib.bib157)]。现有的 GC 方法在同构图上取得了令人鼓舞的成果，其中大多数方法依赖梯度匹配或双层优化来学习紧凑的合成结构和特征 [93 (https://arxiv.org/html/2607.03097#bib.bib112),86 (https://arxiv.org/html/2607.03097#bib.bib113),79 (https://arxiv.org/html/2607.03097#bib.bib133),68 (https://arxiv.org/html/2607.03097#bib.bib158)]。然而，将这些方法扩展到异构场景远非易事。在异构图中，必须同时保留多个特征空间、关系语义和跨类型依赖关系，而简单的同质化操作（如关系联合或元路径投影）可能会扭曲关系语义和类别平衡。尽管已有少数研究开始关注异构图压缩，例如 HGCond [15 (https://arxiv.org/html/2607.03097#bib.bib73)]，但这些方法仍然优化负担重且对中继模型敏感。

异构图压缩的一个关键挑战在于节点类型间的*角色不对称性*。具体来说，有标签的*目标类型*节点直接决定下游决策边界，而*非目标*节点主要提供语义和结构支持。如图 1 (https://arxiv.org/html/2607.03097#S1.F1) 所示，在节点角色相对一致的同构图中，应用统一压缩策略是合适的。相比之下，在异构图中，压缩时平等对待所有节点可能会模糊目标节点的类结构并丢弃关键支持节点。因此，捕获和利用节点角色差异对于有效的异构图压缩至关重要。

参见图标题图 1：异构图中角色感知压缩的动机。(a) 统一压缩适用于同构图。(b) 在异构图中，它可能混淆目标类别并移除支持节点。为解决这一问题，我们提出了 HGC-RC，一个用于异构图压缩的角色感知框架。HGC-RC 不依赖昂贵的迭代合成图优化，而是从数据中心的视角构建紧凑异构图。具体来说，HGC-RC 首先使用 SeHGNN 预处理计算语义嵌入，然后对目标节点执行类别分区聚类，对非目标节点执行按类型的无监督聚类。基于得到的聚类分配，它聚合原始节点特征并通过簇间连接摘要重构紧凑异构图。

我们的主要贡献如下：

- • 我们从*角色感知*视角形式化了异构图压缩问题，强调了目标节点和非目标节点在保留下游分类效用中的不对称角色。
- • 我们提出了 HGC-RC，一个高效的免优化框架，结合了目标节点的类别分区聚类、非目标节点的按类型无监督聚类以及簇级图重构。
- • 在三个异构基准上的实验表明，HGC-RC 在高压缩比下实现了具有竞争力的性能，且压缩成本远低于代表性的基于优化的基线方法。

## II 预备知识

在本节中，我们介绍符号表示、问题形式化以及图压缩的背景知识。

### II-A 符号表示与问题形式化

异构图表示为 G=\(V,E,φ,ψ\)，其中 V 和 E 分别是节点集和边集。映射 φ:V→T 将每个节点分配到一个节点类型，ψ:E→R 将每条边分配到一个关系类型，T 和 R 分别表示节点类型集和关系类型集。当 |T|=|R|=1 时，图为同构图。

我们关注定义在*目标节点类型* τt∈T（例如 DBLP [50 (https://arxiv.org/html/2607.03097#bib.bib12)] 中的 Author）上的节点分类任务，而其余节点类型作为*非目标*类型提供语义上下文和结构支持。令

Vt = {v∈V ∣ φ(v)=τt}   (1)

为目标类型节点集，令

Vu = V ∖ Vt   (2)

为非目标节点集。目标节点具有特征 X_τt 和标签 y∈{1,...,C}^|Vt|，覆盖 C 个类别，而非目标节点具有特征 {X_τ}_{τ∈T∖{τt}} 且没有任务标签。

**元路径特征**。遵循常见的异构学习实践，我们考虑一组定义在节点类型上的元路径 P。一条元路径 P∈P 可以写成

P: τ1→τ2→⋯→τL。   (3)

对于每个目标节点，可以通过沿 P 传播信息来构建基于元路径的特征，得到 X^P。

**问题定义**。给定原始异构图 G 和压缩比 ρ∈(0,1)，我们的目标是构建一个压缩异构图

Gc = (Vc, {A_r^c}_{r∈R}, X_c, y_c)，   (4)

其中 |Vc|≪|V|，使得在 Gc 上训练的 HGNN 达到与在 G 上训练可比的性能。我们按类型分配压缩预算：

|Vc^(τ)| = max(1, ⌊ρ|V^(τ)|⌋)，   (5)

其中

V^(τ) = {v∈V ∣ φ(v)=τ}   (6)

是类型 τ 的节点集，Vc^(τ) 表示类型 τ 的压缩节点。对于目标类型，HGC-RC 进一步在 M 内的类别间分配预算以保持类别平衡。压缩特征 X_c 通过在嵌入空间中学习到的聚类分配聚合原始节点特征得到。

正式地，令 f_θ 为一个 HGNN，L 表示目标节点上的任务损失。我们的目标是构建一个压缩图，使得在 Gc 上训练 HGNN 能够保留在原始图 G 上训练的下游效用，同时满足由 ρ 控制的预算。在实践中，Gc 作为紧凑的*训练图*。压缩掩码 M 对应于待压缩的有标签训练目标节点，而验证和测试目标节点保留在原始图上用于下游评估。因此，压缩的目标是在严格节点预算下保留原始异构图训练效用，而不改变标准评估协议。

### II-B 图缩减

图缩减旨在减小图规模同时保留下游 GNN 效用。现有方法主要分为三类：*图稀疏化*、*图粗化*和*图压缩* [23 (https://arxiv.org/html/2607.03097#bib.bib79),88 (https://arxiv.org/html/2607.03097#bib.bib107),44 (https://arxiv.org/html/2607.03097#bib.bib143),31 (https://arxiv.org/html/2607.03097#bib.bib159)]。

**图稀疏化与粗化**。图稀疏化选择节点或边的子集以近似保留原始图质量 [57 (https://arxiv.org/html/2607.03097#bib.bib62),2 (https://arxiv.org/html/2607.03097#bib.bib122)]。代表性的基于核心集的方法包括 Herding [69 (https://arxiv.org/html/2607.03097#bib.bib69)] 和 K-center [70 (https://arxiv.org/html/2607.03097#bib.bib70)]，它们在特征空间中选择代表性样本。在异构图中，稀疏化更具挑战性，因为必须保留节点/边类型和元路径语义；简单的采样可能会扭曲关系分布和类别平衡，导致在低保留率下准确率显著下降 [11 (https://arxiv.org/html/2607.03097#bib.bib64)]。图粗化将原始节点分组为超级节点并定义其连接以保留结构信息 [30 (https://arxiv.org/html/2607.03097#bib.bib80)]。然而，在高压缩比下，稀疏化和粗化可能会丢失关键语义，并且往往过于以拓扑为中心，无法可靠地支持异构下游任务。

**图压缩**。图压缩（GC）将大图压缩成更小的*合成*图，同时保留训练效用，受计算机视觉中数据集蒸馏成功的启发 [6 (https://arxiv.org/html/2607.03097#bib.bib58),66 (https://arxiv.org/html/2607.03097#bib.bib59),100 (https://arxiv.org/html/2607.03097#bib.bib61)]。一个代表性的早期方法 GCond [33 (https://arxiv.org/html/2607.03097#bib.bib53)] 将 GC 形式化为一个双层优化问题，通过匹配原始图和合成图之间的梯度来联合学习压缩特征和结构。后续方法通过避免代价高昂的内部循环优化并以概率方式建模离散图结构来提高效率 [32 (https://arxiv.org/html/2607.03097