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:
- 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. - Loss Mismatch: Most models use Cross-Entropy loss, which treats neighbors as distinct categories rather than items in a ranked list.
- Ignoring Global Dynamics: Local neighborhood sampling misses "regime shifts" or network-wide trends that affect all nodes simultaneously.
- 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.
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.
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