Temporal Link Prediction Using Matrix and Tensor Factorizations

By Daniel M. Dunlavy, Tamara G. Kolda, Evrim Acar. TKDD, 2010

561 citations recorded by the source corpus.

The data in many disciplines such as social networks, Web analysis, etc. is link-based, and the link structure can be exploited for many different data mining tasks. In this article, we consider the problem of temporal link prediction: Given link data for times 1 through T, can we predict the links at time T + 1? If our data has underlying periodic structure, can we predict out even further in time, i.e., links at time T + 2, T + 3, etc.? In this article, we consider bipartite graphs that evolve over time and consider matrix- and tensor-based methods for predicting future links. We present a weight-based method for collapsing multiyear data into a single matrix. We show how the well-known Katz method for link prediction can be extended to bipartite graphs and, moreover, approximated in a scalable way using a truncated singular value decomposition. Using a CANDECOMP/PARAFAC tensor decomposition of the data, we illustrate the usefulness of exploiting the natural three-dimensional structure of temporal link data. Through several numerical experiments, we demonstrate that both matrix- and tensor-based techniques are effective for temporal link prediction despite the inherent difficulty of the problem. Additionally, we show that tensor-based techniques are particularly effective for temporal data with varying periodic patterns.

Subfields: Artificial Intelligence, Computational Mathematics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/aa1a7fc41bf25c373bf2bcbd35dfd5c45cffaa53

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 Computational Mathematics

In Statistical and Nonlinear Physics

Citations in the corpus

Tensors for Data Mining and Data Fusion (2016, background): “Dunlavyet al. [2011] consider the problem of temporal link prediction , that is, predicting future links based on past data.”
Toward Scalable Systems for Big Data Analytics: A Technology Tutorial (2014, methodology): “Linear algebraic approaches calculate the similarities between the nodes using rank-reduced similarity matrices [231].”
Link prediction in social networks: the state-of-the-art (2014, methodology): “One is to consider the time in the model, which can be named as temporal link prediction [53, 52] .”
Link Prediction via Matrix Factorization (2011, background): “Some scores that look at long-range relationships between node pairs, such as the Katz measure, can be approximated in order to run on large graphs [10].”
Continuous-Time Dynamic Network Embeddings (2018, background): “Temporal networks have been the focus of recent research including node classification in temporal networks [57], temporal link prediction [19], dynamic community detection [16],”
TensorCast: forecasting and mining with coupled tensors (2018, methodology): “C P f o r eca s ti ng [ 10 ] T r i M i n e [ 24 ] T e n s o r C a s t Future tensor is never fully reconstructed.”
On Fast Computation of Gradients for CANDECOMP/PARAFAC Algorithms (2012, methodology): “edCANDECOMP/PARAFAC (CP) [8,16] is a common tensor factorization which has found applications such as in chemometrics, telecommunication, analysis of fMRI data, time-varying EEG spectrum, data mining [7,13], classiﬁcation, clustering [29], stochastic PD Es [15]. For example, CP was applied to analyz”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, methodology): “As was proposed in [66], the adjacency matrices A 1 , . . . , A T for T timestamps can be stacked into an order 3 tensor A ∈ R N × N × T .”
Scalable Temporal Latent Space Inference for Link Prediction in Dynamic Social Networks (2014, background): “In addition, the latent position of each node might also be evolving over time [6], [16], [17], [18], [19].”
Temporal Graph Networks for Deep Learning on Dynamic Graphs (2020, background): “Learning on dynamic graphs is relatively recent, and most works are limited to the setting of discrete-time dynamic graphs represented as a sequence of snapshots of the graph over time (37; 15; 68; 54; 48; 70).”
Big Data: A Survey (2014, background): “Linear Algebra computes the similarity between two vertexes according to the singular similar matrix [141].”
SMF: Drift-Aware Matrix Factorization with Seasonal Patterns (2019, methodology): “Among the seasonal baselines (CPHW and Fold), CPHW is slowest as it performs CPD on the entire tensor.”
Exploiting homophily effect for trust prediction (2013, methodology): “There are several nice properties of the matrix factorization method [4, 16]: (1) many optimization methods such as gradient based methods can be applied to find a well-worked optimal solution, scaled to thousands of users with millions of trust relations; (2) it has a nice probabilistic interpretat”
dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning (2018, background): “Another class of algorithms uses matrix and tensor factorizations to model link dynamics [30, 31].”
Modelling matrix time series via a tensor CP-decomposition (2021, unknown): “The setting adopted by Dunlavy et al. (2011) is equivalent to (2.”
CANDECOMP/PARAFAC Decomposition of High-Order Tensors Through Tensor Reshaping (2012, background): “[12], separated representations for generic functions inv olved in quantum mechanics or kinetic theory descriptions of materials [13], classification, clusterin g [14], compression [15]–[17].”