2025-11-14T22:58:11.335175

Revisiting Node Affinity Prediction in Temporal Graphs

Mantri, Feldman, Eliasof et al.

Node affinity prediction is a common task that is widely used in temporal graph learning with applications in social and financial networks, recommender systems, and more. Recent works have addressed this task by adapting state-of-the-art dynamic link property prediction models to node affinity prediction. However, simple heuristics, such as Persistent Forecast or Moving Average, outperform these models. In this work, we analyze the challenges in training current Temporal Graph Neural Networks for node affinity prediction and suggest appropriate solutions. Combining the solutions, we develop NAViS - Node Affinity prediction model using Virtual State, by exploiting the equivalence between heuristics and state space models. While promising, training NAViS is non-trivial. Therefore, we further introduce a novel loss function for node affinity prediction. We evaluate NAViS on TGB and show that it outperforms the state-of-the-art, including heuristics. Our source code is available at https://github.com/orfeld415/NAVIS

academic

Revisiting Node Affinity Prediction in Temporal Graphs

基本信息

论文ID: 2510.06940
标题: Revisiting Node Affinity Prediction in Temporal Graphs
作者: Krishna Sri Ipsit Mantri, Or Feldman, Moshe Eliasof, Chaim Baskin
分类: cs.LG (Machine Learning)
发表状态: Preprint. Under review
论文链接: https://arxiv.org/abs/2510.06940
代码链接: https://github.com/orfeld415/NAVIS

摘要

节点亲和性预测是时序图学习中的一项重要任务，广泛应用于社交网络、金融网络和推荐系统等领域。尽管最近的研究通过适配最先进的动态链接预测模型来解决节点亲和性预测任务，但简单的启发式方法（如持续预测和移动平均）却能超越这些复杂模型。本文分析了当前时序图神经网络在节点亲和性预测任务中的训练挑战，并提出了相应的解决方案。结合这些解决方案，作者开发了NAVIS（Node Affinity prediction model using Virtual State），通过利用启发式方法与状态空间模型的等价性来实现节点亲和性预测。

研究背景与动机

问题定义

节点亲和性预测旨在预测未来时刻某个节点与其他所有节点的交互强度，这与传统的链接预测任务不同。链接预测关注特定边是否会出现，而亲和性预测需要对所有潜在邻居进行完整排序，这使得任务更具挑战性但也更贴近实际应用需求。

核心问题

性能悖论：复杂的时序图神经网络（TGNNs）在节点亲和性预测任务上表现不如简单的启发式方法
表达能力限制：现有TGNNs无法表示简单的移动平均等基础操作
损失函数不匹配：交叉熵损失与排序性质的亲和性任务不匹配
信息利用不充分：TGNNs未能充分利用全局时序动态和长期依赖信息

研究动机

作者通过理论分析发现，简单启发式方法实际上是线性状态空间模型（SSMs）的特例，这为设计更强大的TGNN架构提供了理论基础。

核心贡献

理论贡献：证明了简单启发式方法是线性SSMs的特例，并基于此连接设计了能够泛化启发式方法的TGNN架构
架构创新：提出NAVIS模型，结合虚拟全局状态和线性状态空间机制，有效解决节点亲和性预测问题
损失函数改进：分析了交叉熵损失在亲和性预测中的不足，提出了基于排序的Lambda损失替代方案
实验验证：在TGB基准和多个数据集上验证了方法的有效性，consistently超越现有方法和启发式基线

方法详解

任务定义

给定连续时间动态图（CTDG）： $G_t = \{(u_j, v_j, \tau_j, w_j)\}_{j=1}^{J(t)}$

对于查询节点 $u \in V$ 和未来时刻 $t^+ > t$ ，目标是预测亲和性分数向量： $s = F_\theta(u, G_t, t^+) \in \mathbb{R}^{|V|}$

理论基础

定理1（线性SSMs泛化基础启发式）：设 $H$ 为基础启发式集合（PF, SMA, EMA）， $F_{\text{lin-SSM}}$ 为线性SSM可实现的映射集合，则： $H \subsetneq F_{\text{lin-SSM}}$

定理2（RNN/LSTM/GRU的表达限制）：标准的RNN、LSTM或GRU单元无法表示最基本的持续预测（PF）启发式，即对于所有输入序列，不存在参数使得 $h_i = x_i$ 。

NAVIS模型架构

NAVIS采用线性状态空间机制维护每个节点的状态 $h \in \mathbb{R}^d$ 和虚拟全局状态 $g \in \mathbb{R}^d$ ：

zh = σ(Wxh*x + Whh*hi-1 + bh)
hi = zh ⊙ hi-1 + (1-zh) ⊙ x
zs = σ(Wxs*x + Whs*hi + Wgs*g + bs)  
s = zs ⊙ hi + (1-zs) ⊙ x

其中：

$x$ ：前一亲和性向量
$h_{i-1}, h_i$ ：前一状态和更新状态
$g$ ：虚拟全局向量
$s$ ：预测亲和性向量
$z_h, z_s$ ：自适应门控机制

关键设计特点

线性更新机制：保持与EMA的概念相似性，但允许运行时自适应调整
虚拟全局状态：通过维护最近亲和性向量缓冲区捕获全局趋势
兼容t-Batch机制：不依赖邻居隐状态，支持高效批处理
可扩展性：通过稀疏化亲和性预测管道适应大规模图

损失函数设计

问题分析： 定理3（交叉熵对排序的次优性）：存在无穷多个三元组 $(y, s_1, s_2)$ ，其中 $\text{rank}(s_1) = \text{rank}(y)$ 且 $\text{rank}(s_2) \neq \text{rank}(y)$ ，但 $\ell_{CE}(s_1, y) > \ell_{CE}(s_2, y)$ 。

解决方案：采用Lambda损失： $\ell_{\text{Lambda}}(s,y) = \sum_{y_i > y_j} \log_2\left(\frac{1}{1 + e^{-\sigma(s_{\pi_i} - s_{\pi_j})}}\right) \delta_{ij} |A_{\pi_i} - A_{\pi_j}|$