Community-Aware Temporal Walks: Parameter-Free Representation Learning on Continuous-Time Dynamic Graphs

📄 arXiv: 2501.11880v1 📥 PDF

作者: He Yu, Jing Liu

分类: cs.LG, cs.AI

发布日期: 2025-01-21

💡 一句话要点

提出CTWalks，解决连续时间动态图表示学习中时序和结构动态建模难题

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

关键词: 动态图表示学习 连续时间动态图 时序游走 社群检测 常微分方程 链路预测 图神经网络

📋 核心要点

  1. 现有动态图表示学习方法在灵活性、适应性以及保持时序和结构动态方面存在挑战。
  2. CTWalks通过社群感知的时序游走采样、匿名化策略和基于ODE的连续时序动态编码来解决上述问题。
  3. 实验结果表明，CTWalks在时序链路预测任务中优于现有方法，实现了更高的准确性和鲁棒性。

📝 摘要（中文）

动态图表示学习在理解演化行为中起着关键作用。然而，现有方法通常在灵活性、适应性以及时序和结构动态的保持方面存在不足。为了解决这些问题，我们提出了社群感知时序游走（CTWalks），这是一个用于连续时间动态图表示学习的新框架。CTWalks集成了三个关键组件：基于社群的无参数时序游走采样机制、富含社群标签的匿名化策略，以及利用常微分方程（ODE）建模的连续时序动态编码过程。这种设计能够精确地建模社群内部和社群之间的交互，从而提供对连续时间动态图中演化时序模式的细粒度表示。CTWalks在理论上克服了游走中的局部性偏差，并建立了其与矩阵分解的联系。在基准数据集上的实验表明，CTWalks在时序链路预测任务中优于现有方法，在保持鲁棒性的同时实现了更高的准确性。

🔬 方法详解

问题定义：现有动态图表示学习方法难以灵活适应动态变化，并且无法充分保留图的时序和结构信息。尤其是在连续时间动态图中，节点和边的交互是连续发生的，如何精确建模这些连续的时序动态是一个挑战。现有方法容易产生局部性偏差，忽略了全局的社群结构信息。

核心思路：CTWalks的核心思路是利用社群结构来指导时序游走，从而克服局部性偏差，并结合常微分方程（ODE）来建模连续时间动态图中的时序演化过程。通过社群感知的游走，模型能够更好地捕捉节点间的长期依赖关系和全局结构信息。匿名化策略则进一步增强了模型的泛化能力。

技术框架：CTWalks框架包含三个主要模块：1) 社群感知的时序游走采样：根据节点所属的社群信息，进行有偏的随机游走，生成节点序列。2) 匿名化策略：使用社群标签对节点进行匿名化处理，增强模型的泛化能力。3) 基于ODE的编码器：利用常微分方程对节点序列中的时序动态进行建模，生成节点表示。整个流程首先进行游走采样，然后进行匿名化处理，最后使用ODE编码器生成节点嵌入。

关键创新：CTWalks的关键创新在于将社群结构信息融入到时序游走过程中，并使用ODE来建模连续时间动态图的时序演化。与传统的随机游走方法相比，CTWalks能够更好地捕捉全局结构信息和长期依赖关系。与离散时间动态图表示学习方法相比，CTWalks能够更精确地建模连续时间动态图中的时序动态。

关键设计：CTWalks使用基于社群的转移概率进行时序游走，转移概率的设计考虑了节点间的时序关系和社群结构。匿名化策略使用社群标签替换节点ID。ODE编码器使用GRU-ODE-Bayes模型，该模型能够处理不规则的时间间隔，并对时序动态进行建模。损失函数采用负采样损失，用于优化节点嵌入，使其能够更好地预测节点间的时序关系。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

CTWalks在多个基准数据集上进行了时序链路预测实验，结果表明CTWalks显著优于现有的动态图表示学习方法。例如，在某些数据集上，CTWalks的准确率提升了5%以上。实验还验证了CTWalks的鲁棒性，即使在数据稀疏的情况下，CTWalks仍然能够取得良好的性能。

🎯 应用场景

CTWalks可应用于社交网络分析、金融风险预测、交通流量预测等领域。例如，在社交网络中，可以利用CTWalks来预测用户之间的互动关系，发现潜在的社群结构。在金融领域，可以利用CTWalks来预测交易风险，识别欺诈行为。在交通领域，可以利用CTWalks来预测交通流量，优化交通调度。

📄 摘要（原文）

Dynamic graph representation learning plays a crucial role in understanding evolving behaviors. However, existing methods often struggle with flexibility, adaptability, and the preservation of temporal and structural dynamics. To address these issues, we propose Community-aware Temporal Walks (CTWalks), a novel framework for representation learning on continuous-time dynamic graphs. CTWalks integrates three key components: a community-based parameter-free temporal walk sampling mechanism, an anonymization strategy enriched with community labels, and an encoding process that leverages continuous temporal dynamics modeled via ordinary differential equations (ODEs). This design enables precise modeling of both intra- and inter-community interactions, offering a fine-grained representation of evolving temporal patterns in continuous-time dynamic graphs. CTWalks theoretically overcomes locality bias in walks and establishes its connection to matrix factorization. Experiments on benchmark datasets demonstrate that CTWalks outperforms established methods in temporal link prediction tasks, achieving higher accuracy while maintaining robustness.