Many sensor networks, such as weather stations, road traffic loops, and gene panels, are too expensive to read all at once. Graph signal processing, the study of signals that live on the nodes of a network, has a mature answer to "which few nodes should I read?". If you know the network, a greedy rule that adds one node at a time to minimize reconstruction error is provably close to the best possible subset. Topology inference answers a different question: "what is the network?". It does so by watching all nodes at once, over and over. In practice both questions arise together, and the second one cannot be answered the usual way, because you can only afford to watch a few nodes per time step.
We propose a sampler that does both at once. It reads a cost-limited subset of nodes at each time step. It maintains a small ensemble of plausible networks learned only from those partial readings, and it chooses the next subset to minimize reconstruction error averaged over the ensemble. The key observation is technical but simple. The near-optimality guarantee for greedy error-minimizing sampling on a known graph survives averaging over graph hypotheses, with a constant equal to the worst hypothesis's constant. The guarantee therefore extends to the unknown-graph case without new machinery. It can also be paired with a single-pass method for tracing the whole cost-versus-error trade-off curve under non-uniform reading costs.
Core Claim
We make two claims. The first concerns where a graph helps. In the regime where nodes are almost never observed all together, a graph learned from partial co-observations is a better prior for choosing sensors than either a fixed similarity graph or a graph-free covariance estimate. Without any full snapshots, the covariance between two nodes that are rarely read together is undetermined, and a sparse graph fills that gap. The second claim is that greedy selection under the averaged error retains a provable approximation ratio at every step, and that sweeping its greedy prefixes gives an approximate Pareto frontier of cost against error.
The guarantee rests on approximate supermodularity, defined in Greedy Sampling of Graph Signals. That paper shows the error of reconstructing a bandlimited signal on a known graph satisfies, for sets $A \subseteq B$ and a node $u \notin B$,
$$f(A) - f(A \cup \{u\}) \ge \alpha \,[\, f(B) - f(B \cup \{u\}) \,],$$
where $f$ is reconstruction mean squared error and $\alpha \in (0,1]$ measures how far $f$ is from having diminishing returns. The same paper shows $\alpha$ approaches 1 as noise grows. If each graph hypothesis $W_m$ in our ensemble yields an error function $f_m$ with constant $\alpha_m$, then the inequality is linear in $f$. Any nonnegative weighting $\bar f = \sum_m w_m f_m$ therefore satisfies it with $\alpha = \min_m \alpha_m$. The greedy bounds from that paper then apply to $\bar f$ directly. What remains open, and is the theoretical core of this work, is twofold. The first open part is how this per-step guarantee composes over time as the ensemble changes with new data. The second is how it interacts with non-uniform costs.
Relation to Prior Work
Three papers motivate the gap. Greedy Sampling of Graph Signals supplies our selection rule and its guarantee, but it assumes a known graph and uniform costs. Active Sampling for Approximately Bandlimited Graph Signals and Sequential Sampling and Estimation of Approximately Bandlimited Graph Signals select nodes adaptively by predictive variance while learning smoothness and noise parameters through expectation–maximization. In both, the adjacency matrix is given, and neither offers approximation guarantees. We make the adjacency itself the unknown.
Two papers supply the methods we reuse. Online Topology Inference from Streaming Stationary Graph Signals learns a graph from streaming signals whose covariance commutes with the graph's shift operator, using one proximal gradient step per observation. It assumes every node is observed every step. We adapt it to a masked covariance in which unobserved entries are imputed from the current posterior, and we run it on bootstrap-resampled time windows to obtain a cheap ensemble. Computing Approximate Pareto Frontiers for Submodular Utility and Cost Tradeoffs gives ParetoGreedy, which archives all prefixes of one greedy run and prunes dominated ones. It proves guarantees only for submodular utilities such as coverage and influence. Our task is to carry its analysis to the $\alpha$-approximate error objective with additive per-node costs.
One paper constrains the design. Graph topology inference benchmarks for machine learning finds that naive k-nearest-neighbor graphs often match elaborate inference methods. It also finds that sparse learned graphs can split into disconnected pieces, which makes graph-based interpolation unstable. That paper names active selection on inferred graphs as an open problem. Taking its warning seriously, we add a small connectivity-preserving regularizer, a lower bound on the second-smallest Laplacian eigenvalue, and we make a k-NN graph a first-class baseline rather than a straw man.
Research Program
The system runs in rounds. In each round it reads a subset $S_t$ whose total cost $c(S_t)$ fits a per-round budget. It then updates each ensemble member's graph by one masked proximal step. Finally it reconstructs the full signal and selects the next subset by cost-aware greedy on $\bar f$, emitting the prefix archive as a frontier.
The analysis has three parts. The first is the averaging lemma above, together with explicit computation of $\min_m \alpha_m$ on real ensembles, to check that the guarantee is not vacuous. The second is a tracking bound. It relates the excess error of ensemble-greedy over oracle-graph greedy to how far the ensemble is from the true graph. It builds on the dynamic tracking error bounds of the online topology inference paper, extended to masked observations. The third is a cost-aware frontier result: either a proved $(\alpha_1, \alpha_2)$ guarantee for ParetoGreedy-style prefixes on $\bar f$, or a counterexample showing where it fails.
To handle scale, we will use rank-one posterior updates. This avoids the $O(N^3)$ per-step cost reported for the sequential sampler.
Baselines
The naive reference is cost-aware random selection: nodes are drawn uniformly until the budget is exhausted, followed by reconstruction on a k-NN graph. Any method that cannot beat it at matched cost is not worth deploying.
The strongest graph-based competitor is a fixed similarity graph plus known-graph greedy. We build a k-NN or correlation graph from a warm-up period and then run the Chamon–Ribeiro greedy error sampler on it, with costs handled by the same ParetoGreedy sweep we use. The benchmark evidence that naive graphs are hard to beat makes this the most likely competitor. On known synthetic graphs, that paper reports greedy finding the globally optimal subset in over 95% of low-SNR cases. It is the right method to beat when its graph is good.
The strongest graph-free competitor is cost-weighted column-pivoted QR from Greedy Sensor Placement With Cost Constraints, run on raw warm-up data, which that paper found better than SVD modes. We pair it with a Gaussian-process variant that uses the empirical covariance from the same warm-up data. That paper reports no exact numbers that can be compared.
We also run the sequential sampler of Sequential Sampling and Estimation of Approximately Bandlimited Graph Signals, given the physical graph where one exists. For it, no reported numeric result was found on Lacuna, only qualitative superiority on the weather data. An oracle runs greedy on the true graph as an upper bound.
Two ablations isolate the key ingredients. The first replaces the ensemble with a single point-estimate graph, which tests whether hedging over hypotheses matters. The second drops the connectivity regularizer.
All methods share the same rounds, the same budget, the same warm-up data, and the same reconstruction model where applicable. Graph-construction hyperparameters get an equal tuning budget on a held-out time window. Beating a baseline means a lower area under the cost-versus-error frontier, averaged over seeds with confidence intervals, at matched total cost.
Why not just…?
Why not just build a k-NN graph once and run known-graph greedy? This is a serious threat. The topology benchmarks show such graphs are hard to beat when features are fully observed. Our bet is narrower: when warm-up data is scarce or nodes are rarely co-observed, a fixed graph built from that data is noisy and never corrected, while ours keeps learning. The history-fraction sweep below decides the question directly. If the fixed graph ties us at every history level, the topology-learning component is unnecessary and we will report that.
Why not skip the graph and do greedy design on an empirical covariance or with QR pivoting? With abundant full snapshots, this is probably as good as ours or better, and we expect it to win there. Its weakness is that entries for pairs never read together are unestimable. The QR paper also documents overfitting under slow singular-value decay. We predict a crossover as the fraction of full-observation history shrinks. If no crossover appears, the claim fails.
Why not random or leverage-score sampling? Leverage scores from Random sampling of bandlimited signals on graphs and Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies require the graph's Fourier basis, which is exactly what is unknown. Independent random draws cluster in dense regions, as Graph sampling with determinantal processes notes. We include leverage sampling on the current point-estimate graph to measure this rather than assume it.
Why not learn everything end to end with a forecasting network such as Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks? That model learns a graph from fully observed histories. It has quadratic cost in the number of nodes and gives no subset-level guarantee. We include it as a reconstruction model on top of our selected subsets, to test whether our selection helps even when the reconstructor is a neural network.
Proposed Experiments
On synthetic Watts–Strogatz, random geometric, and Barabási–Albert graphs with stationary diffusion signals, the true graph is known. This lets us measure the excess error over the oracle, edge-recovery F-measure from partial observations, and the empirical $\min_m \alpha_m$. For reference, the online topology inference paper reports an F-measure of up to 0.94 on the 2,888-node Facebook graph under full observation, which is the ceiling our masked variant aims toward. On real data we use the 381-station China temperature network, Toronto Traffic, and METR-LA and PEMS-BAY, where physical road graphs serve as comparison topologies. Since none of these benchmarks include sensing costs, costs are synthetic: uniform, heavy-tailed random, and distance-from-depot.
The decisive check is a sweep over the fraction of time steps in which all nodes are observed, from zero to one hundred percent. The proposal survives only if our method beats both the fixed k-NN greedy baseline and the covariance-based QR baseline in the low-history regime. A second check asks whether the ensemble beats the point-estimate ablation when the ensemble disagrees most. A third, on Toronto Traffic, asks whether frontiers built on learned graphs match or beat those built on the physical road graph. This would extend to active sampling the benchmark's finding that a learned graph denoised slightly better than the road graph (10.41 dB versus 10.32 dB SNR).
References
- Greedy Sampling of Graph Signals
- Active Sampling for Approximately Bandlimited Graph Signals
- Sequential Sampling and Estimation of Approximately Bandlimited Graph Signals
- Online Topology Inference from Streaming Stationary Graph Signals.
- Computing Approximate Pareto Frontiers for Submodular Utility and Cost Tradeoffs
- Graph topology inference benchmarks for machine learning
- Greedy Sensor Placement With Cost Constraints
- Random sampling of bandlimited signals on graphs
- Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies
- Graph sampling with determinantal processes
- Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks