GG-SSMs: Graph-Generating State Space Models¶

会议: CVPR 2025
arXiv: 2412.12423
代码: https://github.com/uzh-rpg/gg_ssms (有)
领域: 视频理解
关键词: 状态空间模型, 动态图构建, 最小生成树, 视觉SSM, 时间序列预测

一句话总结¶

提出 Graph-Generating State Space Models (GG-SSMs)，通过基于特征相似度动态构建最小生成树（MST）来替代传统 SSM 中固定的一维扫描路径，实现对高维数据中复杂非局部依赖的高效建模，在 11 个数据集上取得 SOTA 性能。

研究背景与动机¶

传统 SSM（如 S4）在序列数据建模中表现出色，但受限于固定的一维序列处理方式，无法有效捕获高维数据（图像、事件流）中的非局部交互。Mamba 和 VMamba 虽然引入了选择性扫描和多方向扫描策略，但仍依赖预定义的 1D 扫描轨迹（如图像网格上的若干方向展开），无法自适应地适配数据的内在结构。

核心挑战在于：如何在不引入高计算成本的前提下，设计一种能自适应捕获复杂非局部依赖的模型？图模型天然适合表示复杂关系，但在大规模图上的构建和处理通常面临高计算复杂度。GG-SSMs 的关键洞察是：将动态图构建集成到 SSM 框架中，利用 Chazelle 的近线性 MST 算法保持高效性，同时通过特征关系驱动的图结构实现自适应扫描。

方法详解¶

整体框架¶

给定输入特征集 \(\{x_i\}_{i=1}^{L}\)，GG-SSM 首先基于特征间的不相似度构建完全连接图，然后用 Chazelle 的 MST 算法提取最小生成树 \(\mathcal{T}\)，最后沿生成树的边进行 SSM 状态传播，得到增强的特征表示。整个过程从"固定扫描"变为"数据驱动的自适应扫描"。

关键设计¶

基于特征不相似度的图构建:
- 功能：将输入特征建模为图结构，边权表示节点间的关系强度
- 核心思路：定义全连接无向图 \(G=(V,E)\)，每个节点 \(v_i\) 对应特征 \(x_i\)。边权通过余弦不相似度计算：\(w_{ij} = \exp\left(-\frac{x_i^\top x_j}{\|x_i\|\|x_j\|}\right)\)。然后用 Chazelle 的 MST 算法提取最小生成树 \(\mathcal{T}\)，MST 仅保留 \(L-1\) 条最关键的边
- 设计动机：MST 保留了连接所有节点的最小权重边集，能以最紧凑的方式捕获数据的核心结构关系。Chazelle 算法的复杂度为 \(\mathcal{O}(E\alpha(E,V))\)，其中逆 Ackermann 函数 \(\alpha\) 增长极慢，实际等价于线性时间
沿图的状态传播机制:
- 功能：在 MST 上进行信息聚合，计算每个节点的隐状态
- 核心思路：定义路径权重 \(S_{ji} = \prod_{m=1}^{n} \bar{A}_{k_m}\)，即从节点 \(v_j\) 到 \(v_i\) 路径上所有状态转移矩阵的乘积。节点 \(v_i\) 的隐状态为 \(h_i = \sum_{v_j \in V} S_{ji} \bar{B}_j x_j\)，汇聚了所有其他节点的贡献（衰减强度由路径权重调制）。最终输出 \(y_i = C_i \text{Norm}(h_i) + D x_i\)
- 设计动机：MST 的树结构保证任意两节点间存在唯一路径，避免冗余计算。通过路径权重的累乘衰减，远距离节点的贡献自然减弱，近似实现了"注意力"效果，但计算复杂度仅为 \(\mathcal{O}(L)\)
高效的前向/后向传播:
- 功能：保证训练和推理的线性计算复杂度
- 核心思路：前向传播从叶节点到根节点，每个节点执行固定操作（初始化状态、聚合子节点状态、更新隐状态）。后向传播从根到叶，利用动态规划存储中间结果避免重复计算。整体依赖局部邻居信息，不需要全局操作
- 设计动机：MST 的 CUDA 实现使得图生成极快，单次前向传播的时间与 Mamba 近似。线性复杂度确保了对大规模数据集和高分辨率输入的可扩展性

损失函数 / 训练策略¶

训练策略随任务而异：ImageNet 分类采用 VMamba 的标准训练协议（200 epochs, AdamW, lr=\(1\times10^{-3}\), cosine decay），配合 RandAugment、MixUp、CutMix 等数据增强。时间序列预测使用 MSE/MAE 损失，lookback 长度 96，预测长度 96/192/336/720。

实验关键数据¶

主实验¶

ImageNet-1K 分类:

模型	参数量(M)	FLOPs(G)	Top-1 Acc(%)
DeiT-S	22	4.6	79.8
Swin-T	28	4.5	81.3
VMamba-T	-	-	82.6
GG-SSM-T	-	-	83.6
Swin-B	88	15.4	83.5
VMamba-B	-	-	83.9
GG-SSM-B	-	-	84.9

事件相机眼动追踪 (LPW):

模型	参数(M)	FLOPs(G)	p3(%)	p5(%)	p10(%)
VMamba+Mamba	0.35	8.60	89.00	98.00	99.30
GG-SSM	0.22	8.01	89.33	98.89	99.50

消融实验¶

时间序列预测 (Weather 数据集, 平均):

配置	MSE	MAE	说明
GG-SSM	0.2250	0.2623	全部 horizon 最优
S-Mamba	0.2510	0.2760	前最佳 SSM 模型
iTransformer	0.2580	0.2780	Transformer 基线
Crossformer	0.2590	0.3150	交叉注意力方案

关键发现¶

GG-SSM 在所有 11 个数据集上均取得最优或接近最优性能，验证了动态图扫描的通用性
在 ImageNet 上比 VMamba 高 1%，证明数据驱动的扫描路径优于预定义路径
在眼动追踪任务中，GG-SSM 用更少参数（0.22M vs 0.35M）实现更高精度
MST 基于 CUDA 实现，前向传播速度与 Mamba 相当

亮点与洞察¶

核心创新：将图构建与 SSM 有机结合，用"特征相似度驱动的 MST"替代"手工设计的扫描路径"，这是一种从"数据无关"到"数据自适应"的范式转变
理论优雅：MST 在数学上保证了以最小代价连接所有节点，天然适合作为信息传播的骨架
实用高效：借助 Chazelle 算法的近线性复杂度和 CUDA 实现，GG-SSM 在效率上与 Mamba 持平
通用性强：同一框架在图像分类、光流估计、事件数据处理、时间序列预测等差异极大的任务上均有效

局限与展望¶

图构建使用全局特征计算不相似度，对于高分辨率输入可能仍有扩展性问题
MST 仅保留 \(L-1\) 条边，可能丢失某些有用的冗余连接
目前主要验证了空间维度的图构建，对视频的时空联合图构建尚未充分探索
论文虽声称为"视频理解"，实际主要实验在图像分类和时间序列上，视频相关实验（如光流）较少

评分¶

新颖性: ⭐⭐⭐⭐⭐ 将动态图构建与 SSM 框架结合的思路非常新颖且优雅
实验充分度: ⭐⭐⭐⭐⭐ 11 个数据集覆盖视觉/时间序列等多领域，充分验证通用性
写作质量: ⭐⭐⭐⭐ 整体清晰，数学推导严谨，但部分细节可更紧凑
价值: ⭐⭐⭐⭐ 为 Visual SSM 提供了新范式，但实际视频理解场景的验证仍需加强