跳转至

Sheaf Graph Neural Networks via PAC-Bayes Spectral Optimization

会议: AAAI 2026
arXiv: 2508.00357
代码: GitHub
领域: Graph Learning / 图神经网络
关键词: Sheaf Neural Networks, PAC-Bayes, 谱优化, 异质图, 最优传输, 半监督节点分类

一句话总结

提出 SGPC（Sheaf GNNs with PAC-Bayes Calibration），结合 Wasserstein 最优传输学习 sheaf 限制映射、方差缩减扩散与自适应频率混合层、以及 PAC-Bayes 谱正则化，在同质和异质图节点分类上全面超越现有 GNN 和 sheaf 方法，同时提供理论泛化保证。

背景与动机

现有痛点

现有痛点：领域现状：经典 GNN（GCN、GAT）本质上是低通滤波器，在同质图（相邻节点标签一致）上效果好，但在异质图上性能严重退化——这就是过平滑问题。Cellular sheaf 理论将边重新解释为局部特征空间之间的线性限制映射，其 sheaf Laplacian 的谱能捕获边的方向性和类别分散度。

现有 sheaf GNN 存在三个关键限制：(1) 通常使用固定或简单门控的限制映射；(2) 缺乏异质性感知的不确定性校准；(3) 除了经验测试准确率外没有泛化保证。PAC-Bayes 分析可提供原理性的泛化界，但现有 GNN 的 PAC-Bayes 界因忽略底层算子的谱而过松。

解决思路

本文目标：如何在学习 sheaf 限制映射的同时，通过谱间隙优化收紧 PAC-Bayes 泛化界，从而在异质图上获得有保证的强性能？

方法详解

整体框架

SGPC 包含三大模块：(1) OT + WE Lift 学习 sheaf 限制映射；(2) SVR-AFM 层进行扩散与频率混合；(3) PAC-Bayes 谱优化校准不确定性并收紧泛化界。

关键设计

  1. Wasserstein-Entropic Lift：用 Sinkhorn OT 初始化传输计划 \(P_0\)，通过 JKO 梯度流步骤精炼为全局 KL 稳定配置 \(P_\star\)，然后生成限制映射 \(R_{ij} = P_{\star,ij} W_\theta\)。这些映射构成 sheaf Laplacian：\(L_\mathcal{F} = (B \otimes I_{d_0})^\top R^\top R (B \otimes I_{d_0})\)。

  2. SVR-AFM 层：

    • 随机方差缩减（SVR）扩散：\(H^{svr} \approx (I + \Delta t L_\mathcal{F})^{-1} H\)
    • 自适应频率混合（AFM）：使用 Chebyshev 多项式 \(H^{afm} = \sum_{q=0}^Q \alpha_q T_q(\tilde{L}) H\)，可学习系数 \(\alpha_q\) 在异质图上自动偏向高频
    • 分支融合：\(H' = F_{mix}([H^{svr} \| H^{afm}])\)

  3. PAC-Bayes 谱优化：

    • \(\beta\)-Dirichlet 先验建模每条边的消息一致率 \(\kappa_{ij}\)
    • 固定点求解器迭代更新后验
    • 谱间隙正则化：\(\mathcal{L}_{spec} = c_{het} / \lambda_2(L_\mathcal{F})\)
    • 总损失：\(\mathcal{L} = \mathcal{L}(y, \hat{y}) + \lambda_{KL}\mathcal{L}_{KL} + \lambda_{spec}\mathcal{L}_{spec}\)
    • 定理保证 \(\lambda_2\) 单调递增（每轮至少增长 \(c_w/4\)），PAC-Bayes 界几何级收缩

实验关键数据

节点分类（9 个基准，准确率 %）

主实验

方法 Cora Citeseer Actor Chameleon Cornell Texas Wisconsin
GCN 81.3 71.1 20.4 49.8 60.2 68.3 57.7
GAT 82.5 72.0 21.7 49.3 63.4 70.2 59.4
GCNII 82.1 71.4 25.1 49.1 79.7 82.6 75.3
NSD (sheaf) — — — — — — —
SGPC top-3 top-3 top-3 top-3 top-3 top-3 top-3

在异质图上优势尤为明显：Cornell/Texas/Wisconsin（同质率仅 0.06-0.16）上大幅超越经典 GNN。

亮点与洞察

  • 理论完备性突出：提供 CG 收敛、\(\lambda_2\) 单调增长、风险-方差收缩、PAC-Bayes 泛化界四重理论保证
  • 谱间隙与泛化界的精妙联系：通过 \(c_{het}/\lambda_2\) 正则化将异质性惩罚与扩散能力绑定
  • 模块设计优雅：OT → Sheaf → SVR-AFM → PAC-Bayes 四阶段层层递进
  • 同质 + 异质图两手抓：AFM 分支的可学习频率系数自动适配

局限与展望

  • OT 和 JKO 步骤的计算开销较大，对大规模图可能成为瓶颈
  • \(\beta\)-Dirichlet 后验的固定点求解器收敛速度依赖先验参数选择
  • 实验中同质图（Cora/Citeseer/Pubmed）的提升相对有限

相关工作与启发

NSD 使用静态或参数化 sheaf 结构但缺乏谱控制和泛化保证；Bodnar et al. 通过路径对齐优化谱间隙但无 PAC-Bayes 校准；现有 PAC-Bayes for GNN 工作界过松因忽略谱信息。SGPC 首次将 OT-based sheaf 学习、谱间隙优化和 PAC-Bayes 风险控制统一。

相关工作与启发

  • PAC-Bayes + 谱优化的范式可推广到其他图上的概率模型
  • Wasserstein Lift 学习 sheaf 映射的思路可启发流形学习方法
  • 频率混合的 Chebyshev 多项式可类比信号处理中的自适应滤波器组

评分

  • 新颖性: ⭐⭐⭐⭐⭐ OT+Sheaf+PAC-Bayes 的统一框架极具原创性
  • 实验充分度: ⭐⭐⭐⭐ 9个数据集覆盖同质/异质，理论推导完整
  • 写作质量: ⭐⭐⭐⭐ 论文结构清晰但公式密度较高
  • 价值: ⭐⭐⭐⭐⭐ 为图学习提供了首个谱感知的泛化保证框架
  • 价值: 待评

相关论文