Revisting Node Affinity Prediction In Temporal Graphs

Or Feldman, Krishna Sri Ipsit Mantri, Moshe Eliasof, Chaim BaskinICLR 2026 · OpenReview

In the realm of temporal graph learning, a surprising paradox exists: sophisticated Temporal Graph Neural Networks (TGNNs) frequently underperform compared to dead-simple heuristics like "Moving Average" or "Persistent Forecast" when predicting how strongly nodes will interact in the future.

While most research focuses on link prediction (deciding if an edge will exist between two nodes), many real-world applications—such as recommender systems or financial tracking—care more about node affinity prediction. This task involves forecasting the strength or intensity of future interactions and ranking potential neighbors accordingly.

To address the performance gap between complex models and simple heuristics, researchers have introduced NAVIS (Node Affinity prediction with VIrtual State). NAVIS bridges this gap by framing heuristics as State Space Models (SSMs), incorporating a virtual global state to capture network-wide trends, and utilizing a specialized rank-based loss function.

Why Do Complex TGNNs Fail at Affinity Prediction?

The authors identify four key reasons why state-of-the-art models like TGN or DyGFormer struggle to beat basic heuristics:

  1. The Expressivity Gap: Standard memory cells (RNNs, LSTMs, GRUs) mathematically cannot represent a simple linear moving average because of their bounded, non-linear activation functions (like tanh). They cannot simply pass through an unbounded input value, which is exactly what a persistent forecast requires.
  2. Loss Mismatch: Most models use Cross-Entropy loss, which treats neighbors as distinct categories rather than items in a ranked list.
  3. Ignoring Global Dynamics: Local neighborhood sampling misses "regime shifts" or network-wide trends that affect all nodes simultaneously.
  4. Information Loss: Batch processing often skips intermediate state updates, leading to "stale" node memories.

The NAVIS Approach

Instead of trying to "beat" heuristics with deeper layers, the authors suggest embedding the logic of heuristics directly into the architecture. NAVIS introduces three main innovations to achieve this:

  • SSM-based Architecture: The authors prove that common heuristics are actually special cases of linear State Space Models (SSMs). NAVIS uses a learnable linear SSM structure to maintain node states, ensuring it retains the "good" inductive bias of a moving average while having the flexibility to exceed it.
  • Virtual Global State ($g$): To capture trends that affect the whole network (e.g., a macroeconomic shift in a financial graph), NAVIS maintains a global buffer. This "virtual state" is aggregated and used to influence individual node predictions, recovering shared latent dynamics that local heuristics miss.
  • Rank-Based Loss: Because node affinity is fundamentally a ranking task, NAVIS replaces Cross-Entropy with a Lambda Loss combined with a Pairwise Margin Regularization. This forces the model to focus on the relative order of nodes rather than just absolute prediction values.
The NAVIS architecture uses linear projections and a gated mechanism to update node states and predict affinity scores using a global state.

Key Results

The model was rigorously evaluated on the Temporal Graph Benchmark (TGB)—specifically the node-ranking datasets tgbn-trade, tgbn-genre, tgbn-reddit, and tgbn-token—as well as converted link prediction datasets like Wikipedia and Flights.

NAVIS consistently outperformed both state-of-the-art TGNNs and baseline heuristics across all tested datasets. Notably, on the tgbn-trade dataset, NAVIS improved upon the best-performing TGNN (TGNv2) by a massive +12.8%. Even in strict settings where heuristics are traditionally strongest (using only previous ground-truth labels), NAVIS maintained a clear lead, proving it doesn't just mimic heuristics but actively improves upon them.

Performance comparison on TGB datasets. NAVIS (bottom row) significantly outperforms all other TGNN baselines and heuristics.

Limitations and Future Work

While NAVIS sets a new standard for node affinity prediction, the authors note a few areas for future refinement:

  • Linearity Constraint: NAVIS currently computes affinities as linear combinations. While this provides a strong inductive bias, it might struggle with highly complex, non-linear interaction patterns.
  • Global State Mechanism: The current global state relies on a simple recency-based buffer. More sophisticated aggregation, such as attention-based mechanisms, could potentially capture global trends with even greater accuracy.
  • Multi-hop Dependencies: The model is primarily focused on temporal dynamics and does not explicitly model complex multi-hop structural dependencies within the graph.

Summary updated

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.
BibTeX
@inproceedings{feldman2026revisting,
  author = {Or Feldman and Krishna Sri Ipsit Mantri and Moshe Eliasof and Chaim Baskin},
  title = {{Revisting Node Affinity Prediction In Temporal Graphs}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=6UvkemEgK3},
}
Figure