时间图注意力网络的冗余感知优化

3540TGOpt：面向时间图注意力网络的冗余感知优化0伊利诺伊大学香槟分校，美国，yufengw2@illinois.edu0伊利诺伊大学香槟分校，美国，charithm@illinois.edu0摘要：时间图神经网络在建模动态图上的交互方面越来越受欢迎。其中，时间图注意力网络（TGAT）在一系列应用领域中的预测任务（如链接预测）中得到了采用。大多数图神经网络（GNNs）的优化和框架都专注于在静态图上操作的GNN模型。虽然其中一些优化利用了静态图上的冗余计算，但它们要么不适用于TGAT中使用的自注意机制，要么不利用与时间执行行为相关的优化机会。在本文中，我们探索了特定于TGAT推断中涉及时间组件的计算中产生的冗余感知优化机会。我们观察到在时间节点嵌入计算中存在相当多的冗余，例如重新计算先前计算的邻居嵌入和重复时间增量值的时间编码。为了利用这些冗余机会，我们开发了TGOpt，它引入了基于去重、记忆化和预计算的优化技术，以加速TGAT的推断性能。我们的实验结果表明，TGOpt在CPU上进行推断时，几何平均加速比为4.9倍，在GPU上为2.9倍，在各种动态图上进行推断时，Reddit帖子数据集的加速比最高可达6.3倍。0CCS概念：•计算方法学→神经网络；•软件及其工程→软件性能。0关键词：时间图神经网络，冗余感知优化，记忆化，动态图0未经许可，可以制作本作品的全部或部分的数字或印刷副本，供个人或课堂使用，但不得为了盈利或商业优势而制作或分发副本，并且副本必须带有本声明和第一页的完整引用。必须尊重本作品中除作者以外的其他组成部分的版权。允许进行带有署名的摘要。要进行其他复制、再版、发布到服务器或重新分发到列表，需要事先获得特定的许可和/或支付费用。请向permissions@acm.org申请权限。PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔 ©2023版权由所有者/作者持有。出版权由ACM许可。ACM ISBN979-8-4007-0015-6/23/02...$15.00https://doi.org/10.1145/3572848.357749001 引言0图神经网络（GNNs）[24]在包括社交网络分析[40]、金融欺诈检测[4, 30]和药物发现[13,27]在内的广泛应用领域中得到了快速采用。GNNs通过使用节点特征和其邻域信息学习节点嵌入表示来对图结构数据进行预测建模。许多流行的GNN模型[9, 16,29]最初是为静态图设计的。随后，有许多努力优化GNNs以在CPU [15]、GPU [33, 34, 39]和硬件加速器 [1, 38,43]上最小化训练和推断时间。此外，多个框架，如DGL[31]、PyTorch Geometric [5]和NeuGraph[19]，使从业者能够更轻松地尝试不同的GNN拓扑结构，并实现高性能。然而，大多数这些框架和优化都专注于仅在静态图上操作的GNNs。最近，时间GNNs（TGNNs）因其能够在动态图上学习预测模型而变得流行，动态图是随着时间的推移以新节点或边的形式演变其拓扑结构的图。在这些TGNN模型中，时间图注意力网络（TGAT）[37]在建模时间知识图[10,11]到基于时间传播的假新闻检测[26]等应用中得到了采用。TGAT在连续时间动态图上进行预测建模，处理随时间发生的边交互的批次。与其静态对应物相比，TGAT的训练和推断计算量更大，因为它依赖于复杂的注意力机制以及其他编码操作来捕捉邻域的时间特性[41]。因此，优化TGAT仍然具有挑战性，但对于提高最终用户的生产力非常重要。在本文中，我们介绍了一些技术，通过主要关注消除冗余计算来提高TGAT的推断性能。冗余消除已在静态GNNs的上下文中进行了探索。例如，HAG [12]和ReGNN[2]是通过识别和重用重叠邻居上的聚合来减少冗余的方法。这些方法需要转换为自定义计算图表示，并且仅适用于简单的聚合运算符，因此不适用于像TGAT这样的基于注意力的模型。在时间上下文中，存在有限的研究关于这个问题。3550PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魁北克省，Wang等人。0优化TGNN的工作已经有很多。其中一项工作是[41]，它用更简单的计算替换了自注意力，并专注于基于FPGA的加速器。相比之下，本文采用了一种不同的方法，专注于TGAT的时间方面，并利用时间冗余来减少时间和推理执行之间的冗余。我们观察到并利用了时间嵌入和时间编码计算中的冗余计算，从而大大减少了TGAT推理的运行时间。与以前的工作相比，我们考虑的冗余消除技术不限于简单的聚合，并且不需要替换自注意力。我们观察到TGAT推理过程中存在三个主要的冗余计算来源。首先，在批处理中处理边交互的源节点和目标节点可能会导致相同的节点嵌入计算。对于某些图形，批处理中可能有多达55%的相同计算。其次，为给定的节点和时间戳计算嵌入将探索已在先前时间步骤中探索过的相同时间邻域，导致重新计算相同的嵌入。在我们的分析中，我们发现一些动态图可能会重复计算其演化生命周期中生成的89.9%的总嵌入。第三，TGAT中的时间编码操作经常使用相同的时间增量值。我们在第3节详细说明了这些观察结果。基于这些关键观察结果，我们开发了TGOpt来利用这些机会，在TGAT推理过程中重用值而不是重新计算它们。TGOpt通过执行以下操作加速推理计算：1）在处理一批边交互时去重复节点/时间戳，2）记忆化先前计算的节点嵌入，以及3）预计算一定时间增量值的时间编码。这些技术是语义保持的冗余感知转换，保持了基线版本的计算语义和最终用户接口，从最终用户的角度来看，实现了透明的性能改进。TGOpt生成的节点嵌入与基线版本相同，浮点容差内，因此保留了模型的准确性。TGOpt中的重用利用技术需要额外的内存来缓存计算值以供以后重用。为了在这些重用和内存消耗之间取得平衡，TGOpt提供了设置来限制其计算值缓存的内存占用。为了评估我们的方法，我们将TGOpt的推理性能与TGAT的基线实现在CPU和GPU环境下进行了比较。我们的结果表明，TGOpt在各种动态图上实现了4.9倍的CPU加速和2.9倍的GPU加速，Reddit帖子数据集在CPU上的加速高达6.3倍。我们在第5节详细说明了我们的结果和发现。总体而言，我们的结果表明，TGOpt在保持模型语义和准确性的同时，为TGAT推理在数据集和机器环境中实现了显著的加速。0本文具有以下具体贡献：0•探索时间图注意力网络中存在的冗余。我们进行了一项系统研究，研究了TGAT中存在的三个不同领域的时间冗余：边交互批次内部的冗余、探索时间邻域的嵌入计算内部的冗余以及时间编码内部的冗余。0•在TGAT推理的背景下，利用冗余计算进行优化。我们通过引入执行去重、记忆化和预计算等技术来最小化冗余计算，以重用先前计算的值。0•在CPU和GPU上对各种动态图进行实现和评估。我们构建了TGOpt，它实现了对TGAT的冗余感知优化，以使最终用户能够获得透明的推理性能优势。我们展示了TGOpt在CPU上能够实现3-6倍的加速，在GPU上能够实现2-3倍的加速，同时带来合理的低开销和内存使用。02 背景在本节中，我们提供了时态图神经网络的符号、概念和计算抽象的概述。GNN运算符。GNN是在图数据上操作的神经网络模型。一个（静态）图是一个二元组 �  =  ( �, � )，其中  �=  { � 1 , � 2 , ..., � � } 是一组节点，�  �  �  ×  � 是一组边。每个节点� � 有一个特征向量  � �  ∈  R � �，每个边有一个特征向量  � ��  ∈  R��。GNN作为图操作符，通过使用局部邻域信息聚合节点特征。它们输出用于下游任务（如节点分类和边预测）的节点嵌入向量  � �  ∈  R ��。节点特征是固有属性，而这些节点嵌入是计算得到的表示。动态图。虽然静态图的图结构是稳定的，但动态图随着时间的推移而演变，出现新的节点或边。我们将动态图定义为一个二元组  �  = ( �  ( � ) , � ( �))，其中节点/边集由时间参数化。边  � ��  ( � � ) ∈  � ( � )表示节点  � �  和  �  �  之间的交互，其边时间戳为  � �  ∈�。我们还定义节点  � �  在时间  �  的时态邻域为  N ( �,� )  =  { �  :� ��  ( � � ) ∈  � ( � ) ∧  � �  <  � }，即如果邻居  �  与节点  � �有交互，并且边时间戳  � �  小于  � ，则邻居  �在时态邻域中。两个节点可以在不同的时间拥有多个边，使得动态图成为一个多图。因此，时态邻域可能包含相同的邻居  � ，但具有不同的边交互时间戳。由于边由节点索引  � ，  �和时间  � �  唯一标识，我们还将使用  � ��  ( � � )作为边特征向量的符号。还要注意，节点特征在动态图中可能会发生变化，但我们假设它们在这项工作中是静态的。图表示。动态图有两种表示方式[14]：离散时间动态图（DTDGs）TGOpt: Redundancy-Aware Optimizations for TGATPPoPP ’23, February 25-March 1, 2023, Montreal, QC, Canada𝑚𝑗 (𝑡) = msg ℎ(𝑙−1)𝑖(𝑡), ℎ(𝑙−1)𝑗(𝜏), 𝑒𝑖𝑗 (𝑡𝑗)(1)𝑟𝑖 (𝑡) = agg �{𝑚𝑗 (𝑡) : 𝑗 ∈ N (𝑖,𝑡)}�(2)ℎ(𝑙)𝑖(𝑡) = upd ℎ(𝑙−1)𝑖(𝑡), 𝑟𝑖 (𝑡)(3)𝑧𝑖 (𝑡) = ℎ(𝑙−1)𝑖(𝑡) ∥ Φ(0)(4)𝑧𝑗 (𝑡) = ℎ(𝑙−1)𝑗(𝑡𝑗) ∥ 𝑒𝑖𝑗 (𝑡𝑗) ∥ Φ(𝑡 − 𝑡𝑗)(5)𝑟𝑖 (𝑡) = Attn �𝑧𝑖 (𝑡), {𝑧𝑗 (𝑡) : 𝑗 ∈ N (𝑖,𝑡)}�(6)ℎ(𝑙)𝑖(𝑡) = FFN�𝑟𝑖 (𝑡) ∥ ℎ(𝑙−1)𝑖(𝑡)�(7)Φ(Δ𝑡) = cos (𝜔 · Δ𝑡 + 𝜙)(8)3560或连续时间动态图（CTDGs）。CTDG是一个带有时间戳的图事件流  G  =  { � ( � 1 ) ,� ( � 2 ) , ... }，其中时间戳 0  ≤  � 1  ≤  ≤  ... 是有序的[32]。事件  � ( � )表示一个变化事件，例如节点特征的变化或两个节点之间的新边（即新的边交互）。DTDG是在间隔时间内获取的一系列静态图快照  S  =  {G( � 1 ) ,  G( � 2 ) , . . .  }，其中 G( � )  =  ( �  [0 ,� ] , � [ 0 ,� ])可以从CTDG中推导出来[22]。因此，DTDG丢失了一些对于某些应用程序可能至关重要的时间信息。在这项工作中，我们专注于CTDG，因为它是TGAT操作的数据，并且它捕捉到更丰富的时间信息。用于动态图的GNN。有越来越多的工作将静态GNN扩展到对动态图进行建模和学习。这些动态GNN的早期工作主要集中在为离散时间动态图生成嵌入表示。它们的计算主要涉及在各个DTDG快照上应用结构运算符和在快照之间应用时间运算符，或者这些运算符的组合[8, 21, 23,25]。最近的工作更关注连续时间动态图，其计算主要基于结构邻域聚合和包含CTDG中新边交互的粒度时间戳或时间差的时间编码方法[22, 32, 37,42]。我们遵循这些后期工作，并在本文中采用时态GNN作为动态图的GNN模型的术语。时态消息传递。许多GNN模型可以用消息传递风格[6]来表示，它将GNN运算符抽象为三个步骤。为了便于后续讨论，我们扩展了消息传递以捕捉时间的概念，时间是动态图的一个关键参数：0其中�≤�。常见的�选择是时间�或边的时间戳��。� ( � − 1 ) � (− 1 ) � ( �)是时间嵌入，用于计算目标节点和时间的。我们将使用��,��表示目标节点-时间戳对。简而言之，方程（1）描述了消息创建，其中为每个邻居�创建了一个“消息”向量。方程（2）是消息聚合，将消息缩减为单个邻域向量。方程（3）是特征更新，它将该向量与节点特征结合起来产生嵌入� ( � ) � ( �)。具体的函数可以是可学习的或不可学习的，例如agg(∙)可以是求和，而upd(∙)可以是神经网络。此外，许多GNN模型使用分层架构，其中相同的GNN运算符堆叠到�层中，从而递归地聚合�跳的邻居信息。因此，当前层�使用来自（�−1）��层嵌入计算输出� ( � ) � ( � )。0时间图注意力网络。TGAT模型是一种可以为CTDG数据生成时间嵌入的时间GNN。它学习一个函数Φ：�→R��，将时间值映射到一个��维向量。这种时间编码技术使其能够捕捉图的时间模式。然后将时间编码向量注入到GNN运算符的输入特征中，从而合并到输出嵌入中。TGAT的计算可以使用时间消息传递模型表示：0其中∥是连接运算符，FFN是前馈神经网络。方程（4，5）是方程（1）中的消息创建步骤，方程（6）是方程（2）中的agg(∙)，方程（7）是方程（3）中的更新函数。方程（6）中的Attn(∙)是[28]中的自注意机制，现在由时间参数化。对于我们考虑的优化，具体细节并不重要，我们将这个注意机制抽象地称为�（详见[37]）。这些方程构成了TGAT模型架构中的一层。一层的输入只是目标��,��，而其他所有内容都是计算得出的。计算嵌入从���层（起始层）开始，然后通过层逆向工作，直到第一层，其中� ( 0 ) � =  ��。更重要的是，注意TGAT对�的选择是边的时间戳��，被编码的时间值是目标时间�和��之间的差值（因此对于目标节点来说是0）。时间编码函数的形式为：0其中�,�是可学习向量，Δ�是时间差[41]。时间采样。在计算对于目标��,��的� ( � ) � ( �)时，一层需要节点和邻居的前一层嵌入。可以考虑所有邻居，但在实践中，由于可扩展性问题，很少这样做。相反，模型通常通过采样将邻居限制为最大数量[9]。常见的策略包括均匀/随机采样和最近邻居采样。虽然两者都适用于TGAT模型，但我们只关注最近采样，因为在[22]中表现更好。批量训练和推理。上述方程是从单个目标节点的角度制定的。实际上，TGAT模型一起处理一批边交互，并为源节点和目标节点生成嵌入。批处理过程通过将节点打包到张量中，允许并行处理节点。2jodie-lastfm94%48%0%jodie-mooc96%74%2%jodie-reddit88%41%0%jodie-wiki96%68%0%snap-email96%55%19%snap-msg96%70%16%snap-reddit83%35%8%3570PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔Wang等人。03个冗余和重用机会0我们首先分享关于促使我们进行优化工作的冗余观察和见解。我们确定了三个主要的冗余和重用可能性发生的地方：在批处理边缘时的重复（§3.1），在相同时间子图上执行相同计算（§3.2），以及编码相同的时间间隔（§3.3）。03.1批处理边缘的重复我们观察到，将边缘打包到批次中的特定方式会导致正在计算重复目标��,��对的重复嵌入。对于CTDG数据，边缘列表被分组成一个批次。每个边缘��（��）被解耦为其源节点和目标节点，使用相同的��作为结果节点-时间戳对中的目标时间戳。在图结构中，节点经常共享共同的邻居，这可能导致重复的��,��对。例如，假设源节点�,�与相同邻居�在时间�有一条图1所示，这将导致��,��在批次中出现两次，其中一个是重复的为了准确，我们定义了以下规则：给定一批边缘作为节点时间戳列表B ={���,���,���,���,...}，如果存在一对元素满足��=��∧��=��0图批处理节点时间0图1.图中新边缘被分组成批次，导致重复的节点-时间戳对的示例。0我们推断存在几种重复出现的情况。首先，它们可能存在于模型在起始层接收的批次B中。其次，当模型递归计算嵌入时，批处理过程意味着它将汇集批次中所有目标节点的邻居作为输入传递给前一层，从而导致潜在的重复。最后，当递归到达层0时，节点特征被检索，目标时间戳是无关紧要的，因为特征是静态的，所以上述规则只需要检查目标节点，这可能会导致在之前可能没有重复的情况下出现重复。为了增加我们的直觉，我们分析了几个数据集，并发现重复项可以占批次的平均55％，并且可以随着层次的下降而迅速增加，如表1所示。03.2时间上冗余的嵌入计算我们的主要观点之一是，模型将不可避免地在不同时间为相同节点计算相同的嵌入。我们的直觉是，动态图中并非所有节点都在同一时间发生变化。当与推理时间不变的事实相结合时，一个层将执行相同的计算，此时可以重复使用先前生成的嵌入，而不是重新进行计算。当模型通过前一层递归计算嵌入时，它也会递归采样邻居。这实际上在�-层模型中引入了一个�-跳子图，该模型从目标节点开始。随着邻居的采样，它需要遵守��<�的时间约束。在递归过程中，时间�变为��，这导致�-跳子图中的所有邻居的边时间戳小于初始目标时间。我们将这个引入的�-跳子图称为时间子图。在检查这个采样过程时，我们意识到一个节点的邻域在节点发生变化时可能保持基本不变。特别地，使用最新采样的选择提供了一个很好的性质，即节点的最新邻居在相对顺序上基本保持不变。这意味着随着节点的演变新的交互，旧的邻居仍然可以保留在采样的时间子图中，只要它们遵守��<�的约束，其中�现在是新的交互时间。0表1.每个模型层200个边的重复百分比，对数据集中的所有批次进行平均。有关这些数据集的摘要，请参见表2。0数据集TGAT层0一个层将执行相同的计算。在这种情况下，可以重复使用先前生成的嵌入，而不是重新进行计算。当模型通过前一层递归计算嵌入时，它也会递归采样邻居。这实际上在�-层模型中引入了一个�-跳子图，该模型从目标节点开始。随着邻居的采样，它需要遵守��<�的时间约束。在递归过程中，时间�变为��，这导致�-跳子图中的所有邻居的边时间戳小于初始目标时间。我们将这个引入的�-跳子图称为时间子图。在检查这个采样过程时，我们意识到一个节点的邻域在节点发生变化时可能保持基本不变。特别地，使用最新采样的选择提供了一个很好的性质，即节点的最新邻居在相对顺序上基本保持不变。这意味着随着节点的演变新的交互，旧的邻居仍然可以保留在采样的时间子图中，只要它们遵守��<�的约束，其中�现在是新的交互时间。0新0交互0相同0子图0图2.当采样最近的3个邻居时，节点�随时间保留大部分的时间子图。0例如，考虑图2中呈现的场景。当为目标对��,�4�进行采样时，时间子图将包括邻居�，�和�，其边的时间戳分别为�1，�2和�3。现在假设节点�在时间�5与新邻居�进行了新的交互。当我们在时间�6再次进行采样时，这个新邻居将被包括在子图中。然而，请注意邻居�和�仍然保留在节点�的邻域中，并且它们的采样子图也将保持不变，因为它们的边交互时间仍然是�2和�3。事实上，我们可以从这个例子中推广，并声称在给定相同的目标��,��时，采样的时间子图将完全相同。在图2中，如果我们在新交互之前再次对��,�4�进行采样，那么这是显而易见的，因为没有任何变化。当我们在新交互之后再次对��,�4�进行采样时，新邻居将不被考虑，因为它违反了时间约束（即边的时间必须<�4）。因此，得到的时间子图将与之前相同。当引发的时间子图相同时，意味着模型将对相同的节点、邻居和时间戳执行相同的计算。为了验证我们是否可以利用这个观察结果来重用先前生成的嵌入，我们对动态图中正在计算的嵌入进行了分析。具体而言，我们对图的每条边进行了模型推理，并跟踪生成的嵌入以及根据我们上述的洞察力有多少可以重用。从这个初步分析中，我们观察到存在令人信服和有利的机会来重用计算的嵌入。图3展示了我们研究的数据集之一中嵌入被重用和重新计算的趋势。这个趋势还向我们展示，随着图随时间演化，可以重用的嵌入数量也在增加。在峰值时，重用嵌入与重新计算嵌入的比例约为8.9比1，或者约占总嵌入的89.9%。事实上，我们看到在其时间演化的最初几天后，重用的数量已经超过了重新计算嵌入的数量。in the subgraph. However, notice that neighbors 𝑏 and 𝑐 arestill retained in node 𝑣’s neighborhood, and their sampledsubgraphs will remain unchanged as well since their edgeinteraction timestamps are still 𝑡2 and 𝑡3.In fact, we can generalize from this example and claim thatgiven the same target ⟨𝑖,𝑡⟩, the sampled temporal subgraphwill be exactly the same. In Figure 2, if we sample for ⟨𝑣,𝑡4⟩ asecond time before the new interaction, then this is triviallytrue since there have not been any changes. When we sample⟨𝑣,𝑡4⟩ again after the new interaction, the new neighbor willnot be considered since it violates the temporal constraint(i.e. edge time must be < 𝑡4). Thus, the resulting temporalsubgraph will be the same as before.When the induced temporal subgraph is the same, it im-plies that the model will be performing the same computa-tions on the same set of nodes, neighbors, and timestamps.To validate if we can exploit this observation in order toreuse previously generated embeddings, we performed ananalysis on the embeddings being computed in dynamicgraphs. Specifically, we ran model inference on each edge ofthe graph and tracked the embeddings being generated andhow many could be reused based on our insight above.From this initial analysis, we observed that there are com-pelling and favorable opportunities for reusing computedembeddings. Figure 3 illustrates the trend of embeddingsbeing reused versus recomputed for one of the datasets westudied. This trend also showed us that as a graph evolvesover time, the amount of embeddings that could be reusedalso increases. At its peak, the ratio of reused embeddingsto recomputed ones is about 8.9 to 1, or about 89.9% of thetotal embeddings. In fact, we see that the number of reusesalready exceeds the number of recomputed embeddings afterthe first few days of its temporal evolution.0501001502000.00.51.01.52.0024680200040001.60.00.20.40.60.81.01.20.10.20.33580TGOpt：面向TGAT的冗余感知优化 PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔0时间（天）0嵌入数量01e60#重用的数量#重新计算的数量0图3.根据边的时间戳，随着时间的推移重新使用和重新计算的嵌入。03.3重复的时间编码最后一个洞察是关于TGAT如何对嵌入计算进行时间信息的编码和注入。0回到公式(4,5)，我们立即注意到它总是将��(�)的时间编码设为0。每次进行这个计算都是不必要的——因为时间编码器的权重在推理时是固定的，我们可以提前计算一次并无限重复使用。同时，对于��(�)，我们注意到时间编码器重复编码相同的时间差(Δ�)。事实上，我们观察到Δ�遵循幂律分布，并且接近0，如图4所示。我们注意到[41]中的作者也对Δ�的性质做出了相同的观察，但是观察结果的解释和背景不同。在我们的情况下，我们推断由于模型使用最近的采样，时间差�−��将相对较小且接近0。此外，采样相同的邻居并引发相同的时间子图意味着时间编码器经常遇到相同的Δ�。再次，我们将此视为避免进行计算的机会，通过重复使用先前计算的值。01.8 1e60时间差值（秒）1e60频率0图4. snap-msg数据集中时间编码器处理的时间差值分布。04基于冗余性的优化0在本节中，我们提出了利用我们在§3中提出的冗余性的优化方法。我们所有的优化都保持模型语义并产生与之前相同的输出，从而保持模型准确性。算法1概述了我们TGOpt系统中推理函数的计算过程。它在计算一批目标��,��对的时间嵌入时使用了一个记忆缓存，并且是原始TGAT推理函数的一种即插即用的替代品。在进行任何计算之前，会执行第8行的缓存查找。当缓存未命中时，它会对邻域进行采样（NghLookup操作）并进行原始计算，最后在第17行存储结果（§4.2）。在缓存操作之前和之后执行第6行和第20行的去重过滤和逆映射操作（§4.1）。第14行的TimeEncode操作将内部使用预计算的时间编码（§4.3）。04.1去重节点正如我们在§3.1中探讨的，批处理边交互时可能存在许多重复项。3590PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔Wang等0算法1：使用TGOpt进行端到端冗余感知的TGAT时间嵌入计算。0数据：动态图G，节点特征�，边特征�，GNN注意力操作符�，采样�个邻居0输入：当前层�，目标节点和时间(��,��)输出：层�的节点嵌入特征�0函数Embed(�,��,��)0如果�==0，则0�←在�中查找节点特征，用于��；0返回�；0结束0��,��,���_���←DedupFilter(��,��)；� § 4.10����←ComputeKeys(��,��)；� § 4.20����,�←CacheLookup(����)；� § 4.20如果没有全部命中，则0将����,��,��列表缩小为仅包含未命中的项；0�����,�����←NghLookup(G, �,��,��)；0�(�−1)←Embed(�−1,��∪�����,��∪�����)；0Δ�←��−�����；0��←TimeEncode(0,Δ�)；� § 4.30��←在�中查找边特征；0��←�(�(�−1),��,��)；� Eqs.(6,7)0CacheStore(����, ��)；� § 4.20将��复制到�；0结束0�←DedupInvert(�,���_���)；� § 4.10返回�；0结束0去重过滤器（DedupFilter）预处理输入批次B并生成唯一元素。在实践中，批次B表示为两个数组：一个是节点列表，另一个是边时间戳列表，两者长度相同。批次中每个边的源节点和目标节点被连接起来形成一个节点列表。注意，TGOpt仅将此过滤器应用于层�>0的输入节点和时间戳列表。尽管表1表明在层0的输入中存在许多重复项，但由于它只需要查找节点特征，因此无需应用DedupFilter。此外，使用逆索引（inv_idx）将唯一项映射回原始数组。此索引在计算完成后用于生成预期形状的输出嵌入，并具有重复结果，以保留语义并产生可与基准实现进行比较的结果。优化过滤器。可以使用NumPy和PyTorch库轻松实现DedupFilter和DedupInvert操作。然而，对于DedupFilter来说，这样做会产生不必要的开销和内存占用。由于唯一性由节点和时间戳确定，0算法2：去重目标节点和时间戳，并构建逆索引。0输入：目标节点和时间(��,��)输出：唯一目标列表和逆索引01 �� ����,�� ����,��� _ ���  ← {}，{}，{}；02 ���������  ← 从键到索引的映射；03 对于� ∈04 从(��,��)中检索元素�；05 ���  ←  Hash(�,�)；06 如果���已经在���������中，则07 ���  ← 从���������中获取索引；08 ��� _ ���  ←  ��� _ ���  ∪ { ��� }；09 否则010 ���  ←  �� ����的当前大小；011 ��� _ ���  ←  ��� _ ���  ∪ { ��� }；012 �� ����  ←  �� ����  ∪ { � }；013 �� ����  ←  �� ����  ∪ { � }；014 将���,���存储在���������中；015 结束016 结束017 返回�� ����,�� ����,��� _ ���；0首先需要通过连接这两个数组来构建一个二维张量，这会消耗内存。我们在算法2中概述了一种方法，该方法同时操作两个单独的数组，以避免创建中间张量。它使用哈希函数来检查唯一性，该函数生成无冲突的哈希值（键）。由于节点和时间戳是32位值，哈希函数通过位移和按位或运算将这两个值构造为64位值，这是高效的并且具有无冲突性质。04.2 嵌入的记忆化0我们的目标是持久化计算出的嵌入，以便在以后的时间中可以重复使用，这需要一种方法来标识每个嵌入并在需要时检索它们。我们基于记忆化技术开发了一种高效的方案来实现这一目标。通常，记忆化缓存将输入映射到输出，不同的输入会产生不同的输出。在我们的情况下，输出是嵌入张量�(�)，而输入将是计算嵌入所需的值。我们首先讨论计算输入的缓存键，然后在第4.2.2节中详细介绍存储/查找值的细节。04.2.1 计算缓存键。算法1中的第11-15行0我们需要至少考虑邻居列表、边的时间戳、边的特征和�(�−1)作为输入。这些输入通常会通过哈希运算合并为单个键值，但是对于完整的输入集来说，这样做会影响性能。正如我们在第3.2节中所建立的，对于相同的目标��,��进行采样将产生相同的时间子图，以及相同的3600TGOpt：面向TGAT的冗余感知优化 PPoPP '23，2023年2月25日-3月1日，加拿大蒙特利尔0计算将被执行。因此，我们可以利用这一点来排除除目标��,��对以外的所有内容。因此，ComputeKeys操作只需要考虑这两个值，以便生成将输入映射到存储的嵌入的键。用于去重过滤器的相同哈希函数也用于此目的。还要注意，由于批处理中的每个��,��对彼此独立，因此ComputeKeys操作可以在这些对之并行执行，我们在TGOpt的实现中利用了这一点。04.2.2缓存存储和查找。用于保留计算出的嵌入的存储方案将影响缓存查找的操作。TGOpt目前使用的是一个简单的方案，即使用哈希表将键映射到嵌入向量。使用这种方案，缓存查找只需要搜索一个数据结构，这也使得其他簿记工作变得简单，但也可以选择更复杂的设计选择。算法3展示了CacheStore操作。0算法3：TGOpt缓存的存储操作。0输入：缓存列表  ���� ，嵌入  � � （���� 中的每个键对应于� 中的一个向量）01  ����  ←  当前缓存表大小 + 键的大小;02 如果  ����  >  �����  则03 从缓存表中淘汰项目;04 结束05 如果使用GPU，则06 将  � �  移动到CPU设备;07 结束08 对于  ���  ∈  ���� ，执行09 � �  ←  下一个在  � �  中的嵌入向量;010 在缓存表中存储  ���,� � ;011 结束0至于 CacheLookup操作，TGOpt使用给定的键列表在缓存表中搜索命中，并返回一个嵌入张量。为了避免创建中间张量，在搜索过程中，它将构造最终的嵌入张量（�），并在搜索过程中部分填充它。任何缺失的嵌入将由返回的命中索引指示。最后，如果使用GPU设备进行计算，它将在返回之前将张量移动到GPU上。我们还注意到，每个键都可以独立操作，因此在 CacheStore 和CacheLookup中的主循环可以并行化，因为TGOpt使用并发哈希表实现。我们根据硬件选择性地并行化这些操作。存储内存限制。为了注意内存使用情况，我们对TGOpt的缓存施加了内存预算。CacheStore操作将检查缓存的大小与此限制的比较，并在必要时淘汰项目。目前，它0使用简单的FIFO淘汰策略。我们通过只缓存 � − 1层来进一步减少内存使用。这是基于这样一个事实，即计算 � (� − 1 ) 需要 � ( � )。而另一方面，最后一层的 � ( � )对其他计算不是必需的。采用什么缓存限制是一个在性能和内存使用之间平衡的决策。通过设置较低的限制，性能增益将较低，因为需要执行更多的计算，而较高的限制允许更多的重用，但也会增加内存使用。我们在第5.2.4节中探讨了这种紧张关系。存储内存位置。另一个设计决策是在CPU还是GPU内存中存储嵌入。在GPU上运行推理时，张量需要驻留在同一设备上。在这项工作中，我们建议仅将缓存的嵌入存储在CPU上，而不是GPU上。这意味着 CacheStore 和CacheLookup操作将产生数据移动成本。但我们推断出，在缓存查找期间的数据大小通常很小，并且当前的查找方法强调在找到命中时进行许多小数据复制，这些都不利于GPU。我们在第5.2.5节中对我们的设计选择进行了分析。04.3预计算时间编码为了减少第3.3节中提到的冗余，TGOpt在运行推理之前预先计算时间编码向量。由于时间编码器参数在推理期间是固定的，并且 Δ �是没有其他依赖关系的简单值，我们可以直接应用 Φ(∙)函数并保留时间向量以供以后使用。与[41]中描述的查找表不同，该表被分为128个时间间隔，TGOpt将预先计算从0开始的一段 Δ � 值。因为这个时间窗口从0开始是连续的， Δ �值本身可以作为索引，用于查找存储时间编码向量的密集张量，从而实现简单的查找过程。然而，我们仍然需要考虑任何缺失并执行原始计算。因此，TimeEncode函数的操作方式类似于CacheLookup，即它构造最终的时间编码张量（��），并在命中向量中部分填充它。05 评估0我们在各种动态图数据集上评估了TGOpt与基线的性能，CPU上的几何平均加速比为4.9×，GPU上的几何平均加速比为2.9×。我们在本节中总结了我们的实验设置、结果和分析。05.1实验设置我们的主要指标是模型在标准推理任务上的运行时间。为了模拟图在时间上的演化，推理任务被设置为按时间顺序和每批200个边的