Repairing a Known-but-Wrong Network from One Graph-Stationary Snapshot

Many systems give us exactly one snapshot of a signal spread over a network, together with a map of that network that we know is partly wrong. Examples include one day's traffic readings over a road map with missing or closed links, one expression profile over a curated gene interaction graph, or one set of paper labels over a citation graph with spurious and absent citations. Methods that estimate parameters from a single networked sample assume the map is correct. Methods that infer the network from signals need many independent snapshots to estimate a covariance matrix. We propose to correct a noisy prior network using a single snapshot. The data are asked only for a small set of edge edits, never for the whole graph. The edits are scored by a node-by-node conditional likelihood, which stays well-posed with one sample, under the constraint that the signal's precision matrix commutes with the corrected network.

The two-sentence version is this. The same diffusion over a network that makes correlations spread along paths also forces the precision matrix to be a polynomial in the network matrix. Each node's value given its neighbors therefore depends on the network in a structured way, and a single snapshot supplies $n$ such conditional equations, enough to identify a sparse set of edge corrections but not a full graph. We build the estimator, test when this identifiability holds, and check whether it beats simpler repairs that ignore the signal or ignore multi-hop structure.

Why the obvious version fails, and what we do instead

The obvious bridge between these literatures is blind topology inference from one snapshot. It does not work. Commutation-based inference, surveyed in Connecting the Dots, fits a graph shift operator $\mathbf{S}$ (a matrix encoding the network, such as an adjacency or Laplacian) so that it commutes with the sample covariance. With one snapshot that covariance is $\mathbf{x}\mathbf{x}^T$. This rank-one matrix leaves $n-1$ eigenvectors unconstrained, so the problem collapses. Polynomial Graphical Lasso (PGL) replaces the covariance fit with a Gaussian likelihood plus a relaxed commutation constraint $\|\boldsymbol{\Theta}\mathbf{S}-\mathbf{S}\boldsymbol{\Theta}\|_F\le\delta$. That cuts the samples needed, but PGL still forms a sample covariance and has no content at $M=1$.

A counting argument rules out any fully blind fix. A scalar snapshot provides $n$ numbers, and a sparse graph typically has more than $n$ unknown edges. Estimating Ising Models from One Sample makes the same point from the single-sample side. It shows an interaction matrix can be learned from one sample only when it lies in a low-dimensional family, with error scaling like $\sqrt{k\log n}$ for a $k$-dimensional family. Ergodicity in Stationary Graph Processes shows a single stationary realization behaves like its own ensemble, but only by diffusing over a known $\mathbf{S}$.

Our resolution is to supply the low-dimensional family through a prior graph $\mathbf{S}_0$. We then estimate an $s$-sparse edit $\boldsymbol{\Delta}$ with $\mathbf{S}=\mathbf{S}_0+\boldsymbol{\Delta}$, and use commutation to tie the precision matrix to $\mathbf{S}$ through only a few polynomial coefficients. This differs from Dagan et al. because the family is not a hand-given dictionary of $k$ matrices. It is a sparse neighborhood of a prior graph, and commutation couples the edges nonlinearly through higher powers of $\mathbf{S}$. It differs from PGL because the fit is a pseudo-likelihood, which is consistent from one sample, not a full Gaussian likelihood built on a covariance.

Core Claim

Consider a Gaussian graph-stationary snapshot, meaning $\mathbf{x}$ is white noise passed through a polynomial filter of $\mathbf{S}$, so its precision is $\boldsymbol{\Theta}=\sum_{k=0}^{K}\beta_k\mathbf{S}^k$. Each node then satisfies $x_i\mid\mathbf{x}_{-i}\sim\mathcal{N}\big(-\sum_{j\ne i}\Theta_{ij}x_j/\Theta_{ii},\,1/\Theta_{ii}\big)$. The objective is

$$ \min_{\boldsymbol{\Delta},\,\boldsymbol{\beta}}\;-\sum_{i=1}^{n}\log p\big(x_i\mid\mathbf{x}_{-i};\,\boldsymbol{\Theta}(\mathbf{S}_0+\boldsymbol{\Delta},\boldsymbol{\beta})\big)\;+\;\lambda\|\boldsymbol{\Delta}\|_1, $$

where $\boldsymbol{\beta}$ holds the $K+1$ filter coefficients, $\lambda$ sets how many edits are allowed, and $\mathbf{S}_0+\boldsymbol{\Delta}$ is kept in the valid set: symmetric, non-negative off-diagonal, zero diagonal.

The objective uses commutation in two forms. The exact form is the polynomial parameterization above. The relaxed form, as in PGL, treats $\boldsymbol{\Theta}$ as a free sparse matrix with $\|\boldsymbol{\Theta}\mathbf{S}-\mathbf{S}\boldsymbol{\Theta}\|_F\le\delta$, which tolerates departures from exact stationarity.

We conjecture the edit error scales like $\sqrt{s\log n}$ in unnormalized Frobenius norm. The form comes from substituting the metric entropy of $s$-sparse edits, about $s\log n^2$, for the $k$-dimensional entropy in the argument of Dagan et al. It should hold in a weak-dependence regime, meaning bounded condition number of $\boldsymbol{\Theta}$, and should degrade as the spectral gap shrinks, consistent with the Gama–Ribeiro gap requirement.

Research Program

The first strand is theory. We will adapt the conditioning and entropy argument of Estimating Ising Models from One Sample and the concentration argument of Statistical Estimation from Dependent Data to Gaussian conditionals whose coefficients are polynomials in $\mathbf{S}_0+\boldsymbol{\Delta}$. The target is a restricted-strong-convexity condition stating when a single snapshot separates two edits. We expect this condition to fail near repeated eigenvalues, which is the known identifiability hazard for commutation, and to fail when $s$ approaches $n$.

The second strand is the algorithm. The objective is nonconvex in $\boldsymbol{\Delta}$ once $K\ge2$. We alternate a closed-form weighted least-squares update of $\boldsymbol{\beta}$ with proximal gradient steps on $\boldsymbol{\Delta}$. The costs are sparse matrix–vector products with $\mathbf{S}$, not eigendecompositions, which sidesteps the $O(n^3)$ cost of standard commutation solvers. Initializing at $\boldsymbol{\Delta}=0$ is natural and limits the local-optimum risk noted for PGL.

The third strand is tuning without a second sample. When measurements carry additive Gaussian noise of known variance, Graph fission can split the one snapshot into two independent copies on the same nodes. One copy fits the edits and the other scores them. This makes it possible to choose $\lambda$ and $K$ honestly, whereas holding out nodes would break the spectrum. Without known noise we fall back to held-out node conditionals, and we report which tuning method was used.

Baselines

The naive reference is doing nothing: use $\mathbf{S}_0$ unchanged. Any repair must lower edge error relative to the true graph and must not hurt downstream tasks.

The most dangerous competitor ignores the signal entirely: prior-only link prediction. We score candidate additions and deletions from $\mathbf{S}_0$'s own structure using common-neighbor and low-rank spectral scores. We then apply the same number of edits $s$ that our method selects. Beating this baseline is the evidence that the snapshot carries information.

The strongest existing signal-based method is smoothness graph learning in the style of Kalofolias, as benchmarked in Graph Topology Inference Benchmarks for Machine Learning. We run it on the single snapshot with a penalty pulling toward $\mathbf{S}_0$. On Toronto traffic that paper reports 10.41 SNR for graph signal denoising with the learned smoothness graph, against 10.32 for the physical road graph. That result uses many readings, so it is a ceiling rather than a like-for-like competitor. Beating smoothness learning in our single-snapshot protocol, with matched edit counts and matched tuning budget, is the bar.

We also run PGL at $M=1$ with its strongest stable regularization, and spectral templates at $M=1$. These should confirm the collapse. The same methods at $M\in\{10,100\}$ serve as upper references. For PGL, no reported NME value was found on Lacuna. For spectral templates on protein contact networks, the file reports 53% contact recovery against 36–43% for mutual information. That was obtained with many samples, so we cite it only as context.

The key ablation sets $K=1$, so that $\boldsymbol{\Theta}=\beta_0\mathbf{I}+\beta_1\mathbf{S}$. This is single-sample pseudo-likelihood with one-hop interactions, the Kandiros et al. model with editable edges. It isolates whether commutation, meaning the multi-hop polynomial, is what does the work. Every method receives the same snapshot, the same $\mathbf{S}_0$, and the same tuning grid.

Why not just…?

Why not just use link prediction on the prior graph? When corruptions are structurally implausible, such as a deleted edge inside a dense triangle-rich cluster, topology alone may find them. This is a real threat. The experiments settle it by varying corruption type. We compare random flips, which are structurally invisible, against structured deletions, which link prediction should catch. Our method must win on the former and match on the latter. If it only matches everywhere, the claim fails.

Why not just learn a smooth graph from the snapshot? Smoothness learning also works from signals and has good reported downstream numbers. It assumes correlation reflects direct edges, however. Single Index Latent Variable Models shows similarity-based graphs producing spurious long-range links, such as Los Angeles to Fargo, and PGL shows one-hop models failing under multi-hop diffusion. We predict smoothness repair adds shortcut edges whenever the filter order $K\ge2$. The synthetic sweep over $K$ tests exactly this prediction.

Why not just collect more snapshots? Sometimes one can, and then PGL applies. Some settings allow only one snapshot, including a single terminal diffusion state as in DASH/DITTO and per-patient networks as in lionessR, where averaging hid the STAT1 rewiring. We also report the full $M$ curve, which shows the sample size at which PGL overtakes us. That crossover is the practical answer.

Proposed Experiments

The synthetic study follows PGL's setup: small-world and Barabási–Albert graphs with $n$ from 100 to 5000. Signals come from polynomial filters of order $K\in\{1,2,3\}$. The prior $\mathbf{S}_0$ is corrupted by flipping a fraction $\rho\in\{1\%,5\%,15\%\}$ of edges. The metrics are edit precision/recall, $F_1$, and normalized error of $\mathbf{S}$. The decisive checks are three predictions. Error should scale like $\sqrt{s\log n}$ as $n$ grows at fixed $\rho$. The method should break down as $s$ approaches $n$. The $K=1$ ablation should lose once the true $K\ge2$.

On Toronto traffic, the road graph is $\mathbf{S}_0$, and synthetic link removals are applied where ground truth is controlled. We repair the network from one time snapshot, then denoise other snapshots with the repaired graph and report SNR against the reported 10.32 for the road graph and 10.41 for the learned graph.

On Cora we corrupt the citation graph. We then run the Ising analog, using a logistic conditional instead of a Gaussian one, on the single label vector with features. We report the MPLE-β classification accuracy of Statistical Estimation from Dependent Data on the repaired graph. The anchors are its reported 85.3% on the clean graph and 74.5% with dependencies ignored. Recovering most of that gap from a corrupted graph is the downstream success criterion.

The result that would kill the idea is prior-only link prediction matching our edit $F_1$ on random-flip corruptions.