Anchor-guided Hypergraph Condensation with Dual-level Discrimination¶
会议: ICML 2026
arXiv: 2605.10001
代码: 未公开
领域: 图学习 / 超图神经网络 / 数据集蒸馏 (Graph/Hypergraph Condensation)
关键词: hypergraph condensation, HKPR diffusion, anchor-guided hyperedge, dual-level discrimination, MMD
一句话总结¶
AHGCDD 把超图凝聚 (HGC) 从"先训练结构生成器、再匹配训练轨迹"的解耦范式重写为端到端框架：用 Heat-Kernel-PageRank 把结构信息塞进初始化特征、用 anchor-guided 思路按特征距离合成稀疏可学的超边，再用粗+细双级判别损失 (类原型 MMD + 实例级对比) 代替昂贵的 HNN 重训练，在 5 个超图基准上 ≥SOTA 同时最高 144× 加速。
研究背景与动机¶
领域现状：超图神经网络 (HNN) 在社交分析、生化、电商等领域擅长建模高阶交互；但大规模超图训练算力开销巨大。图凝聚 (Graph Condensation, GC) 把原图压成小合成图同时保持下游 GNN 性能；2025 年 HG-Cond 把它推广到超图——预训练一个 Neural Hyperedge Linker (NHL) 用变分推断捕捉高阶连通性，再用 GPSM 通过反复重训 HNN 来对齐训练轨迹。
现有痛点：HG-Cond 有两个根本问题——(1) 结构生成与特征优化解耦：NHL 在 amelioration 阶段被冻结，它只优化过"重建原超图" 而没和合成特征联合训过，导致结构与节点不匹配，下游精度受损；(2) 轨迹匹配资源密集：每轮 amelioration 要重训 HNN，再加上 NHL 变分预训练的显存代价，总开销难以扩展到大规模超图。
核心矛盾：把"结构 / 特征 / 训练轨迹" 同时塞进 bi-level 优化必然要么重训要么对齐损失复杂；要在不重训的前提下保持下游精度，必须找到一个既能监督结构又能监督特征的轻量信号。
本文目标：(1) 把结构生成器纳入端到端优化避免错位；(2) 找一个无需 HNN 重训的对齐目标；(3) 在初始化阶段就把高阶结构信息编码进特征，给后续优化一个好起点。
切入角度：先用 Heat Kernel PageRank 在原图上做一次低通谱滤波，把多跳结构知识"烤" 进节点特征；再让每个合成节点轮流当 anchor，通过 MLP 学合成节点之间的 pairwise 关联强度形成可微的稀疏超边；最后用 prototype MMD + 节点级 InfoNCE 的复合损失既保全局类分布又保局部决策边界。
核心 idea：把"结构由生成器 + 特征由匹配"换成"结构和特征都由判别损失同时驱动"，并用 HKPR 把昂贵的"反复传播" 折叠成一次性的初始化滤波。
方法详解¶
整体框架¶
给定大超图 \(\mathcal{T}=(\mathbf{X},\mathbf{H},\mathbf{Y})\), 目标合成超图 \(\mathcal{S}=(\mathbf{X}',\mathbf{H}',\mathbf{Y}')\) 满足 \(N'\ll N, M'\ll M\)。流水线：(1) HKPR 初始化——对原节点特征做截断的 Heat Kernel PageRank 扩散得到 \(\tilde{\mathbf{X}}\)，按类内均值池化映射到 \(N'\) 个合成节点 \(\mathbf{X}'\)；(2) Anchor-guided 超边生成——每个 \(\mathbf{X}'_i\) 当 anchor，用一个 MLP 学它与其它合成节点的关联得分 \(\hat{\mathbf{H}}'_i\)，配上每边自适应阈值 \(\delta_i\) 通过 ReLU 稀疏化得到结构 \(\mathbf{H}'_i\)；(3) 双级判别损失 同时对齐合成与原图的类原型 (粗) 和实例几何 (细)，用 cos/sin 时间加权动态切换。下游只需在 \(\mathcal{S}\) 上训 HNN 即得到接近全图的精度。
关键设计¶
-
HKPR-based 节点初始化 (结构知识烤进特征):
- 功能：在凝聚开始前就把多尺度高阶结构信息融入合成节点特征，给后续优化一个结构感知的起点；也为下一步特征驱动的超边生成提供拓扑信号。
- 核心思路：定义归一化超图传播算子 \(\mathbf{P}=\mathbf{D}_v^{-1/2}\mathbf{H}\mathbf{D}_e^{-1}\mathbf{H}^\top\mathbf{D}_v^{-1/2}\)，HKPR 扩散为 \(\tilde{\mathbf{X}}=\sum_{k=0}^\infty \frac{e^{-\lambda}\lambda^k}{k!}\mathbf{P}^{(k)}\mathbf{X}\)，等价于在超图 Fourier 域加低通滤波 \(g(\mu)=e^{-\lambda\mu}\) (Thm 3.1)。截断到 \(K=\lceil\lambda+3\sqrt{\lambda}\rceil\) 即可——Lemma 3.2 给出 Poisson 尾概率上界保证误差指数衰减。然后每类合成节点的特征通过同类原节点均值池化 \(\mathbf{X}'_i=\frac{1}{|S_i|}\sum_{j\in S_i}\tilde{\mathbf{X}}_j\) 得到。
- 设计动机：直接随机初始化合成特征会让后续优化从零学结构；用 HKPR 把"K 跳邻域+全局上下文" 一次性低通滤波塞进特征，相当于免费给后续优化送了一份强先验，同时高频噪声被滤掉。
-
Anchor-guided 超边生成 + 自适应稀疏阈值:
- 功能：让结构生成可微且与特征联合训练，并支持每边独立的稀疏度。
- 核心思路：让每个合成节点 \(v_i'\) 轮流充当 anchor 节点，对所有其它合成节点 \(j\) 用共享 MLP 计算 pairwise 关联：\(\hat{h}'_{i,j}=\text{sigmoid}(\text{MLP}_\Phi([\mathbf{X}'_i;\mathbf{X}'_j]))\)，连成完整的入射向量 \(\hat{\mathbf{H}}'_i\)；再为每条超边学一个自适应阈值 \(\delta_i\)，最终稀疏化 \(\mathbf{H}'_i=\text{ReLU}(\hat{\mathbf{H}}'_i-\delta_i)\)。这样结构 \(\mathbf{H}'\) 与特征 \(\mathbf{X}'\) 都在同一损失上可求导。
- 设计动机：HG-Cond 等用全局阈值会导致所有超边密度一致，丧失表达力；anchor 视角让每条超边由一个中心节点驱动，与"超图本质上是节点周围的高阶 motif" 直觉吻合。MLP 关联避免预训生成器，让结构在判别 loss 的梯度下与特征一起变。
-
双级判别损失 + cos/sin 动态加权:
- 功能：在不重训 HNN 的前提下，对齐合成数据与原数据的类间全局分布 (粗粒度) 和类内实例几何 (细粒度)，作为凝聚目标。
- 核心思路：(a) 粗粒度 \(\mathcal{L}_c\)：基于类原型 \(\mathbf{C}=\mathbf{Y}^\top\tilde{\mathbf{X}}, \mathbf{C}'=\mathbf{Y}'^\top\tilde{\mathbf{X}}'\)，让同类原型 cosine 相似度→1、不同类→0；Thm 3.3 证明这等价于在 (归一化特征, 标签) 联合分布上最小化 MMD；Prop 3.5 给出 class-level margin 下界。(b) 细粒度 \(\mathcal{L}_f\)：对每个合成节点 \(v_i'\) 采样同类原节点为正、不同类为负，做 InfoNCE 风格对比损失；Prop 3.8 证明它直接上界了"负样本超过正样本相似度" 的 mis-ranking 事件概率 \(\Pr(\mathcal{E}_i)\leq\mathbb{E}[e^{l_i}-1]\)。(c) 动态加权 \(\mathcal{L}_{Disc}^{(t)}=\cos(\frac{\pi t}{2T})\mathcal{L}_c+\sin(\frac{\pi t}{2T})\mathcal{L}_f\), \(T\) 为总轮数；早期偏重全局分布对齐，后期切换到局部决策边界精修。
- 设计动机：粗粒度保证类别全局可分但对类内拥挤区无法精修；细粒度负责实例分辨但单独用会受锚点采样噪声影响。两者加权融合在理论上同时优化 MMD 和 ranking margin；cos/sin 调度无需引入新超参就把"全局 → 局部" 的课程学习实现进去。
损失函数 / 训练策略¶
最终凝聚目标 \(\min_{\mathbf{X}', \Phi, \delta}\mathcal{L}_{Disc}^{(t)}\)，无 HNN 重训步骤；超参主要是 HKPR 路径强度 \(\lambda\)、截断阶数 \(K\)、采样数 \(s\)、负样本数 \(N_{neg}\)、训练轮数 \(T\)。整体时间复杂度 \(\mathcal{O}(KM\delta_e d+T(L_\Phi N'^2 d^2+N'N_{neg}d))\)，主项与原图边数和合成大小相关，远低于轨迹匹配方法的 HNN 训练成本。
实验关键数据¶
主实验¶
作者在 5 个超图基准 (Cora、Pubmed、DBLP-CA、Walmart、Yelp) 上对比 SOTA HGC (HG-Cond) 与多个 GC 方法在凝聚后下游 HNN 精度：
| 数据集 | 节点数 | 超边数 | 类数 | 描述 |
|---|---|---|---|---|
| Cora | 2,708 | 1,579 | 7 | co-citation |
| Pubmed | 19,717 | 7,963 | 3 | co-citation |
| DBLP-CA | 41,302 | 22,363 | 6 | co-authorship |
| Walmart | 88,860 | 69,906 | 11 | co-purchase |
| Yelp | 50,758 | 679,302 | 9 | co-occurrence |
| 方法范畴 | 精度趋势 | 凝聚速度 |
|---|---|---|
| GC 方法 (Jin et al. 2022; Zheng et al. 2023; ...) 直推超图 | 在所有 HG 数据上落后 (无高阶结构建模) | 中等 |
| HG-Cond (轨迹匹配 + NHL) | SOTA 但需多次重训 HNN | 慢 |
| AHGCDD | 在 5 个数据集上 ≥ HG-Cond | 最高 144× 加速 |
消融实验¶
| 配置 | 现象 | 解读 |
|---|---|---|
| w/o HKPR (随机初始化合成特征) | 下游精度明显下降 | 初始化结构感知是重要先验 |
| 用全局阈值代替 anchor-adaptive \(\delta_i\) | 结构同质化、精度下降 | 自适应稀疏让每条超边按需密度 |
| 仅 \(\mathcal{L}_c\) (粗粒度) | 类间清晰但类内拥挤、Yelp/Walmart 掉点 | 缺局部 ranking 信号 |
| 仅 \(\mathcal{L}_f\) (细粒度) | 类原型偏移、训练不稳定 | 缺全局分布约束 |
| 固定 50%/50% 权重 | 不及 cos/sin 动态调度 | 课程学习有效 |
| 用 GPSM (HG-Cond 风格) 重训 | 时间开销 ↑↑、精度无显著提升 | 双级判别已经够准 |
| 抽换 anchor 生成为预训练 NHL | 精度下降 | 端到端优化是关键 |
关键发现¶
- HKPR 初始化与 anchor 生成是两支正交的增益来源：前者带"结构→特征" 的知识传递，后者带"特征→结构" 的端到端反馈，缺一不可。
- \(\lambda\) 控制 HKPR 平均扩散步数；\(\lambda\) 较小 (e.g. 2-3) 对小直径图更好，\(\lambda\) 较大对 Pubmed/Walmart 这种大图更友好——这与超图谱半径相关。
- 凝聚效率提升幅度随原图规模放大：Yelp 上达到 144× 速度，主因 HG-Cond 在大图上要做大量轨迹匹配和 HNN 重训。
- 双级损失中粗→细的课程顺序对收敛稳定性贡献大；若反着先细后粗，模型早期容易陷入类内局部最优。
亮点与洞察¶
- 理论与方法对偶证明：Thm 3.3 把 \(\mathcal{L}_c\) 关联到 MMD、Prop 3.8 把 \(\mathcal{L}_f\) 关联到 mis-ranking 上界，这种"凝聚损失 = 分布对齐 + 排序保证" 的双侧证明在 GC 文献里较稀缺，给后续工作提供了模板。
- HKPR 滤波视角：把"多跳传播"压缩成一次性谱滤波是一个可迁移的技巧——任何需要先验结构信号的初始化都可以用类似的低通滤波代替反复 message passing。
- Anchor 视角的可微超边：每个节点既是 anchor 又是候选成员，自然支持任意 arity 的高阶交互；阈值 \(\delta_i\) 把"边密度" 留给优化器决定。
- 无需 HNN 重训的判别损失：这是工程上最有价值的贡献——把 GC 从"代理任务匹配" 解放到"直接判别对齐"，让算法可扩展到亿级图。
局限与展望¶
- 实验数据规模上限是 Yelp (50K 节点 / 679K 超边)，对真正的工业超图 (百万级) 是否仍 144× 没有验证。
- Anchor MLP 复杂度 \(\mathcal{O}(L_\Phi N'^2 d^2)\) 是 \(N'\) 的二次方，若用户要求更大合成规模 (e.g. 1% 比例) 会成为瓶颈。
- HKPR 路径强度 \(\lambda\) 需要手工调或网格搜，未提供自适应估计；不同超图的最优 \(\lambda\) 差异较大。
- 评测局限在节点分类下游任务；超图链接预测、子图分类等任务下双级判别是否仍能保 SOTA 未知。
- 双级损失的 cos/sin 调度依赖固定总轮数 \(T\)，长训/短训会偏移最优调度。
相关工作与启发¶
- vs HG-Cond (Gong et al. 2025)：HG-Cond 通过 NHL 预训 + GPSM 轨迹匹配实现高保真凝聚但代价高昂；AHGCDD 把结构生成端到端化、用判别损失代替轨迹匹配，显著提速但仍 ≥ 精度。
- vs GCond / SFGC (图凝聚)：这些工作只处理 pairwise 图，AHGCDD 通过 anchor + adaptive sparsity 把同一思路扩到高阶；且首次提出"超图凝聚里 MMD ↔ 类原型对齐" 的等价性。
- vs DSL / GraphSAINT (图采样)：采样保留原图子结构，AHGCDD 直接合成新图，可控性更强；二者面向场景不同 (前者训练加速、后者推理服务)。
- vs 数据集蒸馏 (Wang et al.; Cazenavette et al.)：传统 DD 用梯度匹配 / 训练轨迹匹配，AHGCDD 提供另一条路径——用"分布对齐 + ranking 保证" 取代轨迹匹配，证明无须代理任务也能高质量蒸馏。
评分¶
- 新颖性: ⭐⭐⭐⭐ HKPR 初始化 + anchor 超边 + 双级判别这三件套组合在 HGC 中第一次出现，且每件都有理论支持。
- 实验充分度: ⭐⭐⭐⭐ 5 数据集 + 多 backbone HNN + 消融完整；但缺少更大规模图与不同下游任务验证。
- 写作质量: ⭐⭐⭐⭐ 公式推导严谨、消融对应清晰；Theorem 3.1/3.3 + Prop 3.5/3.8 把理论位置安排得恰到好处。
- 价值: ⭐⭐⭐⭐ 144× 加速 + ≥ SOTA 精度的组合极具落地价值，为超图大规模训练提供了可行的预处理方案。