Many networked systems hide their wiring but reveal its effect. Sensor readings, stock returns or brain signals spread along unseen edges, and when that spreading is a linear diffusion, the covariance of the signals is a polynomial in the network's adjacency or Laplacian matrix. The two matrices then commute. Commutation-based topology inference recovers the graph by searching for a sparse, valid graph matrix that commutes with the measured covariance. The streaming version of this method takes one cheap optimization step per new sample. The existing online methods all take that step with plain proximal gradient descent, meaning one gradient step on the commutation error followed by soft-thresholding and projection onto valid graphs. We argue this choice has a specific, analyzable weakness. The commutation error weights each spectral component of the graph by the squared gap between two covariance eigenvalues. Components tied to nearly equal eigenvalues, such as those inside communities or between clustered modes, therefore receive almost no gradient and adapt extremely slowly after the network changes.
We propose a single-step alternating direction method of multipliers (ADMM), a method that splits a problem into two easier subproblems linked by a consensus constraint. One copy of the graph matrix lives in the covariance eigenbasis, where the commutation penalty becomes diagonal and can be minimized exactly, entry by entry. The other copy lives in the node domain, where sparsity and graph-validity constraints act entry by entry. A cheap single-step tracker updates the eigenbasis alongside the graph. The claim is that this splitting removes the eigengap dependence of tracking speed. Components the data cannot identify stay at their previous value instead of drifting. The disagreement between the two copies serves as a measurable constraint-violation signal with sublinear regret.
Core Claim
Let $\widehat{\mathbf{C}}_t = \mathbf{V}_t \mathbf{\Lambda}_t \mathbf{V}_t^T$ be the recursively updated sample covariance with eigenvalues $\lambda_i$. Write $\widehat{\mathbf{Z}} = \mathbf{V}_t^T \mathbf{Z} \mathbf{V}_t$ for a matrix $\mathbf{Z}$ expressed in that eigenbasis. Then
$$\|\widehat{\mathbf{C}}_t \mathbf{Z} - \mathbf{Z}\widehat{\mathbf{C}}_t\|_F^2 = \sum_{i,j} (\lambda_i - \lambda_j)^2 \widehat{Z}_{ij}^2 .$$
This identity has two consequences. First, a gradient step on this loss must use a step size of order $1/(\lambda_{\max}-\lambda_{\min})^2$, so a component with gap $g_{ij}=|\lambda_i-\lambda_j|$ contracts by a factor of only about $1 - g_{ij}^2/(\lambda_{\max}-\lambda_{\min})^2$ per sample. Second, the ADMM subproblem $\min_{\mathbf{Z}} \|\widehat{\mathbf{C}}_t\mathbf{Z}-\mathbf{Z}\widehat{\mathbf{C}}_t\|_F^2 + \tfrac{\rho}{2}\|\mathbf{Z}-\mathbf{M}\|_F^2$, with $\rho$ the penalty weight and $\mathbf{M}$ the current node-domain estimate minus the scaled dual, has the exact closed form $\widehat{Z}_{ij} = \rho \widehat{M}_{ij}/(2(\lambda_i-\lambda_j)^2+\rho)$.
The other half of the split is the node-domain step. It applies the proximal operator of $\lambda\|\mathbf{S}\|_1$ together with the adjacency constraints (symmetry, nonnegativity, zero diagonal and a linear scale normalization), which reduces to entrywise thresholding with a scalar shift found by one-dimensional search.
The resulting iteration is well-conditioned no matter how the eigengaps are spread. Its proximal term also handles the null space of the commutator, which consists of every polynomial in $\widehat{\mathbf{C}}_t$ and is exactly what breaks the strong-convexity assumption behind the existing tracking theorem. Components with zero or tiny gaps are simply carried over from the previous estimate. Our hypothesis is concrete: after an abrupt topology change, the samples needed to re-identify the graph should scale with the inverse squared smallest relevant eigengap for proximal gradient, and should be roughly flat for the split method.
Relation to Prior Work
The method comes from the commutation formulation in Connecting the Dots: Identifying Network Structure via Graph Signal Processing, which poses topology inference as a sparse search for a graph matrix commuting with the covariance and solves it in batch with general-purpose convex solvers. The stationarity foundations in Stationary Signal Processing on Graphs justify why the covariance eigenbasis is the natural coordinate system. We exploit that basis computationally rather than estimating eigenvalues on a fixed template.
Two papers motivate the proposal directly, because they are the streaming versions of this problem and both take primal proximal gradient steps. Online Topology Inference from Streaming Stationary Graph Signals tracks a sparse shift operator with one gradient-plus-prox step per sample. Its non-asymptotic tracking bound assumes the commutation loss is strongly convex, which the null space above rules out. It reports that the objective "initially diverged after a network perturbation but then recovered" on the karate club graph, which is exactly the lag we aim to explain and remove. Online Network Inference from Graph-Stationary Signals with Hidden Nodes adds a low-rank proxy matrix for unobserved nodes but keeps the same primal step. We do not change the model; we change how the one step per sample is taken.
The step design comes from the smoothness-based online graph learning literature. Online Proximal ADMM for Graph Learning from Streaming Smooth Signals and Dual-based Online Learning of Dynamic Network Topologies show that single-step ADMM and dual steps track faster than primal proximal gradient. However, they use a Dirichlet-energy penalty that is already separable in the node domain and has no commutator, so their splitting does not transfer. Our splitting into a spectral copy and a node copy is the new ingredient.
The analysis comes from Online Alternating Direction Method, which proves $O(\sqrt{T})$ regret for both the objective and the cumulative violation of a linear constraint under one ADMM pass per round. We inherit this for the consensus constraint $\mathbf{S}=\mathbf{Z}$. The missing piece is that our quadratic subproblem is solved in an estimated, time-varying basis. We must bound the extra regret from eigenbasis tracking error, plausibly through a term proportional to the cumulative subspace error weighted by the eigengaps.
Polynomial Graphical Lasso: Learning Edges from Gaussian Graph-Stationary Signals constrains our design. Its finding that pure commutation models need many samples warns that small sample-covariance eigengaps are themselves noisy. We therefore floor the gaps at a level set by the covariance estimation error and treat the floor as a tuned hyperparameter. Making the precision-matrix version of that paper streaming is a natural follow-up but is not the claim here.
Research Program
We will build the algorithm in three coupled single-step updates per sample. The first is the rank-one covariance update with a forgetting factor. The second is one warm-started subspace-iteration and Rayleigh–Ritz step that refreshes $\mathbf{V}_t$ and $\mathbf{\Lambda}_t$ at $O(N^3)$ cost, which matches the matrix products the existing proximal gradient method already performs. The third is one ADMM pass consisting of the spectral closed-form step, the node-domain prox, and the dual update.
We will also implement a cheaper variant that refreshes the eigenbasis only every $k$ samples. This tells us whether exact spectral alignment is necessary.
On the theory side, we will derive dynamic regret and cumulative consensus-violation bounds in the style of the online ADMM analysis, without any strong-convexity assumption. We will state an explicit contraction rate per spectral component for both proximal gradient and the split method, so that the eigengap prediction can be falsified experimentally.
Baselines
The naive reference point is the "do nothing" estimate: the graph is estimated once from an initial window and frozen, with a thresholded sample correlation matrix as a second trivial reference. Any method that cannot beat these after a topology change is not tracking.
The strongest existing competitor is online proximal gradient on the commutation loss from Online Topology Inference from Streaming Stationary Graph Signals. It optimizes exactly the same objective with exactly one step per sample, so any gain must come from the step itself. We will run it on identical streams with the same forgetting factor, sparsity weight and constraint set. Its step size will be tuned on a grid of the same size as our grid over the penalty weight and gap floor. We will also give it a Nesterov-accelerated version, since acceleration is the obvious repair a reviewer would expect.
The reported number to beat is from its companion paper, Online Topology Inference from Streaming Stationary Graph Signals with Partial Connectivity Information: on the Facebook graph it reports an F-measure of 0.94 once observations reach $10^6$. Beating it means reaching an F-measure of 0.94 with substantially fewer samples, and reaching it in fewer samples after an edge perturbation, at equal or lower wall-clock time per step.
The upper-reference baseline is a sliding-window batch solve of the same commutation problem to convergence at every refresh. It shows how much accuracy one step gives up.
The cross-prior baseline is the smoothness-based single-step proximal ADMM of Online Proximal ADMM for Graph Learning from Streaming Smooth Signals, run on the same diffusion streams. It tests whether stationarity matters at all when the step is ADMM.
The key ablation feeds the split method a stale or randomly perturbed eigenbasis. This isolates whether the gain comes from exact spectral diagonalization or merely from having an ADMM proximal term.
Why not just…?
Why not just tune or accelerate the proximal gradient step? Acceleration improves the dependence on conditioning from the condition number to its square root, but the condition number here is $(\lambda_{\max}-\lambda_{\min})^2/g_{\min}^2$. That stays very large when communities produce clustered eigenvalues. The accelerated baseline is included, and our sweep over stochastic block models with controlled eigengaps will show whether its lag still grows with $1/g_{\min}$. If it does not, the core claim fails and we will say so.
Why not just precondition the gradient in the eigenbasis? A diagonal preconditioner in the spectral domain makes the gradient step well-conditioned. However, the $\ell_1$ and nonnegativity prox then has to be computed in that non-Euclidean metric, where it is no longer entrywise and becomes a full inner optimization problem. The split exists precisely to keep each half separable. We will nevertheless run preconditioned gradient with an approximate Euclidean prox as an extra ablation, because it is the closest cheap competitor.
Why not just rerun the batch solver on a sliding window? For small graphs this may truly match us in accuracy, and we expect it to on the karate club graph. Its weaknesses are window lag and cubic cost multiplied by the inner iterations. The original online paper reports that it fails to scale beyond a few hundred nodes. Our comparison reports accuracy against wall-clock time on the 2,888-node Facebook graph, which settles where this alternative stops being competitive.
Proposed Experiments
On synthetic Erdős–Rényi, Barabási–Albert and stochastic block model graphs, we will generate stationary signals by filtering white noise through random polynomial diffusion filters. We will switch the topology abruptly at a known time and vary the within-block density to control the smallest relevant eigengap. Metrics are F-measure and normalized mean error over time, samples-to-recovery after the switch, cumulative consensus violation $\sum_t\|\mathbf{S}_t-\mathbf{Z}_t\|_F$, and time per step.
The decisive check is a plot of recovery samples against $1/g_{\min}^2$. Proximal gradient should rise linearly and the split method should stay roughly flat. The stale-basis ablation should fall between the two.
On the karate club graph we will repeat the published 10% edge-change protocol. No recovery number is reported on Lacuna for that experiment, so we will report full curves for all methods.
On the Facebook graph we will compare samples needed to reach the reported 0.94 F-measure.
On S&P 500 returns spanning 2019–2022, where there is no ground-truth graph, we will measure held-out Gaussian log-likelihood of the next window under the covariance implied by each tracked graph, along with reaction speed around the March 2020 shock. We will also run a hidden-node variant that adds the proxy matrix of Online Network Inference from Graph-Stationary Signals with Hidden Nodes to the node-domain step. No numeric result for that method on Lacuna exists for comparison, so it will be rerun under our protocol.
A negative outcome would also be informative. If the gap floor needed in small-sample regimes erases the advantage, it would show that sample-covariance noise, not optimization conditioning, limits online stationary graph tracking.
References
- Connecting the Dots: Identifying Network Structure via Graph Signal Processing
- Stationary signal processing on graphs
- Online Topology Inference from Streaming Stationary Graph Signals.
- Online Network Inference from Graph-Stationary Signals with Hidden Nodes
- Online Proximal ADMM for Graph Learning from Streaming Smooth Signals
- Dual-Based Online Learning of Dynamic Network Topologies
- Online Alternating Direction Method
- Polynomial Graphical Lasso: Learning Edges From Gaussian Graph-Stationary Signals
- Online Topology Inference from Streaming Stationary Graph Signals with Partial Connectivity Information