动态图表示的时间聚合和传播图神经网络

背景介绍

动态图（temporal graph）是一种在连续时间内节点间具有动态交互的图结构，图的拓扑结构随时间的推移不断演变。这种动态变化让节点在不同时刻展现出变化的偏好，这对捕捉用户偏好和检测异常行为非常关键。然而，现有的研究通常采用有限邻居生成动态表示，这不仅降低了性能，还引发了高延迟的在线推断问题。为了应对这些挑战，本文提出了一种全新的时间图卷积方法，即时间聚合和传播图神经网络（Temporal Aggregation and Propagation Graph Neural Networks，简称TAP-GNN）。该方法通过展开时间图以消息传递的姿态分析了动态表示问题的计算复杂度，并设计了一个聚合和传播模块（AP block），有效减少了历史邻居的重复计算。

来源与作者信息

本文由Tongya Zheng、Xinchao Wang、Zunlei Feng、Jie Song、Yunzhi Hao、Mingli Song、Xingen Wang、Xinyu Wang和Chun Chen等人撰写，分别来自杭州城市大学大图中心、浙江大学计算机科学与技术学院、新加坡国立大学的电气与计算机工程系以及浙江大学上海高级研究所。本研究发表在《IEEE Transactions on Knowledge and Data Engineering》2023年10月刊。

研究优化与工作流程

研究流程

研究以上技术所覆盖的主要程序包括：展开时间图、设计AP模块、实现时间图神经网络系统TAP-GNN并进行实验评估。

时间图展开

研究首先通过消息传递范式展开时间图，形成消息传递时间图（Message-Passing Temporal Graph，简称MPTG），在该图中，时间节点与其时间邻居密集连接。然而，这种展开带来了巨大的计算复杂度。

聚合和传播模块（AP block）

为了降低计算复杂度，设计并实现了聚合和传播模块。AP模块由聚合层和传播层组成： - 聚合层：通过轻量级的消息传递图进行节点信息的聚合处理。 - 传播层：在历史节点进行传播操作，这些节点信息会包含过去聚合邻居的信息。

TAP-GNN框架

最终，设计了TAP-GNN框架，该框架包括多个AP模块和一个投影层。TAP-GNN引入时间点编码与时间激活功能以生成时间节点嵌入，并支持在图流情景下进行在线推断。

实验设计与结果

为了验证TAP-GNN的有效性，研究在各种真实的时间网络上进行了实验，包括未来链接预测和动态节点分类两个任务。研究发现，TAP-GNN在预测性能和在线推断延迟方面相比现有方法均有显著提升。

实验详细数据与讨论

结果说明

在图的各个节点进行分别的实验，采用不同的图卷积核以及批次大小，TAP-GNN框架在提高性能的同时，保持了计算性能的线性增长。

未来链接预测

实验显示，TAP-GNN在所有实验的时间图上表现出优异的性能。特别是在低重复率数据集上，TAP-GNN表现得尤为突出。

动态节点分类

TAP-GNN在处理极端不平衡标签任务上表现良好，并且能够有效捕捉节点的动态变化。

研究意义与价值

1. 科学价值：此研究揭示了捕抓整个时间邻域对动态图表示的重要性，为图引文网络、电子商务推荐、社交网络行为检测等领域提供了新的思路。
2. 应用价值：TAP-GNN独创了AP模块，在成本上大幅削减了时间图表达的复杂度与延迟，适合于在线推断与大规模工业领域应用，如电商推荐系统和实时社交网络监控等。

突出成果

• 算法效率：AP模块显著降低了重复计算，计算复杂度从原来的指数增长变为线性增长。
• 模型性能：在不同的数据集上验证，TAP-GNN的性能表现均优于其他最先进的方法。
• 模块扩展性：节点的在线推断时间几乎与图大小无关，这表明TAP-GNN具有良好的扩展性，适用于大规模动态图。

未来工作方向

尽管本文提出的方法在动态图表示上取得了优异的成果，但研究仍存在一些局限性。后续研究可以进一步开发自适应模型，推断节点动态变化的潜在原因，无论是由于永久性的还是暂时性的变化，从而提升对未来交互行为的准确预测。 通过上述研究及其实验结果，TAP-GNN不仅在学术界揭示了动态图嵌入的新可能性，同时在实际应用中展现出极高的优越性和潜力。