PaperlayerView exact revision on arXiv

Source-linked AI summary

Temporal Link Prediction using Matrix and Tensor Factorizations

Daniel M. Dunlavy, Tamara G. Kolda, Evrim Acar

arXiv:1005.4006v2math.NAphysics.data-anstat.ML

TL;DR

The paper addresses how to predict future links in evolving bipartite graphs, including multiple future steps when temporal periodicity is present. It compares matrix methods that aggregate time slices with tensor methods that retain temporal structure, finding effective prediction from both and particularly strong tensor performance for periodic dynamics.

  • Problem

    The central problem is predicting links at time T+1, or farther ahead when link data contains periodic temporal patterns.

  • Method

    The paper combines weighted matrix aggregation, bipartite Katz and scalable truncated-Katz approximations, and CANDECOMP/PARAFAC tensor factorization with Holt-Winters temporal forecasting.

  • Results

    Both matrix- and tensor-based methods are effective; tensor methods better capture temporal patterns, including accurate multi-day forecasts in the user-service example.

  • Takeaways & Limitations

    Tensor-based techniques are particularly useful when temporal data exhibit varying periodic patterns, while matrix methods provide competitive link-prediction performance.

  • Takeaways & Limitations

    Tensor-based methods typically incur higher computational cost than matrix-based approaches.

Abstract

from arXiv · show

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.

1. INTRODUCTION

The paper frames temporal link prediction as forecasting future relationships in evolving bipartite graphs, including multiple steps when periodic patterns exist. It develops matrix and tensor factorizations that preserve or model temporal structure for this task.

  • 1. INTRODUCTION: Temporal link prediction asks whether relationships at time T+1 can be inferred from link data observed through time T.
  • 1. INTRODUCTION: Periodic temporal link prediction extends this task to forecasting links at times T+1 through T+L, where L is the periodic pattern length.The paper notes that weekly or monthly interaction patterns can arise in communication and network-traffic data.
  • 1. INTRODUCTION: Time-evolving links can be represented as a third-order tensor Z of size M × N × T, with entries indicating whether object i links to object j at time t.Link strength can also be represented with weights rather than binary entries.
  • 1. INTRODUCTION: The matrix methods collapse time slices into one matrix, while CP tensor factorization retains the natural three-dimensional structure and an interpretable time dimension.CP supports both single-step and periodic temporal prediction, whereas matrix methods are limited to a single future time step.
  • 1. INTRODUCTION: The paper proposes weighted temporal aggregation, bipartite Katz and scalable truncated-Katz methods, alongside CP factorization for temporal link prediction.These methods are evaluated using conference-publication and other link-based application settings.

2. MATRIX TECHNIQUES

Matrix techniques collapse temporal link data into one matrix, then apply low-rank approximation and Katz-based scoring for future-link prediction. Weighted collapsing emphasizes recent links, while truncated decompositions improve scalability and extend Katz to bipartite graphs.

  • 2.1 Collapsing the data: Temporal matrices are collapsed into a single M × N matrix using either unweighted summation or backward-decaying weights.The weighted method is called the collapsed weighted tensor (CWT) and gives greater weight to recent links.
  • 2.1 Collapsing the data: CWT improves performance over straight summation CT in single-step temporal link prediction.
  • 2.2 Truncated SVD: TSVD replaces the collapsed matrix with its best rank-K approximation, producing link scores from K rank-one matrix components.The approximation uses the leading singular vectors and singular values of the collapsed matrix.
  • 2.3 Katz: Katz scores count paths with longer paths penalized by β, but the original formulation requires dense matrix inversion and applies only to square symmetric graphs.The paper extends Katz to rectangular weighted adjacency matrices representing bipartite graphs.
  • 2.3 Katz: Truncated Katz replaces the adjacency matrix with a low-rank approximation, enabling score computation in O(L|E|) operations using Arnoldi or Lanczos methods.Its factorization storage is K(M + N + 1), matching the TSVD storage requirement.
  • 2.3 Katz: The paper contrasts efficient truncated Katz with a power-series truncation whose power matrices may become dense depending on graph connectivity.

3. TENSOR TECHNIQUES

Tensor techniques preserve the three-way structure of temporal link data by modeling object pairs and time jointly with CP decomposition. CP supports heuristic recent-activity scoring and Holt-Winters forecasting for single-step or periodic prediction.

  • 3.1 CP Tensor Model: CP models the temporal data as a three-way tensor, explicitly retaining the time dimension instead of collapsing slices into a matrix.This gives the method a direct multi-dimensional representation of the data.
  • 3.1 CP Tensor Model: A K-component CP decomposition represents the tensor as weighted sums of rank-one outer products with object and temporal factors.The component weight is λk, while ak, bk, and ck are normalized factor vectors.
  • 3.1 CP Tensor Model: Unlike SVD, CP imposes no orthogonality constraint, but its components are unique up to permutation and scaling under mild conditions.This uniqueness permits direct use of temporal factors for forecasting.
  • 3.2 CP Scoring using a Heuristic: CP scoring combines object-pair relationships from akb_k^T with temporal profiles ck to assign future-link similarity scores.The heuristic uses average activity over the last T0 = 3 years as the component weight.
  • 3.2 CP Scoring using a Heuristic: The heuristic is simple and uses only the last three time steps, although averaging recent steps can work well in many cases.
  • 3.3 CP Scoring using Temporal Forecasting: Holt-Winters forecasts CP temporal profiles for future periods, supporting periodic prediction when the expected period is supplied.The paper uses additive trend and additive seasonality, including L = 7 for daily data.
  • 3.4 Computational Complexity: CP has computational complexity O(nnz(Z)) per iteration and storage K(M + N + T + 1).

4. EXPERIMENTS WITH LINK PREDICTION FOR ONE TIME STEP

The experiments evaluate matrix- and tensor-based predictors on seven DBLP training/test pairs, using ten years of training data to predict the following year. Weighted temporal aggregation and Katz-CWT perform strongly, while CP provides interpretable temporal factors but requires substantially more computation.

  • Data preparation: The DBLP data are organized as author–conference publication counts in a third-order tensor and transformed with 1 + log(C(i, j, t)) for positive counts.Zero counts remain zero, reducing the effect of large publication numbers.
  • Experimental design: Seven sliding-window evaluations use ten training years and the following 11th year for testing.Authors must have at least 10 training publications, and test sets retain training authors and conferences.
  • Experimental design: The study evaluates predicting all positive test links and the more challenging task of predicting links never observed during training.For evaluation, every nonzero test entry is treated as a positive link regardless of publication count.
  • Link prediction results: Katz-CWT achieves the best average AUC across methods, while CWT consistently outperforms corresponding CT methods.The results attribute this pattern to giving more weight to recent years.
  • Link prediction results: CP, TSVD-CWT, TKatz-CWT, and Katz-CWT achieve close to 75% accuracy among the top 1000 predictions for all links.For new links, accuracy falls to 10% or less but remains two orders of magnitude above the 0.1% chance expectation; CP remains among the best top-prediction methods.
  • Computational cost: Matrix-based methods are much faster than CP, with average runtimes of 61 seconds for TSVD/TKatz variants, 74–80 seconds for Katz, and 1300 seconds for CP.The Katz method uses a full SVD, making it computationally expensive for very large problems.

5. EXPERIMENTS WITH LINK PREDICTION FOR MULTIPLE TIME STEPS

The experiments evaluate CP-based prediction across multiple future time steps under periodic simulated data, noise, and corrupted training signals. CP captures temporal patterns and generally outperforms using the last observed period.

  • Experimental setup: The simulated data models two entity sets over daily observations with seven-day periodic temporal profiles and ten training periods.The training tensor contains 70 time observations, followed by one seven-step testing period.
  • Experimental setup: Training data are made challenging by randomly swapping half of the largest 25% of entries and adding spurious data.The corruption removes important links and introduces false ones.
  • CP interpretation: CP extracts temporal patterns that approximate the original profiles and supplies Holt-Winters forecasts for future link prediction.The extracted patterns are used to generate predictions for the next period.
  • Link prediction results: AUC 0.845 versus 0.686 shows CP outperforming Last Period for seven-step prediction under high noise.CP also achieves 100% accuracy among its top 1,000 scores, compared with 70% for Last Period.
  • Link prediction results: Across corruption experiments, CP consistently exceeds Last Period in AUC and top-1,000 accuracy, while remaining robust as strong links are altered.The paper identifies this robustness as important when noise or missing data is common.

6. RELATED WORK

Related work covers link-mining tasks, temporal graph models, collaborative filtering, and tensor factorizations. The paper distinguishes its contribution by applying tensor methods directly to temporal link prediction and developing matrix-based temporal techniques.

  • Link mining and temporal graphs: Prior link-mining research includes node classification, group detection, and link prediction, including weighted summary graphs for temporal-relational data.The weighted-snapshot idea is incorporated into this paper’s matrix methods.
  • Link mining and temporal graphs: Earlier co-authorship link-prediction work evaluated methods without exploiting temporal information beyond data splitting.The cited data had new-link proportions comparable to those observed in this paper.
  • Link mining and temporal graphs: Other work modeled evolving graphs through latent spaces or aggregated adjacency matrices over time.These approaches address temporal graph structure but differ from the paper’s matrix and tensor prediction framework.
  • Collaborative filtering: Collaborative filtering is related because it predicts user–object interests, with later models explicitly accounting for changing user preferences.The literature also emphasizes predicting likely interactions before ratings.
  • Tensor methods: Tensor factorizations have analyzed web, chatroom, and email networks, but those applications used them exploratorily rather than for link prediction.This paper applies tensor factorization to the prediction problem itself.

7. CONCLUSIONS

The paper finds that matrix- and tensor-based methods are effective for temporal link prediction, while tensor methods better capture temporal patterns and support longer-range forecasting. Matrix methods can be competitive and computationally advantageous, but tensor methods incur higher computational cost.

  • Temporal modeling of multiple time slices outperforms simple summation for matrix-based link prediction.
  • Katz achieves the best AUC on DBLP, but is computationally intractable at large scale; other methods perform nearly as well.
  • TKatz-CWT performs best for predicting new links in the DBLP data.
  • Tensor-based methods are competitive with matrix-based methods and better capture and exploit temporal patterns.
  • Tensor methods accurately predicted links several days ahead in the more complicated user-service dynamics.
  • The main drawback of tensor-based prediction is its typically higher computational cost.
Loading 1005.4006v2…