Link Prediction and Unlink Prediction on Dynamic Networks

Christina Muro, Boyu Li, Kun He

TL;DR

This paper introduces LULS, a novel algorithm for predicting both the formation (link prediction) and dissolution (unlink prediction) of relationships in dynamic networks. By modeling relationships as a combination of stable, long-term connections and transient, short-term interactions, LULS achieves state-of-the-art performance on real-world dynamic network datasets.

What Problem Does This Paper Address?

Many real-world networks, such as social networks, collaboration networks, and communication networks, are not static but evolve over time. Nodes and edges can be added or removed, making it crucial to understand and predict these changes. While link prediction (predicting new connections) has been extensively studied, the complementary problem of unlink prediction (predicting when existing connections will disappear) has received less attention, despite its importance in understanding network dynamics. Existing methods often focus on either the network's structure or its temporal evolution, but rarely combine both effectively. Furthermore, many methods overlook the intrinsic geometric structure of the data, limiting their predictive power. This paper aims to bridge this gap by proposing a unified framework for both link and unlink prediction on dynamic networks that leverages both structural and temporal information, while also considering the network's geometric properties.

Methods

The proposed algorithm, LULS (Link and Unlink Prediction on Dynamic Networks), operates on the assumption that relationships in dynamic networks can be categorized into two types: long-term relations (stable connections) and short-term relations (transient interactions).

Here's a breakdown of the key techniques:

  • Topological Information Collection: For each snapshot of the dynamic network, LULS uses two random walk methods to capture higher-order structural information:
  • Light Lazy Random Walk (LLRW): A variant of random walk that retains some probability of staying at the current node, allowing for more robust topological information.
  • Modified Light Lazy Random Walk (MLLRW): An extension of LLRW that incorporates node degree centrality, biasing random walks towards higher-degree nodes.
  • Non-Negative Matrix Factorization (NMF): LULS employs NMF to learn two types of representations for nodes:
  • Global Representation Matrix (U): This matrix captures the long-term relations and is shared across all network snapshots, representing stable connections.
  • Temporary Representation Matrices (Vt): For each snapshot, a separate matrix captures the short-term relations and local topological information specific to that time point.
  • Graph Regularization: To enhance the global representation matrix (U) and ensure it captures more topological information, LULS incorporates a graph regularization term based on the higher-order topological matrices (Ht). This helps to preserve the geometric structure of the network.
  • Temporal Smoothness: A regularization term is applied to the temporary representation matrices (Vt) to ensure that node representations do not change drastically between consecutive snapshots, reflecting the temporal smoothness of relationships.
  • Prediction: After optimizing U and Vt, the similarity matrix for the future snapshot is computed by combining the latent factors. This similarity score is then used to predict whether a link will form or disappear.

Datasets

The LULS algorithm was evaluated on six real-world dynamic network datasets:

  • Facebook Forum: Private messages exchanged between Facebook users.
  • Reality Mining: Mobile phone call events between users at MIT.
  • Dublin: Human contact network based on proximity.
  • Hep-Th: Collaboration network from arXiv for high energy physics.
  • Facebook Messages: Messages exchanged between students at a university.
  • Haggle: Network reflecting proximity between people measured by wireless devices.

The paper does not mention the introduction of any newly benchmarked datasets.

Key Insights and Ideas

  • Dual Nature of Relationships: The core insight is that relationships in dynamic networks are not monolithic. Distinguishing between stable, long-term connections and fleeting, short-term interactions is crucial for accurate prediction.
  • Synergy of Structure and Time: Combining topological information (how nodes are connected) with temporal information (how these connections evolve) significantly improves prediction accuracy for both link formation and dissolution.
  • Importance of Unlink Prediction: The paper highlights that unlink prediction is as important as link prediction for understanding network dynamics, and that the factors influencing link formation are often inversely related to those causing link dissolution.
  • Geometric Structure Matters: Incorporating graph regularization to preserve the network's geometric structure enhances the learned representations and improves predictive performance.
  • Smoothness in Evolution: The assumption that node representations should evolve smoothly over time is a key factor in capturing temporal dynamics effectively.

Key Results

LULS consistently outperformed several state-of-the-art baselines on all six real-world dynamic network datasets for both link prediction and unlink prediction tasks.

  • Link Prediction: LULS achieved the highest AUC and AP scores across most datasets, demonstrating its ability to effectively integrate temporal and structural information. The paper notes that LULS performed particularly well on sparse graphs like Dublin.
  • Unlink Prediction: LULS also significantly outperformed baselines in unlink prediction. The results suggest that unlink prediction is more challenging than link prediction, as indicated by generally lower AUC scores for unlink prediction.
  • Effectiveness of Components: Experiments with different versions of LULS (varying the smoothness and constraint terms) showed that both components are beneficial, with the full LULS model (LULS1) generally performing best.

Limitations and Future Work

  • Node Set Assumption: The current implementation assumes that the set of nodes remains constant across snapshots, meaning newly added or removed nodes are not explicitly handled.
  • Computational Complexity: While the paper discusses the complexity, it notes that for very large networks, the matrix operations can still be computationally intensive, although sparsity helps.
  • Future Work: The authors suggest extending the model to handle dynamic node sets and exploring more advanced random walk variants or graph representation learning techniques. Further investigation into the interplay between long-term and short-term relations could also be a fruitful direction.

Summary updated

Abstract

Link prediction on dynamic networks has been extensively studied and widely applied in various applications. However, temporal unlink prediction, which also plays an important role in the evolution of social networks, has not been paid much attention. Accurately predicting the links and unlinks on the future network greatly contributes to the network analysis that uncovers more latent relations between nodes. In this work, we assume that there are two kinds of relations between nodes, namely long-term relation and short-term relation, and we propose an effective algorithm called LULS for temporal link prediction and unlink prediction based on such relations. Specifically, for each snapshot of a dynamic network, LULS first collects higher-order structure as two topological matrices by applying short random walks. Then, LULS initializes and optimizes a global matrix and a sequence of temporary matrices for all the snapshots by using non-negative matrix factorization (NMF) based on the topological matrices, where the global matrix denotes long-term relation and the temporary matrices represent short-term relations of snapshots. Finally, LULS calculates the similarity matrix of the future snapshot and predicts the links and unlinks for the future network. Additionally, we further improve the prediction results by using graph regularization constraints to enhance the global matrix, resulting that the global matrix contains a wealth of topological information and temporal information. The conducted experiments on real-world networks illustrate that LULS outperforms other baselines for both link prediction and unlink prediction tasks.
BibTeX
@article{muro2023link,
  author = {Christina Muro and Boyu Li and Kun He},
  title = {{Link Prediction and Unlink Prediction on Dynamic Networks}},
  journal = {IEEE Trans. Comput. Soc. Syst.},
  year = {2023},
  doi = {10.1109/tcss.2022.3162229},
}
Figure