PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Linhong Zhu, Dong Guo, Junming Yin, Greg Ver Steeg, Aram Galstyan

arXiv:1411.3675v3cs.SIcs.AIcs.IR

TL;DR

Link prediction in dynamic networks requires scalable methods that capture both latent node similarity and temporal evolution. This paper proposes a temporal latent space model with non-negative matrix factorization and multiple BCGD algorithms, reporting theoretical convergence results and experiments on large networks.

  • Problem

    Link prediction seeks to predict future social interactions, but scalable inference is challenging because non-negative matrix factorization is NP-hard and historical snapshots may require joint processing.

  • Method

    The paper models nodes in a smoothly evolving low-rank temporal latent space and learns it with global, local, and incremental BCGD algorithms using non-negative matrix factorization.

  • Results

    The global BCGD algorithm has a quadratic convergence rate, while the proposed methods are evaluated on large networks with millions of nodes and links for efficiency and predictive quality.

  • Takeaways & Limitations

    Local and incremental inference use locality and temporal information to reduce computational demands while remaining as effective as global joint inference.

  • Takeaways & Limitations

    The temporal smoothness assumption may fail under abrupt changes, such as rush-hour transitions or external events that shift latent node positions.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper develops a temporal latent space model and scalable inference algorithms for predicting links in evolving networks. It combines smoothly changing node positions with global, local, and incremental optimization, achieving strong predictive quality and scalability.

  • Temporal link prediction uses prior graph snapshots to infer latent node positions and predict links at a future timestamp.
  • The model assumes nearby latent positions make links more likely and that node positions evolve smoothly rather than changing abruptly.
  • The global BCGD algorithm has a quadratic convergence rate despite the temporal smoothness term introducing new optimization challenges.
  • The local and incremental BCGD variants reduce computational cost by exploiting sequential inference and affected-node updates.
  • Average AUC scores are 0.81, 0.79 and 0.78 for global BCGD, local BCGD, and incremental BCGD, respectively, across sparse and dense networks.
  • The incremental BCGD algorithm learns temporal latent spaces for massive networks with millions of nodes and links in less than half an hour.

2 PROBLEM FORMULATION

The formulation represents each timestamp’s network with a low-rank temporal latent space governed by smoothness, network embedding, and latent homophily assumptions. It infers these representations from graph snapshots and uses them to predict the next adjacency matrix.

  • A dynamic network is represented as a sequence of time-indexed graph snapshots G = (G1, ..., Gt), each containing nodes and interactions.
  • At each timestamp τ, Zτ is a low-rank k-dimension latent representation whose rows encode individual node positions.
  • The model assumes temporal smoothness, network embedding, and latent homophily: nearby network nodes have nearby latent positions, and nearby latent nodes interact more frequently.
  • Given graph snapshots G1 through Gt, the method infers Z1 through Zt, approximates Zt+1 from them, and predicts Gt+1.
  • The objective adds temporal regularization that penalizes sudden changes in each node’s latent position.
  • Because non-negative matrix factorization is NP-hard and separability is not guaranteed, the formulation uses BCGD to obtain an approximate solution.

3 A STANDARD BCGD ALGORITHM

The standard global BCGD algorithm decomposes the non-convex temporal latent-space objective and updates each node’s position using projected gradient descent. It provides convergence and complexity guarantees, but can be expensive for high-degree nodes and large networks.

  • Optimization: The objective is a fourth-order, non-convex polynomial, so BCGD fixes other latent positions and solves a convex subproblem for each node and timestamp.The method updates Zτ(u) while holding other nodes’ positions and other timestamps fixed.
  • Optimization: Projected gradient descent iteratively updates each nonnegative latent position, using a step size controlled by the Lipschitz constant.The gradient is Lipschitz continuous, with L determined by the number of nodes and latent dimensions.
  • Limitations: Updating a node requires all neighbors’ latent positions, making the standard update time-consuming for nodes with extra-large degrees.A proposed future direction is stochastic gradient updating using randomly selected neighbors.
  • Algorithm: The global BCGD algorithm jointly infers the temporal latent space and outputs a future link-prediction matrix from graph snapshots and the latent dimension.Algorithm 1 takes graphs and k as input and returns temporal latent-space matrices and Yt+1.
  • Theoretical analysis: O(1/r^2) is the stated convergence rate for the per-node updates under Nesterov’s step-size method.Here, r denotes the iteration number rather than the total number of iterations.
  • Theoretical analysis: O(Rk∑τ(n + mτ)) bounds the total time complexity for sparse networks, while storage must retain all input and output temporal matrices.The per-iteration cost is linear in nodes and edges for sparse graphs.

4 FAST BCGD ALGORITHMS

The paper introduces local and incremental BCGD variants that reduce the computational and storage costs of temporal latent-space inference by exploiting sequential and affected-node updates.

  • Local BCGD Algorithm: Local BCGD sequentially infers each temporal latent space from one graph snapshot and the previous latent space, reducing computational cost.It iteratively updates the current latent positions until convergence before proceeding to the next timestamp.
  • Local BCGD Algorithm: The local algorithm updates each node’s latent position while fixing the positions of all other nodes, using the update rule in Eq. 7.The procedure repeats node updates and normalization until the current temporal latent space converges.
  • Local BCGD Algorithm: The local BCGD algorithm requires storage of one graph snapshot and two latent-space matrices, with memory bounded by O(nk + maxτ mτ).The global algorithm instead requires all historical snapshots and temporal latent spaces in memory.
  • Incremental BCGD Algorithm: Incremental BCGD adjusts the current temporal latent space from the previous one as nodes and edges are inserted or deleted, rather than recomputing it from the entire snapshot.The method uses prior latent-space information and temporal transitions to update the changing network.
  • Incremental BCGD Algorithm: Incremental BCGD initializes updated nodes from their neighbors and propagates conditional updates only through affected nodes until convergence or no affected nodes remain.The affected set begins with updated nodes and is revised as update effects propagate through neighboring nodes.
  • Incremental BCGD Algorithm: The incremental algorithm has computational cost O(k Σr(|Sr| + |N(Sr)|)) and storage cost O(nk + maxτ(mτ + Δmτ)).Sr denotes affected nodes and N(Sr) their neighborhood; the additional storage accounts for graph changes.

5 EXPERIMENTS

Experiments evaluate parameter effects, computational efficiency, and online link-prediction accuracy on real temporal networks. The proposed BCGD variants generally balance scalability with predictive performance, with incremental BCGD emerging as a practical large-scale option.

  • Dataset and evaluation: The experiments use five real temporal datasets and evaluate parameter effects, offline and online efficiency, and online link-prediction accuracy.Efficiency is measured by running time and memory consumption; prediction uses AUCROC.
  • Effect of parameters: Increasing dimensionality k increases inference time while decreasing prediction error, so larger latent spaces trade computational cost for accuracy.The reported dimensionality range is k=5 to 30.
  • Efficiency: BCGDI is more efficient in running time, whereas BCGDL uses less memory; both fast variants are described as time- and memory-efficient.BCGDI requires additional storage for graph changes, while adaptively updating latent spaces.
  • Efficiency: BCGDG is at least five times faster than DMMSB and comparable to NMFR, while PTM and LabelRT fail on the two largest graphs because of memory bottlenecks.BCGDL is comparable to Hott and BigCLAM, and BCGDI is consistently more efficient than both.
  • Link-prediction accuracy: For new-link prediction, BCGDG, BCGDL, and BCGDI are among the strongest methods, while BCGDL and BCGDI retain comparable accuracy to BCGDG and can outperform global approaches on Infection and YouTube.The incremental variant is reported to average higher accuracy than the local variant and to be more scalable than alternatives.

6 RELATED WORK

Related work spans graph-based heuristics, latent-space models, tensor methods, and matrix factorization, while this paper emphasizes scalable BCGD-based inference for dynamic latent spaces.

  • Static link-prediction methods include graph-based heuristics that estimate link probability from topological similarity.
  • Online graph heuristics face a trade-off between costly on-the-fly computation and quadratic storage for precomputed similarity scores.
  • Tensor-based temporal latent-space prediction can require more expensive tensor products and larger memory than the proposed dot-product approach.
  • Static latent-space inference has used Bayesian methods, maximum likelihood, posterior inference, and stochastic approaches, but posterior computation can be infeasible on large graphs.
  • Matrix factorization learns low-dimensional latent spaces, but NMFR does not scale well because of high computation cost per iteration.
  • BCGD is presented as more scalable than NMFR while performing well across input-graph topologies.
  • The incremental BCGD algorithm updates latent positions at each time step conditionally for affected nodes, extending incremental dynamic-network inference.

7 CONCLUSION AND FUTURE WORK

The paper concludes with a scalable temporal latent-space approach and three BCGD inference algorithms, while identifying abrupt network changes and broader graph settings as future challenges.

  • The approach models higher link likelihood for nearby latent positions and penalizes frequent temporal changes in node positions.
  • BCGDG, BCGDL, and BCGDI learn temporal latent spaces through non-negative matrix factorization, with theoretical analyses of their performance guarantees.
  • Experiments on networks with millions of nodes and links evaluate the proposed approaches for efficiency and predictive quality.
  • Temporal smoothness may fail when node positions shift abruptly because of rush hours, external events, or other rapid network changes.
  • Future extensions include nonlinear transitions, continuous-time inputs, directed and weighted graphs, and greater parallelization efficiency.

Supplemental Materials to “Scalable Temporal Latent Space

The supplemental-materials passage contains only a fragment of a title: “Inference for Link Prediction in Dynamic Social Networks.”

  • The supplied passage is a fragment naming inference for link prediction in dynamic social networks.

A PROOF OF LEMMA 1

The proof establishes Lipschitz continuity of the gradient for the time-specific objective, using trace inequalities and the unit-norm constraint on latent vectors.

  • The proof begins by expressing the gradient of J(Z_τ(u)) at timestamp τ.
  • Terms are rewritten and combined across Equations 9 and 10 to derive a simplified gradient expression.
  • The simplification uses the constraint Z_τ(u)Z_τ(u)^T = 1 for every node u.
  • The gradient difference is compared at two row vectors Z1 and Z2 to bound its variation.
  • Applying the positive-semidefinite trace inequality yields a bound proportional to ∥Z1 − Z2∥^2.
  • The resulting Lipschitz constant is 2(n^2 − 2n + k), completing the lemma’s proof.

B PROOF OF LEMMA 2

The proof establishes the correctness of the iterative update rule for each node’s latent representation at a given time point.

  • The update rule iteratively updates Zτ(u) at each iteration r + 1 for node u and time τ.
  • The derivation uses a non-negative projection PL(Y ) and initializes the sequence with ZIτ(u).
  • The step size η is set using the Lipschitz constant L, yielding the expression stated in Lemma 2.
  • The argument concludes that the update rule in Lemma 2 is correct.

C PROOF OF THEOREM 1

The proof derives Theorem 1 by applying inequalities for non-negative projection updates, substituting the algorithm’s iterates, and summing the resulting bounds.

  • The proof applies a projection inequality involving J, PL(Y ), the matrix inner product, and the distance from Y to its projection.
  • Substituting successive iterates relates the projection PL(Y (r)) to Z(r)(u) and bounds updates toward Z∗(u).
  • Because ar+1 > 1, the proof scales and combines inequalities to obtain a recursive bound involving J(Z(r+1)(u)).
  • The derivation uses the recurrence for ar+1 and substitutions for A, B, and C to simplify the matrix-norm expressions.
  • Summing the resulting expressions across iterations and combining the bounds completes the proof of Theorem 1.

D EXTRA RESULTS BASED ON AUCPR

The AUCPR experiments show that the proposed approaches consistently outperform other state-of-the-art methods, with BCGDI performing especially well for link prediction.

  • The experiments evaluate link prediction accuracy using AUCPR.
  • The proposed approaches are consistently better than other state-of-the-art approaches under AUCPR, similarly to their AUCROC results.
  • AA improves under AUCPR, possibly because common-neighbor scoring produces high precision but relatively lower recall.
  • DMMSB performs worse under AUCPR, while the incremental algorithm BCGDI performs especially well on the link prediction task.
Loading 1411.3675v3…