NeLSTM: Bridging Network Embedding and LSTMs for Dynamic Link Prediction

TL;DR

NeLSTM is a hybrid framework designed to predict future connections in dynamic social networks. By combining a Time Aging Algorithm (TAA), LINE embedding, and LSTM networks, the model captures both the structural topology and the temporal decay of social interactions. It effectively handles multi-link networks and outperforms traditional baselines with AUC scores exceeding 0.90 on several real-world benchmarks.

Background: The Moving Target of Social Ties

In the real world, social networks are never static. Friendships form, professional collaborations evolve, and communication patterns shift over time. Most early research treated link prediction as a static problem: "Given the graph now, who will connect next?" However, this ignores the velocity and acceleration of social bonding. The core challenge is treating the network not as a single snapshot, but as a continuous evolution where past interactions gradually lose relevance.

Problem & Motivation: The Decay of Influence

The authors identify a critical gap: existing models either fail to handle the complexity of "multi-link" networks (where nodes interact many times) or they cannot efficiently scale. Their key insight is the Time Aging effect: a link formed five minutes ago is a much stronger predictor of future behavior than a link formed five years ago.

To solve this, they propose an exponential decay function to weight past interactions, providing a nuanced input for temporal modeling rather than binary 0/1 snapshots.

Methodology: From Snapshots to Trajectories

The NeLSTM architecture follows a three-stage pipeline:

1. Time Aging Algorithm (TAA): It transforms raw "edgelists" into weighted snapshots. Using a time attenuation coefficient $heta$, it calculates the impact of past links: $Impact=e^{-heta\cdot Interval}$.
2. Network Embedding (LINE): Instead of raw adjacency matrices, the model uses LINE to map nodes into a $d$-dimensional latent space. This captures both 1st-order (direct ties) and 2nd-order (shared neighbors) proximities.
3. Temporal Prediction (LSTM): The sequence of embeddings is fed into an LSTM. The LSTM learns the "movement" of nodes in the latent space, predicting the node vector at time $t+1$.

The final similarity score between two nodes is computed via the inner product of their predicted vectors, representing the probability of a future link.

Experimental Results: The Power of Recurrence

The authors tested NeLSTM against six baselines, including classic heuristics like Common Neighbors (CN) and Preferential Attachment (PA), and a non-recurrent version of their own model (PNETAC).

Key Performance Highlights:

• Superiority of LSTMs: On the arXiv hep-th dataset (a complex multi-link network), NeLSTM achieved an AUC of 0.87, while PNETAC (no LSTM) collapsed to 0.31. This proves that simply embedding the last snapshot is insufficient; the history of the embedding is what matters.
• Robustness: NeLSTM maintained high accuracy across dramatically different scales, from the small "Infectious" dataset (410 nodes) to the large "Facebook" dataset (63,000+ nodes).

Parameter Sensitivity

The model's performance is sensitive to the embedding dimension ($d$) and the decay coefficient ($heta$). The authors found that a dimension of approximately 100 provides a sweet spot between representational power and over-fitting.

Critical Analysis & Conclusion

NeLSTM successfully demonstrates that temporal link prediction is best handled by combining topology-preserving embeddings with sequence-learning architectures.

Strengths:

• The TAA algorithm is a simple yet elegant way to handle multi-link networks.
• The use of LINE ensures the model can scale to much larger networks than matrix factorization methods.

Limitations:

• The model relies on a fixed $heta$. In reality, different types of social ties might decay at different rates (e.g., family vs. casual acquaintances).
• The inner product similarity assumes a linear relationship in the latent space; exploring non-linear decoders might further boost performance.

In conclusion, NeLSTM sets a strong baseline for dynamic graph representation learning, proving that "how we got here" is just as important as "where we are" in the social fabric.