HOT: Higher-Order Dynamic Graph Representation Learning with Efficient Transformers
HOT融合二阶邻域与Block-Recurrent Transformer，在MOOC上较DyGFormer准确率高9%。
核心发现
方法论
HOT面向连续时间动态图，将节点u、v历史上的1-hop与2-hop交互编码为Transformer输入。模型用TGAT时间编码、邻居类型独热编码和共享邻居计数表示三角形等高阶结构；随后通过patching与线性alignment压缩序列，并采用Block-Recurrent Transformer（BRT）分块注意力和递归状态处理长历史，最后平均池化并解码链路概率。
关键结果
- 在MOOC数据集上，HOT相对DyGFormer、TGN和GraphMixer的准确率分别提高9%、7%和15%，并在AP、AUC及RNES、HNES、INES采样设置中保持领先。
- 在LastFM上，加入2-hop信息通常提升预测；在CanParl上，1-hop结果已较高，额外高阶信息收益有限，较大的s2甚至可能引入噪声。
- 复杂度方面，邻域构建为O(sΔlogΔ)，BRT注意力约为O(sdB/P)，而普通Transformer约为Θ(s²d/P)，体现了长历史下的显著内存优势。
研究意义
论文将静态图学习中常见的高阶结构正式引入动态图链路预测，回应了现有方法只把单次更新视为token、难以利用三角形和多跳关系的问题。它同时处理准确率与资源约束，使动态图模型更接近在线推荐、社交网络和交易分析等真实场景。结果说明，时间维度中的共同邻居及其重复出现模式具有独立预测价值。
技术贡献
核心贡献包括：以Su、Sv保存截断历史邻域；以Cu统计节点在自身及对方邻域中的出现次数，并通过MLP映射为Xu,C、Xv,C；利用水平拼接避免将u、v两侧事件错误解释为严格先后顺序；以BRT局部注意力和递归状态替代全局二次注意力。论文还给出O(sΔlogΔ)邻域预处理与近线性BRT成本分析。
新颖性
相较DyGFormer仅将动态更新作为序列token，HOT把k-hop邻居和包含查询节点对的子图直接注入注意力输入。其新意不只是增加邻居，而是把高阶结构、时间编码、patching与层次化Transformer联合设计，在准确率和内存之间取得折中。
局限性
- 实验主要聚焦1-hop和2-hop邻域及三角形相关结构；更高阶结构会使|Su|按∏si增长，预处理、存储和噪声均快速增加。
- 论文报告相对提升与趋势，但给定文本未提供图2中各数据集的完整AP/AUC数值，因此无法全面复核统计显著性与方差。
未来方向
未来可扩展到任意k-hop、周期组合及其他动态图任务，如动态节点分类；还可研究自适应选择s1、s2、patch大小P和块大小B，以按查询难度动态平衡噪声、延迟和内存，并结合更高效的递归并行机制。
AI 总览摘要
动态图持续产生边增删事件：社交网络、交易系统和交通网络都可能每秒处理海量更新。动态链路预测要根据时间t之前的历史，判断u与v是否将在t连接。传统TGN、GraphMixer和DyGFormer虽已利用记忆、邻居传播或Transformer，但通常把单次更新视为token，难以表达共同邻居、三角形及多跳关系；而直接加入这些信息又会显著拉长序列和扩大注意力矩阵。
HOT提出一种结合高阶图结构与高效Transformer的方案。它保留u、v最近的s1个一跳交互，并从这些邻居继续抽取最近的s2个二跳交互；用TGAT的可学习正弦时间编码描述事件距当前时刻的间隔，用独热向量区分一跳和二跳邻居。矩阵Cu统计共享邻居出现次数，经过MLP后形成高阶特征。patching把多个时间行合并，alignment降维，再由BRT在局部块内注意，并通过递归状态传递较早历史。
实验覆盖MOOC、LastFM和CanParl，比较TGN、CAWN、TCL、GraphMixer、DyGFormer及EdgeBank，并使用RNES、HNES、INES和AP/AUC。MOOC上HOT较DyGFormer、TGN、GraphMixer分别高9%、7%、15%；LastFM也受益于高阶邻居，而CanParl的额外信息收益较弱。BRT将注意力成本从约Θ(s²d/P)降至O(sdB/P)。因此，HOT展示了一个清晰方向：动态图预测不仅要记住“发生了什么”，还要理解事件之间形成的局部结构；但更高阶邻域选择、并行效率和统计稳健性仍待研究。
深度分析
研究背景
动态图用连续时间动态图（CTDG）表示为(G(0),T)，T包含带时间戳的节点、边和特征更新。早期DGRL使用Temporal Random Walk、序列模型、Memory Network和动态GNN；TGN、CAWN、TCL、GraphMixer及DyGFormer进一步提升性能。尤其DyGFormer把更新序列交给Transformer，但主要关注单次交互，未充分利用三角形和多跳邻域。
核心问题
给定t及历史事件，模型需判断边(u,v)是否在t出现，并支持transductive与inductive设置。难点在于动态图历史很长、事件不断变化，而高阶结构会成倍增加token数量；普通Transformer注意力为二次复杂度，迫使模型缩短历史，形成准确率与内存的冲突。
核心创新
HOT有三项核心创新：一是抽取1-hop/2-hop历史交互并编码高阶邻域；二是用Cu及MLP表示共享邻居，从而捕获时间三角形及最长2k+1的周期；三是以patching、alignment和水平拼接组织输入，再用BRT的局部注意力与递归状态保留长程信息。它区别于DyGFormer之处在于同时改变结构表示和注意力组织。
方法详解
- �� 对u、v分别保留最近s1个一跳交互，并从每个一跳邻居继续取s2个二跳交互，大小约为O(s1s2)。
- �� 构造Xu,N、Xu,E和Xu,T；时间编码为p^(1/dT)[cos(w1Δt′),sin(w1Δt′),…]。
- �� Cu两列分别统计邻居在Su中的出现次数及其在Sv中的出现次数，计算Xu,C=MLP0(Cu[:,0])+MLP1(Cu[:,1])。
- �� 每P行patch并映射至d维，水平拼接节点、边、时间和高阶特征；再拼接u、v两侧矩阵。
- �� BRT按块计算注意力，并用递归状态汇总先前块，平均池化后交给链路解码器。
实验设计
数据集为MOOC、LastFM和CanParl；基线包括TGN、CAWN、TCL、GraphMixer、DyGFormer和EdgeBank。指标为Average Precision与AUC。评估同时覆盖transductive/inductive设置及RNES、HNES、INES负采样。消融固定s1并改变s2，另分析BRT块大小B和patch大小P对注意力内存的影响。
结果分析
MOOC上HOT较DyGFormer、TGN和GraphMixer分别提升9%、7%和15%，并在多种负采样策略下领先。LastFM同样受益于高阶邻居；CanParl中1-hop已足够强，增大s2可能带来噪声。s2=1时模型可利用最长5节点周期。BRT的注意力成本约O(sdB/P)，普通Transformer为Θ(s²d/P)。
应用场景
在线商店可用HOT预测未来购买或共购边，提前做推荐和库存配置；社交平台可预测潜在关注关系或社区连接。部署前需保存带时间戳的交互、节点/边特征，并调节s1、s2、B、P以符合延迟和显存预算。交通、协作网络和实时风控也具有直接适用性。
局限与展望
高阶邻域越大，|Su|和预处理开销越高，复杂结构还可能引入噪声；BRT虽然节省内存，但小块会增加串行块数与延迟。实验重点是三数据集、1/2-hop和链路预测，尚不足以证明对超大规模工业图、删除事件或更高阶子图的普适性。后续应增加自适应采样、并行递归和更完整统计报告。
通俗解读 非专业人士也能看懂
把动态图想成一家不断接单的餐厅。每个顾客是一个人，每次点餐或一起用餐就是一条带时间的记录。普通方法只看顾客最近直接认识谁；HOT还会问：这两位顾客是否有共同朋友？共同朋友最近是否又和别人一起出现？这些关系像餐厅里反复出现的小团体，往往暗示两个人很快会一起下单。
HOT先保留每位顾客最近的一跳和二跳关系，再把“共同出现了几次”写进记录。它还给每条记录标上距离现在多久，避免把昨天的订单和一年前的订单混为一谈。随后，它把几条相近记录打包，像把一天的订单装进一个盒子；每个盒子只和附近盒子交流，同时保留前面盒子的摘要。这样既能看长时间历史，又不用一次打开全部订单。
实验表明，在MOOC数据上，HOT比DyGFormer高9%，比TGN高7%，比GraphMixer高15%。简单说，它不只记住“谁和谁联系过”，还理解“他们是否通过共同关系逐渐靠近”。不过，如果把太多远处关系也塞进来，信息可能变成噪声，而且机器仍需更多内存和预处理时间。
简单解释 像给14岁少年讲一样
想象你在学校里预测下周谁会成为新朋友。最简单的办法是看两个人以前有没有直接聊天；但更聪明的办法是看他们有没有共同好友、共同参加社团，或者朋友的朋友是否经常一起出现。HOT就是用这种“关系网里的线索”预测两个同学未来会不会连上。
它先查看两个同学最近的一层和两层关系，还记录每件事发生在多久以前。如果小明和小红都经常和小刚互动，这就像一个三角形信号，说明小明和小红可能很快认识。模型会把这些记录整理成小块，再让每个小块参考附近信息和更早内容的摘要，就像复习时看本章重点，而不是把整本书每一页同时摊开。
为什么这样做有用？因为社交关系不是一条条孤立消息，而是会组成小圈子。MOOC实验中，HOT比DyGFormer高9%，比TGN高7%，比GraphMixer高15%。不过，朋友的朋友太多也会让判断混乱；所以模型要控制查看多少人、每块多大。它真正厉害的地方，是在“看得更广”和“算得动”之间找到了平衡！
术语表
Continuous-Time Dynamic Graph（连续时间动态图）
图的节点、边和特征会在带时间戳的事件中持续变化。它不同于只记录固定快照的静态图。
HOT在CTDG上根据t之前的事件预测t时刻的边。
Dynamic Link Prediction（动态图链路预测）
利用历史交互判断未来某对节点是否会产生边。任务可分为transductive和inductive。
这是HOT及TGN、DyGFormer等模型的主要评测任务。
Higher-Order Structure（高阶结构）
超越单条边的关系模式，如共同邻居、三角形和多跳邻域。它能表达节点间间接依赖。
HOT重点使用1-hop、2-hop邻域及由此形成的周期。
TGAT Time Encoding（TGAT时间编码）
用可学习频率的正弦、余弦函数表示事件距当前时刻的时间间隔。该表示能处理连续时间差异。
HOT将其应用于每个历史交互。
Block-Recurrent Transformer（块递归Transformer）
把长序列划分为块，在块内局部注意，并用递归状态传递早期信息。其注意力避免完整序列的二次矩阵。
BRT是HOT降低高阶历史内存开销的核心组件。
Patching and Alignment（分块与对齐）
Patching合并相邻时间行，Alignment把特征投影到统一维度。两者共同缩短序列并控制输入宽度。
HOT在进入BRT前处理节点、边、时间和高阶矩阵。
开放问题 这项研究留下的未解疑问
- 1 更高阶k-hop结构何时带来真实收益、何时转化为噪声仍不清楚；需要结构感知的自适应采样和跨数据集统计验证。
- 2 BRT的递归状态适合超大规模动态图，但块间并行受限；如何在不损失长程信息的情况下实现低延迟并行仍是开放问题。
- 3 论文未在给定文本中报告完整AP/AUC数值和方差，因此不同数据集上的显著性、鲁棒性及工业部署收益仍需独立复现。
应用场景
近期应用
实时推荐与交易预测
电商可将用户、商品和交易作为动态图，使用HOT预测未来购买或共购关系。系统需提供时间戳、节点/边特征，并通过s1、s2、B和P控制显存与响应时间。
社交关系与内容传播
社交平台可利用共同关注、群组和历史互动预测潜在连接或传播路径。HOT尤其适合关系快速变化且三角形结构具有信号价值的网络，但需处理隐私和噪声。
远期愿景
统一的动态图智能引擎
HOT可扩展到动态节点分类及其他动态图表示学习任务，形成兼顾高阶结构和长历史的实时引擎。关键障碍是更高阶结构的成本、递归并行化和跨领域泛化。
原文摘要
Many graph representation learning (GRL) problems are dynamic, with millions of edges added or removed per second. A fundamental workload in this setting is dynamic link prediction: using a history of graph updates to predict whether a given pair of vertices will become connected. Recent schemes for link prediction in such dynamic settings employ Transformers, modeling individual graph updates as single tokens. In this work, we propose HOT: a model that enhances this line of works by harnessing higher-order (HO) graph structures; specifically, k-hop neighbors and more general subgraphs containing a given pair of vertices. Harnessing such HO structures by encoding them into the attention matrix of the underlying Transformer results in higher accuracy of link prediction outcomes, but at the expense of increased memory pressure. To alleviate this, we resort to a recent class of schemes that impose hierarchy on the attention matrix, significantly reducing memory footprint. The final design offers a sweetspot between high accuracy and low memory utilization. HOT outperforms other dynamic GRL schemes, for example achieving 9%, 7%, and 15% higher accuracy than - respectively - DyGFormer, TGN, and GraphMixer, for the MOOC dataset. Our design can be seamlessly extended towards other dynamic GRL workloads.