Revisiting Node Affinity Prediction in Temporal Graphs

Basic Information

• Paper ID: 2510.06940
• Title: Revisiting Node Affinity Prediction in Temporal Graphs
• Authors: Krishna Sri Ipsit Mantri, Or Feldman, Moshe Eliasof, Chaim Baskin
• Classification: cs.LG (Machine Learning)
• Publication Status: Preprint. Under review
• Paper Link: https://arxiv.org/abs/2510.06940
• Code Link: https://github.com/orfeld415/NAVIS

Abstract

Node affinity prediction is an important task in temporal graph learning with widespread applications in social networks, financial networks, and recommendation systems. Although recent research has addressed node affinity prediction by adapting state-of-the-art dynamic link prediction models, simple heuristic methods such as persistent forecasting and moving averages consistently outperform these complex models. This paper analyzes the training challenges faced by current temporal graph neural networks (TGNNs) in node affinity prediction tasks and proposes corresponding solutions. Combining these solutions, the authors develop NAVIS (Node Affinity prediction model using Virtual State), which leverages the equivalence between heuristic methods and state-space models to achieve node affinity prediction.

Research Background and Motivation

Problem Definition

Node affinity prediction aims to predict the interaction intensity between a given node and all other nodes at a future time point, which differs from traditional link prediction tasks. Link prediction focuses on whether specific edges will appear, while affinity prediction requires complete ranking of all potential neighbors, making the task more challenging yet more aligned with practical application requirements.

Core Problems

1. Performance Paradox: Complex temporal graph neural networks (TGNNs) underperform simple heuristic methods on node affinity prediction tasks
2. Expressiveness Limitations: Existing TGNNs cannot represent basic operations such as simple moving averages
3. Loss Function Mismatch: Cross-entropy loss is misaligned with the ranking nature of affinity prediction tasks
4. Insufficient Information Utilization: TGNNs fail to adequately leverage global temporal dynamics and long-term dependency information

Research Motivation

Through theoretical analysis, the authors discovered that simple heuristic methods are actually special cases of linear state-space models (SSMs), providing a theoretical foundation for designing more powerful TGNN architectures.

Core Contributions

1. Theoretical Contribution: Proves that simple heuristic methods are special cases of linear SSMs and designs TGNN architectures based on this connection that can generalize heuristic methods
2. Architectural Innovation: Proposes the NAVIS model, combining virtual global state and linear state-space mechanisms to effectively solve node affinity prediction problems
3. Loss Function Improvement: Analyzes the limitations of cross-entropy loss in affinity prediction and proposes ranking-based Lambda loss as an alternative
4. Experimental Validation: Verifies the effectiveness of the method on TGB benchmarks and multiple datasets, consistently outperforming existing methods and heuristic baselines

Methodology Details

Task Definition

Given a continuous-time dynamic graph (CTDG): $G_t = \{(u_j, v_j, \tau_j, w_j)\}_{j=1}^{J(t)}$

For a query node $u \in V$ and future time $t^+ > t$, the objective is to predict an affinity score vector: $s = F_\theta(u, G_t, t^+) \in \mathbb{R}^{|V|}$

Theoretical Foundation

Theorem 1 (Linear SSMs Generalize Basic Heuristics): Let $H$ be the set of basic heuristics (PF, SMA, EMA), and $F_{\text{lin-SSM}}$ be the set of mappings realizable by linear SSMs. Then: $H \subsetneq F_{\text{lin-SSM}}$

Theorem 2 (Expressiveness Limitations of RNN/LSTM/GRU): Standard RNN, LSTM, or GRU units cannot represent the most basic persistent forecasting (PF) heuristic. That is, for all input sequences, there do not exist parameters such that $h_i = x_i$.

NAVIS Model Architecture

NAVIS employs a linear state-space mechanism to maintain each node's state $h \in \mathbb{R}^d$ and virtual global state $g \in \mathbb{R}^d$:

zh = σ(Wxh*x + Whh*hi-1 + bh)
hi = zh ⊙ hi-1 + (1-zh) ⊙ x
zs = σ(Wxs*x + Whs*hi + Wgs*g + bs)  
s = zs ⊙ hi + (1-zs) ⊙ x

Where:

• $x$: Previous affinity vector
• $h_{i-1}, h_i$: Previous and updated states
• $g$: Virtual global vector
• $s$: Predicted affinity vector
• $z_h, z_s$: Adaptive gating mechanisms

Key Design Features

1. Linear Update Mechanism: Maintains conceptual similarity to EMA while allowing runtime adaptive adjustment
2. Virtual Global State: Captures global trends through maintaining a buffer of recent affinity vectors
3. Compatible with t-Batch Mechanism: Does not depend on neighbor hidden states, supporting efficient batch processing
4. Scalability: Adapts to large-scale graphs through sparsification of the affinity prediction pipeline

Loss Function Design

Problem Analysis: Theorem 3 (Suboptimality of Cross-Entropy for Ranking): There exist infinitely many triples $(y, s_1, s_2)$ where $\text{rank}(s_1) = \text{rank}(y)$ and $\text{rank}(s_2) \neq \text{rank}(y)$, but $\ell_{CE}(s_1, y) > \ell_{CE}(s_2, y)$.

Solution: Employ Lambda loss: $\ell_{\text{Lambda}}(s,y) = \sum_{y_i > y_j} \log_2\left(\frac{1}{1 + e^{-\sigma(s_{\pi_i} - s_{\pi_j})}}\right) \delta_{ij} |A_{\pi_i} - A_{\pi_j}|$

Combined with pairwise margin regularization: $\ell_{\text{Reg}}(s,y) = \sum_{y_i > y_j} \max(0, -(s_{\pi_i} - s_{\pi_j}) + \Delta)$

Experimental Setup

Datasets

TGB Datasets:

• tgbn-trade: UN country-to-country agricultural trade network 1986-2016 (255 nodes, 468,245 edges)
• tgbn-genre: User-music genre interaction network (1,505 nodes, 17,858,395 edges)
• tgbn-reddit: User-subreddit interaction network (11,766 nodes, 27,174,118 edges)
• tgbn-token: Wallet-cryptocurrency token interaction network (61,756 nodes, 72,936,998 edges)

Converted Link Prediction Datasets:

• Wikipedia: Editor-article interaction network
• Flights: Airport route network during COVID-19
• USLegis: US Senate collaboration network
• UNVote: United Nations General Assembly voting network

Evaluation Metrics

• Primary Metric: NDCG@10 (Normalized Discounted Cumulative Gain)
• Experimental Setup: 70%-15%-15% temporal split, 50 epochs, batch size 200

Baseline Methods

• Heuristic Methods: Persistent Forecast, Moving Average, Historical Average
• TGNN Methods: JODIE, TGAT, CAWN, TCL, GraphMixer, DyGFormer, DyRep, TGN, TGNv2

Experimental Results

Main Results

TGB Dataset Performance (NDCG@10):

• tgbn-trade: NAVIS 0.863 vs best baseline TGNv2 0.735 (+17.4%)
• tgbn-genre: NAVIS 0.520 vs best baseline TGNv2 0.469 (+10.9%)
• tgbn-reddit: NAVIS 0.552 vs best baseline TGNv2 0.507 (+8.9%)
• tgbn-token: NAVIS 0.444 vs best baseline TGNv2 0.294 (+51.0%)

Converted Dataset Performance:

• Wikipedia: NAVIS 0.573 vs TGNv2 0.433 (+32.3%)
• Flights: NAVIS 0.499 vs TGNv2 0.299 (+66.9%)
• USLegis: NAVIS 0.347 vs TGNv2 0.253 (+37.2%)
• UNVote: NAVIS 0.952 vs TGNv2 0.813 (+17.1%)

Ablation Studies

Ablation studies validate the importance of each component:

• Linear State Update vs GRU: 0.863 vs 0.850 on tgbn-trade
• Including Global Vector: Improvement of approximately 1-2 percentage points
• Ranking Loss vs Cross-Entropy: Significant performance improvement

Key Findings

1. Heuristic Advantage Confirmed: Simple heuristic methods indeed outperform complex TGNNs
2. Global Information Importance: Virtual global state effectively captures network-level trends
3. Loss Function Matching: Ranking-aware loss is crucial for affinity prediction
4. Consistent Improvement: NAVIS achieves consistent improvements across all datasets

Related Work

Temporal Graph Expressiveness

Traditional research focuses on structural expressiveness measured by WL tests, while this paper addresses functional expressiveness—the ability to represent specific mathematical operations.

Heuristic Methods and State-Space Models

Recent research has found that simple heuristic methods outperform complex TGNNs on multiple benchmarks. This paper is the first to explicitly leverage the formal equivalence between heuristics and SSMs for architecture design.

Temporal Graph Neural Networks

Existing methods include memory-based (TGN, DyRep) and non-memory-based (DyGFormer, GraphMixer) architectures, but none effectively address the specific requirements of node affinity prediction.

Conclusions and Discussion

Main Conclusions

1. The inadequacy of existing TGNNs in node affinity prediction stems from expressiveness limitations and training objective mismatch
2. Linear state-space models provide a theoretical framework for generalizing heuristic methods
3. NAVIS effectively solves node affinity prediction by combining virtual global state and ranking-aware loss

Limitations

1. Complex Dependency Modeling: Still difficult to model complex multi-hop dependencies
2. Scalability: Parameter scale grows linearly with the number of nodes, requiring sparsification strategies
3. Theoretical Completeness: Not all related issues have been fully resolved

Future Directions

1. Extension to more complex temporal dependency modeling
2. Improved scalability for large-scale graphs
3. Exploration of nonlinear state-space models

In-Depth Evaluation

Strengths

1. Solid Theoretical Contribution: Rigorously establishes the connection between heuristic methods and SSMs through mathematical proofs
2. In-Depth Problem Analysis: Systematically analyzes the inadequacies of TGNNs in node affinity prediction
3. Reasonable Method Design: NAVIS design has clear theoretical justification and practical considerations
4. Comprehensive Experiments: Extensive experiments on multiple datasets validate method effectiveness
5. Clear Writing: Well-structured paper with accurate technical descriptions

Weaknesses

1. Limited Novelty: Primarily applies existing theory (SSMs) to a new problem domain
2. Experimental Setup: Some datasets are relatively small-scale; large-scale experiments are limited
3. Comparison Fairness: Potential implementation differences with baseline methods
4. Generalization Ability: Requires validation on more diverse graph types

Impact

1. Academic Value: Provides new theoretical perspectives for temporal graph learning
2. Practical Value: Direct applicability in recommendation systems and other practical applications
3. Reproducibility: Complete code implementation provided
4. Inspirational Value: Offers valuable insights for subsequent research

Applicable Scenarios

1. Recommendation Systems: User-to-item affinity prediction
2. Social Networks: User interaction intensity prediction
3. Financial Networks: Trading relationship strength prediction
4. Supply Chain Networks: Collaboration relationship prediction

Overall Assessment: This is a high-quality research paper that reveals the inadequacies of existing methods through in-depth theoretical analysis and proposes effective solutions. The NAVIS model is well-designed, experimental results are convincing, and it makes positive contributions to the temporal graph learning field. The paper's primary value lies in providing new theoretical perspectives and a practical methodological framework.