A Deep Learning Approach to Link Prediction in Dynamic Networks

By Xiaoyi Li, Nan Du, Kang Li, Jing Gao, Aidong Zhang. 2014

163 citations recorded by the source corpus.

Time varying problems usually have complex underlying structures represented as dynamic networks where entities and relationships appear and disappear over time. The problem of efficiently performing dynamic link inference is extremely challenging due to the dynamic nature in massive evolving networks especially when there exist sparse connectivities and nonlinear transitional patterns. In this paper, we propose a novel deep learning framework, i.e., Conditional Temporal Restricted Boltzmann Machine (ctRBM), which predicts links based on individual transition variance as well as influence introduced by local neighbors. The proposed model is robust to noise and have the exponential capability to capture nonlinear variance. We tackle the computational challenges by developing an efficient algorithm for learning and inference of the proposed model. To improve the efficiency of the approach, we give a faster approximated implementation based on a proposed Neighbor Influence Clustering algorithm. Extensive experiments on simulated as well as real-world dynamic networks show that the proposed method outperforms existing algorithms in link inference on dynamic networks.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

node2vec: Scalable Feature Learning for Networks (2016, background): “Finally, for both node and edge based prediction tasks, there is a body of recent work for supervised feature learning based on existing and novel graph-speciﬁc deep network architectures [15, 16, 17, 31, 39].”
Predicting multicellular function through multi-layer tissue networks (2017, background): “Finally, there exists recent work for task-dependent feature learning based on graph-specific deep network architectures (Li et al., 2015; Xiaoyi et al., 2014; Wang et al., 2016a; Zhai and Zhang, 2015).”
Differential Privacy Preservation for Deep Auto-Encoders: an Application of Human Behavior Prediction (2016, background): “In fact, the dPAH model is competitive even with privacy non-enforcing models such as CRBM and SctRBM.”
Link prediction in social networks: the state-of-the-art (2014, background): “…evolving networks with sparse connectivities and nonlinear transitional patterns, Li et al. proposed a deep learning framework called conditional temporal restricted Boltzmann machine [127], which predicts links based on individual transition variance and inﬂuence introduced by local neighbors.”
Learning the Structural Vocabulary of a Network (2017, methodology): “Recently, DL was used to cluster graphs by first computing a similarity measure between nodes in the graph and then using deep autoencoders to find a low-dimensional embedding of the similarity matrix (Tian, Gao, Cui, Chen, & Liu, 2014); DL has also been used for learning social representations of v”
LRBM: A Restricted Boltzmann Machine Based Approach for Representation Learning on Linked Data (2014, background): “Therefore, in Eq.14, instead of shifting the activity level of each unit of the link matrix, the model centers the activity levels with means and variances and model the continuous characteristics of weights in weighted linked data.”
Relational Deep Learning: A Deep Latent Variable Model for Link Prediction (2017, background): “(Li et al. 2014; Wang, Cui, and Zhu 2016) deal with the link prediction problem in dynamic/static networks.”
Dropout Training of Matrix Factorization and Autoencoder for Link Prediction in Sparse Graphs (2015, background): “Recently, Chen and Zhang [7] propose a variant of linear AE with marginalized feature noise for link prediction, and Li et al. [11] apply RBM to link prediction in dynamic graphs.”
Substructure Assembling Network for Graph Classification (2018, background): “…as an important source of features for tasks such as node classification (Perozzi, Al-Rfou, and Skiena 2014; Chang et al. 2015; Grover and Leskovec 2016), link prediction (Li et al. 2014; Wang, Cui, and Zhu 2016), and community detection (Tian et al. 2014; Ribeiro, Saverese, and Figueiredo 2017).”
Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks (2019, background): “Accurate real-time recommendation of items and predicting change in the state of users are fundamental problems in these domains [5, 6, 22, 30, 36, 40, 43].”
Heterogeneous Network Embedding via Deep Architectures (2015, background): “Moreover, work in computer vision and speech [18] has shown that layer-wise RBM training is inefﬁcient for large-scale settings when compared to DNNs and CNNs.”