TAPS: Target-Aware Permanent Sampling for Graph Diffusion

1 Introduction

• The motivating problem is how many permanent locations are needed for one future regional exposure, rather than the complete pollution field, amid wildfire PM2.5 exposure and finite monitoring networks.Prior placement objectives include field reconstruction, spatial coverage, and demographic priorities; permanent monitoring adds the cost structure that each new location requires new infrastructure.Source: §1 · p. 1
• TAPS formulates permanent space-time sampling around one prescribed target, valuing both raw target response and information not already supplied by selected sites.Its grouped permanent-location criterion is the analogue of greedy c-optimal design, with each choice committing to a repeated-observation block for one physical installation.Source: §1 · p. 2
• Ten California locations recover the Bay Area target at rank 28 < 40, while ten England locations recover the South East target before the TAPS sequence reaches full-state rank at 22.The target-versus-state gap is visible in both settings.Source: §1 · p. 2
• Under tested rescaled California schedules, increasing readings per location from one to five lowers the greedy exact-target budget from 33 locations to seven.Including the finite-update correction changes six of the ten selected locations.Source: §1 · p. 2
• Across 100 blind prospective California histories, TAPS has the lowest tested ten-location rβ in 92; target-weight and raw-response placements need median budgets of 15 and 17 locations to match TAPS-10.Those budgets correspond to 33.3% and 41.2% fewer permanent monitors for TAPS.Source: §1 · p. 2
• Held-out model-risk and forecast-error rankings are not identical, so the final network should be tested with the estimator that will use it.At 30 scheduled readings, graph diffusion favors 30 × 1 whereas random forest favors 10 × 3; the post hoc best-competitor comparison is unresolved.Source: §1 · p. 2

2 Mathematical Framework

• Each permanent-location decision adds its complete block of repeated observations at the cost of one physical installation.The graph, target, prediction horizon, observation schedule, and candidates are fixed before future measurements are observed.Source: §2 · p. 2, §2.4 · p. 4

2.1 Graph Diffusion and Measurements

• Graph diffusion evolves a retained spectral state to a fixed horizon, and each permanent site contributes r readings while costing one installation.The framework distinguishes physical-location cost from the number of scalar measurements; β is a regularization parameter, not an assumed noise variance.Source: §2.1 · pp. 2–3

2.2 Target Recovery and State Identification

• In the noiseless setting, exact recovery of one target is a row-space condition, whereas full-state identification requires at least ceil(K/r) locations and enough distinct vertices for the largest retained-eigenvalue multiplicity.The bound reflects that repeated observations can add measurement directions, but one permanent vertex contributes at most one independent spatial direction within a repeated eigenspace.Source: §2.2 · p. 3

2.3 Stable Target Estimation

• Regularized target risk balances target mismatch against estimator amplification, while additional readings at fixed locations cannot worsen target-span error or target risk.Effective target dimension measures spectral concentration but does not guarantee that available measurement blocks represent those modes efficiently.Source: §2.3 · pp. 3–4

2.4 Target-Aware Permanent Sampling

• TAPS greedily adds the permanent location whose complete temporal block gives the smallest regularized target risk, making it a grouped permanent-location analogue of c-optimal design.Under the same criterion and tie-breaking, greedy c-optimal design and TAPS make the same selections.Source: §2.4 · p. 4

2.5 Target Response and Redundancy

• Adding a candidate reduces squared normalized target risk by the product of raw target response and a finite-update correction, which alone is not a monotone measure of redundancy.Both factors depend on the installed network.Source: §2.5 · p. 5

3.1 Study Region and Target

• The Bay Area offers the best balance of the four screened districts, with 16 qualified stations and a median 41 smoke-covered days per station-year.The median includes eight medium- or heavy-smoke days.Source: §3.1 · pp. 5–6, Table 1 · p. 5
• The population-weighted target represents approximately 7.41 million people and assigns positive weight to 21 candidates, including 16 inside the district.Tract populations are assigned to the nearest qualified station and normalized.Source: §3.1 · p. 6

3.2 Empirical Graph and Model

• The selected empirical similarity graph uses k=10 and q=2, with 104 vertices, 664 weighted edges, and 40 retained modes capturing 94.7% of training energy.The graph is a similarity model, not a literal model of atmospheric transport.Source: §3.2 · p. 6
• Figure 3 shows the Bay Area target on the 104-station graph alongside TAPS's ten selected permanent locations, which may lie outside the target region.Outside locations may be selected when they add information about the prescribed regional exposure.Source: Figure 3 · p. 6, §3.2 · p. 6

3.3 Evaluation Design

• The evaluation separates model-based information about the prescribed target from held-out prediction of future observed PM2.5, comparing placements at equal budgets and schedules.Model-based measures include target-span error, target mismatch, amplification, regularized target risk, rank, and minimum singular value; placement comparisons include 200 random ten-location sets.Source: §3.3 · p. 6
• Held-out prediction uses readings from days d−4, d−3, and d−2 to forecast Bay Area PM2.5 on 135 untouched 2024 dates, with K=30, τ=2, and β=10^-4 selected on validation.Forecasting graph correlations use 2018–2021, predictor parameters are selected on 2022, and models are refit on 2018–2022.Source: §3.3 · p. 7

4.1 Target Recovery Before State Identification

• At 10 sites, TAPS achieves target-span error below 10^-6 with rank(BS)=28<40; target mismatch is 0.0440 and regularized target risk is 0.1329, below target-weight’s 0.1521.Across 12 bandwidth-horizon settings, ten-site mismatch ranges from 0.0233 to 0.0589 and improves on mean random placement by 81.8%–94.0%; the greedy target is exact below the full-rank counting bound in 11 settings.Source: §4.1 · pp. 7–8, Figure 5 · p. 8
• With D-optimal placement, rank 40 is first reached at 14 locations, but σmin(BS) is about 5 × 10^-6 and rβ is 0.9874; at 40 locations they are 0.5231 and 0.2729.Target recovery, algebraic full rank, and stable state identification therefore occur at different budgets.Source: Figure 6 · p. 8, §4.1 · p. 8

4.2 Repeated Observations and Permanent Sites

• Increasing readings per permanent site from one to five reduces the greedy exact-target budget from 33 locations to seven; extending the final time also lowers mismatch from 0.0565 to 0.0431 and the budget from 10 to nine.Schedules are rescaled rather than nested and β is recomputed, so the 33-to-seven trend is not a direct consequence of the nested-schedule result or evidence about allocation at a fixed observation budget.Source: §4.2 · pp. 8–9, Figure 7 · p. 9

4.3 Conditional Redundancy

• Across 120 selection stages, correction-signature similarity correlates with measured interaction at mean Spearman 0.889 and exceeds every tested geometry-only measure; TAPS bypasses the strongest raw-response candidate in 111 stages.The main partition has 9, 45, and 50 stations, with TAPS allocating its ten locations 4, 3, and 3 across regions; imposing that quota raises rβ by a median 1.76% and at most 7.70%.Source: §4.3 · pp. 9–10

4.5 Space-Time Allocation

• At a fixed 30 scheduled readings, graph diffusion favors 30×1 over 10×3 (MAE 2.272 versus 2.490), while random forest favors 10×3 over 15×2 (2.187 versus 2.383).For random forest, the comparison of 10×3 with 30×1 is unresolved; thus the preferred allocation depends on the estimator, and repeated observations can reduce physical infrastructure when installations are constrained.Source: Table 4 · p. 10, §4.5 · p. 11

4.4 Estimator Dependence

• On 135 untouched 2024 dates, random forest gives the fixed ten-location TAPS network MAE 2.187 µg/m3, while changing the estimator reverses the TAPS and target-weight placement ordering.Under random forest, TAPS beats target-weight by 0.201 µg/m3 MAE (95% CI [−0.317, −0.075]); under graph diffusion, target-weight has lower MAE than TAPS by 0.203 µg/m3 (95% CI [−0.395, −0.0005]).Source: §4.4 · p. 10, Figure 10 · p. 11, Table 3 · p. 11

4.6 Blind Prospective Placement

• In 92 of 100 blind histories, TAPS has the lowest ten-location rβ; with 8–16 windows, 72 of 75 designs lie within 20% of the 2025-only greedy benchmark.Across all 100 histories, TAPS-10 matches target-weight’s risk at a median 15 sites and raw response’s at 17, using 33.3% and 41.2% fewer monitors, respectively; the illustrative annualized equivalents are $112,280 and $157,192.Source: §4.6 · pp. 12–13

4.7 Transfer Results

• The transfer studies ask whether the prescribed target remains easier to recover than the retained state and whether low graph-model risk identifies the best held-out placement.The supplied passage introduces these two questions but gives no transfer-study findings.Source: §4.7 · p. 13
• At 4 Vancouver and 11 Toronto locations, TAPS targets become exact below full-state counting bounds 8 and 12; at 10 locations, ranks remain 19<23 and 30<34, while beating all 200 random networks under rβ.Source: §4.7 · p. 13
• Held-out MAE rankings split by estimator: Vancouver random forest favors TAPS (1.778 µg/m3), graph diffusion favors weighted degree (1.913 vs 1.975); Toronto favors TAPS under graph diffusion (2.878) and D-optimal under random forest (2.609).Under graph diffusion, TAPS outperforms only 36% of random Vancouver networks and 13% of random Toronto networks despite outperforming all of them under rβ.Source: §4.7 · p. 14
• At 10 England locations, TAPS has target-span error below 10^-6 despite rank 30<38; full-state rank is first reached at 22 locations, versus a counting lower bound of 13.The 22-location figure is an achieved budget for the greedy sequence, not a lower bound over all subsets.Source: §4.7 · p. 14
• At 10 England locations, raw response has lower rβ than TAPS (0.1843 vs 0.2036), although both outperform all 200 random networks.Source: §4.7 · p. 14
• On 100 untouched 2024 dates, TAPS MAE was 2.304 µg/m3 with random forest, 2.325 with persistence, and 2.428 with graph diffusion; the random-forest advantage was unresolved.Source: §4.7 · p. 14
• Under graph diffusion, raw response beats TAPS (MAE 2.174 vs 2.428; paired difference −0.254 µg/m3, 95% CI [−0.460, −0.095]); random forest numerically favors D-optimal over TAPS (2.233 vs 2.304), unresolved.Raw response outperforms 89% of random networks under graph diffusion, compared with 69% for TAPS.Source: §4.7 · p. 14

• Across California and England, the prescribed target is recoverable before full-state identification; tested rescaled California schedules reduce the exact-target budget from 33 one-reading locations to seven five-reading locations.Source: §5 · p. 14
• Omitting the finite-update correction raises California rβ by 33.8% despite slightly improving mismatch, and changes the selected network.Source: §5 · p. 14
• In 92 of 100 blind histories, TAPS had the lowest tested ten-location rβ; target-weight and raw-response designs needed median budgets of 15 and 17 locations to match TAPS-10.Source: §5 · p. 14
• Across California, Canada, and England, estimator-dependent reversals occur; at 30 readings, graph diffusion favors broader coverage while random forest favors repeated observations at ten locations.Source: §5 · p. 14
• Scope is constrained by similarity-based graphs, one untouched California test year, a fixed prospective candidate universe without site-feasibility constraints, and no proof of global optimality.Source: §5 · p. 14

• LPS acknowledges hospitality from Magdalen College and the Mathematical Institute at the University of Oxford.Source: Declarations · p. 14
• The authors report no relevant financial or non-financial competing interests; Michelle Lin led methodology, formal analysis, software, and numerical investigation, while Laura P. Schaposnik supervised.Source: Declarations · pp. 14–15
• Funding included NSF awards, support through the NSF-Simons National Institute for Theory and Mathematics in Biology, and a Simons Travel Award.Source: Declarations · p. 15