图神经网络的重要分支：时间图网络

本文最初发表于 TowardsDataScience 博客，经原作者 Michael Bronstein 授权，InfoQ 中文站翻译并分享。

许多现实世界的问题涉及各种性质的交易网络、社会互动和交往，这些都是动态的，可以将其建模为图，其中，节点和边会随着时间的推移而出现。在本文中，我们将描述时间图网络（Temporal Graph Network，TGN），这是一个用于深度学习动态图的通用框架。

本文是 Michael Bronstein 与 Emanuele Rossi 共同撰写的。

图神经网络的研究已经成为今年机器学习领域 炙手可热的话题之一。最近，图神经网络在生物学、化学、社会科学、物理学和许多其他领域的问题上，取得了一系列成功。到目前为止，图神经网络模型主要是针对静态图而开发的，静态图不会随着时间而改变。然而，许多有趣的现实世界图都是动态的，并且会随着时间的推移而不断变化，突出的例子包括社交网络、金融交易和推荐系统。在许多情况下，正是这种系统的动态行为传达了重要的见解，否则，如果只考虑静态图的话，就会失去这种见解。

Twitter 用户与推文进行交互并相互关注的动态网络。所有边都有时间戳。给定这样的动态图，我们想预测未来的交互，例如，用户会喜欢哪些推文，或者他们会关注谁。

动态图可以表示为定时事件的有序列表或异步“流”，例如节点和边的添加或删除【1】。像 Twitter 这样的社交网络就是一个很好的例子：当一个人注册 Twitter 账户时，就会创建一个新的节点。当他们关注另一个用户时，就会创建“关注”边。当他们更改其配置文件时，该节点将被更新。

该事件流由编码器神经网络接受，这个编码器神经网络为图的每个节点生成时间相关的嵌入。然后，可以将嵌入馈送到为特定任务而设计的解码器中。一个例子是通过尝试回答以下问题来预测未来的交互：在时刻 t ，节点 i 和 j 之间具有边的概率是多少？回答这个问题的能力对于推荐系统至关重要，例如，建议社交网络用户关注谁，或者决定显示哪些内容。下图演示了这种场景：

一个时间图网络的例子，它接收了具有七条可见边（时间戳为 t₁ 到 t₇ ）的动态图，目的是预测节点 2 和节点 4 在时刻 t₈ （灰色边 t₈ ）的未来交互。为此，时间图网络在时刻 t₈ 计算节点 2 和 4 的嵌入。然后，将这些嵌入连接起来并馈送到解码器（如 MLP），该解码器输出交互发生的概率。

以上设置中的关键部分是编码器，可以与任何解码器一起训练。对于上面提到的未来交互预测任务，可以采用自监督的方式进行训练：在每个轮数（epoch）中，编码器按时间顺序处理事件，并根据前面的时间预测下一次交互【2】。

时间图网络是我们与同事 Fabrizio Frasca、Davide Eynard、Ben Chamberlain 和 Federico Monti 共同开发的通用编码器架构【3】。该模型可应用于表示为事件流的动态图上的各种学习问题。简而言之，时间图网络编码器根据节点的交互创建节点的压缩表示，并在每个事件发生时更新节点。要实现这一点，时间图网络有以下主要组件：

内存 。内存存储所有节点的状态，作为节点过去交互的压缩表示。它类似于 RNN 的隐状态。但是，在这里，对于每个节点 i ，都有单独的状态向量 sᵢ(t) 。当一个新节点出现时，我们添加一个相应的状态，初始化为零向量。此外外，由于每个节点的内存只是一个状态向量（而非参数），因此，当模型接受新的交互时，也可以在测试时进行更新。

消息函数 是内存更新的主要机制。给定节点 i 和 j 在时刻 t 的交互，消息函数计算两条消息（一条用于 i ，一条用于 j ），用于更新内存。这类似于在消息传递图神经网络【4】中计算的消息。该消息是在节点 i 和 j 在时刻 t 之前交互时的内存函数，交互时刻 t 和边特征为【5】：

内存更新程序 用于使用新消息更新内存。这个模块通常作为 RNN 来实现。

假设节点的内存是随时间更新的向量，最直接的方法是将其直接用作节点嵌入。然而，在实践中，由于陈旧性问题的存在，这并不是一个好主意：假设仅当节点参与交互时才更新内存，则节点的长时间不互动会导致其内存过期。举个例子，假设一个用户有几个月没有使用 Twitter。当用户回到 Twitter 时，他们可能已经在此期间发展出了新的兴趣，因此，对他们过去活动的内存就不再相关了。因此，我们需要一种更好的方法来计算嵌入。

嵌入 。一种解决方案是查看邻近节点。为了解决陈旧性问题，嵌入模块通过在节点的时空邻居上执行图聚合来计算节点的时间嵌入。即使一个节点已处于非活动状态一段时间，它的一些邻居也可能处于活动状态，通过聚合它们的内存，时间图网络可以为该节点计算一个最新嵌入。在我们的示例中，即使用户不上 Twitter，但他们的朋友仍然是活跃的，所以，当他们回来的时候，朋友最近的活动可能比用户自己的历史记录更相关。

图嵌入模块通过在目标节点的时间邻域上执行聚合来计算目标节点的嵌入。在上图中，当计算节点 1 在某个时刻 t 大于 t₂ 、 t₃ 和 t₄ ，但小于 t₅ 时的嵌入时，时间邻域将近包含时刻 t 之前出现的边。因此，节点 5 的边不参与计算，因为它在将来发生。相反，嵌入模块将邻近 2、3、4 的特征 (v) 和内存 (s) 以及边上的特征聚合起来，以计算节点 1 的表示。在我们的实验中，性能最好的图嵌入模块是图注意力模块，它可以根据邻居的记忆、特征和交互时间来判断哪些邻居是最重要的。

时间图网络对一批训练数据执行的总体计算总结如下图所示：

时间图网络对一批训练数据进行的计算。一方面，嵌入由嵌入模块使用时间图和节点的内存 (1) 生成嵌入。然后使用嵌入预测批量交互作用并计算损失 (2,3)。另一方面，这些相同的交互用于更新内存 (4,5)。

通过查看上图，你可能想知道内存相关模块（消息函数、消息聚合器和内存更新器）是如何训练的，因为它们似乎不会直接影响损失，因此不会收到梯度。为了让这些模块能够影响损失，我们需要在预测批交互之前更新内存。然而，这将会导致泄漏，因为内存中已经包含了我们试图预测的信息。我们提出的解决这个问题的策略是用来自前一批的消息更新内存，然后预测交互。时间图网络的操作流程如下图所示，这是训练内存相关模块所必需的：

对内存相关模块进行训练所需的时间图网络的操作流程。引入了一个新组件，即原始消息存储库，它存储了计算消息所需的信息，我们称之为原始消息，用于模型过去处理过的交互。这允许模型将交互带来的内存更新延迟到以后的批处理。首先，使用从存储在先前批次（1 和 2）中的原始消息计算的消息来更新内存。然后可以使用刚刚更新的内存（灰色连接）(3) 来计算嵌入。通过这样做，内存相关模块的计算直接影响损失 (4,5)，并且他们接收梯度。最后，这个批处理交互的原始消息存储在原始小村存储库 (6) 中，以便在将来的批处理中使用。

通过在各种动态图上进行深入的实验验证，在未来边预测和动态节点分类的任务上，时间图网络在正确率和速度上都明显优于竞争方法【6】。维基百科（Wikipedia）就是这样的一个动态图，其中用户和页面是节点，交互表示用户编辑页面。编辑文本的编码用作交互特性。本例中的任务是预测用户将在给定时间编辑哪个页面。我们用基线方法比较了时间图网络的不同变体：

在预测正确率和时间方面，比较时间图网络和旧方法（TGAT 和 Jodie）对维基百科数据集上未来链接预测的各种配置。我们希望有更多的论文，以严谨的方式报道这两个重要标准。

这项消融研究揭示了不同时间图网网络模块的重要性，并使我们能够得出一些一般性结论。首先，内存很重要：内存的缺失会导致性能的大幅下降【7】。其次，嵌入模块的使用（与直接输出内存状态相反）很重要。基于图注意力的嵌入表现最好。第三，拥有内存使得只使用一个图注意力层就足够了（这大大减少了计算时间），因为一跳邻居的内存使模型能够间接访问二跳邻居的信息。

作为结束语，我们认为动态图的学习的研究领域几乎就是个“处女地”，有许多重要和令人兴奋的应用以及重大的潜在影响。我们相信，我们的时间图网络模型是朝着提高学习动态图的能力迈出的重要一步，巩固并扩展了以前的结果。随着这一研究领域的发展，更好、更大的基准将变得至关重要。我们现在正致力于创建新的动态图数据集和任务，作为 Open Graph Benchmark 的一部分。

前文回顾

专栏 | 图深度学习：成果、挑战与未来

参考文献

【1】 这种情况通常被称为“连续时间动态图”。为简单起见，这里我们只考虑节点对之间的交互事件，在图中用边来表示。当其中一个端点不在图中时，节点插入被认为是新边的一种特殊情况。我们不考虑节点或边的删除，这意味着图只能随时间增长。由于一对节点之间可能有多条边，从技术上讲，我们拥有的对象是多重图。

【2】 多个交互可以具有相同的时间戳，并且模型可以独立地预测每个交互。此外，通过将时间的有序列表拆分成固定大小的连续块，可以创建迷你批。

【3】 《 用于动态图深度学习的时间图网络》（Temporal graph networks for deep learning on dynamic graphs），E. Rossi 等人，2020 年，arXiv:2006.10637。

【4】 为简单起见，我们假设该图是无向的。在有向图的情况下，需要两个不同的消息函数，一个用于源，一个用于目的地。

【5】 《 量子化学的神经信息传递》（Neural Message Passing for Quantum Chemistry），J. Gilmer 等人，2017 年，arXiv:1704.01212。

【6】 对于动态图的深度学习，目前只有少数几种方法，如《 时间图的归纳表示学习》（Inductive representation learning on temporal graphs）的时间图网络，D. Xu 等人，2020 年，arXiv:2002.07962；以及《 时间交互网络中的动态嵌入轨迹的预测》（Predicting dynamic embedding trajectory in temporal interaction networks）的 Jodie，S. Kumar 等人，2019 年，arXiv:1908.01207。我们证明了这些方法可以作为时间图网络的特殊配置来获得。由于这一原因，时间图网络似乎是目前在动态图学习上最为通用的模型。

【7】 虽然内存包含关于一个节点过去所有交互作用的信息，但图嵌入模块只能访问时间邻域的样本（出于计算原因），因此可能无法访问对手头任务至关重要的信息。

作者介绍：

Michael Bronstein，伦敦帝国理工学院教授，Twitter 图机器学习研究负责人，CETI 项目机器学习主管、研究员、教师、企业家和投资者。

原文链接：

https://towardsdatascience.com/temporal-graph-networks-ab8f327f2efe