  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.
