When thousands of sensors, stocks or brain regions are recorded over time, the standard linear forecasting model is a vector autoregression: each time step is predicted as a weighted mix of past time steps. It needs one $N \times N$ matrix of coefficients per lag, so the parameter count grows with $N^2$ and exceeds the data whenever there are more variables than time points. A known way out is to assume that the dynamics spread along a network. Each lag matrix then becomes a short polynomial of a single graph matrix $\mathbf{S}$, and the whole model needs only a handful of scalar weights. The catch is that this trick requires knowing the network in advance. Methods that learn the network from data usually look at a single covariance matrix computed as if the time samples were independent.
This proposal makes one observation and builds a method around it. If the dynamics really are polynomials of $\mathbf{S}$, then every lagged covariance $\mathbb{E}[\mathbf{x}_{t+\tau}\mathbf{x}_t^\top]$ commutes with $\mathbf{S}$, not just the zero-lag one. Each lag is a separate algebraic constraint on the same unknown graph. Stacking these constraints into one convex program should identify the graph in cases where the zero-lag covariance alone cannot, because some of its eigenvalues are tied or nearly tied. It should also turn temporal correlation from a nuisance into a source of information. The graph recovered this way then directly yields a compressed, graph-structured autoregression whose cost is $P(K+1)$ filter weights instead of $PN^2$ coefficients.
Core Claim
Commutation-based topology inference rests on graph stationarity. A random signal is called stationary on a graph when its covariance is diagonalized by the eigenvectors of the graph's shift operator $\mathbf{S}$, an adjacency or Laplacian matrix. This is equivalent to the covariance commuting with $\mathbf{S}$, as established in Stationary Graph Processes and Spectral Estimation. The resulting estimator in Connecting the Dots: Identifying Network Structure via Graph Signal Processing finds the sparsest valid $\mathbf{S}$ that commutes with the sample covariance.
Its weakness is well known. Commutation with a single symmetric matrix $\mathbf{C}$ pins down $\mathbf{S}$ only up to the eigenspaces of $\mathbf{C}$. Wherever $\mathbf{C}$ has repeated eigenvalues, or eigenvalues that sampling noise makes indistinguishable, any rotation inside that eigenspace is allowed, and the feasible set becomes large.
Now consider a graph-filter autoregression of the kind used in Forecasting Time Series with VARMA Recursions on Graphs:
$$\mathbf{x}_t=\sum_{p=1}^{P}\mathbf{A}_p\mathbf{x}_{t-p}+\mathbf{e}_t,\qquad \mathbf{A}_p=\sum_{k=0}^{K}h_{p,k}\mathbf{S}^k .$$
Here $\mathbf{x}_t\in\mathbb{R}^N$ is the vector of node values at time $t$, $h_{p,k}$ are scalar filter weights, and the innovation noise $\mathbf{e}_t$ is itself stationary on the graph. In this model, each lagged covariance $\mathbf{C}_\tau=\mathbb{E}[\mathbf{x}_{t+\tau}\mathbf{x}_t^\top]$ is a function of $\mathbf{S}$, and its spectrum is the spectral response of the process at lag $\tau$. Different lags weight each graph frequency differently, so a tie between two eigenvalues at lag 0 is generically broken at some other lag.
The core claim has two parts. The first is identifiability: if, for every pair of distinct graph frequencies, at least one lag $\tau\le L$ separates their spectral responses, then the set of matrices commuting with all of $\{\mathbf{C}_0,\dots,\mathbf{C}_L\}$ is exactly the set of matrices diagonal in the eigenbasis of $\mathbf{S}$. That is the best case for spectral-template recovery. The second is a finite-sample claim: the estimator below recovers edges with fewer time samples than zero-lag commutation whenever $\mathbf{C}_0$ is poorly conditioned in this sense, and it is no worse otherwise.
The estimator solves
$$\min_{\mathbf{S}\in\mathcal{S}}\ \|\mathbf{S}\|_1\quad\text{s.t.}\quad \sum_{\tau=0}^{L}w_\tau\big\|\hat{\mathbf{C}}^{\,s}_\tau\mathbf{S}-\mathbf{S}\hat{\mathbf{C}}^{\,s}_\tau\big\|_F^2\le\delta^2,$$
where $\hat{\mathbf{C}}^{\,s}_\tau$ is the symmetrized sample lag-$\tau$ covariance. Symmetrizing is harmless because $\mathbf{C}_\tau$ is symmetric in the population model when $\mathbf{S}$ is. The weights $w_\tau$ down-weight noisier long lags. The set $\mathcal{S}$ contains symmetric, nonnegative, zero-diagonal matrices whose first row sums to one, which rules out the trivial solution $\mathbf{S}=0$. The tolerance $\delta$ absorbs sampling error. The program is convex, and each iteration costs $L+1$ times the cost of the single-covariance version.
Relation to Prior Work
Two papers motivate the gap from opposite sides. Forecasting Time Series with VARMA Recursions on Graphs and its precursor Predicting the evolution of stationary graph signals solve the parameter explosion by writing lag matrices as polynomials of a graph Laplacian. They show that projecting onto the graph's eigenvectors splits the system into $N$ independent scalar autoregressions. Both take the graph as given, from station coordinates for example, and name learning it as future work. We supply that missing graph from the time series itself.
Semi-Blind Inference of Topologies and Dynamical Processes over Graphs does learn networks inside a structural autoregression, alternating Kalman smoothing with sparse matrix updates. It keeps a separate sparse $N\times N$ matrix per lag and never uses stationarity, so its parameter count still scales as $PN^2$.
Three papers supply method and constrain the design. Polynomial Graphical Lasso (also; Polynomial Graphical Lasso: Learning Edges from Gaussian Graph-Stationary Signals; Polynomial Graphical Lasso: Learning Edges From Gaussian Graph-Stationary Signals) relaxes commutation to a Frobenius-norm inequality between the precision matrix and $\mathbf{S}$, the device we reuse with $\delta$. It is built for independent Gaussian samples and has no lag structure. Joint Inference of Multiple Graphs from Matrix Polynomials uses several covariances to infer several related graphs and proves recovery bounds for independent samples. We invert that setup: several covariances, all generated by the same process, constrain one graph. The guarantees must therefore handle serial dependence.
For serial dependence we borrow from Estimating Structured Vector Autoregressive Models. That paper shows that temporal dependence in a stable vector autoregression changes only the constants, not the rate, of covariance deviation bounds, and that those constants degrade near instability. We expect the same constants to set how $\delta$ must scale with $T$ and with the spectral radius.
On the parameter-explosion side, the competitors compress statistically rather than through a graph. Lasso-type penalties come from Estimating Structured Vector Autoregressive Models. The sparse Tucker tensor estimator SHORR comes from High-Dimensional Vector Autoregressive Time Series Modeling via Tensor Decomposition. Node clustering comes from Simultaneous Estimation and Group Identification for Network Vector Autoregressive Model with Heterogeneous Nodes. None of them outputs an explicit sparse graph whose polynomials are the dynamics.
Research Program
The work has three parts.
The first part is theory. We will prove the population identifiability statement: the joint commutant of the lag covariances equals the commutant of $\mathbf{S}$ under a lag-separation condition on the spectral responses $\{\tilde h_\tau(\lambda_i)\}$. We will then show that the existing sparse spectral-template recovery conditions transfer unchanged. For finite samples, we will bound $\|\hat{\mathbf{C}}_\tau-\mathbf{C}_\tau\|$ under graph-VAR dependence using the generic-chaining arguments of Melnyk and Banerjee. This gives a recovery guarantee whose sample requirement depends on the smallest across-lag separation of graph frequencies rather than on the zero-lag eigengap. We also want to characterize honestly when extra lags hurt. For a nearly white process, $\mathbf{C}_\tau\approx 0$ for $\tau\ge1$, so those terms add noise and no information. The weights $w_\tau$ should then be chosen from estimated signal-to-noise per lag, and the theory should say how.
The second part is the estimator and forecaster. Stage one solves the convex program above, with an ADMM solver adapted from the single-covariance case. Stage two fixes $\hat{\mathbf{S}}$ and fits the $P(K+1)$ weights $h_{p,k}$ by ordinary least squares. This regression is linear in the weights and therefore well-posed even when $N>T$. An optional stage three alternates the two steps: it re-estimates $\mathbf{S}$ by adding a penalty that makes it commute with the fitted lag matrices, then refits $h$. This stage is biconvex rather than convex, so it is treated as an ablation and not as the main method.
We restrict to undirected graphs. The file is explicit that commutation breaks down for directed, non-normal operators Stationary Graph Processes and Spectral Estimation, and we do not claim otherwise.
The third part is diagnostics. A method that assumes graph stationarity should be able to say when the data violate it. We will report the residual commutation error at each lag after fitting. A large residual at long lags but not short ones indicates dynamics that are not graph filters, and flags datasets where the method should not be trusted.
Baselines
The naive reference point is a separate univariate autoregression per node, plus Ridge-regularized full vector autoregression. Both use the same lag order $P$ chosen by validation on the same splits. Any graph method that cannot beat per-node models is not using the network.
The strongest statistical compression competitor is SHORR from High-Dimensional Vector Autoregressive Time Series Modeling via Tensor Decomposition. It is the strongest because it compresses all three axes of the lag tensor at once and has a published win over Lasso. On the US macroeconomic panel ($N=40$), that paper reports out-of-sample $\ell_2$ forecast error 5.35 for SHORR, against 6.72 for Lasso and 8.16 for nuclear-norm regularization. We will reuse their split and error definition. Matching 5.35 with an explicit graph would be a meaningful result, and beating it would be a strong one. Lasso vector autoregression, following Estimating Structured Vector Autoregressive Models, runs on every dataset with the same regularization grid size as our $\delta$ and $\lambda$ grid.
The strongest graph-learning competitor is the two-step pipeline. First, estimate $\mathbf{S}$ from the zero-lag sample covariance by spectral-template commutation Connecting the Dots, or by Polynomial Graphical Lasso, pooling time points as if independent. Then fit the same graph-filter autoregression. This baseline uses identical stage-two code and identical tuning budget, so it differs from our method only in whether lags $\tau\ge1$ enter graph estimation. That makes it simultaneously the key ablation ($L=0$ versus $L>0$). Beating it means higher edge F1 or lower normalized error in $\mathbf{S}$ on synthetic data at matched $T$, and lower forecast error on real data.
We also include the structural autoregression of Semi-Blind Inference of Topologies and Dynamical Processes over Graphs as the existing joint graph-and-dynamics method. Beating it means equal or better forecasts with orders of magnitude fewer dynamic parameters. Finally, where a physical graph exists, G-VARMA run on that known graph Forecasting Time Series with VARMA Recursions on Graphs is an oracle-style reference. Coming within noise of it with a learned graph is the target, not exceeding it. A further ablation compares uniform against SNR-based lag weights $w_\tau$, and stage-three refinement against none.
Why not just…?
Why not just pool the time samples and run single-covariance commutation or Polynomial Graphical Lasso, then G-VARMA? This is the main threat, and it is plausible that it works equally well whenever the zero-lag covariance has a well-separated spectrum. Polynomial Graphical Lasso is developed for independent samples and does not use lagged structure. The identifiability argument predicts a gap only where $\mathbf{C}_0$ has tied or near-tied eigenvalues. We will therefore construct synthetic processes that control that tie directly. The $L=0$ versus $L>0$ ablation then settles the question. If no gap appears even with engineered ties, the core claim is wrong and we will report it.
Why not just read the graph off the support of a Lasso-estimated lag-one matrix? Lasso vector autoregression has clean rates Estimating Structured Vector Autoregressive Models, but it estimates $PN^2$ entries. Under polynomial dynamics, $\mathbf{A}_1$ is a polynomial of $\mathbf{S}$, so its support covers multi-hop neighbors and is denser than the graph itself. We expect inflated false positives as the filter order $K$ grows, and the synthetic edge-F1 curves against $K$ will show whether this happens.
Why not just use a low-rank tensor autoregression and skip the graph? SHORR's 5.35 on macro data shows tensor compression works High-Dimensional Vector Autoregressive Time Series Modeling via Tensor Decomposition. On a 40-variable economic panel, graph stationarity may simply be the wrong assumption, and SHORR may win there. We treat that dataset as a stress test, not a showcase. Our case rests on diffusion-like data (temperatures, meshes, epidemics), where an explicit sparse graph is both the right model and the interpretable output.
Proposed Experiments
Synthetic tests generate graph-filter autoregressions on Erdős–Rényi, Barabási–Albert and small-world graphs, following the topologies used for Polynomial Graphical Lasso. We vary $N$ from 50 to 500, $T$ from below $N$ to well above it, the filter order $K$, the spectral radius, and a degeneracy knob that flattens the zero-lag spectrum while keeping later lags informative. Metrics are edge F1, normalized error of $\mathbf{S}$, and forecast error. The decisive check is that the advantage of $L>0$ grows with the degeneracy knob and vanishes when it is off. A second check is that the required $T$ grows as the process nears instability, as the dependence bounds predict.
Real-data experiments use five sources. On Molene ($N=32$), Loukas and Perraudin report a median 2-hour-ahead error of approximately 0.4 Predicting the evolution of stationary graph signals using a known graph, and we ask whether a learned graph matches it. On NOAA ($N=109$), standard vector autoregression failed and G-VARMA was stable Forecasting Time Series with VARMA Recursions on Graphs; no scalar forecast error is reported on Lacuna for NOAA, so we rerun the known-graph G-VARMA ourselves as the reference. We also report how close the learned graph comes to the geographic one. The US macro panel is compared against SHORR's 5.35. The walking-dog mesh ($N=251$) has a known mesh graph for edge-recovery scoring. ChronoGraph ($N\approx708$) ChronoGraph tests scalability, scored against the symmetrized dependency graph; because that graph is directed, it also probes our undirected assumption. No scalar forecast result for ChronoGraph is reported on Lacuna, so all its baselines are run fresh. On every dataset we report the per-lag residual commutation diagnostic alongside accuracy, so a reader can see where the stationarity assumption holds.
References
- Stationary Graph Processes and Spectral Estimation
- Connecting the Dots: Identifying Network Structure via Graph Signal Processing
- Forecasting Time Series With VARMA Recursions on Graphs
- Predicting the evolution of stationary graph signals
- Semi-Blind Inference of Topologies and Dynamical Processes Over Dynamic Graphs
- Polynomial Graphical Lasso: Learning Edges From Gaussian Graph-Stationary Signals
- Polynomial Graphical Lasso: Learning Edges from Gaussian Graph-Stationary Signals
- Joint Inference of Multiple Graphs from Matrix Polynomials
- Estimating Structured Vector Autoregressive Models
- High-Dimensional Vector Autoregressive Time Series Modeling via Tensor Decomposition
- Simultaneous estimation and group identification for network vector autoregressive model with heterogeneous nodes
- CHRONOGRAPH: A Real-World Graph-Based Multivariate Time Series Dataset