DyGSSM: Multi-view Dynamic Graph Embeddings with State Space Model Gradient Update

📄 arXiv: 2505.09017v2 📥 PDF

作者: Bizhan Alipour Pijan, Serdar Bozdag

分类: cs.LG, cs.SI

发布日期: 2025-05-13 (更新: 2025-12-21)

备注: Published in LOG conference, 2025. This version corresponds to the published article

💡 一句话要点

DyGSSM：结合状态空间模型梯度更新的多视角动态图嵌入方法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 动态图嵌入 图卷积网络 随机游走 状态空间模型 HiPPO算法 时间依赖性 多视角学习

📋 核心要点

  1. 现有动态图嵌入方法忽略了快照中全局和局部信息的同步提取，且参数更新缺乏对时间依赖性的有效管理。
  2. DyGSSM结合GCN和GRU提取局部和全局特征，并利用交叉注意力融合，同时引入基于HiPPO的SSM管理长期依赖性。
  3. 实验结果表明，DyGSSM在五个公共数据集上，相较于现有方法，在大部分情况下取得了更优的性能表现。

📝 摘要（中文）

大多数动态图表示学习方法将动态图分割成离散的快照，以捕获节点随时间演变的行为。现有方法主要使用消息传递和基于随机游走的方法来捕获每个快照中节点的局部或全局结构。然后，他们利用基于序列的模型（例如，transformers）来编码节点嵌入的时间演变，并使用元学习技术来更新模型参数。然而，这些方法有两个局限性。首先，它们忽略了在每个快照中同时提取全局和局部信息。其次，它们未能考虑模型在当前快照中的性能对参数更新的影响，导致缺乏时间依赖性管理。最近，HiPPO（高阶多项式投影算子）算法因其在状态空间模型（SSM）中优化和保持序列历史的能力而受到关注。为了解决动态图表示学习中的上述局限性，我们提出了一种名为“基于状态空间模型梯度更新的多视角动态图嵌入”（DyGSSM）的新方法。我们的方法结合了图卷积网络（GCN）进行局部特征提取，以及带有门控循环单元（GRU）的随机游走进行全局特征提取。然后，我们使用交叉注意力机制整合局部和全局特征。此外，我们还结合了基于HiPPO算法的SSM，以在更新模型参数时考虑长期依赖性，确保模型在每个快照中的性能能够影响后续更新。在五个公共数据集上的实验表明，我们的方法在20个案例中的17个案例中优于现有的基线和最先进（SOTA）方法。

🔬 方法详解

问题定义：现有动态图嵌入方法通常将动态图分割为离散时间快照，分别处理每个快照，忽略了快照内部局部和全局信息的关联性。此外，模型参数的更新过程缺乏对时间依赖性的有效管理，即当前快照的性能未能充分影响后续快照的模型更新，导致模型无法有效捕捉长期的时间演化模式。

核心思路：DyGSSM的核心思路是同时提取每个快照的局部和全局信息，并利用状态空间模型（SSM）来建模时间依赖性，从而更有效地学习动态图的嵌入表示。通过结合图卷积网络（GCN）和随机游走（Random Walk）来分别捕获局部和全局结构，并使用交叉注意力机制融合这些信息。同时，利用基于HiPPO算法的SSM来更新模型参数，确保模型在每个快照中的性能能够影响后续更新。

技术框架：DyGSSM的整体框架包含以下几个主要模块：1) 局部特征提取：使用GCN提取每个快照中节点的局部特征。2) 全局特征提取：使用带有GRU的随机游走提取每个快照中节点的全局特征。3) 特征融合：使用交叉注意力机制融合局部和全局特征，得到每个节点的综合表示。4) 状态空间模型：使用基于HiPPO算法的SSM来建模时间依赖性，并更新模型参数。整个流程是，对于每个时间快照，首先提取局部和全局特征，然后融合这些特征，最后使用SSM来更新模型参数，并将更新后的参数用于下一个时间快照的处理。

关键创新：DyGSSM的关键创新在于以下几点：1) 多视角特征提取：同时考虑了每个快照的局部和全局信息，并通过交叉注意力机制进行融合。2) 基于SSM的梯度更新：利用基于HiPPO算法的SSM来建模时间依赖性，并指导模型参数的更新，从而更好地捕捉长期的时间演化模式。与现有方法相比，DyGSSM能够更全面地捕捉动态图的结构信息和时间演化模式。

关键设计：在局部特征提取中，GCN的层数和每层的隐藏单元数是重要的参数。在全局特征提取中，随机游走的步数和GRU的隐藏单元数需要仔细调整。交叉注意力机制中的query、key和value的维度也需要根据实际情况进行设置。损失函数通常采用链接预测或节点分类等任务相关的损失函数。HiPPO算法的具体实现，包括多项式的阶数和投影算子的选择，也会影响SSM的性能。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，DyGSSM在五个公共数据集上，相较于现有的基线方法和最先进方法，在20个案例中的17个案例中取得了更优的性能。例如，在某些数据集上，DyGSSM的性能提升超过了5%。这些结果验证了DyGSSM在动态图表示学习方面的有效性。

🎯 应用场景

DyGSSM在社交网络分析、交通流量预测、金融风险评估等领域具有广泛的应用前景。它可以用于识别社交网络中的关键节点和社区演化，预测交通流量的变化趋势，以及评估金融市场的风险传播。通过更准确地捕捉动态图的结构信息和时间演化模式，DyGSSM可以为这些应用提供更可靠的决策支持。

📄 摘要（原文）

Most of the dynamic graph representation learning methods involve dividing a dynamic graph into discrete snapshots to capture the evolving behavior of nodes over time. Existing methods primarily capture only local or global structures of each node within a snapshot using message-passing and random walk-based methods. Then, they utilize sequence-based models (e.g., transformers) to encode the temporal evolution of node embeddings, and meta-learning techniques to update the model parameters. However, these approaches have two limitations. First, they neglect the extraction of global and local information simultaneously in each snapshot. Second, they fail to consider the model's performance in the current snapshot during parameter updates, resulting in a lack of temporal dependency management. Recently, HiPPO (High-order Polynomial Projection Operators) algorithm has gained attention for their ability to optimize and preserve sequence history in State Space Model (SSM). To address the aforementioned limitations in dynamic graph representation learning, we propose a novel method called Multi-view Dynamic Graph Embeddings with State Space Model Gradient Update (DyGSSM). Our approach combines Graph Convolution Networks (GCN) for local feature extraction and random walk with Gated Recurrent Unit (GRU) for global feature extraction in each snapshot. We then integrate the local and global features using a cross-attention mechanism. Additionally, we incorporate an SSM based on HiPPO algorithm to account for long-term dependencies when updating model parameters, ensuring that model performance in each snapshot informs subsequent updates. Experiments on five public datasets show that our method outperforms existing baseline and state-of-the-art (SOTA) methods in 17 out of 20 cases.