Revisting Node Affinity Prediction In Temporal Graphs
Authors: Or Feldman
Krishna Sri Ipsit Mantri
Moshe Eliasof
Chaim Baskin
Venue: ICLR 2026 Poster (2026)
Keywords: Node affinity
Temporal graph networks
dynamic graphs
graph neural netowrks
Primary area: learning on graphs and other geometries & topologies
TL;DR: This paper revisits node affinity prediction on temporal graphs and explains why simple heuristics often beat modern TGNNs.

Abstract: 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.

Published as a conference paper at ICLR 2026
REVISITING NODE AFFINITY PREDICTION IN TEMPORAL GRAPHS
Or Feldman' Krishna Sri Ipsit Mantri Moshe Eliasof Chaim Baskin Been-Gurion University of the Negev, Israel Purdue University, USA
3 Universstyy of Cambridge, UK
ABSTRACT
Node affinity prediction 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-ar dynamic link property prediction models 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 dedicated 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 htttts:: /ttp//ggttttttttt//// htt.a//b...cooofffeeaa/////////
INTRODUCTION
Temporal graphs provide natural way represent evolving interactions in systems such trade networks, recommender systems, social platforms, and financial transactions (Kumar et al. 2019 Sheuty & Adibi 2004 Huang al. 2023). A central challenge in this setting is future node affinity prediction: forecasting how strongly node will interact with other nodes at a future time. This differs from future link prediction, which instead asks whether a particular edge will appear. In contrast, affinity prediction requires producing full ranking over potential neighbors, making it more demanding but also more relevant to many real-world applications (MacDonald et al., 2015)
Mertin-Mahieux et al. 2011 Nadiri & Takes
2022 Shamsi et al. 2022).
In the context of link-level prediction, recent progress in Temporal Graph Neural Networks (TGNNs), including TGN (Rossi et al. 2020). TGAT (Xu et al.) (020), DyGFormer (Yu et al.) (023), and GraphMixer (Cong et al. 2023), has improved state-of-the on local neighborhood sampling and nonlinear message- taaggg---psing.... which are effective for future link prediction task. However, when applied to node affinity prediction, is evident that they perform worse than simple heuristics such as Persistent Forecast and Moving Average (Huang al. 2023). This gap suggests that current TGNNs designs do not align well with the inductive biases required for affinity prediction.
performance. These methods rely
Accordingly, this paper aims to answer the following questions: why do heuristics outperform more sophisticated TGNNs for future node affinity prediction? and can we push TGNNs to do better? We argue that the advantage arises from confluence of factors and identify several contributing issues that collectively explain this phenomenon, including: (i) Expressivity. Existing TGNNs cannot represent a simple Moving Average of past affinities, because their nonlinear updates and reliance on sampled neighborhoods prevent them from maintaining the required linear memory. (ii) Loss mismatch. Cross-entropy, commonly used as a loss function for link prediction, is not well-aligned with the
" "Equal contribution.
I Work done while interning at the INSIGHT Lab, Ben-Gurion University of the Negev.
I Equal supervision.

---

Published as a conference paper at ICLR 2026
ranking nature of affinity tasks. (iii) Global temporal dynamics. Affinities often depend shared network-wide trends (c.g,, regime shifts), which local sampling does not capture. (iv) Information loss. TGNNs are broadly categorized into memory -eeery-based and non-memory meemory-based architectures. Memory-based models (e.g., TGN (Rossi et al., 2020) and DyRep (Trivedi et al. 2019)) maintain per-node states; however, batch processing of events can cause short-term updates within batch be missed (Feldman & Baskin, (024). In contrast, non-memory- based methods recompute embeddings from scratch at prediction time and maintain no states, making them prone to overlooking earlier updates in the evolving graph (Cong et al., 2023 Yu et al., 2023
These observations guide and motivate our work. Our key idea is that heuristics like persistent Forecast and Moving Average are not arbitrary fixes, but rather special cases of linear state space models (SSMs) (Gu et al. 2021 2022 Ceni et al., 2025 [Fliasof et al. 2025). which naturally provide memory and long-range temporal dependencies. By embedding the structure of SSMs into learnable TGNN, we can retain the robustness of heuristics while extending their expressivity.
Building this idea, we introduce NAVIS (Node Affinity prediction with Virtual State). NAVIS maintains both per-node state and a virtual global state that co-evolve with the dynamic graph structure, thereby providing principled memory mechanism suitable for the requirements of future node affinity prediction. Additionally, to address the loss mismatch, we propose a rank-based objective that is better suited to ordinal affinity outputs. Importantly, do not claim to have solved the problem entirely: the approach still inherits limitations, for example, in modeling complex multi-hop dependencies. Nonetheless, results indicate meaningful progress that can shape the future of node affinity prediction.
To illustrate the existing challenges and the effectiveness of NAVIS, we include synthetic node- affinity experiment in Figure 1 In this controlled setting, node affinities depend on a hidden global process with nonlinear structure. Although simple heuristics outperform state-of-the-an TGNNs, since they capture only per-node history, as TGNNs, they fail to recover the shared latent space. By maintaining virtual global state, NAVIS achieves the lowest error. Although simplified, this example highlights the importance of global temporal dynamics and motivates one of the design choices in NAVIS. We provide the full experiment details in Appendix C
Our contributions.
We theoretically show that simple heuristics are special cases of linear SSMs, and use this connection to design a TGNN architecture that generalizes them, making it more expressive.
2. We analyze why cross-entropy loss is suboptimal for affinity prediction, and develop a rank-based alternative that improves optimization and aligns with evaluation metrics.
3. We provide extensive experiments on the Temporal Graph Benchmark (TGB) and additional datasets, demonstrating consistent improvements over both heuristics and prior TGNNs. The significance of our experiments is that they validate the importance of aligning model inductive biases and training objectives with the task.
BACKGROUND
In this section, we provide essential information related our work, from basic notations and definitions, to simple future node affinity prediction baselines, which we generalize in NAVIS.
Notations and Definitions. We consider a continuous-fime dynamic graph (CTDG) as stream of timestamped interactions between ordered node pairs drawn from the node set V = (l....,n) The CTDG observed up time t is:
G. {(uj, Uj Ty. wy) }5=1:
where Uy, M4 E V denote source and target nodes, Tj IR. is the interaction time, wy E RR is its weight and (t) is the number of interactions occurred up to time t. The future node affinity prediction problem seeks, for query node V and future time ++ > t, estimate the node's 's affinity to every other node e E V \ {u} conditioned on G. A parameterized model F9 produces the predicted affinity scores vector
Fo(u, Gr, (+) M
(2)
2

---

Published as a conference paper at ICLR 2026
Mean Squared Error
0.025
70
Mean Rank
0.015
30
0.005
PF
SMA
AR(1)
EMA
Ours
20
PF
SMA
AR(1)
EMA
Ours
Method
Method
Figure I: Synthetic node aflinity experiment. Node affinities depend on a global, regime-switching latent g(t) with nonlinear component g(t)² and node-specific phases. Baselines relying only on per-node histories (PERSISTENT FORECAST, SMA, EMA) or a local AR(1) SSM cannot recover the shared latent space, leading to higher error. OURS, indicating NAVIS, maintains virtual global state, achieves the lowest error on both metrics. In Appendix C we provide the full experiment details and baseline descriptions.
Given the ground truth affinities y realized tt, we learn 0 by minimizing task-specific loss
min Σ e (F, NEV
Historical Average. A simple interaction-level baseline is the historical average, which estimates each source-destination affinity by the mean weight of all past interactions observed prior to [+:
((v)
1
Σ
Wj.
#u, U (1.
Here #u,e denotes the number of observed (u, interactions to time t.
Moving Average and State Space Models. Allowing the tested models to use previous ground truth affinity vectors at inference, instead of the full fine-grained CTDG, creates additional schemes to most basic one that
predict the future affinity vectors. The Persistent Forecust (PF) heuristic utilizes previous affinity vectors. PF outputs the previous affinity vector as future prediction, i.e.:
==x
where x is the previous (most recent) ground truth affinity vector. Another natural vector-level heuristic for future node affinity prediction is the Exponential Moving Average (EMA), which maintains an estimate of a node's ' affinity vector by exponentially weighting recent affinity vectors:
s = h, = oh; + (1 x:
here, a [0, 1] is the decay parameter and h, h are hidden states. Note that PF is a specific case of EMA where O.
An alternative is the Simple Moving Average (SMA) with window size w, which averages over finite window. Its recursive form is:
x.
EMA and SMA use infinite geometric decay, retaining long but diminishing memory. Although these filters can capture long-term dynamies, they are limited fixed, hand-crafted memory kernels. To move beyond such ad-hoe designs, we can view EMA through the lens of latent dynamical systems.
Departing from simple averaging approaches, State Space Models (SSMs) provide principled framework to model temporal sequences via hidden state evolution and observation processes (Hamilton, 1994 Aoki 2013). A discrete linear SSM is defined as:
h; Ah; + Bx,
(8)
s Ch, Dx,
(9)
Where A, B, C. D are learable matrices.
3

---

Published as a conference paper at ICLR 2026
NAVIS
g
Linear
S
Linear
ADD
Linear
h
Linear
h
ADD
Linear
1
Figure 2: NAVIS architecture for node affinity prediction. The current and previous affinity vector are projected through linear transformations and aggregated into a new state. A lightweight gated mechanism ensures persistent, linear outptt. The predicted affinity vector then produced directly from this state based on the virtual global state.
Beyond Moving Average. We show that vector-level heuristics are instances of SSMs. This reveals clear hierarchy in model expressiveness, where SSMs are more expressive, generalizing Moving Average.
Theorem 1 (Linear SSMs generalize basic heuristics). Let H be the set basic heuristics (PE, SMA, EMAJ, Fin-SSM be the set of maps realizable by the linear SSM in Equation & and Equation 9 Then, the following strict inclusion holds:
H. S Fin.SSM.
(10)
Proof. H. C. Fii--SM- First, we show containment (9). Each heuristic corresponds to a specific choice of (A, B, D)
EMA(a): A al, B (1 a. C I, D = 0. --1 w
SMA(w): A
I, B 1T, C I, D,D
PF: A = 0, B = 0, C D
Next, we show the inclusion is strict (g). Consider set of 2 2 SSM matrices with A
diag(a1, dr2,, B diag(1 01, 022), C= I,D = 0 where an * az-- These models' weights on past inputs cause each entry in the affinity vector to decay different rate. This behavior cannot be replicated by the single decay of an EMA. Thus, Flin.SSM H + Ø.
Implications. This hierarchy that stems from Theorem reveals the potential of SSMs: although simple heuristics outperform any tfate-of-the-ar TGNN, carefully designed SSM-based TGNN can potentially outperform these heuristics because generalizes them.
METHOD
This section contains our key contributions and is organized follows: in Section 3.1 we detail factors that hinder TGNNs performance for future node affinity prediction. Motivated by these
findings, Section 3.2 we introduce our model. In Section 3.3 we detail how to train it effectively.
WHAT HINDERS TGNNS IN FUTURE NODE AFFINITY PREDICTION
common heuristics like PF and EMA special cases of SSMs. This advantage of SSMs over heuristics is achieved due to the fact that SSMs can output a linear combination of the previous affinity vector and the previous predicted affinity vector. We now discuss
As established in Section 2
4

---

Published as a conference paper at ICLR 2026
another important theoretical direction: RNN (Elman 1990), LSTM (Hochreiter & Schmidhuber 1997) or GRU (Cho et al. 2014) cells that are commonly used in popular memory- TGNNs
(Trivedi et al. 20191 al., 2020; Tjandra al. 2024) cannot express the most basic heuristic of PF, thereby hindering memory- based TGNNS performance.
Theorem 2. Let (hs) be the hidden states generated by a single standard RNN cell, LSTM cell, or GRU cell driven by inputs {24)22 _ [Rd. There do not exist parameters of these cells such that, for all t and all input sequences, fi; = (PF).
Proof. We assume the standard elementwise nonlinearities (u)) THe E (0, 1) and tanh(u) (-1,1). Below, we present the equations that define common recurrent models.
(RNN) h, 6(W, Wa + b),
tanh.
(11)
i; o (Wi[b:-1;x] + b,),
f = a (W, [1; by):
(LSTM) O o [. - bo):
gi = tanh (W [h,-1;x]] + by),
(12)
C f. c +1 0 ga.
h, o, O tanh(c.).
2, = [W + bz),
= oW, b,),
(GRU)
h: tanh (onh(W(r) 1; b),
(13)
h = (1 - (2,) 0 h + 2 0 h.
We show that no choice of parameters in RNN, LSTM or GRU yields the map h; = x,.
RNN: h = tanh (W,, W,x; + b) takes values in (-1,1)4, while the mapping x, r> h, is unbounded on Idd Hence, equality Vx, is impossible.
LSTM: h, @ tanb(c;) with o; (0, 1)d and tanh(c:) E (-1, implies h, E (-1, 1)², again contradicting the unbounded range h,,
GRU: Set h = Then h, 2, @ h with 2, E (0, 1)d and h, = tanh(-) (-1, hence h; () cannot equal x, for arbitrary E Rd.
Theorem 2 has profound implications: any memory-based TGNN that applies standard memory cells cannot represent even the simplest heuristic - Persistent Forecasting (PF), which have been proven empirically to perform exceptionally well on node affinity tasks. This theoretical result is at the underpinnings our work, and motivates us to generalize heuristics while remaining more expressive. Thus, design NAVIS simple learnable linear SSM. Tjandra al. (2024) showed that identifying the target node when updating the node state of the source node is a necessary property. Without this property, TGNNs cannot express the persistent forecast heuristic. In the proof of Theorem
2 we explicitly assume that the target node is identified via its corresponding index in the affinity vector of the source node. Hence, Theorem holds even when the target node is identified, revealing another necessary condition for expressing the persistent forecast heuristic.
Current TGNNs Underutilize Available Temporal Information
We argue that a major source of empirical underperformance in TGNNs is the systematic loss of temporal information. Memory- TGNNs often rely on batching for tractable runtimes; however, batching can obscure multiple interactions that affect the same node within a single batch window, thereby dropping intermediate state transitions (Feldman non-memory architectures, e.g., DyGFormer (Yu et al. (023). GraphMixer (Cong et al. (023), and DyGMamba (Ding et al., 2025), avoid within-batch omissions by maintaining a buffer of recent events and recomputing node embeddings on demand. To bound latency, these buffers are fixed in size; once filled, the oldest events are evicted, discarding potentially informative long-term interaction events. This hard truncation differs from EMA. where the influence of older events decays but remains non-zero, allowing previous interaction events to shape future affinity predictions. further, underexploited source of information is the evolving global graph state. Memory-basee TGNNs
Baskin 2024). In contrast,
5

---

Published as a conference paper at ICLR 2026
typically use few message-passing layers per state update. limiting the incorporation of broader context (Rossi et al. 2020), while non non-nonnenn memory methods commonly restrict buffered events to 1-hop neighborhoods. Notably, also recent sophisticated state-of-thh-aa TGNNs do not utilize the full global state (Lu et al. 2024 Gravina et al. 2024). We leverage these observations to design a TGNN that preserves fine-gres one-grained temporal transitions, retains long-term interaction events, and integrates global graph context to maximize the use of available information to give an accurate prediction for future node affinity.
3.2 NAVIS: NODE AFFINITY PREDICTION WITH A GLOBAL VIRTUAL STATE
propose NAVIS a node-affinity prediction model that utilizes a linear state-space mechanism to maintain a state h E Rd for each node, and a virtual global state g E F where d | denotes the affinity-space dimension. Transitions are computed by a learnable linear SSM that enforces the output to be a linear combination of the inputs, akin to an EMA, but with flexibility allow the coefficient a to be computed at runtime from the current events rather than being fixed. Concretely, we define NAVIS as the following sequence of update steps:
Motivated by Section 3.1
Zy σ (W +
bn),
h = Zn. @ h + (1 = x, Z. ( Wh,h; Wg.g + bz),
(14)
s = 2, @ h; (1-z.) z.) + x,
where x, h g. g.s E Fd are the previous affinity vector, previous node state, updated node state, virtual global vector, and predicted affinity vector, respectively. The parameters Wah, WAA, Wa,, WA,, Wg E RRidd are learnable weights, bn, b, E k are learnable biases, and is the sigmoid function, forcing Zn, 2, to be in [0, 1J. maintain conceptual similarity with a in Equation 66). In Figure 2 we provide detailed scheme of NAVIS.
We compute the virtual global vector g by maintaining a buffer of the most recent previous affinity vectors, globally. Then, the virtual global vector is computed by performing aggregation over all the vectors in the buffer. The goal of the global vector is detect a global trend (e.g. new song or a new TV series that is globally streamed) before we are queried about a specific node. In practice, aggregating the buffer with the most recent vector selection is efficient and empirically effective, as we show later in Section
4
Handling a full CTDG. When a previous affinity vector is unavailable and predictions must rely solely on interaction weights of the CTDG, we estimate the previous affinity vector of x, via x. We initialize x = 0 and, upon each weighted interaction between source node u and destination node add the interaction weight to the v-th entry of &. When & is required for prediction, we normalize it by dividing by the sum of its entries. After computing the future affinity vector of u we again set & O.
Key Properties of NAVIS. We note that NAVIS generalizes EMA and other heuristics by allowing the gates n and n, to adapt new information, in contrast fixed a. Large gate values enable the model to retain long-term information when beneficial. Notably, NAVIS does not rely on neighbors' hidden states, unlike other memory-based TGNNs, and therefore is compatible with the t-Batch mechanism (Kumar et al. 2019), enabling efficient batching without missing updates. In addition, we show in Appendix that incorporating global information via g can improve the accuracy of the predicted affinity vector when global trends affect the nodes' affinities.
NAVIS for large-scale graphs. For graphs with N nodes, the number of learnable parameters in NAVIS scales as O(N). which can be prohibitive for graphs with millions of nodes. To make NAVIS practical at this scale, we introduce sparsified affinity prediction pipeline. Specifically, for each node we retain only the entries corresponding to candidate target nodes. In real-world settings, such as streaming services where users and movies are nodes and interactions are edges, we are interested in each user's affinity to movies rather than to other users. In practice, this substantially reduces the parameter count of NAVIS. For example, on the tgbn-token dataset (Shamsi et al. 2022), which records token interactions, NAVIS requires about (5,000) parameters. while the graph contains over (60,000) nodes. We further provide a detailed empirical runtime and memory analysis of NAVIS in Appendix G

---

Published as a conference paper at ICLR 2026
3.3 LEARNING WITH RANK-BASED LOSS: WHY
FAILS
With NAVIS specified in Section 3.2 we now turn to the question of how to Irain it effectively. Because most downstream uses of aftinity vectors depend on the induced ordering of candidates rather than the actual affinity values (Huang et al., 2023 Tjandra et al. 2024), the choice of the loss function is critical. Most TGNNs use the cross-entropy loss (Luo Li 2022; Yu et al. 2023 Tjandra et al., 2024), which treats the output as a categorical distribution and ignores ordinal structure. As we show next, this property is suboptimal, and requires designated loss address this limitation.
The Limitation of Cross- Cross-Entropy Loss. Let s E Idd be the ground-trum truth and predicted affinity vectors. The cross-entropy loss reads:
(cE(s,y) =- Σ y())) loglsoftmax(s)(().
(15)
eEV
By construction, this loss is suboptimal because it penalizes well-ranked predictions with mismatched magnitudes. We formalize this claim in Theorem 3
Theorem (Cross-Entron) Entsosy is Suboptimal for Ranking). There exist infinitely many triplets of y, a ground-truth affinity vector, and $1, 82, two predicted logits of affinity vectors such that: S₁ ordering exactly matches the ground-truth node affinity scores (i.e. yields perfect ordering). S2 fiom S only in the logit of the most-affinitive node or the least-affinitive node-therebh making the ordering of s2 different from $1 and y, and (cE(S1. > LCr($2.
Proof. Set y = [0.4,0.6, 81 [1, 2.4] (correctly rank logits), S2 = [1, 0.6] (wrongly ranked logits). Then 0.75 ICE (S) (CE y) 0.78, where s ranks the same as y while $2 does not. Since fce is a continuous function, there are infinitely many such triplets.
To address this shortcoming, we train NAVIS using Lambda Loss (Burges et al. 2006) that is defined follows:
Lambda (s.
Σ log2
81g |An, - -An,
(16)
1 e (st, xx,)
where n; is the index of the node at rank i after sorting the affinity scores and Ax,, dej, Dj are defined as:
2 Vn: Ar, maxDCG
1
8ig
D; = log (1 + i)
(17)
D
Dis-11+1
and maxDCG is the maximum Discounted Cumulative Gain (DCG) computed by: Mat(e) max,' Ee log.li++) The loss in Equation (6) was previously shown to be effective for ranking tasks (Burges al. 2011: Wang al. 2018). This loss directly optimizes rank-based objectives via pairwise "lambdas" that approximate the gradient of non-differentiable ranking-based metrics, focusing learning on swaps that most impact the final ranking.
Pairwise Margin Regularization. In our experiments, we discovered that the use of the loss in Equation (16) alone is sufficient for future node affinity prediction tasks, we elaborate in Appendix Hence, we suggest the following regularization:
RRg (s, y)
Σ 9N3-1/3
max ((so, - Sx,) + +
(18)
Here, A is hyperparameter that represents the minimum margin required between each pair of affinity scores. The goal of this regularization to prevent NAVIS from incorrectly learning to shrink the affinity scores to minimize Equation (16). In Appendix H we show that the undesirable property in Theorem does not hold for the suggested loss function.
4 EXPERIMENTS
We evaluate NAVIS across multiple future node affinity prediction benchmarks and compare it with recent state-of-the-art baselines, including both heuristics and TGNNs. Sections 4.1 and 4.2 present
7

---

Published as a conference paper at ICLR 2026
Table 1: NDCG@ 10 on TGB datasets (1 higher is better). NAVIS is benchmarked against TGNNS that use all available graph messages. Boldface marks the best method.
Lyhn-trude
lgbo-geare
Igbu-reddit
Eghnn token
Method
Val.
Test
Val.
Test
Val.
Test
Val.
Test
Moving Avg
0.793
0,777
0.496
0,497
0.498
0.480
0,401 0.402
0.414
Historical Avg
0.793
0.777
0.478
0.472
0:499
0.481
0.415
JODIE
0.394:20.05
0.374=00.09
0.358=+0.03
0.350=20.04
0.345::0.02
0.314:00001
TGAT
0.395:1:.114
0.375:10.07
0.360:1:0044
0.352.10.03
0.345.10.01
0.314110.01
CAWN
0,393=t0.07
0.374=0.00
TCL
0.394:t0.11
0.375=0.09
0.362:+0004
0.354=0.02
0.347:40.01
0.314++0.01
GraphMixer
0.394:::0.11 17
0.375=0.11
0.361=:0:04
0.352=00.03
0:347:::001
0,314:00.01
DyGFormer
0.408::00.56
0.388=0.64
0.371=:0.06
0.365
0.348:4:0022
0.316:#0.01
Dy GMambu
0.393:1000001
0.304:100001
0.359:10.001
0.351
0.347=0.000
0.314:100000
Dy Rep
0.394.10.011
0.374110.00
0.357.10.001
0.001110.001
0.344_..0011
0.312.10.001
0.151
0.0400
TGN
0.445.1:0.009
0.409:10.005
0.443:10.002
0.423-10.007
0.402=00.007
0.400:10.000
0,251 0.000
0.200:10.005
TGN22
0.807.1.0.006
0.705.0.006
0.481110.001
0.469 0.000200.002
0.544_0..00
1.0002
1.0001
0.294.10.001
NAVIS (ours)
0.872:4:0001
0.863-20.011
0.512=00.011
0.520=t0.001
0.564=0.001
0.552::00001
0,423-00.001
0.444:10.001
Table 2: NDCG@ 10 on TGB datasets using only previous ground-truth labels (1 higher is better). This setting is suited for heuristics. Boldface marks the best method. Baselines have standard deviation because they are pre-defined and deterministic.
Method
Igbu-trade
tgbu-genre
Igbu-reddit
tgba-token
Val.
Test
Val.
Test
Val.
Test
Val.
Test
Persistent Forecast
0,860
0.855
0.350
0.357
0.380
0.369
0,403
0.430
Moving Avg
0,841
0.823
0.499
0,509
0,574
0.559
0.491
0.508
NAVIS (surs)
0.872:20.001
0.803=00001
0.517=00.001
0.528:20:001
0.584 001
0.569:10.001
0.000
0.513=20.001
our key empirical findings, and Appendix F Proviiess additional ablation studies. Our experiments aim to address the following research questions: (RQ1) How does NAVIS perform compared to prior art for future node affinity prediction? (RQ2) Does our method generalize across various types of graphs? (RQ3) What is the contribution of each component in NAVIS?
Experimental setup We compare NAVIS to the following TGNN baselines JODIE Kumar et al. 2019), Xu et al.] 22020). CAWN (Wang al. (021b), TCL (Wang et al. 202 Graph- Mixer(Cong et al. (202), DyG..DyeFrrmeer Yu et al. 2023) y. DyRep et al. 2024) and the standard heuristics presented in (Huang al. 2023) and in (Tjandra et al. (024). Following the standard protocols (Huang et al. (023). we use 70% 15% 155% chronological split, train for 50 epochs, use batch size of 200, and report the average NDCG @ 10 (Järvelin & Kekäläinen, 2002) over three runs. We include both future node affinity prediction settings: (1) using the full iine-grained CTDG up to the prediction time, and (2) using only previous ground-truth affinity vectors. Previous TGNNs only support the first setting (ijanrr et al. 2024). and, therefore, only heuristics are included in the second setting comparisons.
et al. 2019). TGN
et al. 2020),
4.1 NODE AFFINITY PREDICTION ON TGB
To answer (RQ1), we use the TGB datasets for node affinity prediction (Huang al.) 2023) I Egbn-trade, tggh- genre, tgbn-reddit, and tgbn-token. As shown in Tables and 2. NAVIS outperforms all baselines in both experimental settings. It improves over the best- performing TGNN TGNv2, by +12.8% on tgbn-t Notably, many TGNNs underperform simple heuristics, which aligns with our theoretical analysis that they are not optimized for ranking and underutilize available temporal information. In contrast, NAVIS linear design and rank-aware loss enable superior performance.
4.2 GENERALIZATION TO LINK PREDICTION DATASETS
To answer (RQ2), we repurpose four temporal link prediction datasets (Wikipedia Kumaar al. 2019). Ftights(Strommeier et al. 2021), USLegis(Fowles 2006), and UNVotte (Voeten et al.) 2009)) for the future node affinity prediction task. We detail how adjust these datasets in Appendix B TGNNs are known to operate well on these datasets YYu et al. 2023), and, therefore, should constitute
strong baseline. As shown in Tables 3 and 4 NAVIS consistently outperforms both TGNN and
8

---

Published as a conference paper at ICLR 2026
Table 3: NDCG @ 10 on converted link prediction datasets (f higher is better). NAVIS benchmarked against TGNNs that use all available graph messages. Boldface marks the best method.
Wikipedia
Flights
USLegis
UNeo
Method
Val.
Test
Val.
Test
Val.
Test
Val.
Test
Historical Avg
0.547
0,555
0,487
0,499
0.274
0.287
0,926
0.917
Moving Avg
0.547
0.555
0.029
0.028
0.150
0.154
0,926
0.918
DyRep
0.019::0.022
0.023::0.026
0.000:00.000
0.000::0.000
0.231=0.031
0.123::0.011
0.800=20.002
0.804:000002
DyGFormer
0.058:10.002
0.058-10.002
0.201
0.220:10.057
0.817100.007
0.809-1:0.00
DyGMamba
0.046:00003
0.050:20.002
0.246=0.015
0.154:::004
0.814=0.002
0.804=:0.002
TGN
0.056:t:0.005
0.065==0.006
0.249=00.003
0.227=00007
0.219=0.022
0.190::0.024
0.807=00003
0.792:+0.006
TON+2
0.478::00005
0.433::0.004
0.326=t0.008
0.209::0.014
0.323=0.036
0.253::0.040
0.824=0.0008
0.813=+0.010
NAVIS Cours)
0.564:10.001
0.573=:0.001
0.489=00.011
0.499=00:001
0.331=0.001
0.347:00000
0.969=00001
0.952::0.001
Table 4: NDCG@ 10 on converted link prediction datasets using only previous ground-truth labels (1 higher is better). Baselines have no standard deviation because they are pre-defined and deterministic. Boldface marks the best method.
Wilkipedia
Flights
USL.ggis
UNoe
Method
Val.
Test
Val.
Test
Val.
Test
Val.
Test
Persistent Farecast
0.499
0.507
0.296
0.307
0.328
0.320
0.963
0.917
Moving Avg
0.538
0.552
0,468
0,482
0,250
0.276
0.963
0.953
NAVIS (ours)
0.559=0.000
0.566=0.000
0.002
0.404
0.333:40.001
0.326:+:.001
0.971=00001
0.953=0.001
heuristic baselines, with gains ranging from +13.9% to +20% over the second performing TGNN, suggesting NAVIS generalizes well to many dynamic graph datasets. Similar to the results in Tables]] 2nd other TGNNs fall behind simple heuristies even though they were shown to produce great results on these datasets for future link prediction tasks, strengthening that the TGNNs design choices are incompatible for future node affinity prediction.
mentioned earlier in Sections 3.
and 3.3
4.3 ABLATION STUDY
To answer (RQ3), we conduct an ablation study isolate the contribution of each core component of NAVIS: (1) the linear state update mechanism (vs. the commonly used GRU), (2) the inclusion of the global virtual vector g, and (3) the proposed loss (vs. cross-entropy. CE). Full results are provided in Appendix F The ablations show that each component contributes substantially to the overall performance.
5 RELATED WORK
Expressivity in Temporal Graphs. The dominant view of expressivity in graph learning is measured by the Weisfeiler-Lehman (WL.) test's ability to distinguish non-isomorphic graphs (Gilmer et al. 2017 Xu et al., 2019). This concept extends to temporal graphs, with temporal-WL. (Souza et al. 2022) for CTDG and supra Laplacian WL (Galron et al. 2025) for DTDG, where models are evaluated on their capacity to differentiate evolving graph structures (Kazemi et al. 2020 ENNADIR al.) 2025). We diverge from this perspective by focusing on functional expressivity: model's ability to represent specific mathematica operations. While prior models aim to capture complex graph topology, they often cannot represent simple Moving Average, a critical function for affinity prediction.
Heuristics and State Space Models. According to the recent literature, simple heuristics, like Moving Average, often outperform complex TGNNs on various relevant benchmarks (Huang et al.) 2023, Cornell et al. (225)), suggesting the problem is fundamentally sequential. Recent work formally establishes the equivalence between linear SSMs and Moving Average (Eliasof et al. 2025) and explores their use in language modeling (Gu et al. 2022 Gu & Dao 2024) and dynamic link prediction (Li et al. 2024 Ding et al.) 2025). While these works connect SSMs to temporal data, approach is distinct. We are the first to explicitly leverage the formal equivalence between heuristics and SSMs design architecture, NAVIS, that is purpose-buil built for node affinity prediction.

---

Published as a conference paper at ICLR 2026
Temporal link prediction on weighted dynamic graphs. Temporal link prediction (TLP) on weighted dynamic graphs (Qin et al. [002]] Yang et al.] 2019 Lei et al. 2019) is the task in which, given discrete-time weighted dynamic graph (a sequence of snapshots of the graph at specific points in time), the model is required to predict the next snapshot, i.e., the weighted adjacency matrix future time. Although this task resembles node affinity prediction, there are several key differences. First, the downstream objectives differ, and accordingly different metrics are used to measure performance in each setting. In TLP on weighted dynamic graphs, the end goal is to construct the entire future weighted adjacency matrix. Hence, metrics such as RMSE, MSE, and MAE are often used. In node affinity prediction, however, the goal is to rank different nodes with respect to specific node by their affinity to it, and therefore ranking metrics such as NDCG or MRR are used. Moreover, TLP on weighted dynamic graphs operates in discrete-time setting, while node affinity prediction operates in continuous-ting time setting. Consequently, solutions for the former (Qin) itt al. 2023 Yang et al. 2019 Lei et al. 2019) operate on the full graph at each change, which may lead to unreasonable runtime if applied in the latter setting. In addition, upon each query, TLP on weighted dynamic graphs requires computing the full weighted adjacency matrix, while for node affinity prediction only the affinity scores between the queried node and the other nodes need to be computed. These factors are likely to hinder methods for TLP on weighted dynamic graphs from transferring well to node affinity prediction, and vice versa.
CONCLUSION
In this work, we identified critical gaps in the design of TGNNS for future node affinity prediction. These gaps, including an inability to express simple heuristics such as moving averages and Persistent Forecast, often lead these baselines to outperform TGNNs. We further showed that current under- performance also stems from the use of suboptimal, non non-ranking losses such as cross-entropy. To address this, we introduced NAVIS, a novel architecture grounded in the ability of linear state-space models to generalize heuristic behavior. By incorporating a virtual state to capture global dynamics and carefully designed rank-aware loss, NAVIS preserves the robustness of heuristics while offering greater expressive power. Extensive experiments demonstrate that NAVIS consistently outperforms state-of-tee of-thh-art models and heuristics across multiple benchmarks, underscoring the importance of aligning model's inductive biases and training objectives with the specific demands of the task.
Limitations and future work Although NAVIS has shown strong performance, both theoretically, by generalizing common heuristics that excel in node affinity prediction, and empirically on TGB benchmarks, NAVIS remains elementary, and further research in this direction is required. For example, NAVIS currently utilizes a basic virtual global state based on recency selection from global buffer to capture trends in dynamic graphs. Advanced aggregation schemes over the global buffer (e.g.. attention based mechanisms) and more sophisticated buffer-eviction strategies (e.g., non-deterministic eviction) may improve the modeling of global state and further enhance TGNN performance node affinity prediction. In addition, NAVIS computes node affinities linear combination of the input and current state, with coefficients in [0, 1] that are adaptive to both. Consequently, NAVIS cannot, for example, represent certain non-lime conelinear functions. This limitation could be addressed by adding a third non-linear component with an associated coefficient such that all three coefficients sum to 1. We leave to future work the investigation of how to best combine linear and non-linear components to enable TGNNs to perform optimally on the node affinity task.
ACKNOWLEDGMENTS
ME acknowledges support from the Israeli Ministry of Innovation, Science & Technology.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Masao Aoki. State Space Models: A Unifying Framework. Springer, Berlin, Germany, 2013. ISBN 978-3-642-35040-66
Thierry Mertin-Mahieex, Daniel PW Ellis, Brian Whitman, and Paul Lamere. The million song dataset. In Ismir, volume 2. pp. 10, 2011.
Christopher Burges, Robert Ragno, and Quoc Le. Learning to rank with nonsmooth cost functions. Advances in neural information processing systems, 19, 2006.
Christopher Burges, Krysta Svore, Paul Bennett, Andrzej Pastusiak, and Qiang Wu. Learning to rank using an ensemble of lambda-gradient models. In Proceedings of the learning to rank Challenge, pp. 25-355-35 PMLR, 2011.
Andrea Ceni, Alessio Gravina, Claudio Gallicchio, Davide Bacciu, Carola-Bibiane Schonlieh, and Moshe Eliasof. Message-passing state-space models: Improving graph learning with modern sequence modeling. arXiv preprint arXiv:2505.18728, 2025.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using mnn encoder-decoder for statistical machine translation. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, meeting of SIGDAT, Special Interest Group of the ACL, pp. 1724-1723 1734, 2014.
Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do we really need complicated model architectures for temporal networks? The Eleventh International Conference Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023.
Filip Cornell, Oleg Smirnov, Gabriela Zarzar Gandler, and Lele Cao. On the power of heuristics in temporal graphs, 2025. htlhttsss///xxiii org/ abs 2502 04910
Zifeng Ding, Yifeng Li, Yuan He, Antonio Norelli, Jingcheng Wu, Volker Tresp. Michael M. Bron- stein, and Yunpu Ma. DyGMamba: Efficiently modeling long-term temporal dependency on continuous-time dynamic graphs with state space models. Transactions on Machine Learn- ing Research, 2025. ISSN 2835-8856. URL https:://penrevieet net. net/forummio sq5AJvVuha
Moshe Eliasof, Alessio Gravina, Andrea Ceni, Claudio Gallicchio, Davide Bacciu, and Carola- Bibiane Schönlieh. Grama: Adaptive graph autoregressive moving average models. In The Forty-Second International Conference on Machine Learning, 2025.
Jeffrey L Elman. Finding structure in time. Cognitive science, (42):179-2111 1990.
Sofiane ENNADIR, Gabriela Zarzar Gandler, Filip Cornell, Lele Cao, Oleg Smirnov, Tianze Wang, Levente Zólyomi, Bjöm Brinne, and Sahar Asadi. Expressivity of representation learning continuous- time dynamic graphs: An information- flow centric review. Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL Col.htts:: fttt::::///peeeevieeee net forum?
id=M7Thr2anjg Survey Certification.
Or Feldman and Chaim Baskin. Leveraging temporal graph networks using module decoupling, In The Third Learning on Graphs Conference, 2024.
James H Fowler. Legislative cosponsorship networks in the us house and senate. Social networks, 28 (4):454 465, 2006.
Yaniv Galron, Fabrizio Frasca, Haggai Maron, Eran Treister, and Moshe Eliasof. Understanding and improving laplacian positional encodings for temporal gnns. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 420-437. Springer, 2025.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. Pmlr, 2017.
11

---

Published as a conference paper at ICLR 2026
Alessio Gravina, Giulio Lovisotto, Claudio Gallicchio, Davide Bacciu, and Claas Grohnfeldt. Long range propagation on continuous- time dynamic graphs. International Conference on Machine Learning, pp. (6206-16225 PMLR, 2024.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. In First Conference on Language Modeling, 2024. https:: wet.www..eeeee...e..........e... wewtfooummmiie
tEYskw VY2
Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré. Combining recurrent, convolutional, and continuous-time models with linear state space layers. Advances in neural information processing systems, 34:572-585, 2021.
Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022. URL https
net net. /
James D) Hamilton. State-space models. Handbook of econometrics, 4:3039-3080, 1994.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997.
Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabusscau, and Reihanch Rabbany. Temporal graph benchmark for machine learning on temporal graphs. Advances in Neural Information Processing Systems, 36, 2023.
Kalervo Järvelin and Jaana Kekäläinen. Cumulated gain based evaluation of ir techniques. ACM Transactions on Information Systems (TOIS), 20(4):422-446, 2002.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey. The Journal of Machine Learning Research, 21(1):2648-273 2020.
Srijan Kumar, Xikun Zhang, and Jure Leskovee. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1269-1278, 2019.
Kai Lei, Meng Qin, Bo Bai, Gong Zhang, and Min Yang. Gen-gan: A non-linear temporal link prediction model for weighted dynamic networks. In IEEE INFOCOM 2019-IEEE conference on computer communications, pp. 388-396. IEEE, 2019.
Dongyuan Li, Shiyin Tan, Ying Zhang, Ming Jin, Shirui Pan, Manabu Okumura, and Renhe Jiang. Dyg-mamba: Continuous state space modeling on dynamic graphs, 2024. URL https://
arxiv. wttp://///bbbb/bgeeeee 06966
Xiaodong Lu, Leilei Sun, Tongyu Zhu, and Weifeng Lv. Improving temporal link prediction via temporal walk matrix projection. Advances in Neural Information Processing Systems, 37:141153- 141182, 2024.
Yuhong Luo and Pan Li. Neighborhoodd-wwrre scalable temporal network representation learning. In Learning Graphs Conference, pp. 1-1. PMLR, 2022.
Graham K MacDonald, Kate A Brauman, Shipeng Sun, Kimberly M Carlson, Emily S Cassidy, James S Gerber, and Paul C West. Rethinking agricultural trade relationships in of global- ization. BioScience, 65(3):275-22 2299, 2015.
Amirhossein Nadiri and Frank W Takes. A large-scale temporal analysis of user lifespan durability on the reddit social media platform. In Companion Proceedings of the Web Conference 2022, pp. 677-685, 2022.
James W Pennebaker, Martha E Francis, and Roger Booth. Linguistic inquiry and word count: Liwe 2001. Mahway: Lawrence Erlhaum Associates, 71(2001):2001, 2001.
12

---

Published as a conference paper at ICLR 2026
Meng Qin, Chaorui Zhang, Bo Bai, Gong Zhang, and Dit- Yan Yeung. High-quality temporal link prediction for weighted dynamic graphs via inductive embedding aggregation. IEEE Transactions on Knowledge and Data Engineering. 35(9):9378-99) 00999,9333999 2023.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. CoRR, abs/2006. 10637, 2020.
Kiarash Shamsi, Friedhelm Victor, Murat Kantarcioglu, Yulia Gel, and Cuneyt G Akcora. Chartalist: Labeled graph datasets for utxo and account- based blockchains. Advances in Neural Information Processing Systems, 35:34926-34939, 2022.
Jitesh Shetty and Jafar Adibi. The enron email dataset database schema and brief statistical report. Information sciences institute technical report, University of Southern California, 4(1):120-128, 2004.
Amauri Souza, Diego Mesquita, Samuel Kaski, and Vikas Garg. Provably expressive temporal graph networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 32257-32269. Curran Asso- ciates, Inc., 2022, / 2022/file/ 222p:///440222211006666666606330
pawpr wwwes/fapeeeeeeeeeeeeeeeaaasaeee
Martin Strohmeier, Xavier Olive, Jannis Lübbe, Matthias Schäfer, and Vincent Lenders. Crowd- sourced air traffic data from the opensky network 2019-2020. Earth System Science Data, 13(2):
357-366, 2021.
Benedict Aaron Tjandra, Federico Barbero, and Michael M Bronstein. Enhancing the expressivity of temporal graph networks through source-targe identification. In NeurlPS 2024 Workshop on Symmetry and Geomeiry Neural Representations, 2024.
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019.
Erik Voeten, Anton Strezhnev, and Michael Bailey. United Nations General Assembly Voting Data. Harvard Dataverse, 2009. URL httpt::t///ettt doi. org/orggg//... 10. wwt...91///// 7910/DVV/LEJUQX
Lu Wang, Xiaofu Chang, Shuang Li, Yunfei Chu, Hui Li, Wei Zhang, Xiaofeng He, Le Song, Jingren Zhou, and Hongxia Yang. Tel: Transformer-based dynamic graph modelling via contrastive learning. CoRR, abs/2105.079444 2021a.
Xuanhui Wang, Cheng Li, Nadav Golbandi, Michael Bendersky, and Marc Najork. The lambdaloss framework for ranking metric optimization. In Proceedings of the 27th ACM international conference on information and knowledge management, pp. 1313-132221 1322, 2018.
Yanbang Wang. Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021b.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive represen- tation learning on temporal graphs. 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https
//openreview net wttt:/ooormiddrreeeeeee
Min Yang, Junhao Liu, Lei Chen, Zhou Zhao, Xiaojun Chen, and Ying Shen. An advanced deep generative framework for temporal link prediction in dynamic networks. IEEE transactions on cybernetics, 50(15) (1:11)::44449999 4957, 2019.
Le Yu, Leilei Sun, Bowen Du, and Weifeng Lv. Towards better dynamic graph learning: New architecture and unified library. Advances in Neural Information Processing Systems, 36:67686 67700, 2023.
13

---

Published as a conference paper at ICLR 2026
A DATASETS STATISTICS AND DESCRIPTION
In our empirical evaluation, we employed the following dynamic graph datasets, each capturing a dis- tinct dynamic system and providing varied graph structures, edge features, and temporal resolutions:
models global agricultural commerce among UN-affiiiated countries over 1986-2016 as a time-evolving network: countries are the nodes and directed links record, for each calendar year, the aggregate value of agricultural goods moved from one country to another. Because entries are reported yearly, the temporal resolution is annual. The accompanying learning objective is anticipate, for chosen country, how its overall agricultural trade will be apportioned across partner countries in the subsequent year- that is, the next-year distribution of trade shares.
TGBN-TRADE (MacDonald et al. 2013):
et al. 2011) models listening behavior as weighted bipartite graph linking users to musical genres. Nodes consist of users and genre labels; time-stamped edges indicate that a user listened to a track associated with that genre, with the edge weight reflecting the fraction of track's composition attributed to that genre. The downstream objective is a ranking problem: for each user, predict the genres they are most likely to engage with during the upcoming week.
TGBN-GENRE,
REDN-TEDDIT (Nadiri & Takes 2022) models Reddit as a temporal bipartite graph linking users and subreddits. Nodes represent both entities, and timestamped edge records user's post within a subreddit. The dataset covers activity from 2005 through 2019, The predictive objective is, for each user, to produce a next-week ranking of subreddits by expected engagement intensity.
TGBN-TOKEN (Shamsi et al., 2022) models bipartite interaction graph linking wallet users to cryptocurrency tokens. Nodes consist of users and tokens, and directed edges record transfers from a user to a particular token. Edge weights capture the logarithmic normalized transaction quantity. The predictive objective is to estimate, for the next week, how often each user will engage with different classes of tokens.
WIKIPEDIA Kumar et al., 2019): models bipartite, time-stamped interaction graph derived from a single month of edit activity. Nodes correspond to editors and articles, and each interaction edge denotes an edit event. Every edge annotated with its event time and feature vector from the Linguistic Inquiry and Word Count framework (LIWC (Pennebaker et al. 2001h) summarizing the edit's linguistic characteristics. The predictive objective for this converted version of the dataset is to predict the expected engagement intensity of each editor with existing articles.
Flights (Strohmeier et al. 2021): models air traffic patterns during the COVID-19 period as temporal network in which airports are nodes and connections represent observed routes between them. Each connection carries a timestamp and an associated intensity, with the edge weight recording how many flights operated on that route on given day. The downstream objective is rank future airport destinations intensity, given the source airport.
USLegis (Fowler 2006): models the collaboration dynamics of the U.S. Senate as temporal, weighted network: senators are represented as nodes, ties are created whenever pair co- sponsors the same bill, and each tie is stamped with the time of occurrence. Edge weights record the frequency of joint sponsorships within legislative term, capturing how often two members work together. The predictive objective is to estimate the joint sponsorship frequencies for the next term.
UNVooe (Voeten et al. 2009): models the United Nations General Assembly roll-call record from 1946 through 2020 as a time-evolving graph: countries are nodes, and edge appears between two countries whenever they cast matching affirmative ("yes"") votes on the same resolution. Each edge carries timestamp and a weight, where the weight counts how many times that pair of countries voted "yes" together over the period. The predictive objective is to estimate the joint positive votes for the next period.
14

---

Published as a conference paper at ICLR 2026
Table 5: Statistics of various datasets used in our experiments
Dataset
Domain
#Nodes
#Edges
Bipartite
Duration
TGBN-TRAN GRANE
Economy
255
468,245
Falsc
30 years
IGBN-GENRE
Interaction
1,505
17,858,395
True
4 years
IGBN-REDDIT
Social
11,766
27.174,118
True
years
IGBN-TOKEN
Cryptocurrency
61,756
72,936.998
True 2 years
WIKIPEDIA
Social
9,227
157,474
True
month
FLIGHTS
Transport
13,169
1,927,145
Falsc
4 months
USLEGIS
Politics
225
60,396
False
12 terms
UNVOTE
Politics
201
1,035,742
False 72 years
B CONVERTING LINK PREDICTION DATASETS TO NODE AFFINITY PREDICTION DATASETS
Each of the future link-prediction datasets use (Wikipedia, Flights, USLegis, and UNVote) comprises a CTDG with weighted interaction events between node pairs. For each dataset and node, we define the ground-truth future affinity vector as the normalized sum of weighted interaction it received over a specified period (day, week, year, etc.). Immediately before the start a new period, the task is to predict each node's 's affinities for the upcoming period. Table summarizes the periods used for each dataset.
Table 6: Chosen period for link property prediction datasets.
Dataset
Period
Wikipedia
Day
Flights
Day
USL Legis
Legislative term
UNVote
Year
Our code release includes step-by-step guide processing these datasets and integrating them into TGB framework support future research on node-afiintyy prediction.
C SYNTHETIC EXPERIMENT
We construct controlled continuous-time dynamic graph (CTDG) where each node (1,..., N) emits events according to a Poisson process (rate X) over a horizon [0, T). Node affinities time governed by shared global latent g(t that switches between two damped-oscillatory regimes. Concretely, on grid with step At, g(t) follows a piecewise AR(2) process with coefficients chosen to approximate low- and high-fregh fregufrey damped cosines; regime switches are exogenous and uncorrelated with any single node's local history. Each node is assigned a phase du. a mixing coefficient 3u, and small bias Tu- The instantaneous (pre-softmax) affinity logits are nonlinear readout of the global state (t)2),
(1) = cos((w)) g(1) + B. sin(h))))) (0(1)2 -1) + 7u + cu()),
and, for each source node u, we mask self-transitions and apply softmax over destinations to obtain ground-truth affinity distributions. The forecasting task is one-step prediction of node's destination distribution at query times, given only the previous ground- -atun affinity vectors at inference. We compare per-node, history-only baselines that cannot share information across nodes Persiitten Forecast (PF; last observation), Simple Moving Average (SMA; window w=5), Exponential Moving Average (EMA; 0022), and diagonal per-node AR(1) l).
15

---

Published as a conference paper at ICLR 2026
Table 7: MRR on TGB datasets (f higher is better). NAVIS is benchmarked against TGNNs that use all available graph messages. Boldface marks the best method.
tghn-trade
Igbn-genre
igbn-reddit
tgbn-token
Method
Val.
Test
Val.
Test
Val.
Test
Val.
Test
TGN22
0.00=0.01
0.53++:.01
0.43+00.01
0.40+00.11
0.43+0001
0.40#0.01 0.44=00.001
0.28 0.39
0.26+t0.01 0.41
NAVIS (ours)
0.78=0.00
0.77=:0.011
0.40
0.42::0.00
0.45
Table 8: Recall on TGB datasets (t higher is better). NAVIS is benchmarked against TGNNs that use all available graph messages. Boldface marks the best method.
tgbn-trade Val.
igbn-genre
tgbn-reddit
tgbn-token
Method
Test
Val.
Test
Val.
TGNv2
0.60=10.11
0.32+t0.01 0.72-10.00 0.34
0.56==0.11
0.31 0.33:10.00
0.19 0.21
0.18+0.01 0.20-10.00
0.05++0.00 0.30:10.00
0.05=+0.00
NAVIS (ours)
0.75=10.00
0.28
D IMPLEMENTATION DETAILS
We initialized each linear layer in NAVIS with values drawn uniformly from the range [- Vd, Vdl, where d is the input dimension of the layer. No normalization of the output vector s were required as the ground true affinity scores in TGB are already normalized. The final loss used is Laambda Reg, where C is regularization coefficient. In the experiments we set C = 1. We adopted standard hyperparameters, consistent with prior work: batch size 200, Adam optimizer, and learning rate 10-4. Following the TGB protocol, all models were trained for 50 epochs, and the checkpoint with the best performance on the validation set was selected. We set the regularization margin to A = 10 During training, NAVIS computes the loss only over the top-20 affinities, ensuring that loss computation requires constant time and memory. We used single NVIDIA GeForce RTX 3090 GPU and a single AMD Ryzen 9 7900X 12-Core Processor CPU.
E ADDITIONAL RESULTS
Additional Evaluation Metries We additionally compare NAVIS to the best performing baseline
in each setting and report the results in terms of MRR (the average value of RANKT where RANK is the predicted rank of the ground-truth top-scored node) and Recall @ 10 (the average number of top-10 ground-truth nodes ranked within the top-10 predicted scores). We report the results Tables to TO From the results, observe that the performance gap between the baselines increases under the MRR metric but decreases under the Recall@ 10 metric. This can be explained by our objective, which penalizes mismatches top-ranked ground-truth nodes (e.g., ranks 1-3) more strongly than on lower-ranked ones (e.g., ranks 8-10).
Noisy data experiment To examine the robustness of NAVIS, we performed an additional ex- periment on noisy data. We used the igbn-genre benchmark and, for each node that received its N-th update, we added an extra random update from that node to random node and weighted the interaction with largest magnitude of affinity. We ran this experiment twice, once with N 10 and second time with N 20, and did not observe a significant change in the performance of NAVIS on the dataset. This experiment provides empirical evidence that NAVIS is robust to noise such as short-term spikes.
What NAVIS learns? Table 2 the Persistent Forecast baseline performs better than Moving Average on tgbn-trade, while on tgbn-genre the opposite holds. This means that tgbn-genre requires more memory to accurately perform node affinity prediction while in tghn-trade needs to rely
16

---

Published as a conference paper at ICLR 2026
Table 9: MRR on TGB datasets using only previous ground-truth labels (f higher is better). This setting is suited for heuristics. Boldface marks the best method. Baselines have no standard deviation because they are pre-defined and deterministic.
tgbn-trade
igbn-genre
tgbn-reddit
tgbn-token
Method
Val.
Test
Val.
Test
Val.
Test
Val.
Test
Moving Avg
0.77
0.78
0.31
0.32
0.41
0.40
0.44
0.47
NAVIS (ours)
0.77100.00
0.78 1..00
0.41
0.42.10.00
0.47 1.000.000
0.46
0.000
0,48 0.481.0.00
Table 10: Recall @ 10 on TGB datasets using only previous ground-truth labels (1 higher is better). This setting is suited for heuristics. Boldface marks the best method. Baselines have no standard deviation because they are pre-defined and deterministic.
tgbn-trade
tgbn-genre
tgbn-reddit
fgbn-
Method
Val.
Test
Val.
Test
Val.
Test
Val.
Test
Moving Avg
0.74
0.73
0.29
0.30
0.25
0.24
0.30
0.29
NAVIS (ours)
0.74.10.00
0.73
0.34
0.34.10.00
0.25
0.24
0.30.10.00
0.29110.00
more on the newly arrived data. To examine what NAVIS learns in these two regimes, we measured the average values of o and from Equation (4), which control the relative influence of the memory component. We expect lower values on tgbn-trade to resemble persistent forecast and larger values on igbn-genre to resemble moving average. The measured values are 2/2 0.48, 2, 0.49 for tgbn-tradk and 24, = 0.90, 2 = 0.84 for tgbn-genre. This alignment between the learned 24+ 2, and the heuristic that performs better on each dataset provides empirical evidence that NAVIS learss the intended heuristic behavior in practice.
Additional SSM comparison We further compared NAVIS to an additional general SSM baseline, the S4 block (Gu et al. 2022), and report the results in Table [T The comparison was performed under the same ground ground-truth label setting as in our main experiments. Both our method and the S4 block utilized the same learning rate, batch size, and number of training epochs. The results in Table 11 show that although the S4 block achieves relatively strong performance on the tested benchmark, NAVIS still outperforms it, indicating that there remains substantial room for improving general SSM architectures on this benchmark.
F ABLATION OF DESIGN CHOICES
Table 12 shows the ablation study results on the four TGB test sets. The results confirm that each component provides significant impact on NAVIS performance. The full NAVIS with our suggested linear state updating-medt mechanism, global vector, and ranking loss establishes the strongest performance. Replacing the ranking loss with cross-entropy causes notable drop performance, validating our theoretical motivation. Switching to the GRU mechanism and removing the global signal further degrades performance, highlighting the importance each component in the final design.
We further ablate on the regularization term of our loss, and performed an additional experiment on the TGB datasets where the regularization term is not included the loss computation. We report the results in Table [3]
Applying our proposed regularization not only significantly improves the performance of NAVIS, but also accelerates convergence, with convergence typically reached in roughly 30 epochs.
We also performed an empirical analysis on the effect of the hyperparameters of delta and batch size on the perfance of NAVIS, and report the results in'all 14 From Table [4] we see that on the tested datasets and batch size values has no effect on the performance of NAVIS. In addion, choosing too small too large values for delta slightly hurt the performance of NAVIS.
Additionally, we performed an analysis to examine the effect of the global buffer size and its aggregation scheme the performance of NAVIS, compared to the recency selection aggregation
17

---

Published as a conference paper at ICLR 2026
Table 11: NDCG@ @ on TGB datasets using only previous ground-truth labels (f higher is better). Boldface marks the best method.
tghn-trade
tgbn-genre
Method
Val.
Test
Val.
Test
S4
0.819#00005 0.872-10.001
0.796=0.0002
0.451 0.461
NAVIS (ours)
0.863
0.517
0.528
Table 12: Ablation study of NAVIS components on TGB sets. denotes exclusion.
denotes inclusion and (x)
State Update
Global vector
Loss
Igbn-trade
igbn-genre
Igbn-reddit
igbn-token
Linear
Rank
0.80310.001
0.528
0.569-10.00
0.513
GRU
X
Rank
0.850=00001
0.398=0.001
0.454=0.001
0.444=1.001
Linear
X
Rank
0.857=0.001 0.521
0.557=0.004
0.511=0.001
Lincar
CE
0.859=0.0001
0.461=10.001
0.530=10.001
0.508=10.001
scheme used in previous experiments. We report the results in Table 15 The results in Table [5 show that changing the aggregation scheme or the size of the buffer has little to no effect on the NAVIS. The slight drop in performance when the buffer size is 8 and the aggregation scheme is mean may be explained by the reliance on relatively old values in the buffer. We leave the exploration of new and more sophisticated virtual global state mechanisms (e.g.. attention-based aggregation) for future work.
existing implementation
G MEMORY AND RUNTIME ANALYSIS
We conducted a runtime and memory analysis to examine the efficiency of NAVIS. In Table I6 we report the number of parameters of the TGNN baselines and NAVIS. NAVIS only requires the fewest parameters among the compared methods, but also scales well to large graphs due to the sparsification pipeline detailed in Section 3.2
In Table 17 we report runtime comparison for single training epoch and inference between NAVIS, heuristies, and TGNN baselines. NAVIS more efficient the TGNN baselines and has runtime comparable to the heuristics. Since all methods use the same batch size, their throughput proportional to their runtime. Since the heuristies not contain learnable parameters they only require a single pass over the training data compute node states before entering the validation and test phases. Other methods require multiple iterations over the training data (epochs) like standard deep learning models.
H THEORETICAL REMARKS
In Theorem we showed that standard memory cells (RNN, LSTM, and GRU) cannot express the simple Persistent Forecast heuristie. The proof assumes that the input to the cells may unbounded, and since tanh and other nonlinear activation functions have bounded images, this prevents the memory cells from expressing this heuristic, A natural question what happens when the input x is bounded, e.g., in [0, 1] or [1, Recall that persistent forecast is defined by h; 24. while an W.Y, + b). Denote fx; = W W. + To
RNN cell is defined by h, = tanh(W,,4411 obtain h4 F;, need tanh(f(x.)) = Iz, i.e., tanh f-1 on the relevant range by composition of functions. However, f-1 must be aftine, as the inverse of an affine function, which contradicts the fact that tanh not affine. The same argument applies to the GRU cell from Equation 13 This also holds for any non-affine activation on [-1, 1), such ReLU or leaky ReLU.. On [0, 1]. ReLU
18

---

Published as a conference paper at ICLR 2026
Table 13: Results of NAVIS in terms of NDCG@ 10 TGB datasets, with and without the suggested regularization term. (V) denotes inclusion and (X) denotes exclusion.
ighn-genre
tghn-reddit
tgbn-token
Regularization
Val.
Test
Val.
Test
Val.
Test
0.510:10.001
0.520:10.001
0.570-10.001 0.528
0.553-10.001 0.569
0.487=100001 0.493=+0.001
0.510=E0.001
0.0001
0.584=0.000
0.513-t0.001
Table 14: Analysis of different batch sized and deltas, results are measured in NDCG@ @ 10 on test sets of datasets from TGB, averaged for 3 runs.
Hyperparameter tgbn-trade
tgbn-genre
delta=0.1
0.863=0000
0.526=1..001
delta=0.01
0.863=0.001
0.528=0.001
delta=0.001
0.863=0.001
0.527=0.001
batch size = 100
0.001
0.528
batch size 200
0.863 0.863-0.001
0.001 0.528+
batch size = 400
0.863 0.001
0.528+0.001
Table 15: Ablation study of NAVIS components on TGB test sets. (V) denotes inclusion and (X)
denotes exclusion.
Buffer size
Aggregation scheme
tgbn-trade
ighn-genre
Recent Selection
0.863++0001
0.528=0.001 0.001
MEAN
0.863+0.001
0.528 0.001
Time Decay
0.528 0.803
MEAN
0.863+0.001
0.527=0.001
8
Time Decay
0.863+0.0001
0.528=0.001
is equal to the identity, and hence applying ReLU to inputs normalized to this range allows these memory cells to learn the Persistent Forecast heuristic.
Tjandra et al. (2024) state that There exists formulation of TGN22 that can represent persistent fore- casting and moving average of order k. To prove this claim Tjandra et al. (2024) utilize permutation matrices, block matrix and dedicated generator vector for the memory module of TGNv2. However, in practice TGNv2 is officially implemented with a GRU cell as the memory module. We showed in Theorem that GRU cell cannot express the simple Persistent Forecast heuristic.
In Theorem we proved that the cross-entropy loss is suboptimal by showing that there exist two rankings such that ranks the elements identically the ground truth while the other does not, yet under cross-entropy the latter achieves a smaller loss, contrary to what is desired in the task of node affinity prediction. We then argued that there exist infinitely many such examples since the cross- entropy loss is continuous function. Consider the cross-entropy loss evaluated on the ground-truth order vector and correctly ordered score vector as function of the first entry of the correctly ordered vector (all other entries are fixed). Denote this function by f(x). Let Liue be the cross-entron
loss of a fixed incorrectly ordered vector, and define A = f(x) Line 0. By continuity of f. there exists
8 > 0 such that for any x' satisfying xx'' - x < 5 we have !/(a²) f(x)) < A/2, which implies [ax) >> Tine- Since there are infinitely many such x', we obtain infinitely many correctly ordered
score vectors that incur larger cross-entropy loss than the incorrectly ordered vector.
In Section 3.3] we introduced our loss function and claimed that the guarantee in Theorem does not apply to it. We now formalize and prove this claim. Let denote the ground-truth affinity vector, and let $1 and sy be two predicted logit vectors such that: (i) the ordering induced by $1 exactly matches the ground-trute -otuuhhtruuhhh node affinity scores, and (ii) sy differs from $ only in the logit of either the most-affinitiee node or the least-affinitive node, thereby inducing an ordering different from that of ss. Since all logits in 82 identical those in $ except for the most- least-
19

---

Published as a conference paper at ICLR 2026
Table 16:
Number of parameters of TGNN baselines and NAVIS, compared the total number of nodes in each TGB benchmark for node affinity prediction.
Method
tgbn-trade
igbn-genre
fgbn-reddit tgbn-token
#Nodes
255
1505
11766
61756
DyGMamba
255125
257963
259998
DyGFormer
1027877
1030715
1032750
TGN
207655
233713
252398
283401
TGNv2
6433023
6565377
6660282
6817769
NAVIS
1280
2570
3495
5010
Table 17: Training and inference runtimes of the TGNN baselines, heuristics and NAVIS on the igbn-genre dataset.
Method
Training runtime (sec)
Inference runtime (sec)
Persistent Forecast / Moving Avg
34
6
DyGMamba
2080
381
DyGFormer
1440
304
TGN
170
33
TGNv2
130
36
NAVIS
46
8
affinitive node, for any pair (i.j) where neither nor j is the most- or least-affinitive node, we have b $1 (i) (j)) 67, (1) sj). For pairs (i.j) in which is the most-affinitiee node j is the least-affinitive node, we obtain o%, < 6% because the logit of the most-affinitve node can only decrease in relative to S1, and the logit of the least-affinitive node can only increase. In both Equations (3) and (18), smaller differences between correctly ranked affinity scores yield smaller loss values.
20


Reviews:
[{"review_id": "bjJFKuwt02", "reviewer": "Reviewer_hEbc", "summary": "This manuscript addresses the task of future node affinity prediction in continuous time dynamic graphs. Unlike future link prediction, the model output a full ranking / affinity vector over all other nodes. The authors observe that simple heuristics (like persistent forecast and moving average) often outperforms more recent Temporal Graph Neural Networks on this task, and attributes this to four main factors: current TGNN memory cells cannot express even the simplest persistence heuristic; common cross entropy loss is misaligned with the ranking nature of affinity; global temporal dynamics are not captured by local sampling; and batching / truncated buffers cause information loss. To address this, the authors propose NAVIS - TGNN style model built as a linear state space mechanism with both per node and virtual global states. On TGB node affinity and on four converted temporal link datasets, NAVIS outperforms TGNN baselines and the strong heuristics.", "questions": "1. What is the buffer size, eviction policy, aggregation function and normalization? Is g updated per batch or globally across epochs?\n2. How are candidate sets constructed? What fraction of true next interactions falls outside the candidate set? Please report recall@K of candidate generation and confirm all methods share the same candidates.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Clearly distinguishes future node affinity prediction (requiring a full ranking) from future link prediction (binary task).\n2. Proves that simple heuristics are special cases of linear State-Space Models; and that standard RNN, LSTM, and GRU cells are functionally incapable of representing the persistent forecast heuristics.\n3. Extensive experiments on TGB node affinity datasets and four converted link prediction datasets. The results consistently show NAVIS outperforms baselines.", "weaknesses": "1. All experiments / comparison is against TGNNs and not against the most recent SSM based temporal models on the same TGBN tasks.\n2. Empirical evaluation or ablation study on the performance impact of sparsified affinity prediction pipeline is missing.\n3. Evaluation is performed on 4 link prediction datasets that the authors repurposed using a custom pipeline - releasing the exact scripts is important for reproducibility.\n4. Analysis of ranking loss is limited to small constructed example. Sensitivity to the margin and to batch size would strengthen the empirical section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "94QLEUFUK9", "reviewer": "Reviewer_uBoh", "summary": "The paper revisits the task of node affinity prediction in temporal graphs, which aims to forecast the future affinity distribution of each node rather than just predicting future links. The authors observe that simple heuristics like Persistent Forecast (PF) and Exponential Moving Average (EMA) often outperform existing Temporal Graph Neural Networks (TGNNs). To address this, they theoretically show that such heuristics can be viewed as linear State Space Models (SSMs) and propose a new TGNN architecture called NAVIS, which integrates a learnable linear SSM with a “virtual global state” to capture global temporal dynamics. The paper also replaces the cross-entropy loss with a ranking-based LambdaLoss to better align with the affinity prediction objective. Extensive experiments on multiple temporal graph benchmarks demonstrate that NAVIS consistently outperforms both heuristic and neural baselines.", "questions": "Please see the weakness above", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper explains why existing TGNNs fail to capture simple temporal dependencies and provides a theoretical basis for improving them.\n\n2. The proposed NAVIS model is conceptually simple yet achieves strong and consistent performance across benchmarks.", "weaknesses": "1. There exists a conceptual gap between the theoretical analysis and the modeling assumptions used in practice.\nTheorem2 argues that standard RNN/LSTM/GRU units cannot reproduce the persistent forecast (PF, i.e., $h_i = x_i$) because their activation functions restrict the output range. While mathematically valid, this result relies on an assumption that the inputs are unbounded and not normalized. If the inputs are bounded, or if a fixed linear readout is added to counteract activation saturation, the expressive limitation may no longer hold. \n\n2. The design and motivation of the global virtual state $g$ are intuitive but lack precise statistical or identifiability analysis.\nThe paper only states that $g$ is ``an aggregation of recent affinity vectors in a buffer`` and claims that ``using recent vectors works well in practice``.\nHowever, the following points are not clarified:\n(1) What's the specific aggregation operator (mean, exponentially weighted average or  attention？);\n(2) There is no statistical or identifiability analysis showing under what conditions this aggregation can truly extract a global trend rather than just averaging noise. \n(3) Without (2), it is unclear whether it  models a global latent factor or merely performs temporal smoothing of the previous global affinity distribution.\nSince $g$ is central to the claim that heuristics $\\approx$ linear SSMs but still require global trend modeling, a deeper ablation across different aggregators and buffer lengths is necessary.\n\n3. Although the authors acknowledge that parameter size grows as $O(N^2)$ and propose truncation by retaining the top-$a$ affinities for each node, there is no quantitative evaluation of the trade-off between $a$, accuracy, and efficiency. In highly dynamic graphs, where new neighbors emerge or distributions shift, truncation based solely on previous affinity magnitudes may omit critical new relations. \n\n4. The main comparisons involve TGNNs and heuristic methods, showing consistent improvements, but no experiments include modern nonlinear, selective SSMs or DyG-Mamba[1,2] under the same protocol. Without such baselines, the claim that ``linear SSM-based TGNNs outperform more complex temporal models`` remains context-dependent and potentially overstated.\n\n5. The authors convert several link-prediction datasets into affinity-prediction datasets by temporal aggregation over daily, yearly, or term-based intervals. This transformation smooths the data and amplifies temporal continuity, which inherently favors linear smoothing models like NAVIS. In scenarios with bursty or non-stationary behaviors, such as cold-start or short-term spikes, the benefit may vanish. Evaluation on finer time resolutions or non-aggregated event streams would better test model robustness to abrupt dynamics.\n\n6. While Table7 reports ablations for three core components, the paper omits finer interpretability analyses: (1) distributions and temporal trajectories of the learned gates $z_h$ and $z_s$; (2) feature-attribution or permutation-importance tests for $g$; and (3) quantitative evidence that $g$ captures regime shifts earlier than node-local dynamics. These analyses would strengthen the claim that the virtual global state encodes shared temporal trends.\n\n7. The paper reports only NDCG@10 and trains on top-20 samples. Metrics such as Recall, MRR should be included for a more complete assessment of affinity prediction quality.\n\n[1] DyGMamba: Efficiently Modeling Long-Term Temporal Dependency on Continuous-Time Dynamic Graphs with State Space Models. \n\n[2] DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BSV06qdSbx", "reviewer": "Reviewer_6w2j", "summary": "The authors consider the task of node affinity prediction in temporal networks, which they describe as more challenging than temporal link prediction because it concerns predicting node affinities for a set of possible neighbour nodes at a future time rather than the existence of only one link. They consider simple yet strong baselines for node affinity prediction; specifically, baselines as simple as predicting a recent ground-truth affinity vector for a future point in time, or a moving average over previous affinity vectors. Then, they argue (and show directly) that linear state space models can capture the heuristics defined by those simple baselines. However, they also show that temporal GNNs that use RNN, LSTM, or GRU memory cells suffer from fundamental limitations such that they cannot learn those simple baselines. To address this shortcoming of TGNNs, the authors develop a GNN based on linear state space models for learning node affinities and call it NAViS. On a range of benchmark datasets from TGB, the authors demonstrate that NAViS outperforms current TGNNs and simple heuristic baselines.\n\nI found the paper well written and the authors' arguments easy to follow. I believe the paper makes a valuable contribution, and I found it refreshing to see that the authors considered the possibility that TGNNs suffer from fundamental limitations, which, once discovered, allowed them to formulate a suitable solution. I was also happy to see that the authors highlighted the importance of \"aligning model inductive bias and training objectives with the task\", which I believe should be more often in focus than it tends to be.", "questions": "I have a couple of questions about points I did not fully understand when reading the paper, and I hope that the authors can help me clarify them.\n\n1. I am unsure whether the main questions from page 1 were answered: It became clear why heuristics outperform more sophisticated TGNNs, but I do not believe that you answered the question of whether we can push TGNNs to do better. But perhaps I have simply missed the answer. Could you elaborate whether your work suggests ways, or even a general recipe, for how to improve TGNNs for node affinity prediction?\n2. I am curious whether, as claimed in the first point of the contributions, we can really say that NAViS is more expressive than other TGNNs that use memory cells such as RNN, LSTM, or GRU. I believe that, at least in some regards, NAViS is more expressive because it is designed to be powerful enough to represent what linear state space models can do, and you showed that conventional memory-cell-based TGNNs cannot do that. However, I suspect that there are things that memory-cell-based TGNNs can do that NAViS cannot do---is that correct?\n3. Connected to the previous question, is there a way to check whether NAViS actually learns simple heuristics, such as persistent forecasting? Typically, expressivity and learnability are different aspects, and just because NAViS can express something, it doesn't necessarily mean that it can actually learn what is desired in practice. I understand that you used the Lambda Loss specifically to nudge the training in the right direction. Nevertheless, I'm wondering whether you have checked, or whether it is at all possible to check, that NAViS learns what you want it to learn?\n4. L.423 mentions that the performance of current TGNNs \"[suggests] an incompatible design choice of TGNNs for future node affinity prediction\". What precisely do you mean by \"incompatible design choice\" here? Does this refer back to using memory cells, or are there other unsuitable design choices you are referring to? I also seem to remember, but may be wrong, that not all of the TGNN baselines build on memory cells. If that's the case, can you speculate what could be a reason for their weak performance?\n5. I am also wondering whether it has been established that those simple baselines, such as persistent forecasting, generally work well in practice? Clearly, the empirical evaluation shows that this is the case at least in the considered networks. However, are there any other arguments to support this? Do we generally expect node affinities to remain quite stable over time, such that those simple heuristics work well? Are there scenarios where we expect a different behaviour, such that conventional TGNNs would perform better than NAViS?\n6. Could you provide an intuitive interpretation of the global vector g? I understand that it maintains previous node affinity vectors, but is that on a per-node basis, or is it a global vector? Would it make sense to think of it similarly to a vector of node centralities?\n\nMinor points\n- It seems like the wording in the abstract is somewhat misleading. The abstract states that the authors \"introduce a novel loss function for node affinity prediction\", which sounds like they designed it from the ground up. However, section 3.3 states that NAViS is trained with the so-called Lambda Loss, introduced by Burges et al. in 2006. Perhaps it would be appropriate to adjust the wording.\n- The sentence in l.89 seems to end abruptly: \"... they fail to recover the shared latent\"\n- Typo in l.423 \"deign choice\"", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written, and the authors' arguments are easy to follow.\n- The authors consider a relevant research question and identify fundamental limitations of TGNNs that prevent TGNNs from learning simple heuristics that are strong baselines in node affinity prediction.\n- The empirical evaluation, including an ablation study, demonstrates the good performance of the authors' proposed method.", "weaknesses": "- I believe there might be a claim that is not fully substantiated. The authors claim that \"any memory-based TGNN that applies standard memory cells cannot represent even the simplest heuristics -- persistent forecasting.\", which I agree with. However, they state that \"[TGNNs] lack the functional expressivity required for node affinity prediction\", which I find questionable. The only thing that was established is that they cannot do so by learning such simple baselines. But it has not been established that this is the only way to make good node affinity predictions.\n- The authors do not discuss the complexity of their approach, leaving it open whether it scales to large-scale networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p6Hq599GbT", "reviewer": "Reviewer_QArm", "summary": "This work considers the node affinity prediction on continuous-time dynamic graphs (CTDGs), a more challenging yet realistic task than the conevntional temporal link prediction. Based on some simple analysis regarding the (i) equivalance between heuristic and state space models as well as (ii) failure of widely-used cross-entroy loss, a new NAVIS (Node Affinity prediction model using Virtual State) method was then proposed, with some original designs of global virtual state and using regularized lambda loss. Experiments on large-scale dyanmic benchmark (i.e., TGB) validates the effectiveness of NAVIS.", "questions": "See **W1**-**W5**.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "**S1**. The overall presentation of this paper is well-written and well-motivated, and thus easy to read.\n\n**S2**. As claimed in the paper, node affinity prediction is a more chellenging yet realistic task compared with the conventional temporal link prediction.\n\n**S3**. The proposed method was evaluted on large-scale dyanmic graph benchmark (i.e., TGB)\n\n**S4**. This work anonymously provide its code to ensure the reproducibility of experiments.", "weaknesses": "**W1**. There are no discussions about some related work about the inference on weigthed dynamic graphs.\n\nAccording to the problem statement in Section 2, the proposed method considers weighted dynamic graphs, which each edge assocaited with a weight in addition to a timestamp. Different from conventional temporal link prediction (TLP) on unweighted graphs, there are some prior studies [1-3] consider TLP on weigthed dynamic topology (although they still adopt the data model of discret-time dynamic graphs), which are not discussed in this work. In particular, [1-3] can effectively tackle the wide-value-range and sparsity issues of weigthed dynamic graphs. Can the proposed method handle these issues?\n\n[1] GCN-GAN: A Non-linear Temporal Link Prediction Model for Weighted Dynamic Networks. InfoCom 2019.\n\n[2] An Advanced Deep Generative Framework for Temporal Link Prediction in Dynamic Networks. IEEE Transactions on Cybernetics 2020.\n\n[3] High-Quality Temporal Link Prediction for Weighted Dynamic Graphs via Inductive Embedding Aggregation. TKDE 2023.\n\n\n***\n**W2**. From the perspective of rigirous theoretical analysis, Theorem 1 and Theorem 2 are more likely to be facts rather than theorems, as they are staightforward. For Eq. (11), setting $\\phi$ to tanh is just one possible choice of the non-linear activation function. In addition, one can also set $\\phi$ to ReLU, LeakyReLU, etc. Will these settings change the main results of Theorem 2? It seems that the issue mentioned in Theorem 2 can be easily handled by first normalizing the input into [0, 1] or [-1, 1] and finally recovering to the original value range for output. Will this simple modification chanege the main results of Theorem 2?\n\nIt seems that Theorem 3 was proved only based on a specific toy example, which may not be a rigrious proof to show that there exist infinitely many triplets.\n\n\n***\n**W3**. Some details about the proposed method are missing.\n\nAfter reading Section 3.2, it remains unclear how to derive a feasble prediction result (e.g., normalized ${\\bf \\hat x}$) using the new structure defined in (14), as there is no ${\\bf \\hat x}$ in Eq. (14).\n\nThere are no formal equations to explictly describe how to use Eq. (14) to derive feasible outputs for a batch of nodes.\n\nIt seems that the final training loss of NAVIS was not foramlly given in tha main paper, which may be a combination of Eq. (16) and (18) with a tunable hyper-parameter.\n\nThere is no pseudo-code to summarize the overall training and inference procedures of NAVIS, in which some of the aforemention details can be checked.\n\n\n***\n**W4**. Current experiment setups may not fully validate the effectiveness of NAVIS. Some more further experiments are suggested.\n\nThe pre-experiments shown in Fig. 1 were evaluated based on MAE and mean rank, while main experiment results in Tables 1-4 were based on NDCG@10, which may not be consistent.\n\nThere seem no parameter analysis to test the effects w.r.t. different settings of hyper-paramters.\n\nThere seems no comparison about the training time, inference time, and memory consumption. As NAVIS may potentially result in a better trade-off between the inference quality and effciency of node affinity prediction, some further analysis about its efficiency is reommended.\n\nTable 5 does not provide details about the value range of edge weights. As mentioned in **W1**, wide-value-range issue may make the inference on weigthed graphs more challenging than that on unweighted topology.\n\n\n***\n**W5**. There are no discussion about the limitations of this work and possilbe solutions as future research directions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)