Scalable and Efficient Temporal Graph Representation Learning via Forward Recent Sampling

📄 arXiv: 2402.01964v2 📥 PDF

作者: Yuhong Luo, Pan Li

分类: cs.LG

发布日期: 2024-02-03 (更新: 2024-11-25)

备注: Learning on Graphs Conference (LoG 2024)

🔗 代码/项目: GITHUB

💡 一句话要点

提出无回溯前向采样方法以解决时序图表示学习的计算挑战

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

关键词: 时序图表示学习 前向采样 哈希表 计算效率 动态系统

📋 核心要点

  1. 现有的时序图表示学习方法在处理动态系统时，常常因回溯历史交互而导致计算效率低下和推理延迟。
  2. 本文提出的无回溯（NLB）框架通过前向最近采样策略，避免了历史交互的回溯，利用哈希表快速记录和查询最近交互。
  3. 实验表明，NLB在六个真实数据集上实现了1.32-4.40倍的训练加速，1.2-7.94倍的能效提升，以及1.63-12.95倍的推理延迟降低。

📝 摘要（中文）

时序图表示学习（TGRL）对于建模现实网络中的动态系统至关重要。然而，传统的TGRL方法在采样时序邻居时面临显著的计算挑战和推理延迟。本文提出了一种新颖的TGRL框架——无回溯（NLB），通过引入前向最近采样策略，克服了这些挑战。该策略利用每个节点的GPU可执行、大小受限的哈希表，记录下采样的最近交互集，从而实现快速查询响应，推理延迟最小化。实验结果表明，NLB在准确性上与最先进的方法相当或更优，同时在训练速度、能效和推理延迟方面显著提升。

🔬 方法详解

问题定义：本文旨在解决传统时序图表示学习方法在采样时序邻居时的计算效率低下和推理延迟问题。现有方法通常需要回溯节点的历史交互，导致计算开销大。

核心思路：论文提出的无回溯（NLB）框架通过前向最近采样策略，避免了对历史交互的回溯，利用哈希表记录最近交互，从而实现快速查询和低延迟推理。

技术框架：NLB框架主要包括两个模块：前向最近采样模块和哈希表维护模块。前者负责实时记录节点的最近交互，后者则确保哈希表的高效更新与查询。

关键创新：NLB的核心创新在于引入了前向最近采样策略和GPU可执行的哈希表，这与传统方法的回溯采样形成了本质区别，显著提升了计算效率。

关键设计：在设计中，哈希表的大小受到限制，以确保内存使用的高效性；同时，哈希表的维护操作复杂度为O(1)，保证了快速的更新与查询能力。整体架构兼容GPU处理，最大化了可编程性和并行性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，NLB在六个真实数据集上实现了与最先进方法相当或更优的准确性，同时在训练速度上提升了1.32-4.40倍，能效提升1.2-7.94倍，推理延迟降低1.63-12.95倍，展现出显著的性能优势。

🎯 应用场景

该研究在社交网络分析、交通流量预测和金融网络建模等领域具有广泛的应用潜力。通过提高时序图表示学习的效率，NLB框架能够支持实时数据处理和决策制定，推动相关领域的智能化发展。

📄 摘要（原文）

Temporal graph representation learning (TGRL) is essential for modeling dynamic systems in real-world networks. However, traditional TGRL methods, despite their effectiveness, often face significant computational challenges and inference delays due to the inefficient sampling of temporal neighbors. Conventional sampling methods typically involve backtracking through the interaction history of each node. In this paper, we propose a novel TGRL framework, No-Looking-Back (NLB), which overcomes these challenges by introducing a forward recent sampling strategy. This strategy eliminates the need to backtrack through historical interactions by utilizing a GPU-executable, size-constrained hash table for each node. The hash table records a down-sampled set of recent interactions, enabling rapid query responses with minimal inference latency. The maintenance of this hash table is highly efficient, operating with $O(1)$ complexity. Fully compatible with GPU processing, NLB maximizes programmability, parallelism, and power efficiency. Empirical evaluations demonstrate that NLB not only matches or surpasses state-of-the-art methods in accuracy for tasks like link prediction and node classification across six real-world datasets but also achieves 1.32-4.40x faster training, 1.2-7.94x greater energy efficiency, and 1.63-12.95x lower inference latency compared to competitive baselines. The link to the code: https://github.com/Graph-COM/NLB.