Temporal Link Prediction using Matrix and Tensor Factorizations

Abstract

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 paper, 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 paper, 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 multi-year 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.

References in corpus (1)

• Hierarchical structure and the prediction of missing links in networks

Cited by in corpus (27)

• Modern temporal network theory: A colloquium
• Motifs in Temporal Networks
• Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey
• Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Common neighbours and the local-community-paradigm for link prediction in bipartite networks
• Modeling the Heterogeneous Duration of User Interest in Time-Dependent Recommendation: A Hidden Semi-Markov Approach
• Distributed Methods for High-dimensional and Large-scale Tensor Factorization
• Scalable Tucker Factorization for Sparse Tensors - Algorithms and Discoveries
• Newton-Based Optimization for Kullback-Leibler Nonnegative Tensor Factorizations
• Joint community and anomaly tracking in dynamic networks
• Reconstructing networks
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Estimating the outcome of spreading processes on networks with incomplete information: a mesoscale approach
• Influence-guided Data Augmentation for Neural Tensor Completion
• Dynamic Hidden-Variable Network Models
• Continuous-Time Relationship Prediction in Dynamic Heterogeneous Information Networks
• Unsupervised EHR-based Phenotyping via Matrix and Tensor Decompositions
• Link prediction in dynamic networks using random dot product graphs
• Graph link prediction in computer networks using Poisson matrix factorisation
• A Dynamic Embedding Model of the Media Landscape
• Improving Link Prediction in Intermittently Connected Wireless Networks by Considering Link and Proximity Stabilities
• Understanding and Predicting Delay in Reciprocal Relations
• Network interpolation
• A Time-aware tensor decomposition for tracking evolving patterns
• Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms
• Individualized Context-Aware Tensor Factorization for Online Games Predictions