论文标题：Temporal Graph Rewiring with Expander Graphs
论文领域：图神经网络，图重连算法
论文发表：ICML 2024
论文背景：
现实世界网络中的演化关系通常由时间图建模。时间图神经网络（TGNN）通过利用图神经网络核心的消息传递原语来模拟此类图的进化行为。众所周知，GNN容易受到与输入图拓扑直接相关的几个问题的影响，例如欠可达和过度压缩——我们认为这些问题在时间图中往往会加剧，特别是由于节点和边过时。虽然图重新布线技术在GNN中得到了频繁的使用，使图拓扑更有利于消息传递，但它们在TGNN上还没有得到任何主流使用。在这项工作中，我们提出了时态图重连（TGR），据我们所知，这是在时态图上重连图的第一种方法。TGR通过利用扩展器图传播在连续时间动态图中在时间上相距遥远的节点之间构建消息传递高速公路，扩展器图传播是一种用于在静态图上重新布线的突出框架，它对底层图结构做出了最小的假设。在具有挑战性的TGB基准测试中，TGR在撰写本文时在tgbl-review、tgbl-coin、tgbl-comment和tgbl-flight数据集上取得了最先进的结果。对于tgbl审查，TGR的MRR比基础TGN模型提高了50.5%，比基础TNCN模型提高了22.2%。对基本模型的显著改进表明了时间图重新布线的明显好处
借鉴来自时间序列，不断发展的关系可以用时间图来建模，其中节点和边可以随着时间的推移被插入或删除。其中TGNN被设计为通过引入时间记忆和时间编码等新型模型组件来捕捉图的时间变换
时序图神经网络（TGNNs）基于静态图神经网络的消息传递机制，这使得它们同样容易受到静态图神经网络所面临的信号覆盖不足和过度压缩效应的影响。本文将证明，引入时间维度会沿着时间轴产生额外的层次化信息流动，这种机制不仅会加剧上述缺陷，还会让节点间的信息交互变得更加困难。由此引出一个自然问题：通过引入时间图重连技术，我们能否有效缓解这些问题并提升TGNN的性能表现？
图重连从根本上包含了现实世界数据的动态特性。任何特定输入图都很少能完美地阐明给定任务所需的信息交换。时序图重连可以在TGNN中解决记忆老化的问题，记忆老化问题是在TGNN的时间记忆中发生的过程，只有感兴趣的节点被观察到与图中的另一个节点相互作用，时序记忆才会更新，导致了非活动节点的状态变为陈旧。但这在现实世界的动态图中存在重大问题；例如，在社交网络中，如果用户一段时间不活跃，即使他们仍在社交网络之外与活跃的朋友互动，也会失去与这些朋友的联系。
本文提出，时序图重布线产生的额外连接将通过允许信息在用户之间持续流动来缓解这种影响，否则这些用户可能会长时间处于不活跃状态。
图重连算法的扩展图的好处：1）能够有效地在输入图中全局传播信息，2）消除瓶颈和过度压缩，3）空间和时间复杂度为次二次方，4）无需对输入图进行额外的预处理。
TGR算法通过扩展图来时序远距离节点上形成快速有效的消息传递，缓解了欠可达问题和内存老化问题。
基于图的TGNN通过学习输入图的时序图特征来作为图的结构特征，可以在小型的TGB数据集获得SOTA的效果，但是因为算法严重依赖于结构特征的复杂计算，所以难以推广到大型数据集。
基于记忆的TGNN通过额外的模型组件如循环网络或两次尺度深度时序点过程，使用时序记忆来保留节点的历史信息，从而动态追踪节点交互过程。
1，提出时序图重连的理论动机。在静态图中重要的挑战，例如覆盖不足，当图获得时间轴时变得更加具有挑战性。这直接推动了对时间图进行重连的需求。
2，提出时序图的首个重连方法，TGR算法，TGR是首个将图重连技术应用于时间图的方法。该方法通过扩展图传播机制对基础时间图神经网络进行重连操作，同时保持极低的额外开销。此外，TGR对基础时间图学习模型的选择具有普适性，我们通过在两种广泛使用的TGNN上进行评估验证了这一点。
3，实验证明了TGR算法的SOTA效果，表明TGR算法确实开启了节点对之间的通信，这对各种现实世界的时间图任务都是相关和关键的。
连续时间动态图的定义为
时序连接预测任务
关注这个任务会使用到时序图神经网络TGNN，先计算节点的时间嵌入，再根据这两个节点的嵌入值来预测边存在的概率。
时序图神经网络的安全漏洞
时序图神经网路的缺点源自其时序图拓扑结构，下面介绍TGNN如何从CTDG中聚合信息。
TGN模型主要是实现一个时序记忆
其中在一个记忆向量中包含了一个节点的所有信息，分别通过学习函数和记忆向量来更新
每个节点的时序邻居可以写为函数
可学习的消息传递函数
最终的连接预测的相关概率为
TGN也有着表达能力和复杂计算的权衡。
时间节点嵌入仅用于回答链接预测查询且不会回写到内存中，因此我们可以专注于研究时间记忆向量的混合过程，而将嵌入混合视为后续处理案例。
假设节点u的输入特征在时间τ被临时混合到节点v的记忆中，前提是s依赖于x(0)u的信息。由于节点的记忆向量仅在其通过边被观察时更新，我们可以通过追踪信息传递路径来正式定义时间混合和欠达现象。
虽然时间τ上的潜在不足可能与G≤τ的静态不足有关，但正如我们通过以下命题可以证明的那样，这种情况实际上发生得更频繁。
时序欠可达比静态的欠可达的情况更为严重。
时序欠可达是非对称的
时序的批处理：一般为了效率，不会一次添加一个时序边，而是批次处理。由于一个批次中的所有边同时传播，这意味着它们不能在相同的混合路径上出现。
动态节点和边的更新：在时间图中，新增信息往往不仅限于边的添加，还可能以两种形式进入网络：要么作为需要考虑的新节点或边特征，要么直接形成全新的节点。
嵌入模型每次都需要执行新的时序链接预测查询。这就存在一个固有的权衡：如果让嵌入模块过于复杂，随着动态图规模的扩大，很容易导致计算复杂度难以承受。 事实上，在大多数实际实现中，嵌入邻域的直径不超过两个跳——这只会将我们的时间混合路径约束减少两步。
还有一个关键问题可能会影响嵌入模块的使用效果——即节点/边删除操作。在时间τ之前删除节点或边，实际上也会将其从图G≤τ的静态图中移除，这可能导致整个结构出现完全断裂。在这种情况下，嵌入模块将无法有效融合特定节点。因此，在TGR中，我们不追求过度增强嵌入模块的功能，而是采用轻量级方式实现信息的广泛传播——既不过度依赖提供的时序边，又能确保传播的信息能及时反馈至内存。
TGR算法是基于扩展图传播和TGNN的基础模型，来保证全局的信息通过时序距离节点来进行传递。
TGR的主要组件包括memory mixing（记忆混合） 和expander embedding（扩展嵌入）。 记忆混合是使用扩展图来诱导欠覆盖节点之间的混合；扩展嵌入是将此信息转换到基础TGNN模型。
TGR基于扩展图传播框架进行改进，该框架以缓解静态图中的过度压缩和覆盖不足问题而著称，并将其应用于时序图学习。
TGR通过记忆混合计算扩展嵌入，增强观察节点的输入节点特征。
记忆混合有助于在断开连接的、相距较远的节点之间进行信息交换，这些节点容易受到诸如范围不足和内存陈旧等问题的影响。
通过使用扩展器嵌入来增强TGNN的输入节点特征，TGR为基本TGNN模型提供了关于潜在欠可达节点的额外信息。
由于CTDGs被解析为按时间顺序排列的边批次，TGR在先前批次中计算扩展器嵌入，并将其包含在当前批次中，自然地整合到TGNN模型的工作流程中。
扩展图的几何属性：容易创建，没有瓶颈，优化的通勤时间。
有效的预计算： 扩展图是通过使用群运算符构建的，并作为独立的图拓扑结构，用于对输入图进行重连。本文的方法采用的是基于特殊的线性群作为生成集的Cayley图来作为扩展图族。
无瓶颈：由扩展图的Cayley图保证了高度的连接性和无瓶颈。
优化的通勤时间：在扩展图中图的通勤时间随着节点的数量的增长呈现线性增长
图重连算法的扩展图属性：使用原始邻接矩阵A和扩展图$A^{Cayley}$ 的相互交替。
该架构通过虚拟创建时间路径连接欠覆盖节点，利用底层扩展图（CTDG）实现节点间关联，这种机制独立于节点在CTDG中的历史交互。观测节点存储于节点库模块中，该模块会在每个时间批次动态更新内容。生成的扩展嵌入向量用于增强节点库中观测节点的输入特征，并将交换信息作为动态输入特征注入基础图神经网络（TGNN）模型。
通过提供动态节点特征，TGR对底层图神经网络（TGNN）架构保持中立，能够轻松集成各类TGNN模型而无需修改其层级结构。这种设计与静态图重连方法形成鲜明对比，后者通过添加重连掩码来改变输入图的拓扑结构，从而在模型架构内部单独调整图神经网络层。
在TGNN前向传播中，输入特征向量X(t)的构建方式是将时间记忆中的扩展嵌入$H(t-)$（对应已观测节点）与TGNN节点状态$S(t-)$（对应新节点）进行拼接（∥）。其中$t^-$表示紧接在$t$之前的时刻戳。
基线数据集是TGB（Temporal Graph Benchmark）
基线模型是TGN和TNCN，TGN的特点是使用TGN时间记忆来存储和更新节点状态，采用循环神经网络或GRU进行更新；TNCN通过在时间维度中采用神经共同邻居算法对链路进行编码嵌入，在大多数数据集的TGB链接预测任务中取得了业界领先的表现。
TGR是在TGNN基础上实现的，通过添加节点银行来存储观测到的节点ID，并通过记忆混合模块计算扩展嵌入。
在TGB基准上获得的动态链接属性预测标准差，基线结果直接从排行榜导入。
实验数据为
消融实验
建立在不同的基线模型上，GAT，GCN，和GIN。
将时间序列的使用在图重连领域，使用时间序列结合扩展图来实现。结合的有点牵强，对比的图重连领域的方法也比较少。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。