Seeing Untraversed Links: Graph Stationarity Under Path Tomography

Network operators often need to know how a network is wired internally, but they can only measure what happens between its edges. Probes sent between a few monitoring hosts report end-to-end delay or loss, and each measurement is the sum of what the probe experienced at every router it crossed. This setting is called network tomography. Its core difficulty is that there are far more internal quantities than independent paths, so many internal states explain the same boundary data. A separate line of work in graph signal processing learns a graph from signals that spread across it by local diffusion. It relies on a single algebraic fact: if a signal is "stationary" on a graph (its randomness arises from diffusion over the graph's edges), then its covariance matrix commutes with the graph's adjacency matrix. That fact has only ever been applied to signals measured directly at the nodes. Tomography never measures at nodes. It measures sums along paths.

This note proposes moving the commutation condition behind the routing matrix. We treat per-router load as a latent stationary signal, the path covariances as a known linear projection of that signal's covariance, and the routing as a hard constraint that every probe path must be a walk on the unknown graph. The payoff is specific. Second-order path statistics grow quadratically with the number of probed paths, while stationarity reduces the latent router covariance to roughly one free number per router. That combination should make the graph identifiable, including links that no probe ever crosses. Such links are invisible by construction to path-union and path-sharing methods.

Core Claim

Let $\mathbf{x} \in \mathbb{R}^N$ be per-router delay or load fluctuations, $\mathbf{R} \in \{0,1\}^{M \times N}$ the path-router incidence matrix, and $\mathbf{y} = \mathbf{R}\mathbf{x} + \mathbf{e}$ the path measurements, so the path covariance is $\mathbf{C}_y = \mathbf{R}\mathbf{C}_x\mathbf{R}^T + \sigma^2\mathbf{I}$. If $\mathbf{x}$ is stationary on the router graph $\mathbf{S}$, then $\mathbf{C}_x$ shares eigenvectors with $\mathbf{S}$. Once $\mathbf{S}$ is fixed, $\mathbf{C}_x$ has only $N$ free eigenvalues instead of $N(N+1)/2$ entries, while the data supply $M(M+1)/2$ distinct covariances. The usual tomography counting, $L \gg M$, therefore flips in our favor once $M$ grows like $\sqrt{2N}$ plus whatever is needed to pin the sparse support of $\mathbf{S}$. We estimate the latent covariance and the graph jointly:

$$ \min_{\mathbf{S}\in\mathcal{S},\ \mathbf{C}\succeq 0}\ \|\hat{\mathbf{C}}_y - \mathbf{R}\mathbf{C}\mathbf{R}^T\|_F^2 + \mu\|\mathbf{C}\mathbf{S}-\mathbf{S}\mathbf{C}\|_F^2 + \lambda\|\mathbf{S}\|_1 . $$

Here $\hat{\mathbf{C}}_y$ is the sample path covariance, and $\mu,\lambda$ weight the commutation and sparsity terms. The feasible set $\mathcal{S}$ contains non-negative, zero-diagonal matrices whose support must include every pair of consecutive routers on a measured path. That walk constraint is what tomography contributes. It does two jobs. It ties $\mathbf{S}$ to the physical routing, and it removes the trivial solution $\mathbf{S}=0$ without the arbitrary normalization that nodal methods need. The claim is that the minimizer recovers edges outside the path union, provided the measured paths' covariance matrices $\mathbf{R}\mathbf{S}^k\mathbf{R}^T$ are rich enough. We will characterize when that holds.

Relation to Prior Work

Two results motivate this work. Network loss inference with second order statistics of end-to-end flows (LIA) showed that path covariances identify link variances even when first-order means are under-determined. It does so by assuming internal quantities are independent, which gives a diagonal $\mathbf{C}_x$, and a known topology. We keep its insight that second-order statistics break under-determination, but we replace independence with stationarity and make the topology the unknown. On the other side, Joint Network Topology Inference in the Presence of Hidden Nodes (JH-GSR) and its streaming extension Online Network Inference from Graph-Stationary Signals with Hidden Nodes show that unobserved nodes leave a column-sparse "commutator gap" on the observed covariance. Their observation model is a coordinate selection, meaning a few nodes are read directly. Ours is a general aggregation. Selection is the special case in which every "path" is a single router.

We think the right response is to lift the covariance back into router space rather than to model a gap. When paths are sums, every path's projection mixes with the null space of $\mathbf{R}$, so the gap is not column-sparse and the group-lasso prior has no reason to hold. Two other papers supply method. Polynomial Graphical Lasso gives the relaxed-commutation formulation and the alternating linearized solver we adapt. Connecting the Dots: Identifying Network Structure via Graph Signal Processing and Stationary Signal Processing on Graphs give the stationarity model itself.

Three papers constrain the design. OCCAM reconstructs routing topology from path-sharing and distance metrics with a mixed-integer program. It uses only first-order sharing, so it cannot see links absent from every path, and it scales poorly. We use it as an initializer, not a rival formulation. Multicast-Based Weight Inference in General Network Topologies shows that even additive, single-hop models are unidentifiable without wider probes. This warns that adding multi-hop diffusion could worsen identifiability unless the counting argument above actually holds, which is the tension the research file flags as Gap 3. Network Tomography with Path-Centric Graph Neural Network (DeepNT) learns an adjacency matrix from path metrics with neural path attention. It depends on best-performance routing for path sampling and offers no identifiability analysis. Our method has no learned components, and its output is a graph whose recoverability conditions can be stated.

Research Program

The first component is analysis. For a fixed walk-consistent $\mathbf{R}$, we will ask when the map from $(\mathbf{S}, \text{eigenvalues of } \mathbf{C}_x)$ to $\mathbf{R}\mathbf{C}_x\mathbf{R}^T$ is locally injective. We will express the condition through the linear independence of the projected powers $\mathbf{R}\mathbf{S}^k\mathbf{R}^T$, combined with the sparsity of the untraversed part of $\mathbf{S}$. The output should be a probe-design rule stating how many paths, and which monitor pairs, are needed for a given $N$ and edge count. We expect that rule to show a phase transition near $M^2/2 \approx N + |\text{untraversed edges}|$. That expectation comes directly from the parameter count, so a transition far from that line would mean the counting picture is wrong.

The second component is the solver. It alternates a convex step in $\mathbf{C}$ (a projected least-squares problem constrained to positive semidefinite matrices) with a proximal step in $\mathbf{S}$, following the linearized ADMM scheme of PGL. We initialize from the path-union graph. Because the walk constraint fixes part of the support, we expect fewer bad local optima than in fully nodal biconvex problems, and we will measure this across random restarts.

The third component tests robustness. We will check what happens when routes are only known at the logical level (we use OCCAM's output as $\mathbf{R}$), when routing is multipath, and when the stationarity assumption is mildly violated.

Baselines

The naive reference is the path-union graph: an edge is declared wherever two routers are consecutive on some probe. It is exact on traversed edges and has zero recall on untraversed ones. Any method that cannot beat it on untraversed-edge recall adds nothing to the central claim.

The strongest existing topology competitor is OCCAM, run on the same instances from first-order path-sharing and distance metrics computed from the same probes. Its authors report an average Network Similarity of 93% and a Path Edit Distance of 0.20 on Internet Topology Zoo networks. We will reproduce OCCAM on our instances rather than compare against the cited averages. Beating it means higher Network Similarity on the same instances at an equal wall-clock budget, with the gain concentrated on edges that OCCAM's parsimony objective has no evidence for.

The strongest stationarity competitor is JH-GSR, applied in its most favorable reading. Monitors are treated as observed nodes and all internal routers as hidden. JH-GSR will also be run with paths treated as pseudo-nodes. Each variant gets the same sample covariance and a grid search over its regularization weights equal to ours.

DeepNT will be trained on the same path measurements with its released hyperparameters and an equal tuning budget. On its Internet probe data, its authors report a MAPE for additive metrics reduced from 0.81 to 0.69. Our method targets second-order structure rather than mean prediction, so we will not claim to beat that figure directly. We will instead report held-out path covariance error, and the change in DeepNT's MAPE when it is given our graph as a prior.

For congestion localization, LIA is the reference. On BRITE graphs with independent link losses, its authors report detection rates of 86% to 96% with false positive rates of 2% to 6%. We will reproduce LIA under both independent and spatially correlated congestion.

The key ablation sets $\mu=0$. This keeps the lifted covariance and the walk constraint but removes commutation, and it isolates whether stationarity, rather than the lift alone, is what reveals untraversed edges.

Why not just…?

Why not just fit a polynomial graph filter, $\mathbf{C}_y \approx \sum_k \alpha_k \mathbf{R}\mathbf{S}^k\mathbf{R}^T$, directly? This is the most serious alternative. If the diffusion degree $K$ is known, the fit has very few filter parameters and may work as well as our method. Commutation's advantage is that it does not require knowing $K$, which the research file lists as an open problem for graph signal processing in general. We will run the parametric fit with $K$ chosen by held-out path likelihood under the same budget. If it matches our method across degrees and topologies, we will report that the lift and the commutation term are unnecessary and adopt the parametric form.

Why not just run JH-GSR, treating monitors or paths as the observed nodes? JH-GSR's gap prior assumes the hidden part touches few observed coordinates. Under path summation, every path draws on many internal routers, so the gap is dense. In addition, monitor-level signals are not what tomography measures. The pseudo-node variant also ignores the walk constraint and therefore has no link back to physical routers. The paths-as-nodes and monitors-as-nodes runs described above test this directly.

Why not just apply Graphical Lasso to the path covariance? PGL's authors show that Graphical Lasso produces spurious edges and higher error than stationarity-based estimators when data come from multi-hop diffusion, even with full nodal observation. Here the precision matrix of path covariances is also indexed by paths rather than routers, so its sparsity pattern has no direct physical meaning. We will include it to show that loss of meaning concretely.

Why not just use OCCAM or DeepNT? Neither uses second-order coupling. Both can only recover edges that some measured path's first-order behavior implies. OCCAM is the stronger threat on traversed structure, so we use it as our initializer and measure only what commutation adds on top of it.

Proposed Experiments

The synthetic study uses router graphs from BRITE (Barabási-Albert, Waxman, and hierarchical models), the Rocketfuel AS6461 map, Internet Topology Zoo backbones, and the 37-node Roofnet mesh. Monitors are placed at low-degree boundary routers, and probes follow shortest-path routing in one condition and equal-cost multipath routing in another. Router signals are generated as diffusion of white noise through polynomial filters of degree one to four. In a mismatch condition, per-router gains are heterogeneous, which breaks exact stationarity. We sweep the number of paths, the number of snapshots (starting from LIA's roughly 50), noise level, and the fraction of edges left untraversed.

The metrics are F1 on all edges, recall on untraversed edges, normalized error of $\mathbf{S}$, and Network Similarity for comparison with OCCAM. The decisive check is untraversed-edge recall against the $\mu=0$ ablation and the polynomial-fit alternative, plotted against $M^2/(2N)$. The prediction is a sharp rise near the counting threshold for the commutation method and a flat curve for the ablation. A flat curve for both would refute the core claim.

A second check uses BRITE with spatially correlated congestion. Our recovered $\mathbf{C}$ gives per-router variances without the independence assumption, and we will compare its detection rate and false positive rate with LIA's.

For real data, ground-truth internal graphs are unavailable for PlanetLab and the DeepNT probe sets. There we evaluate held-out path covariance prediction: we fit on some monitor pairs and predict covariances on unseen pairs, which only a correct internal graph can do. We also test whether the inferred graph improves DeepNT's MAPE when supplied as its adjacency prior. We will report negative outcomes, notably a failure to beat the polynomial fit or poor results under mismatch, as findings rather than tuning them away.