Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank

I. INTRODUCTION

• Dynamic anomalography estimates a map of anomalies across flows and time from noisy, possibly incomplete link measurements, which are superpositions of unobserved OD flows.The aim is real-time tracking that provides a depiction of the network’s health state across both dimensions.Source: §I · p. 2, §II · p. 5
• The online estimator uses exponentially weighted least squares regularized by the anomalies’ ℓ1-norm and the nominal traffic matrix’s nuclear norm, with alternating minimization updating anomalies by Lasso and the traffic subspace by RLS.The paper recasts the non-separable nuclear norm for online optimization and establishes convergence under simplifying technical assumptions.Source: §I · pp. 2–3
• A lightweight online stochastic-gradient algorithm using Nesterov’s acceleration is also developed for settings where computational complexity reduction is critical.The introduction also outlines distributed implementation as a possibility.Source: §I · p. 3
• The proposed algorithms unveil anomalies and track them with slowly time-varying routes and incomplete link measurements, jointly estimating nominal traffic and anomalies with better performance than the two-step batch method.The two-step method first learns the nominal traffic subspace and then detects anomalies via ℓ1-norm minimization.Source: §I · p. 3

II. MODELING PRELIMINARIES AND PROBLEM STATEMENT

• The model treats link traffic as routed superpositions of nominal OD flows and anomalies; nominal traffic is low-rank, while anomalies are sparse across flows and time.The estimation goal is to recover the anomaly matrix from link measurements and the known routing matrix, exploiting both structures.Source: §II · pp. 4–5
• Traffic-engineering measures can address network congestion.Source: §II · p. 5

III. UNVEILING ANOMALIES VIA SPARSITY AND LOW RANK

• The model exploits the low-rank structure of nominal link-count traffic and estimates anomalies from link measurements.The nominal traffic matrix is defined as X := RZ and inherits low rank from Z.Source: §III · p. 5
• The objective fits the data while minimizing the nominal matrix’s rank and the number of nonzero anomaly entries, but these direct criteria are generally NP-hard to optimize.The nuclear norm and ℓ1-norm are used as convex surrogates for rank and sparsity.Source: §III · p. 5
• The formulation encompasses compressive sensing and principal component pursuit in specified special cases, while noisy low-rank-plus-compressed-sparse recovery further challenges identifiability.The special cases include no missing data with X = 0 and the decomposition Y = X + A.Source: §III · pp. 5–6
• Large variable counts, costly per-iteration SVDs, and nuclear-norm nonseparability complicate scalable and sequential optimization.The nonseparability is a challenge when new measurement columns arrive over time.Source: §III · p. 6
• Assuming a known upper bound ρ on the estimate’s rank permits factoring X as PQ′, reducing variables from (L + F)T to ρ(L + T) + FT.The factorized problem is non-convex because of the bilinear terms PQ′; savings can be significant when ρ is small and L and T are large.Source: §III · p. 6

A. A separable low-rank regularization

• When ρ ≥ rank(X̂), separable Frobenius-norm regularization in P3 loses no optimality relative to P1 and may use fewer variables.A global minimum of P3 can recover P1’s optimal solution.Source: A. A separable low-rank regularization · p. 7
• Because P3 is non-convex, some of its stationary points may fail to be globally optimal.Source: A. A separable low-rank regularization · p. 7
• If the residual satisfies Proposition 1’s threshold, every stationary point of P3 yields a globally optimal solution of P1.The proposition states this under relatively mild assumptions on rank and noise variance.Source: A. A separable low-rank regularization · p. 7

B. Batch block coordinate-descent algorithm

• Each BCD iteration updates the anomaly map, nominal traffic subspace, and projection coefficients in turn.The variable groups are updated while fixing the others at their most up-to-date values.Source: B. Batch block coordinate-descent… · pp. 7–8
• Inexact cyclic coordinate-descent updates converge to a stationary point of P3; a subsequence meeting the residual threshold converges to P1’s optimal solution set.Source: B. Batch block coordinate-descent… · pp. 8–9
• Algorithm 1 is less computationally complex than the accelerated proximal-gradient algorithm in [25], because its iterations require no SVD computations.Source: B. Batch block coordinate-descent… · p. 8

• Large-scale monitoring generates data that can outstrip modern computers’ ability to store and analyze it in real time, while network nonstationarities complicate monitoring.Source: §IV · p. 9
• Routing changes and missing data complicate anomaly identification, so the model accommodates slowly varying routing matrices and partially observed link measurements.Source: §IV · p. 9
• Because routing changes are sporadic relative to measurement acquisition, the section assumes link-level traffic remains low-dimensional and exploits temporal correlations to identify anomalies.The passage cites Internet-2 data showing only a few routing-matrix rows change per week.Source: §IV · p. 10
• Sequential measurements motivate recursively updating estimates rather than recomputing them from scratch, using an exponentially weighted least-squares estimator.Source: §IV · p. 10
• When β < 1, the estimator exponentially downweights distant-past data to facilitate tracking anomalies in nonstationary environments.Source: §IV · p. 10

• The alternating scheme updates the subspace matrix by minimizing the cost with respect to P, with row-wise subproblems solved in parallel.Source: A. Tracking network anomalies · pp. 10–11
• At each time instant, the online solver jointly estimates projection coefficients and anomalies using the prior subspace estimate.The coefficient step is a ridge-regression problem, followed by a Lasso estimate for anomalies.Source: A. Tracking network anomalies · pp. 10–11
• For 0 < β < 1, regularization prevents expressing H_l[t] as a rank-one correction to H_l[t−1], precluding the matrix-inversion-lemma shortcut.The algorithm instead uses direct inversions, each with O(ρ^3) cost per link.Source: A. Tracking network anomalies · p. 11
• The online estimation problem is more challenging than robust subspace tracking because it includes the fat compression matrix R_t.For computationally constrained settings, the paper also describes an online stochastic-gradient algorithm.Source: A. Tracking network anomalies · p. 12

• Evaluating the target cost C_t becomes computationally challenging as t grows because it entails solving t Lasso problems.Source: B. Convergence Analysis · p. 13
• Under the stated assumptions, the online subspace iterates satisfy lim_t→∞ ∇C_t(P[t]) = 0 almost surely and asymptotically coincide with stationary points of batch problem P3.Source: B. Convergence Analysis · p. 13
• The convergence analysis assumes data independent across time; as β approaches 1, the authors say the analysis extends accurately to settings with spatiotemporal correlations.The bounded-subspace requirement is identified as a technical assumption simplifying the proof.Source: B. Convergence Analysis · pp. 13–14
• Whether the learned online estimates become an optimal solution of P1 as the observation window grows is left for future research, although finite-time tests empirically attain P1’s performance.Source: B. Convergence Analysis · p. 14

C. Proof of Proposition 3

• The proof is inspired by, but treats additional non-convex bilinear terms, including sparse anomaly coding with a known routing matrix.These features make the convergence analysis more challenging than the related online dictionary-learning treatment.Source: C. Proof of Proposition 3 · p. 14
• Lemma 1 establishes Lipschitz continuity of the anomaly and projection minimizers, the objective, and its gradient on a compact set, with constants independent of time.This regularity result assumes a2 and a5.Source: C. Proof of Proposition 3 · p. 15
• Lemma 2 gives an O(1/t) bound on successive subspace-estimate changes, but this does not imply that the subspace iterates converge.The paper notes that convergence may not hold under the current assumptions.Source: C. Proof of Proposition 3 · p. 15
• Lemma 3 shows that the empirical cost converges almost surely and its difference from the target cost vanishes almost surely.The proof’s preliminary lemmas are used to establish the final stationarity result.Source: C. Proof of Proposition 3 · pp. 14–15
• The online subspace iterates converge to the set of stationary points of the batch problem, with their gradient of the target cost vanishing asymptotically.The proof establishes this by showing the empirical and target cost gradients approach one another.Source: C. Proof of Proposition 3 · pp. 15–16

V. FURTHER ALGORITHMIC ISSUES

• The paper also discusses the possibility of developing distributed algorithms for dynamic anomalography.The section introduces this as an additional algorithmic aspect without specifying a distributed method.Source: §V · p. 16

A. Fast stochastic-gradient algorithm

• The lightweight first-order alternative uses Nesterov-type gradient updates for the traffic subspace, aiming to speed learning without increasing per-iteration computational complexity.Its subspace update avoids matrix inversions; anomaly and projection updates remain as in Algorithm 2.Source: §V · p. 16, A. Fast stochastic-gradient algorithm · pp. 16–17
• Nesterov acceleration with backtracking stepsizes yields the fast online stochastic-gradient algorithm tabulated as Algorithm 3.The updates use a linear combination of the previous two subspace iterates.Source: A. Fast stochastic-gradient algorithm · p. 17
• Convergence analysis of Algorithm 3 is outside the paper’s scope and is corroborated only through computer simulations.With a non-diminishing stepsize, its iterates asymptotically remain within a ball around the expected-cost minimizer, with radius proportional to noise variance.Source: A. Fast stochastic-gradient algorithm · p. 18

B. In-network anomaly trackers

• Routers can process their own link measurements and refine local estimates through exchanges with directly connected neighbors to reach a global anomaly map.This distributed approach is motivated by centralized collection overhead, communication errors that can cause missing data, and the monitoring station’s single-point-of-failure risk.Source: B. In-network anomaly trackers · p. 18
• Using AD-MoM, the companion paper [24] presents a general framework for in-network sparsity-regularized rank minimization; its distributed algorithms tackle only batch formulation (P3), while acceleration techniques remain a research direction.Source: B. In-network anomaly trackers · p. 18

VI. PERFORMANCE TESTS

• The performance tests assess the proposed batch and online estimators using synthetic and real network data.Source: §VI · p. 19

A. Synthetic network data tests

• Online estimators converge, possibly within a ball, to the batch counterpart (P3), and more missing data slows learning the low-rank nominal traffic subspace.The online average cost is compared with the batch cost normalized by window size T = t.Source: Figure 3 · p. 21, A. Synthetic network data tests · p. 21
• For flows f2, f6, and f9, Algorithm 2 achieved PD = 0.83, 1, 1 at PFA = 0.0171, 0.0040, 0.0081, with PQ = 0.7606, 0.5863, 0.4028, respectively.Performance improves after the low-rank subspace is learned; early iterations produce more false alarms.Source: Figure 3 · p. 21, A. Synthetic network data tests · p. 21
• Average estimation error decreases quickly and becomes almost invariant after the estimator learns the subspace.Fig. 4(a) plots average estimation error across noise variances and amounts of missing data.Source: A. Synthetic network data tests · p. 22, Figure 4 · p. 23
• Algorithm 2 tracks anomalies and link-level traffic; the examples include link 12 dropping to zero and link 31 flows varying with routing changes at t=220 and t=940.The passage notes that traffic is not tracked at those routing-change instants.Source: Figure 4 · p. 23, A. Synthetic network data tests · p. 23
• At α=0.01, π=0.8, raising noise variance from 10^-5 to 10^-2 lowers detection probability 10%; dropping 20% of observations at σ=10^-5, α=0.01 yields 11% more misdetections; changing α from 0.01 to 0.1 at σ=10^-5, π=0.8 has an adverse effect of about 6% on detection rate.Source: A. Synthetic network data tests · p. 23

Test data

• Internet-2 measurements span three weeks at five-minute intervals, and the network has 11 nodes, 41 links, and 121 flows.Link loads are obtained from flow measurements using an invariant routing matrix during the acquisition period.Source: B. Real network data tests · p. 24
• The estimated nominal traffic matrix has three dominant singular values, supporting its low-rank characterization for the test.Important spikes above a threshold are retained as benchmark anomalies.Source: B. Real network data tests · p. 24

Batch estimator

• The batch estimator markedly outperforms both PCA-based methods in detection performance on Internet-2 data.Fig. 6 also illustrates anomaly amplitudes at PFA = 0.04 and PD = 0.93.Source: Figure 6 · p. 25, B. Real network data tests · p. 25

Online operation

• 0.72 detection and 0.011 false-alarm rates are approached after about a week of full-data online operation.Fig. 7 shows the evolution of estimation errors and detection and false-alarm rates.Source: B. Real network data tests · p. 26, Figure 7 · p. 26
• With 15% missing data, online detection performance degrades gracefully.The incomplete-data scenario discards a randomly chosen subset of link counts.Source: B. Real network data tests · pp. 25–26
• The online estimator accurately tracks representative link traffic and OD-flow anomalies.Fig. 7 compares estimated and true values for three representative links and anomalies.Source: B. Real network data tests · p. 26, Figure 7 · p. 26

VII. CONCLUDING REMARKS

• Dynamic anomalography uses sequential link-level measurements, which are noisy superpositions of OD flows, to map anomalies across flows and time in real time.The map is intended to summarize the network’s health state.Source: §VII · p. 27
• Online tracking addresses nonstationary environments, including those arising from routing changes and missing data, and scales gracefully with flow count or acquisition-window length.The conclusion presents online schemes as an alternative to batch algorithms.Source: §VII · p. 27
• Tests on synthetic and real network data corroborate the algorithms’ effectiveness and tracking capabilities, and report better performance than existing workhorse approaches.Source: §VII · p. 27

Proofs

• The proof establishes Lipschitz continuity for the minimized variables and loss, then derives a gradient expression using Danskin’s theorem.The cited proof passages give the Lipschitz arguments and identify the gradient of the loss.Source: APPENDIX · pp. 28–29
• Strong convexity and the mean-value theorem are used to bound changes between successive approximate cost functions.The proof then shows the auxiliary function has Lipschitz constant O(1/t).Source: APPENDIX · p. 30
• The proof identifies a quasi-martingale sequence and concludes that the approximate-to-true cost gap converges to zero almost surely.The convergence follows after bounding the variation of the gap.Source: APPENDIX · p. 31