Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization

Abstract

We propose a scalable temporal latent space model for link prediction in dynamic social networks, where the goal is to predict links over time based on a sequence of previous graph snapshots. The model assumes that each user lies in an unobserved latent space and interactions are more likely to form between similar users in the latent space representation. In addition, the model allows each user to gradually move its position in the latent space as the network structure evolves over time. We present a global optimization algorithm to effectively infer the temporal latent space, with a quadratic convergence rate. Two alternative optimization algorithms with local and incremental updates are also proposed, allowing the model to scale to larger networks without compromising prediction accuracy. Empirically, we demonstrate that our model, when evaluated on a number of real-world dynamic networks, significantly outperforms existing approaches for temporal link prediction in terms of both scalability and predictive power.

Technical report for paper "Scalable Temporal Latent Space Inference for Link Prediction in Dynamic Social Networks" that appears in IEEE Transactions on Knowledge and Data Engineering 2016

References in corpus (4)

• What's in a crowd? Analysis of face-to-face behavioral networks
• Latent Space Models for Dynamic Networks
• Nonparametric Link Prediction in Dynamic Networks
• Tripartite Graph Clustering for Dynamic Sentiment Analysis on Social Media

Cited by in corpus (41)

• Graph Embedding Techniques, Applications, and Performance: A Survey
• Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks
• dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning
• EvoKG: Jointly Modeling Event Time and Network Structure for Reasoning over Temporal Knowledge Graphs
• GC-LSTM: Graph Convolution Embedded LSTM for Dynamic Link Prediction
• Time2Graph: Revisiting Time Series Modeling with Dynamic Shapelets
• Representation Learning for Dynamic Graphs: A Survey
• GloDyNE: Global Topology Preserving Dynamic Network Embedding
• Link prediction with hyperbolic geometry
• Recurrent Event Network: Autoregressive Structure Inference over Temporal Knowledge Graphs
• E-LSTM-D: A Deep Learning Framework for Dynamic Network Link Prediction
• Capturing Edge Attributes via Network Embedding
• Learning Continuous System Dynamics from Irregularly-Sampled Partial Observations
• Mining and Forecasting Career Trajectories of Music Artists
• Learning Dynamic Embeddings from Temporal Interactions
• Dynamic Hidden-Variable Network Models
• Models for Capturing Temporal Smoothness in Evolving Networks for Learning Latent Representation of Nodes
• Link prediction in dynamic networks using random dot product graphs
• EasyDGL: Encode, Train and Interpret for Continuous-time Dynamic Graph Learning
• Dynamic Node Embeddings from Edge Streams
• Spectral embedding for dynamic networks with stability guarantees
• Dynamic Network Embeddings for Network Evolution Analysis
• H-VGRAE: A Hierarchical Stochastic Spatial-Temporal Embedding Method for Robust Anomaly Detection in Dynamic Networks
• EPNE: Evolutionary Pattern Preserving Network Embedding
• DynWalks: Global Topology and Recent Changes Awareness Dynamic Network Embedding
• Temporal Network Embedding via Tensor Factorization
• Understanding and Predicting Delay in Reciprocal Relations
• ForeSeer: Product Aspect Forecasting Using Temporal Graph Embedding
• TSAM: Temporal Link Prediction in Directed Networks based on Self-Attention Mechanism
• Label Propagation on K-partite Graphs with Heterophily
• Representing Social Networks as Dynamic Heterogeneous Graphs
• Temporal Network Embedding with Micro- and Macro-dynamics
• Temporal Network Representation Learning via Historical Neighborhoods Aggregation
• Robust Dynamic Network Embedding via Ensembles
• ConvDySAT: Deep Neural Representation Learning on Dynamic Graphs via Self-Attention and Convolutional Neural Networks
• Subset Node Representation Learning over Large Dynamic Graphs
• Unifying Local and Global Change Detection in Dynamic Networks
• SPAN: Subgraph Prediction Attention Network for Dynamic Graphs
• TME-BNA: Temporal Motif-Preserving Network Embedding with Bicomponent Neighbor Aggregation
• FeatureNorm: L2 Feature Normalization for Dynamic Graph Embedding
• Multi-View Dynamic Heterogeneous Information Network Embedding