# TIMERS: Error-Bounded SVD Restart on Dynamic Networks

arXiv: https://arxiv.org/abs/1711.09541 · HTML: https://mlsanity.com/paper/1711.09541/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2017.

## Built on by (most cited first, 19 of 19)

- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [A Survey on Embedding Dynamic Graphs](https://mlsanity.com/paper/2101.01229/) (2021)
- [Dynamic Network Embedding Survey](https://mlsanity.com/paper/2103.15447/) (2021)
- [Dynamic Graph Collaborative Filtering](https://mlsanity.com/paper/2101.02844/) (2021)
- [CGC: Contrastive Graph Clustering for Community Detection and Tracking](https://mlsanity.com/paper/2204.08504/) (2022)
- [Parameter-free Dynamic Graph Embedding for Link Prediction](https://mlsanity.com/paper/2210.08189/) (2022)
- [On the Equivalence Between Temporal and Static Graph Representations for Observational Predictions](https://mlsanity.com/paper/2103.07016/) (2021)
- [DynG2G: An Efficient Stochastic Graph Embedding Method for Temporal Graphs](https://mlsanity.com/paper/2109.13441/) (2021)
- [DyGCN: Dynamic Graph Embedding with Graph Convolutional Network](https://mlsanity.com/paper/2104.02962/) (2021)
- [Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs](https://mlsanity.com/paper/2210.00032/) (2022)
- [Dyn-Backdoor: Backdoor Attack on Dynamic Link Prediction](https://mlsanity.com/paper/2110.03875/) (2021)
- [Gradient-Based Spectral Embeddings of Random Dot Product Graphs](https://mlsanity.com/paper/2307.13818/) (2023)
- [TPGNN: Learning High-order Information in Dynamic Graphs via Temporal Propagation](https://mlsanity.com/paper/2210.01171/) (2022)
- [Robust Dynamic Network Embedding via Ensembles](https://mlsanity.com/paper/2105.14557/) (2021)
- [Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds](https://mlsanity.com/paper/2306.08967/) (2023)
- [ChronoSpike: An Adaptive Spiking Graph Neural Network for Dynamic Graphs](https://mlsanity.com/paper/2602.01124/) (2026)
- [Space-Invariant Projection in Streaming Network Embedding](https://mlsanity.com/paper/2303.06293/) (2023)
- [DySuse: Susceptibility Estimation in Dynamic Social Networks](https://mlsanity.com/paper/2308.10442/) (2023)
- [Subspace Projection Methods for Fast Spectral Embeddings of Evolving Graphs](https://mlsanity.com/paper/2603.19439/) (2026)

## Abstract (arXiv)

Singular Value Decomposition (SVD) is a popular approach in various network applications, such as link prediction and network parameter characterization. Incremental SVD approaches are proposed to process newly changed nodes and edges in dynamic networks. However, incremental SVD approaches suffer from serious error accumulation inevitably due to approximation on incremental updates. SVD restart is an effective approach to reset the aggregated error, but when to restart SVD for dynamic networks is not addressed in literature. In this paper, we propose TIMERS, Theoretically Instructed Maximum-Error-bounded Restart of SVD, a novel approach which optimally sets the restart time in order to reduce error accumulation in time. Specifically, we monitor the margin between reconstruction loss of incremental updates and the minimum loss in SVD model. To reduce the complexity of monitoring, we theoretically develop a lower bound of SVD minimum loss for dynamic networks and use the bound to replace the minimum loss in monitoring. By setting a maximum tolerated error as a threshold, we can trigger SVD restart automatically when the margin exceeds this threshold.We prove that the time complexity of our method is linear with respect to the number of local dynamic changes, and our method is general across different types of dynamic networks. We conduct extensive experiments on several synthetic and real dynamic networks. The experimental results demonstrate that our proposed method significantly outperforms the existing methods by reducing 27% to 42% in terms of the maximum error for dynamic network reconstruction when fixing the number of restarts. Our method reduces the number of restarts by 25% to 50% when fixing the maximum error tolerated.