Many Covariances, One Graph: Learning Sensor Networks from Incomplete Traffic Tensors

Traffic, metro, and air-quality monitoring produce data shaped like a cube: sensors × time of day × days. Much of it is missing, often as "blackouts" where a sensor goes dark for hours or days at a time. Two literatures address parts of this. One fills in the missing entries using the cube's low-rank structure, but it needs a sensor graph supplied in advance, usually road distance or a nearest-neighbour heuristic. The other recovers an unknown graph from signals using commutation, but it needs complete data and a single covariance matrix. This note proposes to use the cube's shape as the source of identifiability. Each time-of-day window, such as the morning rush or the night, yields its own sensor-by-sensor covariance. If traffic fluctuations spread over one fixed network, all of these covariances must commute with the same graph matrix, even though their spectra differ from window to window.

Here is the idea in two sentences. Stack the per-window covariances of an incomplete spatiotemporal tensor and find the single sparse graph that commutes with all of them. Estimate those covariances with a missing-data-aware EM step that alternates with the graph update, so the learned graph also imputes the blackouts. The payoff is twofold. The graph becomes identifiable in regimes where one pooled covariance is ambiguous, and blackout imputation can use a data-driven graph instead of a fixed road graph.

Core Claim

Some terms first. A graph shift operator $S$ is an $N\times N$ matrix, such as an adjacency or Laplacian, encoding which of the $N$ sensors are connected. A signal is stationary on $S$ when its covariance shares $S$'s eigenvectors, as with diffusion-like spreading (Stationary Signal Processing on Graphs, Connecting the Dots). The two matrices then commute, and existing methods search for a sparse $S$ minimizing $\|\widehat C S - S\widehat C\|_F$.

The weakness of the single-covariance version is algebraic. If $\widehat C$ has nearly repeated eigenvalues, many non-graph matrices also nearly commute with it, and the problem is poorly posed. Traffic covariances pooled over a whole day are dominated by a few daily-profile directions, which makes this worse.

Our claim concerns $W$ window covariances $C_w = V\,\mathrm{diag}(h_w)\,V^\top$, which share eigenvectors $V$ but have different spectral responses $h_w$. The set of matrices commuting with all of them is exactly the set of polynomials in $S$ under one condition: for every pair of eigenvectors $i\neq j$, some window $w$ must have $h_w(i)\neq h_w(j)$. Rush hour and night must disagree somewhere. This is the same condition, in different clothing, under which the symmetric three-way factorization of the stacked covariances is essentially unique.

We will prove this separation result with finite-sample error bounds. We will also show empirically that joint commutation over windows recovers graphs from fewer days and under heavier blackouts than pooled commutation. Finally, we will show that the learned graph improves blackout imputation over fixed-graph tensor completion.

Model and Algorithm

Write the tensor as $X\in\mathbb{R}^{N\times T\times D}$ (sensors, time of day, days), observed on an index set $\Omega$. Each sensor snapshot is split into two parts:

$$x_{t,d} = m_{t,d} + e_{t,d},\qquad e_{t,d}\sim\mathcal N\big(0,\;V\,\mathrm{diag}(h_{w(t)})\,V^\top\big).$$

The mean $m$ is a low-rank tensor that captures the daily and weekly profile. It is fitted with a data-driven unitary-transform, low-tubal-rank model in the style of LSTC-Tubal. The fluctuation $e$ is stationary on the unknown graph, and $w(t)$ maps each time step to its window.

Removing the mean before learning the graph matters. Otherwise the dominant, graph-uninformative daily profile swamps the covariance.

The algorithm alternates three blocks.

Mean step. Update $m$ by low-rank tensor completion on the observed entries.

E-step. Given the current $S$ and spectra, compute the conditional mean and conditional covariance of each missing fluctuation given the observed sensors on that day. This is the generalized Wiener or best-linear-unbiased estimator of Wide-Sense Stationarity in Generalized Graph Signal Processing, used here with an estimated rather than known graph. The expected window second moments $\widehat C_w$ include the conditional-covariance term. This avoids a specific bias: plugging imputed values into a sample covariance shrinks it toward low rank and corrupts the commutator exactly where blackouts are densest.

Graph step. Solve

$$\min_{S\in\mathcal S}\;\sum_{w=1}^{W}\big\|\widehat C_w S - S\widehat C_w\big\|_F^2 + \lambda\|S\|_1 - \alpha\sum_{i=1}^N \log\,(S\mathbf 1)_i ,$$

where $\mathcal S$ is symmetric, non-negative, zero-diagonal matrices and the log term prevents the empty graph. We reuse the log-barrier model and linearized ADMM of LogSpecT, which gives closed-form updates. The summed loss is still quadratic in $S$, so the cost per iteration is $O(WN^3)$ matrix products, with no $N^7$ blow-up of the kind reported for Gaussian GGSR. The spectra $h_w$ then follow in closed form by projecting $\widehat C_w$ onto the eigenvectors of $S$.

Warm starts come from the pooled single-covariance solution, since alternating schemes are initialization-sensitive (MNT-TNN).

Research Program

The work has three parts.

Theory. We prove the separation condition for joint commutation. We derive how estimation error scales with days $D$, windows $W$, and the per-sensor observed fraction. The expected rate is $O(1/\sqrt{D_{\text{eff}}})$, where $D_{\text{eff}}$ is the number of days on which a sensor pair is co-observed, since each $\widehat C_w$ is an average over those days. We also prove convergence of the three-block scheme to a coordinate-wise stationary point, following the Kurdyka-Łojasiewicz arguments used by Guan et al..

Controlled studies. On synthetic graphs, window filters with tunable spectral diversity are applied under random and blackout masks. These studies map where joint commutation beats pooled commutation.

Real benchmarks. On traffic tensors, we measure imputation quality and graph stability.

Two scope limits apply. Sensors that are dark for the entire record are hidden nodes. For them we add the group-sparse correction of Joint Network Topology Inference in the Presence of Hidden Nodes as an extension, not the main contribution. Graphs that switch regime across days (Gap 4 in the file) are out of scope; we assume one graph with varying filters.

On related work, the joint-inference approach of Navarro et al. estimates many graphs from many covariances with a known signal-to-graph assignment and complete data. We estimate one graph from many incomplete covariances. The closest work is Shen, Baingana, Giannakis, which already stacks window covariances into a three-way tensor and uses factorization uniqueness to identify a directed structural-equation graph. We differ in four ways: we use commutation with sparsity and barrier priors rather than unconstrained factorization, we handle missing and blackout data through the E-step, we remove a low-rank mean first, and we feed the graph back into imputation. Their method is therefore a baseline, not a precursor to ignore. The graph-regularized completion methods (Guan et al., Duan et al., MNT-TNN) motivate the work: all take the graph as fixed input, and MNT-TNN's authors name non-adaptive Laplacians as a limitation.

Baselines

Pooled commutation. The naive reference point runs rLogSpecT on a single covariance computed from pairwise-available entries of the flattened sensors × time matrix, with no tensor structure and no imputation. It is what a practitioner would try first. It shares our graph solver, barrier weight grid, and iteration budget, so any gain is attributable to windows and missing-data handling. On complete data, rLogSpecT reports an F-measure of 0.96 on USPS pixel-graph recovery (LogSpecT). We will reproduce this on complete USPS first as a sanity check, then mask pixels.

Two-stage pipeline. The strongest graph-learning competitor imputes the tensor with LATC or LSTC-Tubal, then runs rLogSpecT on the imputed data. It is also run in an iterated variant that re-imputes with the learned graph. This competitor is the real threat, because it reuses the best available imputer. The file reports no numbers for LATC on the Guangzhou, Hangzhou, Seattle, or Portland data ("no reported result found on Lacuna for LATC RMSE/MAPE"). LSTC-Tubal reports 1.72–2.5% MAPE at 70% random missing (LSTC-Tubal).

Stacked-covariance factorization. Following Shen et al., we run a symmetric three-way factorization of the stacked window covariances, then spectral-template edge fitting (Connecting the Dots) on the recovered eigenvectors. This tests whether uniqueness alone, without commutation priors, suffices.

Fixed-graph imputation. The strongest imputation competitors are MNT-TNN with its warm-start booster and Guan et al.'s graph-regularized completion, each given a road-distance Gaussian-kernel graph. MNT-TNN reports about 36.5% MAPE at 97% missing on CHSP (MNT-TNN).

Ablations. The key ingredient is isolated by three ablations: $W=1$ (pooled) against $W>1$; plug-in second moments against EM second moments; and mean removal on against off.

Fairness and success criteria. All methods get the same masks, the same tuning budget on a held-out validation mask, and the same hardware. Beating the field means two things. On synthetic data, higher edge F-measure than all graph baselines at matched observed fraction. On real data, lower blackout-scenario RMSE and MAPE than the fixed-graph and two-stage methods on at least three of the four sensor-network datasets.

Why not just…?

Why not just impute first and then run LogSpecT? This is the most serious alternative, and under light random missingness it may well tie. Its covariance is computed from imputed values that are too smooth, and the error concentrates on blacked-out sensors, which are precisely the ones whose edges matter. The iterated two-stage variant closes part of this gap. What remains is the conditional-covariance correction and the use of multiple windows, which the two ablations measure separately. If the iterated two-stage variant matches us under blackouts, we will report that the contribution reduces to the window identifiability result and not to the joint algorithm.

Why not just flatten and use Graphical Lasso or pooled commutation? Graphical Lasso assumes precision-matrix zeros are edges. It fails outright under polynomial diffusion (GGSR). Flattening also discards the daily-versus-weekly separation that makes tensor methods beat their matrix counterparts, as LATC does against LAMC (LATC). The $W=1$ ablation directly measures what pooling costs.

Why not just use the road-distance graph? Physical adjacency need not match functional influence. Shen et al. found dependencies between business competitors driven by market shocks, not proximity. Learned shift operators outperformed fixed transforms for imputation in Jian and Tay. Still, road graphs are a strong prior. We therefore also test initializing and regularizing toward the road graph, and report whether learning adds anything beyond it.

Why not just train a diffusion model or transformer imputer? MNT-TNN reports that optimization methods beat CSDI and Imputeformer at extreme missingness. Diffusion imputers struggle beyond roughly a hundred channels (SADI, SSSD). Neither yields an interpretable graph. We treat them as imputation references on Hangzhou (80 stations), where they are feasible, not as graph learners.

Proposed Experiments

Synthetic graphs. We use Erdős–Rényi and geometric graphs with 50–300 nodes, with window filters built as polynomials in $S$. A single knob sets how far apart window spectra are. Masks cover random missing and blackouts of 30–90%. Edge F-measure and relative graph error are plotted against days, blackout fraction, and spectral diversity.

The decisive check is a predicted crossover. When window spectra are proportional, so the separation condition fails, joint and pooled commutation should perform equally. As diversity grows, joint commutation should pull ahead. If no crossover appears, the core claim is wrong.

Real graphs with known structure. USPS pixel graphs and the protein contact benchmark are run with artificial masking. This measures how fast recovery degrades from the reported complete-data performance (0.96 F-measure on USPS; 53% contact recovery for spectral templates, per Connecting the Dots). These datasets have no time-of-day axis, so windows are formed from sample batches. The test here is the E-step, not window diversity.

Traffic tensors. Guangzhou (214 × 144 × 61), Hangzhou metro, Seattle (323 stations), and Portland (1,156 stations; the scaling stress test) are evaluated under the random, non-random, and blackout masks used by LATC, with held-out RMSE and MAPE. PEMS-BAY and CHSP are added at up to 97% missing to meet MNT-TNN on its own ground. Real traffic has no ground-truth graph, so graph quality is judged indirectly in three ways: stability of learned edges across disjoint day subsets, overlap with road adjacency as a plausibility check rather than a target, and the imputation gain that swapping the learned graph into MNT-TNN produces over its road graph. Wall-clock time is reported against LSTC-Tubal's roughly 8 minutes on PeMS-4W to make the $O(WN^3)$ cost concrete.

The proposal succeeds if joint commutation shows the predicted crossover on synthetic data and also reduces blackout imputation error on real tensors beyond the iterated two-stage pipeline. If only the first holds, the result is a topology-inference paper, and we will present it as one.