Revisiting Node Affinity Prediction in Temporal Graphs

Krishna Sri Ipsit Mantri, Or Feldman, Moshe Eliasof, Chaim BaskinarXiv 2025 · DOI · arXiv

In the evolving landscape of temporal graph analysis, researchers have encountered a counterintuitive phenomenon: sophisticated Temporal Graph Neural Networks (TGNNs) often struggle to outperform simple heuristics. This "heuristic gap" suggests that current deep learning approaches may be overlooking fundamental properties of how node interactions evolve. This paper introduces NAVIS (Node Affinity prediction model using Virtual State), a lightweight architecture designed to bridge this gap by combining the robustness of linear heuristics with the flexibility of learnable state-space models.

The Heuristic Gap in Node Affinity

Node affinity prediction involves forecasting the strength of future interactions between nodes in a dynamic network. Unlike binary link prediction, this task requires generating a full ranking of potential neighbors. Despite the complexity of models like TGN or DyGFormer, simple baselines such as Persistent Forecast (assuming the future mirrors the immediate past) or Moving Averages frequently yield superior results.

The authors identify four primary reasons for this performance discrepancy:

  1. Expressivity Constraints: Standard non-linear memory cells (RNNs, LSTMs, GRUs) are mathematically unable to represent simple linear heuristics because their activation functions (e.g., sigmoid, tanh) have bounded ranges, whereas affinity spaces are often unbounded.
  2. Loss Mismatch: Most models optimize for Cross-Entropy, treating neighbors as independent classes rather than items to be ranked.
  3. Local Blindness: Models often focus exclusively on local neighborhoods, failing to account for global, network-wide shifts.
  4. Information Loss: Fixed-size buffers and batch processing often discard long-term interaction data essential for accurate forecasting.

The NAVIS Architecture

NAVIS addresses these issues through a streamlined architecture built on three pillars: a linear State Space Model (SSM), a virtual global state, and a rank-aware loss function.

The NAVIS architecture utilizes linear SSMs and a virtual global state (g) to update node representations (h) and predict affinity (s).

Linear SSMs and Heuristics

Instead of complex non-linear gates, NAVIS employs a learnable linear SSM. The authors prove that common heuristics, such as Exponential Moving Averages, are restricted cases of linear SSMs. By adopting this structure, NAVIS inherently possesses the capacity to represent these robust heuristics while remaining fully learnable.

Virtual Global State ($g$)

To overcome "local blindness," NAVIS maintains a global buffer of recent affinity vectors. This "Virtual State" allows the model to adjust individual node predictions based on broader network trends, such as viral topics on social platforms or systemic shifts in financial markets.

Rank-Based Learning

To align the training objective with the evaluation metric, NAVIS replaces standard Cross-Entropy with Lambda Loss and Pairwise Margin Regularization. This approach prioritizes the relative ordering of nodes, which is critical for effective affinity prediction.

Experimental Results

NAVIS was evaluated against a suite of state-of-the-art TGNNs and heuristics across multiple datasets from the Temporal Graph Benchmark (TGB). The results demonstrate a significant performance leap over existing methods.

Performance comparison on TGB datasets showing NAVIS (ours) consistently outperforming both heuristics and complex TGNN baselines.

As shown in the table above, NAVIS achieves state-of-the-art results across all benchmarks. On the tgbn-trade dataset, it improved upon the best-performing TGNN (TGNv2) by +12.8% in NDCG@10. Remarkably, NAVIS achieves these results with extreme computational efficiency. For instance, on the tgbn-genre dataset, NAVIS utilizes only ~2,500 parameters, compared to the 6.5 million parameters required by TGNv2.

Conclusion

NAVIS demonstrates that for node affinity prediction, "more complex" does not necessarily mean "better." By framing heuristics as linear SSMs and incorporating global context, NAVIS provides a theoretically grounded and highly efficient solution that outperforms models orders of magnitude larger. Future work will explore integrating non-linear components and more sophisticated global state aggregation mechanisms to further enhance the model's predictive power.

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. Our source code is available at https://github.com/orfeld415/NAVIS
BibTeX
@misc{mantri2025revisiting,
  author = {Krishna Sri Ipsit Mantri and Or Feldman and Moshe Eliasof and Chaim Baskin},
  title = {{Revisiting Node Affinity Prediction in Temporal Graphs}},
  year = {2025},
  eprint = {2510.06940},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.06940},
}
Figure