Joint Learning of Evolving Links for Dynamic Network Embedding

Aakas Zhiyuli, Xun Liang, Yanfang Chen, Peng Shu, Xiaoping ZhouAAAI 2018 · DOI

Introduction

Real-world networks, such as social media platforms and recommendation systems, are inherently dynamic. Nodes and links are constantly being added or removed. Traditional network embedding methods like DeepWalk or node2vec are designed for static graphs and struggle to adapt to these temporal changes. While some dynamic embedding approaches have been proposed, they typically focus exclusively on link additions. When a link is deleted, these models lose the historical structural information it provided.

The RDEM (Joint Learning of Added and Deleted Links) framework addresses this gap by treating link deletions not as lost data, but as valuable information to be preserved in a "Dynamic Memory Network."

Methodology: The RDEM Framework

The core of RDEM is the "Law of Conservation of Dynamic Links," which posits that the total structural information of a network should be maintained even as links shift between active and inactive states. The framework operates using two parallel graph structures:

  1. Real Observed Network (RON): Represents the current state of the network in the real world.
  2. Dynamic Memory Network (DMN): A "shadow" graph that stores links deleted from the RON.
The RDEM framework illustrating the interaction between the Real Observed Network and the Dynamic Memory Network over time.

Online Learning and Feature Merging

As the network evolves from timestamp $T$ to $T+1$, RDEM performs incremental updates:

  • Update RON: New links are added to the RON, and node vectors are updated using a Local Searching (LS) algorithm.
  • Update DMN: Deleted links are transferred from the RON to the DMN. The LS algorithm updates node representations within the DMN to reflect these changes.
  • Feature Merge: For nodes present in both networks, the model calculates a merged representation (typically the mean). This ensures that the "memory" of deleted links continues to inform the node's current embedding, preventing structural "drift" as the network evolves.

Experimental Evaluation

The model was evaluated on two large-scale dynamic datasets: SCnet (a User-User relationship graph based on shared clicks) and Google+ (a social connection network). The primary task was future link prediction, measured by the Area Under Curve (AUC) metric.

Key Results

RDEM consistently outperformed baseline methods such as DeepWalk (DW) and LINE across all tested timestamps.

Performance comparison (AUC) of RDEM against DeepWalk and LINE on SCnet and Gplus datasets.

As shown in the results, the performance advantage of RDEM grows over time. On the SCnet dataset, the gap between RDEM and DeepWalk increased from 1.8% at timestamp 1 to nearly 4% by timestamp 3. This suggests that as more links are deleted, the structural history preserved in the DMN becomes increasingly critical for maintaining accurate embeddings.

Conclusion

RDEM demonstrates that "deletions are data." By maintaining a Dynamic Memory Network and applying a conservation law to links, the framework preserves the structural context of evolving graphs more effectively than methods that only track additions. This approach provides a robust foundation for various dynamic network tasks, including community discovery and influence prediction. Future work may explore the computational scaling of the DMN and more sophisticated handling of node deletions.

Summary updated

BibTeX
@inproceedings{zhiyuli2018joint,
  author = {Aakas Zhiyuli and Xun Liang and Yanfang Chen and Peng Shu and Xiaoping Zhou},
  title = {{Joint Learning of Evolving Links for Dynamic Network Embedding}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12153},
}
Figure