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 把昂贵的"反复传播" 折叠成一次性的初始化滤波。
方法详解¶
整体框架¶
AHGCDD 要解决的是：把大超图压成一张小合成超图，让下游 HNN 在小图上训练就能逼近全图精度，但又要绕开 HG-Cond "预训结构生成器 + 反复重训 HNN 匹配轨迹" 的高昂代价。它的做法是把凝聚拆成三件互补的事——先用一次性的谱滤波把原图的高阶结构 "烤" 进合成节点的初始特征，再让这些特征自己生成可微的稀疏超边，最后用一个无需重训 HNN 的判别损失同时监督结构和特征。给定大超图 \(\mathcal{T}=(\mathbf{X},\mathbf{H},\mathbf{Y})\), 合成超图 \(\mathcal{S}=(\mathbf{X}',\mathbf{H}',\mathbf{Y}')\) 满足 \(N'\ll N, M'\ll M\)；优化完成后下游只需在 \(\mathcal{S}\) 上训一遍 HNN。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["大超图 T=(X, H, Y)"] --> B["HKPR 初始化<br/>谱低通滤波烤入结构，类内池化得初始 X'"]
B --> C["Anchor-guided 超边生成<br/>节点轮流当 anchor，MLP 算关联 + 自适应阈值 δ 稀疏化得 H'"]
C --> D["双级判别损失 + cos/sin 动态加权<br/>粗粒度类原型 MMD + 细粒度 InfoNCE"]
D -->|"梯度更新 X', Φ, δ"| C
D --> E["合成超图 S=(X', H', Y')<br/>下游训一遍 HNN"]关键设计¶
1. HKPR 初始化：把多跳结构知识一次性烤进特征
凝聚的痛点之一是合成特征若随机初始化，后续优化就得从零开始学结构。AHGCDD 在凝聚开始前先做一次 Heat Kernel PageRank 扩散，把原图 "K 跳邻域 + 全局上下文" 的高阶结构信息低通滤波进节点特征，给后续优化送一份强先验。具体是定义归一化超图传播算子 \(\mathbf{P}=\mathbf{D}_v^{-1/2}\mathbf{H}\mathbf{D}_e^{-1}\mathbf{H}^\top\mathbf{D}_v^{-1/2}\)，HKPR 扩散写成
Thm 3.1 证明它等价于在超图 Fourier 域施加低通滤波 \(g(\mu)=e^{-\lambda\mu}\)，所以高频噪声被自然滤掉、只留多尺度结构信号。无穷级数在实现上截断到 \(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\)，这样初始特征既携带结构又按类对齐，也为下一步特征驱动的超边生成提供了拓扑信号。
2. Anchor-guided 超边生成：让结构可微且每边密度自适应
HG-Cond 用预训练的生成器加全局阈值，结果是结构与特征解耦、且所有超边密度一律相同，丧失表达力。AHGCDD 换成 anchor 视角——让每个合成节点 \(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\) 做 ReLU 稀疏化 \(\mathbf{H}'_i=\text{ReLU}(\hat{\mathbf{H}}'_i-\delta_i)\)。这样设计有两层好处：一是结构 \(\mathbf{H}'\) 和特征 \(\mathbf{X}'\) 落在同一个损失上一起可导，避免预训生成器带来的错位；二是 anchor 视角让每条超边由一个中心节点驱动，与 "超图本质是节点周围的高阶 motif" 的直觉吻合，而每边独立的 \(\delta_i\) 把边密度交给优化器按需决定。
3. 双级判别损失 + cos/sin 动态加权：用分布对齐代替轨迹匹配
为了彻底丢掉昂贵的 HNN 重训，AHGCDD 用一个 "粗 + 细" 的判别损失直接对齐合成与原图。粗粒度 \(\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 下界。但粗粒度对类内拥挤区无能为力，于是细粒度 \(\mathcal{L}_f\) 对每个合成节点采样同类原节点为正、异类为负做 InfoNCE 风格对比，精修局部决策边界；Prop 3.8 证明它直接上界了 "负样本相似度超过正样本" 的 mis-ranking 概率 \(\Pr(\mathcal{E}_i)\leq\mathbb{E}[e^{l_i}-1]\)。两者单独都有短板——粗粒度精修不了类内、细粒度单用会受锚点采样噪声拖累，所以用时间加权融合
\(T\) 为总轮数。这条 cos/sin 调度不引入任何新超参，就把 "早期对齐全局分布、后期精修局部边界" 的课程学习写了进去，理论上同时优化 MMD 与 ranking margin。
损失函数 / 训练策略¶
最终凝聚目标是 \(\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 精度的组合极具落地价值，为超图大规模训练提供了可行的预处理方案。