DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs¶

会议: NeurIPS 2025
arXiv: 2408.06966
代码: https://github.com/Clearloveyuan/DyG-Mamba
领域: 动态图学习
关键词: 状态空间模型, 动态图, 时间跨度感知, Mamba, 链接预测

一句话总结¶

DyG-Mamba 将连续状态空间模型（SSM）引入动态图学习，设计时间跨度感知的连续 SSM——用 Ebbinghaus 遗忘曲线启发的指数衰减函数建模不规则时间间隔，配合谱范数约束的输入依赖参数实现 Lipschitz 鲁棒性，在 12 个动态图基准上平均排名 2.42（vs DyGFormer 2.92），且保持 \(O(bdL)\) 线性复杂度。

研究背景与动机¶

领域现状：动态图方法主要有 RNN 类（GRU/LSTM，捕获长期依赖但有梯度问题）和 Transformer 类（DyGFormer，\(O(N^2)\) 注意力高效-准确权衡差）。Mamba/SSM 在序列建模中展现了线性复杂度 + 长期依赖捕获的优势。
现有痛点：(a) 真实动态图交互间隔高度不规则——固定步长离散化损失时间信息；(b) 图数据含噪声大——需要鲁棒的参数化；(c) MLP/GNN 方法虽快但丢失长期时序模式。
核心矛盾：标准 Mamba 假设固定步长，但动态图的交互时间间隔从秒到天跨度极大。需要使 SSM 时间步长自适应于实际时间间隔。
本文要解决什么？ 设计时间跨度感知的连续 SSM，在线性复杂度下处理不规则时间间隔的动态图。
切入角度：Ebbinghaus 记忆遗忘曲线 \(R = \exp(-t/S)\) 描述了记忆随时间的指数衰减——将其作为 SSM 的时间步长自适应函数。
核心 idea 一句话：遗忘曲线启发的时间步长 \(\Delta t\) + 对角负特征值的 \(A\) 矩阵保证稳定性 + 谱范数约束的输入依赖 \(B,C\) 保证鲁棒性 = 时间感知连续 SSM for 动态图。

方法详解¶

整体框架¶

动态图交互序列 → 节点/边/时间/共现频率编码 → 时间跨度感知参数化（\(\Delta t_k, A, B, C\)）→ 连续 SSM 状态转移 + 并行扫描 \(O(bdL)\) → 链接预测/节点分类

核心特点：所有参数均有理论保证——\(A\) 的负特征值保证稳定性（Theorem 4.1），\(B,C\) 的谱范数约束保证鲁棒性（Theorem 4.3）。

关键设计¶

时间跨度感知的 \(\Delta t\):
做什么：根据实际交互时间间隔自适应调整 SSM 步长
核心思路：\(\Delta t_k = w_1 \odot (1 - \exp(-w_2 \odot \frac{t_{k+1} - t_k}{\tau - t_1}))\)，\(w_1, w_2\) 可学习。时间间隔大 → \(\Delta t\) 大 → 更多"遗忘"；间隔小 → \(\Delta t\) 小 → 保留更多
设计动机：Ebbinghaus 遗忘曲线表明记忆保留与时间间隔指数相关——自然地编码了"最近交互比久远交互更重要"
对角负特征值 \(A\) 矩阵:
做什么：保证 SSM 的稳定性（状态不发散）
核心思路：\(A = \text{diag}(\lambda_1, ..., \lambda_d)\)，\(\lambda_i < 0\)。则离散化后 \(\bar{A}_k = \text{diag}(e^{\lambda_i \Delta t_k})\)，所有特征值绝对值 < 1（Theorem 4.1）
设计动机：Theorem 4.1 证明对角负特征值是稳定性的充要条件——避免RNN的梯度爆炸/消失
谱范数约束的输入依赖 \(B, C\):
做什么：根据输入内容动态调整 SSM 参数，同时保证 Lipschitz 连续性
核心思路：\(B = W_B x + b_B\)，\(C = W_C x + b_C\)，约束 \(\|W_B\|_2 \leq 1, \|W_C\|_2 \leq 1\)（谱范数）。Theorem 4.3 证明输出对输入扰动的敏感度有界
设计动机：动态图数据噪声大——输入依赖性提高表达力，谱范数约束保证鲁棒性

损失函数 / 训练策略¶

链接预测：对比学习损失（正样本 vs 随机采样负样本）
并行扫描优化：\(O(bdL)\) vs Transformer \(O(bdL^2)\)
编码：节点 + 边 + 绝对时间 + 共现频率 + 编码对齐

实验关键数据¶

主实验（12 个数据集链接预测 AP）¶

数据集	DyG-Mamba	DyGFormer	CAWN	改善
Wikipedia	99.06±0.01	99.03±0.02	98.50	+0.03
Reddit	99.25±0.00	99.22±0.01	98.82	+0.03
MOOC	90.17±0.19	87.52±0.49	85.67	+2.65
LastFM	94.22±0.04	93.00±0.12	88.21	+1.22
平均排名	2.42	2.92	4.33	—

消融实验¶

配置	效果
时间跨度函数 vs 固定步长	时间跨度函数一致更优（MOOC +3%+）
谱范数约束 vs 无约束	约束提高鲁棒性（Theorem 4.3）
输入依赖 B,C vs 固定 B,C	输入依赖更好（噪声过滤）
负特征值初始化 vs 随机初始化	负特征值保证稳定收敛

关键发现¶

在 MOOC/LastFM 等交互间隔变化大的数据集上改善最显著（+2.65/+1.22 AP）——验证了时间跨度感知的价值
Wikipedia/Reddit 等密集交互数据集改善较小（+0.03）——交互频繁时间间隔差异不大
线性复杂度使其可扩展到更长的历史序列（vs DyGFormer 受限于注意力窗口）
归纳设置（新节点）下同样保持排名优势

亮点与洞察¶

遗忘曲线 → SSM 步长的类比非常自然且有理论支撑：时间间隔直接反映了信息衰减程度
稳定性 + 鲁棒性的双重理论保证（Theorem 4.1 + 4.3）使方法在噪声图数据上可靠
线性复杂度使处理超长交互历史成为可能——这对社交网络等不断积累的动态图至关重要

局限性 / 可改进方向¶

在密集交互数据集上改善幅度很小（Wikipedia +0.03）——频繁交互时时间间隔差异不显著
假设交互按时间顺序排列——乱序或并发交互需要额外处理
未测试多模态动态图（如带文本/图像的社交网络）——扩展到多模态可能需要修改编码
时间跨度函数的参数化（指数衰减）可能不适用于所有分布——如周期性交互模式
仅在链接预测上评测——节点分类、图分类等任务未验证
对角 \(A\) 矩阵的表达力受限——非对角可能更强但牺牲并行性

评分¶

新颖性: ⭐⭐⭐⭐ 连续 SSM + 遗忘曲线步长在动态图上的首次应用
实验充分度: ⭐⭐⭐⭐⭐ 12 个数据集 + 归纳/转导 + 充分消融
写作质量: ⭐⭐⭐⭐ 理论推导严谨，定理保证清晰
价值: ⭐⭐⭐⭐ 为动态图学习提供了线性复杂度的强基线，特别适合不规则时间间隔场景