EdgeReMIND: 一个可扩展的顶级记忆基线用于时间多关系链接预测

# EdgeReMIND：一种可扩展、排名靠前的时间多关系链接预测记忆基准模型  
来源：https://arxiv.org/html/2609.17916  

###### 摘要  
在时间图基准 2.0（TGB 2.0）[4 (https://arxiv.org/html/2609.17916#bib.bib4)] 上进行时间链接预测面临着可扩展性瓶颈：在基准测试的三个最大数据集上，所有现有的嵌入方法要么内存不足，要么超出时间限制。这些大规模图最接近实际部署规模，因此在这些图上失败是一个真正的生产限制。EdgeReMIND 在八个 TGB 2.0 数据集中的六个上取得了报告的最高测试平均倒数排名（MRR），并且是唯一能在所有数据集上运行的关系感知方法。因此，这种通过学习关系特定权重应用于数据校准特征的线性记忆模型，并不仅仅是嵌入方法失效时的后备方案，而是该基准测试上一个实用的先进基准模型。  

## 1 引言  
时间链接预测询问在随时间演化的图中，未来将形成哪条边。本工作解决其多关系形式：给定一个源节点、一种关系类型和一个时间，任务是将真实的目标节点排在一组候选目标节点之前。它涵盖两种主要的图类型：时间知识图谱（TKGs）和时间异构图（THGs）。TKGs 通过类型化关系链接实体，每个事实带有一个时间戳，并应用于诸如基于演化患者记录的医疗诊断[18 (https://arxiv.org/html/2609.17916#bib.bib18)]等任务。THGs 允许多种节点和边类型随时间交互，并用于诸如演化式恶意软件检测[3 (https://arxiv.org/html/2609.17916#bib.bib17)]等应用。  

该领域的当前前沿基准是 TGB 2.0[4 (https://arxiv.org/html/2609.17916#bib.bib4)]。该基准揭示了一个已成为进展关键约束的可扩展性天花板。这个天花板在按节点数计算的三个最大数据集上最为突出。在这些数据集上，排行榜上的所有基于嵌入的方法都缺席、内存不足或超时，而且没有任何关系感知方法能够运行，只剩下基于对的 EdgeBank 类记忆化[16 (https://arxiv.org/html/2609.17916#bib.bib2)]（§4.3 (https://arxiv.org/html/2609.17916#S4.SS3)）。预算是基准自身的：评估硬件上最多 40 GB 的 GPU 内存，以及每个实验七天的时间限制。这个差距是结构性的，而非偶然的。  

表示学习的每条边内存成本随着图规模的扩大而难以优化地增长[6 (https://arxiv.org/html/2609.17916#bib.bib3),4 (https://arxiv.org/html/2609.17916#bib.bib4)]，因此当数据集接近部署规模时，问题恰好随之加剧。在这些数据集上，即使尚未权衡绝对准确性，能够提升可达到的天花板（在合理预算内运行的任何方法）也具有价值。  

##### 记忆化启发式方法强大但有限。最近的基准测试发现，在许多数据集上，重参数化的时间模型被简单的记忆化启发式方法超越[16 (https://arxiv.org/html/2609.17916#bib.bib2),5 (https://arxiv.org/html/2609.17916#bib.bib5)]。最突出的是 EdgeBank[16 (https://arxiv.org/html/2609.17916#bib.bib2)]，它预测如果同一对之前见过，则存在链接，可选在最近的窗口内。更强的变体随后出现，包括无需训练的 Base3[9 (https://arxiv.org/html/2609.17916#bib.bib10)] 和按关系的 Recurrency Baseline (RecB)[5 (https://arxiv.org/html/2609.17916#bib.bib5)]。这些方法共享沿着三个轴线的局限性，而且没有先前的方法能同时解决这三个问题。  

首先，固定规则方法（EdgeBank、Base3）对关系类型视而不见，即使某些关系频繁再现而其他关系几乎从不出现，也使用相同的规则对每个查询进行评分；RecB 通过按关系拟合来调整关系，但接下来的两个局限仍然存在。  

其次，“曾经见过”与“最近见过”之间的平衡是手工设置或通过粗略的网格搜索来设置的，而不是从重现间隔统计中学习。  

第三，最近信号对每个关系使用单一的衰减时间尺度，该尺度以绝对时间单位固定，而不是根据数据自身的间隔进行校准。这个单一时间尺度不仅与具有其他时间尺度的数据集不匹配，而且与一个数据集中以不同速率再现的关系也不匹配。  

##### 贡献。本文介绍了 EdgeReMIND（带区间衰减的关系感知记忆化，Edge Relation-aware Memorization with INterval Decay），一个仅限 CPU、无嵌入（没有学习的节点或实体表示）的关系感知记忆化模型，它解决了所有三个局限，并在先前关系感知方法无法扩展的地方实现扩展：  

1. 1\. 一个可扩展的、仅限 CPU 的基准。EdgeReMIND 是第一个在仅 CPU（单个多核节点，无 GPU）上端到端运行于所有 TGB 2.0 数据集的关系感知时间链接预测模型，包括三个基于嵌入的方法无法访问的大型数据集（§3.6 (https://arxiv.org/html/2609.17916#S3.SS6)）。  
2. 2\. 一个数据校准的多时间尺度库。库的衰减率是从每个数据集自身的训练划分重现间隔中校准的、无量纲的。其零初始化列提供了一种安全属性，经每个种子验证：在间隔结构需要多时间尺度的地方，库有所帮助，而在其他地方则无害（§3.3 (https://arxiv.org/html/2609.17916#S3.SS3)）。  
3. 3\. 按关系学习作为主要驱动力。关系既调节记忆化特征，也为每个关系索引一个单独学习的权重向量。学习这些权重，而不是应用固定的启发式规则，是主要驱动力；因此 EdgeReMIND 在八个数据集中的六个上设置了最先进的测试 MRR（§3.4 (https://arxiv.org/html/2609.17916#S3.SS4), §4.2 (https://arxiv.org/html/2609.17916#S4.SS2), §4.3 (https://arxiv.org/html/2609.17916#S4.SS3)）。  
4. 4\. 跨组件的性能分解。按关系学习带来了最大的提升，在预定义的记忆化特征中，最近性是最广泛承担负荷的，而计数在某些 THGs 上变得至关重要（§4.4 (https://arxiv.org/html/2609.17916#S4.SS4)）。  

## 2 相关工作  
##### 记忆化基准。EdgeReMIND 借鉴了 §1 (https://arxiv.org/html/2609.17916#S1) 中介绍的三类基于记忆化的工作。EdgeBank[16 (https://arxiv.org/html/2609.17916#bib.bib2)] 为 EdgeReMIND 扩展提供了基础：其成对的“之前见过”规则是源-目标重现关系的非特定关系版本，EdgeReMIND 基于此并将其扩展到特定关系重现和多尺度最近性。RecB[5 (https://arxiv.org/html/2609.17916#bib.bib5)] 是另一种类似方法，它是唯一一个既按关系又对数据进行拟合的方法；决定性的区别在于*如何*拟合。RecB 通过验证网格搜索为每个关系选择两个重现参数（一个单一衰减率和严格与宽松的混合权重）。EdgeReMIND 通过梯度下降学习每个关系完整的 15 维权重向量（§B.3 (https://arxiv.org/html/2609.17916#A2.SS3)）。更高维度的加权赋予了 EdgeReMIND 额外的灵活性：对更广泛特征集的梯度学习让每个关系找到自己的计数、最近性和时间尺度信号之间的平衡，一旦拟合超越两个参数，这种平衡就变得可表达。RecB 还固定了单一的衰减时间尺度，而 EdgeReMIND 提供了一个校准的多时间尺度库。Base3[9 (https://arxiv.org/html/2609.17916#bib.bib10)] 最接近 EdgeReMIND 的基础部分，它在原始 TGB[6 (https://arxiv.org/html/2609.17916#bib.bib3)] 的单关系数据集上将几种启发式方法融合到一个无需训练的分数中，并使用固定的插值权重。EdgeReMIND 保留了融合启发式方法的理念，但针对多关系设置，用按关系学习的权重替换了 Base3 的全局数据集插值，并为每个范围增加了数据校准的多时间尺度库。  

##### 多时间尺度时间建模。多重衰减率在时间建模中有着悠久历史，其中指数混合捕捉了不同时间尺度上的效应。在神经时间图学习中，time2vec[7 (https://arxiv.org/html/2609.17916#bib.bib8)] 和用于 TGAT[19 (https://arxiv.org/html/2609.17916#bib.bib7)] 及 TGN[17 (https://arxiv.org/html/2609.17916#bib.bib6)] 的时间编码可以被视为学习多个时间-频率分量，尽管是作为深度网络的参数，而不是记忆化模型的特征。EdgeReMIND 的库在两个方面有所不同。它在一个基于记忆化特征的无嵌入模型内运行。其衰减率不是学习的，而是根据数据自身的重现间隔统计进行校准的（§B.2 (https://arxiv.org/html/2609.17916#A2.SS2)），使其成为以数据集原生时间戳单位表示的、可按范围解释的半衰期。  

##### 学习方法。主流方法在动态图上学习节点和边表示。它们包括嵌入轨迹方法如 JODIE[11 (https://arxiv.org/html/2609.17916#bib.bib1)]、基于内存的消息传递如 TGN[17 (https://arxiv.org/html/2609.17916#bib.bib6)] 及其边类型变体、Transformer 风格架构如 STHN[12 (https://arxiv.org/html/2609.17916#bib.bib14)]，以及自回归知识图谱模型如 RE-GCN[14 (https://arxiv.org/html/2609.17916#bib.bib11)] 和 CEN[13 (https://arxiv.org/html/2609.17916#bib.bib12)]。与这些方法一样，EdgeReMIND 从数据中学习其权重，而不是应用固定规则。与它们不同的是，它只学习一个线性层，每个关系 15 个权重，应用于预定义的记忆化特征，而不是表示。  

## 3 方法  
EdgeReMIND 使用记忆化特征的线性函数对每个候选目标进行评分，每个关系使用一个权重向量。它在三个范围内提取六个基础计数和最近性特征（*基础提取*），使用校准的多时间尺度库增强最近信号（*库校准*）以形成固定的 15 维向量，并通过梯度下降学习按关系权重（*按关系学习*）。图1 (https://arxiv.org/html/2609.17916#S3.F1) 总结了这三个阶段，下面的子章节将依次详细说明每个阶段。附录 B (https://arxiv.org/html/2609.17916#A2) 扩展了校准和按关系权重阶段，并给出了完整的每个数据集的量，附录 B.1 (https://arxiv.org/html/2609.17916#A2.SS1) 给出了完整的伪代码：基础提取（算法1 (https://arxiv.org/html/2609.17916#alg1)）、库校准（算法2 (https://arxiv.org/html/2609.17916#alg2)）和按关系学习（算法3 (https://arxiv.org/html/2609.17916#alg3)）。  

训练流 (s, r, d, t) (s, r, d, t) 基础提取 6 个基础特征，t'_i }。G_{X}=\{\,t_{i+1}-t_{i}\;:\;\text{事件 }i,i+1\text{ 共享相同的 }X\text{-键},\;t_{i+1}>t_{i}\,\}。 (3) 三个半衰期在范围内围绕中位数间隔 m_X=median(G_X) m_{X}=\operatorname{median}(G_{X}) 几何放置： h^{geo}_{X,j}=m_X⋅γ^{c_j}, c_j=j-\frac{n+1}{2}, j=1,...,n, (4) 其中 γ 是几何间距因子，居中指数 c_j 关于零对称，因此中间列恰好锚定在中位数上。部署的配置使用 n=3 和 γ=2（敏感性分析见附录 D (https://arxiv.org/html/2609.17916#A4)），给出的间距为 h^{geo}_{X}=\{m_X/2,m_X,2m_X\}。相应的衰减率为 λ_{X,j}=\ln 2/h_{X,j}，库添加九个有界特征： φ^{bank}_{X,j}=1_{X\text{-键}(c)\in H_t}⋅e^{-λ_{X,j}(t−t^{⋆}_X)}, X∈\{srd,rd,d\}, j∈\{1,2,3\}。 (5) 间隔→中位数 m 训练划分，自身单位 半衰期 {m/2,m,2m} {m/2,m,2m} 总是不同 衰减列 e^{-\frac{\ln 2}{h}(t−t^{⋆})}∈[0,1] 权重决定 ×3 范围 =9 列  

图2：一个范围的库校准：三个半衰期围绕中位数间隔几何放置，对三个范围重复以给出九个库列。每个库特征重用其基础对应项的最后看到的时间戳 t^{⋆}_X，仅衰减率不同。  

##### 中位数锚定和间距因子。锚定在中位数上而非固定的绝对时间尺度是使校准无量纲的原因。因为中位数间隔 m_X 以数据集自身的时间戳单位表示，所以间距 {m_X/2,m_X,2m_X} 无需每数据集常数即可跟踪数据的重现规模，在秒级事件流上产生从分钟到天的半衰期，在年度时间戳图上产生年级别的半衰期。间距因子 γ 设置了这个跨度的宽度。在 γ=1 时，三列合并为一列；部署的 γ=2 将它们分得足够开，以捕捉范围内不同的快速和慢速重现关系。这为按关系学习器提供了独立的短、中、长时间尺度列，而不是单一的重缩放衰减。间距因子 γ 和时间尺度数量 n 是唯一手工设置的超参数，在所有八个数据集上固定；校准仅使用训练划分。该机制如图2 (https://arxiv.org/html/2609.17916#S3.F2) 所示；其每个数据集的半衰期和实证效果在 §4.4 (https://arxiv.org/html/2609.17916#S4.SS4) 和附录 B.2 (https://arxiv.org/html/2609.17916#A2.SS2) 中报告。  

表 1：完整的 15 维候选特征向量 φ(s,r,c,t)，用于查询 (s,r,t) 和候选目标 c。范围：srd=(s,r,c), rd=(⋅,r,c), sd=(s,⋅,c), d=(⋅,⋅,c)；t^{⋆}_X 是范围 X 最后一次匹配的时间，1_X 是它曾经匹配的指示符（否则特征为 0）。计数无界；所有最近性和库特征位于 [0,1]。基础最近性（φ4–φ6）使用单一固定衰减率 λ；每个库速率是 λ_{X,j}=\ln 2/h_{X,j}，其中 h_{X,j}∈\{m_X/2,m_X,2m_X\}（§3.3 (https://arxiv.org/html/2609.17916#S3.SS3)）。  
索引 范围 类型 定义 含义  
φ1 srd count |{(s,r,c)∈H_t}| 精确三元组重现  
φ2 rd count |{(⋅,r,c)∈H_t}| 关系-目标流行度  
φ3 sd count |{(s,⋅,c)∈H_t}| 源-目标亲和度  
φ4 srd recency 1_{srd}e^{-λ(t−t^{⋆}_{srd})} 精确三元组最近性（固定速率）  
φ5 rd recency 1_{rd}e^{-λ(t−t^{⋆}_{rd})} 关系-目标最近性（固定速率）  
φ6 d recency 1_{d}e^{-λ_d(t−t^{⋆}_d)} 目标最近性（固定速率）  
φ^{bank}_{srd,j} srd bank 1_{srd}e^{-λ_{srd,j}(t−t^{⋆}_{srd})} 精确三元组最近性（三个校准半衰期）