TGOpt：时态图注意网络的冗余优化

3540TGOpt：面向时间图注意网络的冗余感知优化0伊利诺伊大学香槟分校，美国，yufengw2@illinois.edu0伊利诺伊大学香槟分校，美国，charithm@illinois.edu0摘要时间图神经网络在建模动态图上的交互方面越来越受欢迎。其中，时间图注意网络（TGAT）在一系列应用中都被用于预测任务，如链接预测。大多数针对图神经网络（GNNs）的优化和框架都专注于在静态图上操作的GNN模型。虽然其中一些优化方法利用了静态图上的冗余计算，但它们要么不适用于TGAT中使用的自注意机制，要么不利用与时间执行行为相关的优化机会。在本文中，我们探索了特定于TGAT推理中涉及时间组件的计算所产生的冗余感知优化机会。我们观察到在时间节点嵌入计算中存在相当多的冗余，例如重新计算先前计算的邻居嵌入和重复时间增量值的时间编码。为了利用这些冗余机会，我们开发了TGOpt，它引入了基于去重、备忘录和预计算的优化技术，加速了TGAT的推理性能。我们的实验结果表明，TGOpt在广泛的动态图上进行推理时，在CPU上实现了4.9倍的几何平均加速，在GPU上实现了2.9倍的几何平均加速，Reddit帖子数据集在CPU上最高加速6.3倍。0CCS概念：•计算方法学→神经网络；•软件及其工程→软件性能。0关键词：时间图神经网络，冗余感知优化，备忘录，动态图0未经许可，您可以制作本作品的全部或部分的数字或印刷副本，供个人或课堂使用，但不得为了牟利或商业优势而制作或分发副本，并且副本必须带有本声明和第一页的完整引用。除非获得作者之外的其他组件的版权，否则必须尊重其版权。允许带有署名进行摘要。未经事先特定的许可和/或费用，不得复制、转载、发布到服务器或重新分发到列表。请向permissions@acm.org申请权限。PPoPP ’23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，©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 ]、PyTorchGeometric[ 5 ]和NeuGraph[ 19]，使从业者能够更轻松地尝试不同的GNN拓扑结构，同时实现高性能。然而，大多数这些框架和优化方法都集中在仅操作静态图的GNNs上。最近，基于时间的GNNs（TGNNs）因其在动态图上学习预测模型的能力而受到欢迎，这些图在时间上演化，具有新的节点或边。在这些TGNN模型中，时间图注意网络（TGAT）[ 37]已经在多个应用中得到了采用，从建模时间知识图[ 10 , 11]到基于时间传播的假新闻检测[ 26]。TGAT在连续时间动态图上进行预测建模，处理随时间发生的边交互的批次。与其静态对应物相比，TGAT的训练和推理计算量更大，因为它依赖于复杂的注意机制以及其他编码操作来捕捉邻域的时间特性[ 41]。因此，优化TGAT仍然具有挑战性，但对于增加最终用户的生产力非常重要。在本文中，我们介绍了一些增加TGAT推理性能的技术，主要是通过消除冗余计算。冗余消除已经在静态GNNs的背景下进行了研究。例如，HAG[ 12 ]和ReGNN[2]是通过识别和重用重叠邻居的聚合来减少冗余的方法。这些方法需要转换为自定义计算图表示，并且仅适用于TGAT这样的基于注意力的模型。在时间上下文中，与涉及TGAT推理的计算相关的冗余计算机会有限。在本文中，我们探索了特定于TGAT推理中涉及时间组件的计算的冗余感知优化机会。我们观察到在时间节点嵌入计算中存在相当多的冗余，例如重新计算先前计算的邻居嵌入和重复时间增量值的时间编码。为了利用这些冗余机会，我们开发了TGOpt，它引入了基于去重、备忘录和预计算的优化技术，加速了TGAT的推理性能。我们的实验结果表明，TGOpt在广泛的动态图上进行推理时，在CPU上实现了4.9倍的几何平均加速，在GPU上实现了2.9倍的几何平均加速，Reddit帖子数据集在CPU上最高加速6.3倍。3550PPoPP ’23，2023年2月25日至3月1日，加拿大蒙特利尔，Wang等人0优化TGNNs的努力。例如，[ 41 ]取代了自注意力，专注于基于FPGA的加速器。相比之下，在本文中，我们采用了一种不同的方法，即专注于TGAT的时间方面，并利用时间和推理执行之间发生的时间冗余。我们观察并利用了时间嵌入和时间编码计算中的冗余，大大减少了TGAT推理运行时间。与之前的工作不同，我们考虑的冗余消除技术不仅局限于简单的聚合，也不需要替换自注意力。我们观察到TGAT推理过程中存在三个主要的冗余计算来源。首先，在一个批次中处理边交互的源节点和目标节点可能会导致相同的节点嵌入计算。对于某些图形，一个批次中可能有高达55%的相同计算。其次，为给定的节点和时间戳计算嵌入将探索在先前时间步骤中已经探索过的相同时间邻域，从而导致相同嵌入的重新计算。在我们的分析中，我们发现一些动态图形的89.9%的总嵌入会重复计算。第三，在TGAT中，时间编码操作经常使用相同的时间增量值。我们在§3中详细阐述了这些观察结果。基于这些关键观察，我们开发了TGOpt来利用这些机会，通过重用值而不是在TGAT推理过程中重新计算值来加速推理计算。TGOpt通过执行以下操作来加速推理计算：1）在处理一批边交互时去重复的节点/时间戳，2）缓存先前计算的节点嵌入，3）预计算一定窗口的时间增量值的时间编码。这些技术是语义保持的冗余感知转换，保持了基线版本的计算语义和最终用户接口，从最终用户的角度来看，透明地改善了性能。由TGOpt生成的节点嵌入与基线版本的节点嵌入相同，浮点容差内，因此保持了模型的准确性。TGOpt中的重用技术需要额外的内存来缓存计算后的值以供后续重用。为了在这些重用和内存消耗之间取得平衡，TGOpt提供了设置来限制其计算值缓存的内存占用。为了评估我们的方法，我们在CPU和GPU环境中将TGOpt的推理性能与TGAT的基线实现进行了比较。我们的结果表明，对于各种动态图形，TGOpt在CPU上实现了4.9倍的几何平均加速，GPU上实现了2.9倍的几何平均加速，Reddit帖子数据集在CPU上最高加速6.3倍。我们在§5中详细阐述了我们的结果和发现。总的来说，我们的结果表明，TGOpt在保持模型语义和准确性的同时，为TGAT推理提供了显著的加速。03560或连续时间动态图（CTDGs）。CTDG是一个时间戳图事件流G = {�(�1),�(�2),...}，其中时间戳0≤�1≤�2≤...按顺序排列[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模型可以用消息传递风格[6]来表示，它将GNN操作符抽象为三个步骤。为了方便后续讨论，我们扩展消息传递以捕捉时间的概念，时间是动态图的一个关键参数：0� �  ( � )  =  msg � � ( � − 1 ) � ( � ) , � ( � − 1 ) � ( (0� �  ( � )  =  agg � { � �  ( � )  :  �  ∈ N ( �,� )} � (20� ( � ) � ( � )  =  upd � � ( � − 1 ) � ( � ) , � �  ( � ) �0其中∥是连接运算符，FFN是一个前馈神经网络。方程（4，5）是方程（1）中的消息创建步骤，方程（6）是方程（2）中的agg(∙)，方程（7）是方程（3）中的更新函数。方程（6）中的Attn(∙)是[28]中的自注意机制，只是现在根据时间进行参数化。对于我们考虑的优化问题，具体细节并不重要，我们将这个注意机制抽象地称为�（详见[37]）。这些方程构成了TGAT模型架构中的一层。一层的输入只是目标��,��，而其他所有内都是计算得到的。计算嵌入从���层（起始层）开始，然后从各层向前计算，直到第一层，其中�(0)� =��。更重要的是，注意TGAT对�的选择是边时间戳��，而被编码时间值是目标时间�和��之间的差（因此对于目标节点来说是0）。时间编码函数的公式为：0时序图注意力网络。TGAT模型是一种可以为CTDG数据生成时序嵌入的时序GNN。它学习一个从时间值映射到��维向量的函数Φ: � →R��。这种时间编码技术使其能够捕捉图的时间模式。然后将时间编码向量注入到GNN操作符的输入特征中，从而并入输出嵌入。TGAT的计算可以用时序消息传递模型表示：0) ∥  Φ ( �  −  � � ) (5)0� ( � ) � ( � )  =  FFN � � �  ( � ) ∥  � ( � − 1 ) � ( � ) � (7)0Φ(Δ�)=cos(π∙Δ�+π)（8）0其中�,�是可学习的向量，Δ�是一个时间增量[41]。时间采样。在计算�(�)�(�)的同时，层需要前一层的节点和邻居嵌入。可以考虑所有邻居，但实际上由于可扩展性问题，这很少发生。相反，模型通常通过采样来限制最大数量的邻居[9]。这种采样的常见策略包括均匀/随机采样和最近邻居采样。尽管TGAT模型都适用，但我们只关注最近邻居采样，因为它具有更好的性能特征，如[22]所示。批量训练和推断。上述方程从单个目标节点的角度进行了描述。实际上，TGAT模型同时处理一批边的相互作用，并为源节点和目标节点生成嵌入。批处理过程通过将节点打包成张量来允许并行处理节点。23570PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔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。0jodie-lastfm 94％ 48％ 0％jodie-mooc 96％ 74％ 2％jodie-reddit 88％ 41％ 0％jodie-wiki 96％ 68％ 0％snap-email 96％ 55％ 19％snap-msg 96％ 70％ 16％snap-reddit 83％ 35％ 8％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％。实际上，我们看到在其时间演变的前几天后，重用的嵌入数量已经超过重新计算的嵌入数量。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. snap-msg数据集上随时间重复使用与重新计算的嵌入数。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输入：当前层 �，目标节点和时间 ( ��,�� ) 输出：层 �的节点嵌入特征 �01  函数  Embed ( �,��,�� )02 如果 � == 0 则03 �  ←  在 � 中查找节点特征;04 返回 �;05 结束06 ��,��,��� _ ���  ←  DedupFilter( ��,�� ) ; �  § 4.107 ����  ←  ComputeKeys( ��,�� ) ; �  § 4.208 ����, �  ←  CacheLookup( ���� ) ; �  § 4.209 如果没有全部命中，则010 缩小 ����,��,�� 列表只包含未命中的元素;011 �� ��� ,�� ���  ←  NghLookup( G , �,��,�� );012 � ( � − 1 ) ←  Embed ( �  −  1 ,��  ∪  �� ��� ,��  ∪  �� 013 Δ �  ←  ��  −  �����;014 � �  ←  TimeEncode( 0 ,  Δ � ) ; �  § 4.3015 � �  ←  在 � 中查找边特征;016 � �  ←  � ( � ( � − 1 ) , � � , � � ) ; �  Eqs.( 6 , 7 )017 CacheStore( ����, � � ) ; �  § 4.2018 将 � � 复制到 �;019 结束020 �  ←  DedupInvert( �,��� _ ��� ) ; �  § 4.1021 返回 �;022 结束0去重滤波器 ( DedupFilter ) 对输入批次 B进行预处理并生成唯一元素。在实践中，批次 B表示为两个数组：一个是节点列表，另一个是边的时间戳列表，它们的长度相同。批次中每个边的源节点和目标节点连接在一起形成一个节点列表。注意，TGOpt仅将此过滤器应用于层 � > 0的输入节点和时间戳列表。尽管表1表明在层0的输入中存在许多重复项，但由于它只需要查找节点特征，因此不需要应用DedupFilter。此外，逆索引(inv_idx)用于将唯一项映射回原始数组。此索引在计算完成后使用，以产生预期形状的输出嵌入，并带有重复结果，以保持语义并生成可与基准实现进行比较的结果。优化过滤器。可以使用NumPy和PyTorch库很容易地实现 DedupFilter 和 DedupInvert 操作。但是，为DedupFilter这样做将产生不必要的开销和内存占用。由于唯一性是由节点和时间戳决定的，0算法2：目标节点和时间去重以及构建逆索引。0输入: 目标节点和时间 ( ��,�� ) 输出:唯一目标列表和逆索引01  �� ���� ,�� ���� ,��� _ ���  ← {} ,  {} ,  {} ;02  ���������  ←  从键到索引的映射;03  对于 �  ∈  0 ..���� ( �� )  做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 end05 如果使用GPU，则06 将  � �  移动到CPU设备;07 end08 对于  ���  ∈  ����09 � �  ←  � � 中的下一个嵌入向量;010 在缓存表中存储  ���,� � ;011 end0至于CacheLookup操作，TGOpt使用给定的键列表在缓存表中搜索命中，然后返回嵌入张量。为了避免创建中间张量，它将构建具有预期形状的最终嵌入张量（ �），并在搜索过程中部分填充它。任何缺失的嵌入将由返回的命中索引指示。最后，如果使用GPU设备进行计算，它将在返回之前将张量移动到GPU。我们还注意到每个键都可以独立地进行操作，因此CacheStore和CacheLookup的主循环可以并行化，因为TGOpt使用并发哈希表实现。我们根据硬件有选择地并行化这些操作。存储内存限制为了节省内存使用，我们对TGOpt的缓存设置了内存预算。CacheStore操作将检查缓存的大小是否超过此限制，并在必要时驱逐项目。目前，它使用简单的FIFO驱逐策略。0使用简单的FIFO驱逐策略。我们通过仅缓存  �  −  1层来进一步减少内存使用。这是基于这样一个事实，即计算  �( � − 1 ) 需要计算  � ( � ) 。另一方面，最后一层的  � ( � )对其他计算没有影响。采用哪种缓存限制是一个在性能和内存使用之间平衡的决策。通过设置较低的限制，性能增益将较低，因为需要执行更多的计算，而较高的限制允许更多的重用，但也会增加更多的内存使用。我们在第5.2.4节的实验中探讨了这种紧张关系。存储内存位置。另一个设计决策是在CPU内存还是GPU内存中存储嵌入。当在GPU上运行推理时，张量需要驻留在同一设备上。在这项工作中，我们建议仅在CPU上存储缓存的嵌入，而不是GPU上。这意味着在进行缓存查找操作时，数据移动开销会增加。但是我们认为，在缓存查找期间的数据大小通常很小，并且当前的查找方法强调在找到命中时进行多个小数据复制，所有这些都对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个边的顺序遍历图中的所有边。对于每个批次，我们运行模型生成时间嵌入。我们3610PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魁北克省王等人。0将运行时间定义为遍历动态图数据集中所有边的总时间。模型按照标准训练程序进行训练，然后在推理过程中使用训练后的参数。05.1.1基准模型和数据集。我们的基准是官方的TGAT实现1，我们更新为使用更高版本的Python（v3.7）和PyTorch（v1.12）。所使用的TGAT模型有2层、2个注意头、20个最近邻居的采样，其余设置为默认值。我们评估了各种大小的二部图和同质图。按照基准，二部图被视为同质图，并且所有图都被认为是无向图。数据集的进一步描述如下，而表2总结了它们的数据统计信息。 •二部图：jodie-lastfm、jodie-mooc、jodie-reddit（Reddit帖子）和jodie-wiki是广泛使用的具有用户和项目节点类型的二部图。我们使用JODIE[17]的经过筛选的数据集来处理这四个数据集。0•  同质： snap-email是一个研究机构发送的电子邮件数据集。 snap-msg捕捉了大学社交媒体网络上用户之间的消息。 snap-reddit表示在帖子的标题或正文中创建的子论坛之间的超链接引用。这三个数据集都来自SNAP数据存储库[18]，分别是CollegeMsg，email-Eu-core-temporal和soc-RedditHyperlinks。0表2。我们评估TGOpt的数据集。节点特征使用与边特征相同维度的零向量。†当缺少边特征时，使用随机生成的100维向量。0数据集|�||�|�†� max (�)0jodie-lastfm 1,980 1,293,103 - 1.4e8jodie-mooc 7,144 411,749 4 2.6e6 jodie-reddit10,984 672,447 172 2.7e6 jodie-wiki 9,227157,474 172 2.7e6 snap-email 986 332,334 -6.9e7 snap-msg 1,899 59,835 - 1.1e9snap-reddit 67,180 858,488 86 1.5e905.1.2机器环境我们在两台不同的机器上进行了实验。一个是配备2个Intel Xeon Gold 6348 @2.6GHz，每个28个核心和1TB内存的CPU服务器。我们的GPU机器是一个AWS p3.2xlarge实例，配备8个vCPU @2.3GHz，61GB内存和一块Nvidia Tesla V100GPU（16GB）。01https：//github.com/StatsDLMathsRecomSys/Inductive-representation-learning-on-temporal-graphs05.2结果我们以下列实验结果为基础。我们报告了所有图的推理性能结果，并对两个选择数据集进行了深入分析。对于我们的删除研究（§ 5.2.2）和其他分析（§5.2.3，5.2.4，5.2.5），我们重点关注jodie-lastfm和snap-msg作为大型/小型和双分图/同质图的代表性数据集。05.2.1推理性能如图5所示，TGOpt在所有数据集和机器环境上都明显优于基线。它在CPU上的速度提高范围为3-6倍，在GPU上为2-3倍。正如结果所示，性能提升在CPU上比在GPU上更高。正如我们在我们的细分分析中所展示的（§5.2.3），GPU上的张量操作比CPU更高效，通过重用值，TGOpt能够最小化在CPU上重新计算嵌入张量的昂贵开销。在CPU的结果中，我们看到双分jodie-*数据集的加速比比snap-*数据集更高。在[17]中，JODIE的作者提到，双分数据集是专门为用户与同一项连续交互的重复行为而策划的。自然地，这会导致与单个邻域的新交互，但其余的邻域大部分保持不变，这正是TGOpt利用的冗余类型。具体来说，这意味着未更改邻域的相同时间增量的重复时间编码将更多。正如我们的删除研究所示，预计算优化能够利用这一点，在CPU上为jodie-*数据集产生更高的加速。01002003004005006000501001502002461233620TGOpt：TGAT的冗余感知优化PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔0jodie-lastfm0jodie-mooc0jodie-reddit0jodie-wiki0snap-email0snap-msg0snap-reddit05.5倍05.8倍06.3倍05.5倍03.4倍04.3倍04.0倍0基准*TGOpt0jodie-lastfm0jodie-mooc0jodie-reddit0jodie-wiki0snap-email0snap-msg0snap-reddit02.5倍02.8倍03.3倍03.6倍3.0倍03.0倍02.4倍0基准*TGOpt0图5。不同数据集的推理性能（左侧为CPU服务器，右侧为GPU机器）。运行时间平均值为10次。条形图顶部的线是其标准偏差。 TGOpt的条形图标签是加速比。�基准是TGAT官方代码。0与此同时，GPU上的结果更加一致，标准偏差较低。由于TGOpt使用CPU内存作为缓存，这使得每个设备的物理缓存层次结构得到更好的利用，并减少内存争用，从而产生更一致的GPU加速。尽管在CPU上运行时间更长，但数据集相对性能在两台机器上的比较是相似的（例如，jodie-lastfm与snap-msg相比，运行时间大约要长20倍）。0jodie-lastfm snap-msg 00CPU加速（x）0jodie-lastfm snap-msg 00GPU加速（x）0基准缓存缓存+去重缓存+去重+时间0图6。顺序应用优化时的累积推理加速。05.2.2 删除研究。为了更好地理解我们的三种优化的贡献，我们进行了一项删除研究，逐步启用每一项。如图6（顶部）所示，仅通过在CPU上应用缓存优化，我们就看到了至少3倍的加速。启用去重操作对加速性能的贡献略微增加，而启用时间预计算则大大提高了性能。事实上，jodie-lastfm数据集的加速性能有了显著提升。由于张量计算在CPU上更昂贵（如表3所示），预计算优化所避免的重新计算超过了产生的开销。当与其他优化组合使用时0与§5.2.1中提到的交互重复行为相结合，这导致jodie-*数据集的性能提升更为明显。为了从另一个角度看，我们在GPU机器上进行了相同的删除研究（图6底部）。启用缓存/去重优化可使两个数据集的速度提高至少2倍，但时间预计算产生了小幅回归。正如表3中的成本细分所示，时间编码查找对TimeEncode操作产生开销，这对GPU上的性能产生了负面影响。由于GPU在执行时间编码张量操作时效率更高，从重复使用的时间编码值中节省的成本变得较小，而查找开销变得更加显著。从这个角度来看，将优化调整到硬件（以及可能是数据集）可能会产生更好的性能提升。05.2.3成本细分分析。我们对TGOpt中每个主要操作的成本进行了细分分析，并进行了其他指标的分析。我们得出了三个主要结论。首先，通过缓存和重用嵌入，TGOpt能够避免重量级操作，同时降低其他操作的成本。在表3中，对于GPU机器，我们注意到基线上的NghLookup操作花费的时间最长，而TGOpt能够显著减少这个时间。例如，jodie-lastfm看到了132秒的减少，同时只产生了44秒的缓存/去重操作的开销。零的TimeEncode涉及创建中间零张量和数据移动，因此在GPU上的成本比邻居DeltaA的TimeEn