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:
- 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.
- Loss Mismatch: Most models optimize for Cross-Entropy, treating neighbors as independent classes rather than items to be ranked.
- Local Blindness: Models often focus exclusively on local neighborhoods, failing to account for global, network-wide shifts.
- 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.
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.
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