Graph Persistence goes Spectral¶

会议: NeurIPS 2025
arXiv: 2506.06571
代码: GitHub
领域: 图学习 / 拓扑数据分析 / 图表示学习
关键词: 持续同调, 图拉普拉斯谱, GNN表达力, SpectRe, Weisfeiler-Leman

一句话总结¶

提出 SpectRe——将图拉普拉斯谱信息融入持续同调（PH）图的新拓扑描述符，证明其表达力严格强于 PH 和谱信息单独使用，建立了局部稳定性理论，在合成和真实数据集上提升 GNN 的图分类能力。

研究背景与动机¶

领域现状：消息传递 GNN 的表达力受 WL 层级限制，无法计算环、连通性等拓扑性质。持续同调（PH）方法通过过滤函数追踪拓扑特征的演化（如连通分量的合并、环的出现），可以提供超越 WL 的额外信息。
现有痛点：
经典 PH 图仅记录 (birth, death) 对，表达力有限
RePHINE 通过添加顶点颜色信息（α, γ）增强了 PH，但在单色图上退化为普通 PH——仍无法区分一些简单的非同构图
PH 只捕获谐波信息（图拉普拉斯核 = 连通分量数），而忽略了丰富的非谐波谱信息
核心矛盾：PH 和谱方法各有盲区——PH 可检测环但不关注谱，谱方法关注全局结构但不追踪拓扑特征的演化。两者不可比较（incomparable）。
本文要解决什么：设计一个新的拓扑描述符，将谱信息融入 PH 框架中，使其严格比 PH 和谱信息都更强。
切入角度：在 RePHINE 的持续同调元组中增加第五个分量 \(\rho(v)\)——顶点死亡时其所在连通分量的图拉普拉斯非零特征值列表。这将谱信息嵌入到 PH 的时间演化框架中。
核心idea一句话：在持续同调的每个persistence pair中增加对应子图的 Laplacian 谱，获得严格更强的图区分能力。

方法详解¶

整体框架¶

SpectRe = RePHINE + 图拉普拉斯谱。给定一个带颜色的图和一个过滤函数 \((f_v, f_e)\)，SpectRe 为每个顶点产生五元组 \((b, d, \alpha, \gamma, \rho)\)，其中 \(\rho\) 是该顶点"死亡"（被合并到另一个连通分量）时所在连通分量的图拉普拉斯非零特征值列表。

关键设计¶

SpectRe 描述符：
做什么：在 RePHINE 的 \((b, d, \alpha, \gamma)\) 四元组上扩展第五个分量 \(\rho(v)\)
核心思路：\(\rho(v)\) 记录顶点 \(v\) 在边过滤中"死亡"时刻，其所在连通分量的图拉普拉斯非零特征值。对于1维持续同调（环），\(\rho(e)\) 记录边 \(e\) 形成环时所在连通分量的谱
设计动机：正经典 PH 只知道两个分量合并，但不知道合并前分量的结构细节；谱信息精确刻画了这些结构
表达力分析：
SpectRe ≻ RePHINE：存在单色图（如图3a）RePHINE 无法区分但 SpectRe 可以（因为谱不同）
SpectRe ≻ LS（拉普拉斯谱）：存在图（如图3b）LS 无法区分但 SpectRe 可以（因为颜色过滤提供额外信息）
持续拉普拉斯不额外增强（命题3.4）：用 Wang et al. 的持续拉普拉斯谱替代图拉普拉斯谱并不增加表达力
稳定性理论：
为 RePHINE 和 SpectRe 定义了新的 bottleneck 距离度量（扩展经典 PH 的 bottleneck 距离以包含 α, γ, ρ 分量）
RePHINE 全局稳定：过滤函数的小扰动导致 RePHINE 图的小变化
SpectRe 局部稳定：在过滤函数注入（injective）的条件下稳定；但不全局稳定（反例：当过滤函数穿越非注入点时谱可能跳变）。给出了不稳定度的显式上界，与图的复杂度相关
与 GNN 的集成：
在每个 GNN 层计算 SpectRe 图
用 DeepSets 编码 \((b, d, \alpha, \gamma)\) 和 \(\rho\)（单独的 DeepSet 处理谱特征）
向量化后的拓扑嵌入拼接到 GNN 的图级嵌入上

实验关键数据¶

主实验：合成数据（图同构测试）¶

方法	Cayley c-12	Cayley c-60	BREC All (400)
PH0	0.67	0.69	0.03 (12/400)
PH1	0.95	0.78	0.41 (164/400)
RePHINE	0.95	0.78	0.41
LS	-	-	higher
SpectRe	1.00	1.00	best

SpectRe 在所有 Cayley 图上达到 100% 区分率，且在 BREC 基准上是表现最好的方法。

关键发现¶

SpectRe 严格提升区分能力：在单色 Cayley 图上，PH 和 RePHINE 无法完全区分，SpectRe 全部区分
融入 GNN 后提升图分类：在多个真实数据集上，SpectRe 增强的 GNN 优于仅用 PH/RePHINE 增强的版本
局部稳定性在实践中足够：尽管理论上不全局稳定，实验中未观察到不稳定性带来的问题

亮点与洞察¶

理论完备的表达力层级：建立了 SpectRe ≻ RePHINE ≻ PH 和 SpectRe ≻ LS，且 RePHINE 与 LS 不可比较的完整关系图
谐波 + 非谐波信息的统一：PH 捕获谐波信息（Betti 数 = 拉普拉斯核维度），SpectRe 额外捕获非谐波谱，实现了完整的拓扑-谱信息融合
新的稳定性概念：传统 PH 稳定性理论基于全局 bottleneck 距离，本文引入的局部稳定性概念更适合实际应用

局限性 / 可改进方向¶

谱计算开销：每个 persistence pair 需要计算对应子图的拉普拉斯特征值，在大图或密集过滤中可能较慢
不全局稳定：虽然局部稳定在实践中足够，但理论上的非全局稳定性限制了某些应用场景
过滤函数的选择：实验中主要使用度数和 Forman-Ricci 曲率作为过滤函数，最优过滤函数的选择仍是开放问题
无 WL 层级的精确定位：知道 SpectRe+GNN 超越 1-WL，但不清楚在 k-WL 层级中的精确位置

评分¶

新颖性: ⭐⭐⭐⭐⭐ 将谱信息融入 PH 的想法新颖且自然，理论分析完备
实验充分度: ⭐⭐⭐⭐ 合成数据充分验证表达力，真实数据验证实用性