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:
- Real Observed Network (RON): Represents the current state of the network in the real world.
- Dynamic Memory Network (DMN): A "shadow" graph that stores links deleted from the RON.
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.
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