Over-squashing in Spatiotemporal Graph Neural Networks¶

会议: NeurIPS 2025
arXiv: 2506.15507
代码: 待确认
领域: 图学习 / 时空图神经网络 / 理论分析
关键词: over-squashing, 时空GNN, 因果卷积, 信息传播, 图重布线

一句话总结¶

首次形式化时空图神经网络(STGNN)中的 over-squashing 问题，揭示了因果卷积中反直觉的"时间远处偏好"现象（最早时间步对最终表示影响最大），并证明 time-and-space 和 time-then-space 架构在信息瓶颈上等价，为使用计算高效的 TTS 架构提供理论支持。

研究背景与动机¶

领域现状：时空图神经网络(STGNN)将 GNN 与序列模型（RNN/TCN）结合，处理图上节点特征随时间演化的数据（如交通预测、能源系统）。over-squashing 在静态 GNN 中已被深入研究，但在时空场景中完全未被探索。
现有痛点：
静态 GNN 的 over-squashing 理论不能直接推广到 STGNN——时间维度引入了额外的信息传播轴，使压缩效应更复杂
T&S（time-and-space，交替处理）和 TTS（time-then-space，先时后空）两种架构设计选择缺乏理论指导，主要靠经验
因果卷积的信息传播模式未被理论分析过
核心矛盾：STGNN 中信息需要同时跨越空间和时间两个维度传播，每个维度都可能产生瓶颈，两个维度的瓶颈还会叠加。
本文要解决什么：(1) 形式化时空 over-squashing；(2) 分析 TCN 中时间维度的信息传播特性；(3) 比较 T&S 和 TTS 在信息传播上的差异。
切入角度：将 STGNN 的信息传播分解为空间和时间两个正交分量，分别用 Jacobian 灵敏度分析，再组合得到时空联合界。
核心idea一句话：时空 over-squashing 的灵敏度界可以分解为空间拓扑和时间拓扑的乘积，T&S 和 TTS 在固定预算下等价。

方法详解¶

整体框架¶

考虑由 \(L\) 层 STMP（时空消息传递）组成的 STGNN，每层内包含 \(L_T\) 层时间处理（TCN）和 \(L_S\) 层空间处理（MPNN）。通过 Jacobian \(\nabla_i^u \mathbf{h}_t^{v(L)}\) 分析节点 \(u\) 在时间 \(t-i\) 的初始特征对节点 \(v\) 在时间 \(t\) 的最终表示的影响。

关键设计¶

TCN 中的时间 over-squashing（定理4.1 + 命题4.2）：
做什么：建立 TCN 中灵敏度的上界，揭示反直觉的时间偏好
核心思路：\(\|\frac{\partial \mathbf{h}_{t-j}^{(L_T)}}{\partial \mathbf{h}_{t-i}^{(0)}}\| \leq (c_\sigma \mathsf{w})^{L_T} (\mathbf{R}^{L_T})_{ij}\)，其中 \(\mathbf{R}\) 是因果卷积的时间拓扑矩阵（下三角 Toeplitz 矩阵）
反直觉发现：\(\mathbf{R}^l\) 的结构使得最早的时间步（而非最近的）对最终输出影响最大！因为早期时间步通过 \(l\) 层叠加累积了指数级更多的传播路径。最近时间步仅能通过自环保持信息，影响以 \(O(l^{-(i-j)})\) 衰减
与 Transformer 的 attention sink 现象类比：当感受野超过序列长度时，最早 token 的影响不成比例地大
时间图重布线策略：
膨胀卷积：每层使用不同的 \(\mathbf{R}^{(l)}\)（膨胀率 \(d^{(l)} = P^{l-1}\)），使感受野指数扩张且影响均匀分布。但超过 \(\log_P T\) 层后需重置膨胀率，重新引入偏差
行归一化卷积：将 \(\mathbf{R}\) 行归一化为 \(\mathbf{R}_N\)，使每行和为 1。效果是最终时间步收到的影响趋向均匀分布，特别适合预测任务
MPTCN 的时空联合界（定理5.1）：
做什么：证明时空灵敏度可分解为空间和时间分量的乘积
核心思路：\(\|\nabla_i^u \mathbf{h}_t^{v(L)}\| \leq (c_\xi \theta_\mathsf{m})^{LL_S} (c_\sigma \mathsf{w})^{LL_T} (\mathbf{S}^{LL_S})_{uv} (\mathbf{R}^{LL_T})_{i0}\)
关键推论：界只依赖总预算 \(LL_S\) 和 \(LL_T\)，而非 \(L\) 的大小。这意味着 TTS（\(L=1\)）和 T&S（\(L>1\)）在信息传播能力上等价——TTS 的计算优势不以信息瓶颈为代价

实验关键数据¶

合成实验¶

任务	标准卷积	膨胀卷积	归一化卷积
CopyFirst（回忆最早值）	成功（受益于 sink）	成功	成功
CopyLast（回忆最近值）	\(L_T>5\) 时失败	部分成功	成功
RocketMan（时空联合）	符合理论预测	-	-

真实数据（交通预测 MAE）¶

模型	\(L\)	METR-LA	PEMS-BAY
MPTCN \(\mathbf{R}\)	6(T&S)	3.19	1.66
MPTCN \(\mathbf{R}\)	1(TTS)	3.14	1.63
MPTCN \(\mathbf{R}_N\)	1(TTS)	更优	更优

关键发现¶

TTS ≈ T&S：在固定预算下，\(L=1\)（TTS）与 \(L>1\)（T&S）性能相当甚至更好，验证了定理5.1
标准因果卷积有 "sink 效应"：层数增多后，模型偏向最早时间步的信息，CopyLast 任务失败
归一化卷积有效缓解时间 sink：行归一化使影响趋向均匀，显著改善最近时间步的信息保持
时空 over-squashing 需同时解决两个维度：仅优化空间或时间一个维度不够

亮点与洞察¶

首次揭示 TCN 的 "时间 attention sink"：因果卷积叠加多层后偏向最早输入——这个发现与 Transformer 的 attention sink 不谋而合，暗示信息压缩瓶颈的普遍性
TTS = T&S 的理论证明：为实践中偏好计算高效的 TTS 架构提供了理论支持（TTS 空间计算复杂度仅 \(O(T)\) 而非 T&S 的 \(O(T \times L)\)）
时间图重布线类比空间图重布线：将图重布线的思想从空间域推广到时间域，建立了优雅的对偶

局限性 / 可改进方向¶

仅分析 TCN 作为时间组件：未分析 RNN 或 Transformer 作为时间处理器的情况
灵敏度上界不紧：上界是必要但非充分条件，实际 over-squashing 程度可能与界松紧相关
归一化卷积仅利于最终时间步：对需要在中间时间步读出的任务（如插值）可能无帮助
未考虑自适应时间拓扑：固定的时间重布线策略，未探索可学习的时间注意力机制

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次形式化时空 over-squashing，反直觉发现有重要理论价值
实验充分度: ⭐⭐⭐⭐ 合成+真实数据验证，但真实数据仅限交通预测