Learning Graph Beliefs for Active Radio Mapping With Decision-Certified Multi-Step Sensing

iComAI Lab

INTEGRATED COMMUNICATIONS AND AI LAB

Learning Graph Beliefs for Active Radio Mapping With Decision-Certified Multi-Step Sensing Wangqian Chen1 , Hao Wang2 , Yumeng Zhang1 , Chenghong Bian1 , Junting Chen2 , Jun Zhang1 1

arXiv:2610.37717v1 [cs.NI] 27 Oct 2026

2

The Hong Kong University of Science and Technology The Chinese University of Hong Kong, Shenzhen

Radio maps provide essential wireless propagation knowledge for network optimization and autonomous platforms. Acquiring dense measurements, however, is prohibitively costly, requiring active sampling to prioritize informative measurements. Existing active sampling methods typically rely on variances from prescribed spatial models or learned pointwise uncertainty, which may not fully capture the spatial correlation of different measurements. This paper proposes GraphBARC, a graph-structured active radio map construction framework that integrates learned spatial modeling with analytical Bayesian inference. A graph network learns correlated node and edge factors using only acquired measurements, inducing a joint full-map belief that supports analytical observation updates without retraining. Rather than immediate one-step acquisition, it adopts a nonmyopic sensing strategy that evaluates joint map-wide Bayes risk reduction over feasible multi-step routes, accounting for information redundancy among planned measurements. We reuse candidate responses and derive residual-based bounds directly on route-value differences, retaining shared response-error structure to avoid uniformly high-accuracy evaluation. An error-aware continuation bound screens unpromising prefixes, after which only responses needed for unresolved comparisons are refined. We further establish a computable decision-gap bound and show that certified exclusions remain valid during refinement. Experiments show that GraphBARC reduces mean root-mean-square error (RMSE) by over 16% relative to the evaluated baselines and core planning time by 56% compared with the fixed-accuracy, unpruned implementation. Correspondence to: Jun Zhang (eejzhang@ust.hk)

1

Introduction

Low-altitude wireless networks are expected to support a wide range of aerial platforms, including unmanned aerial vehicles (UAVs), aerial robots, and emerging air mobility terminals. These platforms require reliable connectivity for navigation, trajectory planning, sensing, data collection, and control (Wang et al., 2025b). In urban environments, however, wireless channels can vary significantly with location, building blockage, line-of-sight (LOS) availability, and surrounding scatterers. As a result, low-altitude communication systems require accurate and timely awareness of the radio environment. In this context, radio maps provide a natural representation of wireless environmental knowledge, such as received signal strength (RSS), interference level, beamforming gain, or low-dimensional channel state information (CSI) descriptors, which can support connectivity-aware trajectory planning, coverage-hole detection, beam management, and wireless digital twins (Zeng et al., 2024; Li and Chen, 2024; Wu et al., 2024). Therefore, an accurate radio map can significantly improve the safety and efficiency of autonomous aerial operations. Constructing high-fidelity radio maps is challenging due to the prohibitive costs of dense spatial sampling. Under a sensing budget, it is crucial to prioritize highly informative measurements in complex environments. While existing approaches, including interpolation techniques (Shao et al., 2026; Sun and Chen, 2024), tensor completion (Timilsina et al., 2024; Zhang et al., 2020), and deep learning models (Wang et al., 2025a; Chen and Chen, 2025; Teganya and Romero, 2022; Jaensch et al., 2026; Chen and Chen, 2024), can reconstruct 1

radio maps from sparse observations, they typically rely on predefined measurements that are sufficiently representative. These passive approaches do not actively decide where to measure and thus fail to reduce measurement overhead. In online missions with limited flight time, the lack of immediate feedback during passive data collection can lead to redundant, low-quality, or uninformative measurement efforts. Active radio map construction integrates sensing and reconstruction into a closed-loop process. As new measurements arrive, it updates the current map estimate and uses current insights to guide subsequent measurements. Compared with offline passive reconstruction, this active setting is more challenging as it requires a principled mechanism to quantify measurement informativeness to select high-utility samples. Model-based Bayesian frameworks provide principled uncertainty estimates for active radio map sensing (Chen et al., 2025a; Lin et al., 2026; Zhang et al., 2025; Polyzos et al., 2024; Shrestha et al., 2023). Gaussian process approaches (Zhang et al., 2025; Polyzos et al., 2024) have been widely adopted to facilitate sampling through analytical posterior variances and specialized acquisition functions. The model-based estimator in (Shrestha et al., 2023) further enables online Bayesian updates under the Gudmundson shadowing model. However, their fixed or predefined kernels may inadequately capture heterogeneous and site-specific spatial correlations in complex environments. Deep learning approaches, such as UNet and Transformers (Chen et al., 2025b; Zheng et al., 2025), can learn spatial representations directly from data. While these deterministic models can achieve high-resolution predictions, they typically lack a principled uncertainty quantification for active sensing. Deep reinforcement learning (Zhao et al., 2024) and trajectory planning (Li et al., 2026) have been developed to optimize UAV measurement paths. However, these methods often demand extensive offline pre-training or trial-and-error episodes, imposing heavy computational or training burdens that hinder real-time deployment on resourceconstrained UAV platforms. Generative models have enabled uncertainty-aware reconstruction through ensembles of generated samples. Flow matching (Sun et al., 2026) uses location-wise ensemble variance to guide candidate selection and utility-aware path planning, while diffusion-based spectrum cartography (Gu et al., 2025) combines posterior sampling with diversity-aware sensing-location selection. Although these methods capture spatial distributions, their iterative sampling procedures incur substantial computational overhead for online deployment. In summary, existing approaches face two key limitations. First, model-based methods support analytical updates but rely on prescribed covariance structures, whereas data-driven methods learn richer spatial structures, yet often provide only deterministic predictions or marginal uncertainty. Second, effective sensing requires evaluating the joint map-wide benefit of multiple measurements under mobility constraints, rather than solely one-step scores, as high local uncertainty does not necessarily imply a large reduction in overall uncertainty. Some studies (Lu et al., 2025; Chen et al., 2026) have extended beyond one-step acquisition, but they require selecting a destination before planning the route, which may overlook the joint value of the endpoint and intermediate measurements. Joint route optimization also entails combinatorial search and repeated posterior computations, whose numerical errors may still affect route ranking. To address these limitations, we develop GraphBARC, a graph-induced Bayesian framework that learns a full-map belief with explicit cross-location dependencies using nonmyopic active sensing. Newly acquired measurements are assimilated analytically, with their information propagated across correlated locations through the learned graph dependencies. Rather than relying on one-step gains, GraphBARC evaluates joint map-wide Bayes risk reduction over feasible multi-step routes. To reduce computational cost, shared posterior responses are reused across routes, while residual-certified bounds on route-value differences enable safe prefix pruning and selective numerical refinement of unresolved comparisons. New observations immediately update the belief, while periodic adaptation refines the graph factors as more data accumulate. The novelty and contributions are summarized as follows: • We develop a graph-factor network that combines local message passing and graph attention to learn map-wide propagation dependencies from acquired measurements without external side information. Unlike deterministic predictors, it induces a full-map belief that jointly characterizes the map estimate and its uncertainty, while remaining compatible with analytical Bayesian conditioning. • We derive bounds on the response inner-product and innovation-inverse errors induced by approximate 2

Feasible set

Next sensing action Historical measurements

Current location

BS

Figure 1 System scenario for active radio map construction, where a sensing platform sequentially acquires measure-

ments and selects the sensing locations under sensing-budget constraints to improve overall reconstruction accuracy.

posterior solves, and use them to certify route-value differences directly rather than separately certifying each value. The resulting comparison intervals guide selective refinement and can be tighter than those obtained by adding separate route-error bounds under the same allowances. • We derive an error-aware continuation bound for safe prefix pruning and establish a computable decision gap under a fixed belief and complete route coverage. Certified prefix exclusions remain valid during subsequent numerical refinement, allowing unresolved comparisons to be refined without repeating the prefix search. • Experiments show that GraphBARC achieves over 16% lower reconstruction RMSE than the evaluated baselines while reducing core planning time by 56% relative to the fixed-accuracy, unpruned implementation. The rest of the paper is organized as follows. The system model is reviewed in Section II. Section IIIV develop the graph-induced Bayesian active learning framework and the corresponding implementation. Numerical results are presented in Section VI, and Section VII concludes the paper.

2

System Model and Problem Formulation

We consider a low-altitude urban environment with multiple base stations (BSs). Let X ⊂ RD be the area of interest, where D is the spatial dimension. Discretizing X into M grid cells gives the radio map T M ×d , where xi ∈ Rd represents the channel feature associated with the ith cell, and d is X = [xT 1 , ..., xM ] ∈ R the feature dimension. For a power map, d = 1, and xi reduces to the average power value within the cell. Let ξ = vec(XT ) ∈ RM d , where vec(·) denotes column-wise vectorization. As shown in Fig. 1, a mobile platform visits selected cells and acquires measurements to refine the current radio map. Let Ei = eT i ⊗ Id ∈ Rd×M d , where ei ∈ RM is the ith canonical basis vector, Id is the d × d identity matrix, and ⊗ denotes the Kronecker product. It follows that Ei ξ = xi . The channel measurement collected at cell i is thus given by ni ∼ N (0, Ri ),

yi = Ei ξ + ni ,

3

(1)

where Ri ∈ Rd×d denotes the measurement noise covariance. Let D0 denote a small set of initialization measurements acquired in the current scene. After t active sensing actions, the available measurement set is Dt = D0 ∪ {(is , ys ) : 1 ≤ s ≤ t}. Given the radio map estimator fθ (·) with parameters θ and the sensing policy π(·), the next location is selected by it+1 = π(Dt , fθ (Dt )) ∈ At

(2)

where At denotes the feasible set at step t. Consider a sensing budget Γ and an available travel distance ℓmax , the active radio map construction problem is formulated as (π ∗ , θ ∗ ) ∈ argmin E[L(fθ (DΓπ ), ξ)] π,θ PΓ s.t. t=1 ct ≤ ℓmax ,

(3)

where DΓπ denotes the measurement history collected after Γ sensing steps under policy π(·), L(·) is the reconstruction loss, and ct denote the corresponding travel distance at step t. Active radio map construction aims at identifying informative measurements to minimize the final reconstruction error. This task thus involves the joint optimization of radio map reconstruction and measurementlocation selection.

3

Graph-Structured Belief and Inference

Active radio mapping requires a spatial representation that supports both reconstruction and sensing decisions. The challenge is to adapt spatial dependencies to the acquired measurements while retaining an explicit mechanism for assimilating new observations and evaluating future measurements. We construct a graph-structured belief that captures spatial dependencies, whose induced covariance governs both analytical measurement updates and map-wide Bayes-risk reduction, providing a unified basis for reconstruction and active sensing.

3.1

Learned Graph-Induced Full-Map Belief

A local observation informs unmeasured locations only if the model captures their spatial dependence. Classical interpolation kernels or predefined Gaussian models may be restrictive in complex environment that affected by blockages and scatterers. While purely data-driven neural estimators learn complex spatial mappings, they lack a reliable uncertainty estimates or an analytic full-map belief for active sampling. Our key idea is to use the network to learn a graph, and model the radio map as a graph-structured random field. Let G = (V, E) be a graph over M cells, where each node i ∈ V corresponds to one cell, and edge (i, j) ∈ E represents a structural relation from cell i and j. The graph captures spatial dependencies learned from the acquired measurements. For an acquired context Dτ , it learns a node prior mi ∈ Rd and a precision matrix Ωi ∈ Rd×d . The node factor is 1 (4) ψi (xi ; Dτ ) = exp[− (xi − mi )T Ωi (xi − mi )]. 2 Here, mi specifies the local estimation tendency at cell i, and Ωi ≻ 0 measures the confidence of this prior. For an edge (i, j) ∈ E, we define an edge relation as φij (xi , xj ; Dτ ) = exp[− 21 (xi − Mij xj )T Wij (xi − Mij xj )],

(5)

where Mij ∈ Rd×d describes the correlation from cell i to cell j, and Wij ∈ Rd×d is a positive edge precision. Because these factors are context dependent, the learned dependence can vary across location, direction, and feature dimensions. Combining these factors gives the full-map belief qτ (ξ; Dτ ) ∝

M Y

ψi (Ei ξ; Dτ )

i=1

Y (i,j)∈E

4

φij (Ei ξ, Ej ξ; Dτ ).

(6)

This factorization combines local information and cross-cell structural dependence. The node factors describe what each cell is expected to be, while the edge factors describe how information should propagate between related cells. Thus, the graph belief provides a probabilistic mechanism for propagating information beyond the set of directly measured locations. Proposition 1. (Graph-induced full-map belief ). Suppose that Ωi ≻ 0, ∀i ∈ V and Wij ⪰ 0, ∀(i, j) ∈ E. Define M X X Λτ = ET AT (7) i Ωi Ei + ij Wij Aij i=1

and ητ =

M X

(i,j)∈E

ET i Ωi mi , Aij ≜ Ei − Mij Ej .

(8)

i=1

Then, Λτ ≻ 0, and the graph-induced belief in (6) defines the proper Gaussian distribution qτ (ξ; Dτ ) = N (ξ; µτ , Στ ),

(9)

−1 µτ = Λ−1 τ ητ , Στ = Λτ .

(10)

where Here, µτ ∈ RM d and Στ ∈ RM d×M d are the mean and covariance induced by the fixed graph factors. Proof. See Appendix A.1. Proposition 1 connects factor learning to a valid full-map belief. The first term in Λτ encodes node-wise confidence, while the second introduces cross-cell coupling. Although Λτ is sparse, its inverse is generally dense within connected components. The diagonal block Στ,ii quantify cell-wise uncertainty, whereas the off-diagonal blocks Στ,ij encode cross-location dependencies, which are the key quantities governing both measurement propagation and sensing value.

3.2

Measurement Responses and Multi-step Sensing Value

Active radio map construction requires each new measurements to be immediately incorporated into both the map estimate and its uncertainty. Conventional neural estimators, however, typically lack an explicit probabilistic mechanism for incremental conditioning and map-wide uncertainty propagation. We condition the learned graph-induced belief on the acquired measurements via analytical Bayesian updates and use the same posterior response to evaluate candidate value. Let µt and Σt be the mean and covariance at sensing step t. For a new observation yt+1 at cell j, define Ct,j = Σt ET j and St,j = Ej Ct,j + Rj . Gaussian conditioning gives
−1 µ+ yt+1 − Ej µt , t = µt + Ct,j St,j −1 T Σ+ Ct,j . t = Σt − Ct,j St,j

(11)

The superscript + denotes conditioning on the new observation while retaining the current graph factors. Each action adds a localized positive information block without recomputing the graph factors at every sensing step. To quantify the map-wide sensing value, let W ∈ RM d×M d be a positive-semidefinite task-weight matrix satisfying trace tr(W) = 1. The map-wise posterior Bayes risk is   Rt = Eqt ∥ξ − µt ∥2W = tr(WΣt ), (12) where ∥z∥2W = zT Wz. A common choice W = IM d /(M d) gives average squared error per cell and feature component.

5

The one-step risk reduction obtained by measuring cell j is −1 T ∆t (j) = Rt − R+ Ct,j WCt,j ) ≥ 0 t (j) = tr(St,j

.

(13)

It follows the same posterior response used for belief refinement. However, selecting sensing locations solely by these immediate gains may be myopic. We therefore jointly evaluate prospective measurements along feasible multi-step routes. At planning step t, consider a hypothetical feasible route Pt = (jt,1 , . . . , jt,ht ) with ht prospective locations. P Let Pt,1:k denotes its first k locations and Σt t,1:k the corresponding counterfactual posterior covariance. For an unvisited cell j, its branch-conditioned one-step gain is P

P

P

∆t (j | Pt,1:k ) = tr((St,jt,1:k )−1 (Ct,jt,1:k )T WCt,jt,1:k ).

(14)

The prospective terminal route value consequently satisfies t Jt (Pt ) = Rt − tr(WΣP t )=

ht X

∆t (jk | Pt,1:k−1 ).

(15)

k=1

The equality follows by telescoping successive risk differences. Each measurement is valued after accounting for the information already planned on that branch. Let put be the current location and Bt = (Γt , ℓt ) the remaining budgets. Let Pt = P(At , put , Bt ) be the feasible routes set under the constraints. The multi-step sensing objective is Pt⋆ ∈ arg max Jt (Pt ). P ∈Pt

(16)

This objective selects measurements jointly according to their terminal map-wide improvement, rather than independently maximizing immediate gains. A smaller immediate gain can be preferred when it enables a more informative feasible batch. Let Pbt = (b jt,1 , . . . , b jt,ht ) be the final route returned by the planner. All selected locations are visited in order: it = b jt,ht , Dt+ht = Dt ∪ {(it+k , yt+k ) : k = 1, . . . , ht } . The current location is updated to the route endpoint. This planning thus enables nonmyopic sensing by considering the cumulative information gain among multi-step future choices.

4

Decision-Certified Multi-Step Sensing

Section 3 defines the route value over a multi-step lookahead horizon. Finding a high-value route remains computationally demanding due to the combinatorial growth of candidate routes and the costly posteriorresponse solves. Uniformly accurate response solves may waste computation on comparisons that are already decisive, whereas insufficient accuracy can reverse route rankings and invalidate pruning. We address these through shared posterior responses and decision-level error control. Candidate responses are reused, and their residuals yield bounds directly on route-value differences. A continuation bound then excludes uncompetitive prefixes, after which numerical refinement focuses on unresolved comparisons. Throughout a planning call, the graph belief, task weights, noise model, and candidate domain remain fixed.

4.1

Shared Conditional-Response Representation

Two routes visiting the same locations with different orders have the same terminal value. Even routes with different measurement sets can reuse their common candidate responses. For a feasible route P , stack its block-selection matrices into EP ∈ R|P |d×M d , and define T P P CP t = Σt EP , St = EP Ct + RP ,

6

(17)

where RP = blkdiag(Rj : j ∈ P ) is the block-diagonal noise matrix. Gaussian conditioning gives Pt Pt T Pt t −1 t Jt (Pt ) = tr((SP GP t ) t ), Gt = (Ct ) WCt .

(18)

The candidate responses Ct,j and Gram blocks Gt,ij = CT t,i WCt,j are computed once and reused across route evaluations. Routes visiting the same candidate set have identical terminal values because reordering does not change the trace. The same representation supports conditional queries. For a prefix P and a candidate j ∈ / P, P P CP t,j = Ct,j − Ct St

−1

EP Ct,j .

(19)

The second term removes the response component already explained by the planned prefix. Different prefixes therefore require only small conditional updates rather than independent full-map conditioning. Together, the order-invariance property and shared response representation avoid repeated full-map response solves and duplicate value evaluations.

4.2

Residual-Certified Decision Bounds

The shared representation reduces route evaluation to small matrix operations. However, approximate response solves perturb both the Gram blocks and the inverse innovation matrices. We first bound these effects, and then combine shared Gram errors before applying norm bounds to competing routes. b t,j approximate the response satisfying Λt Ct,j = ET . For a verified bound Λt ⪰ αt IM d , with αt > 0, Let C j define b X ||ET j − Λt Ct,j ||F , ϵt (P ) = ( ϵ2t,j )1/2 , (20) ϵt,j = αt j∈P

where || · ||F is the Frobenius norm. These residual-based quantities bound the errors of individual and stacked response blocks. Because approximate responses need not induce a symmetric positive-semidefinite signal covariance, define b P = sym(EP C b P ) + RP + γt I, S t t where sym(A) = (A+AT )/2, and γt ≥ 0 is a correction to make the numerical covariance positive semidefinite, b P ⪰ RP ≻ 0 for every considered route P . yielding S t Let Jbt (P ) be the approximate route value obtained by numerical solvers. Its error admits the decomposition b P )−1 (GP − G b P )) Jt (P ) − Jbt (P ) = tr((S t t | {z t } Gram error

−1 b P )−1 )GP ). + tr(((SP − (S t ) t | {z t }

(21)

innovation-inverse error

It separates the two error sources and allows shared Gram errors to be combined across competing routes before bounding, yielding tighter route-value comparison intervals. b P ⪰ RP ≻ 0. Let sP , Proposition 2. (Residual-Based Route Error Bounds). Suppose that Λt ⪰ αt IM d , S t p P bP sbP be valid positive lower bounds on the smallest eigenvalues of St , St , respectively, and ω = ||W||2 . Consequently, −1 b P )−1 ∥2 ≤ ϵt (P ) + γt , ∥(SP − (S (22) t ) t sP sbP where ∥ · ∥2 is the spectral norm. Furthermore, the Gram-block errors and the innovation-inverse error satisfy b t,ij ∥F , βt,ij ≥ ∥Gt,ij − G −1 b P )−1 )GP ) , κt (P ) ≥ tr(((SP − (S t ) t t

7

(23)

where

b t,j ∥F + ϵt,j ∥W1/2 C b t,i ∥F ) βt,ij = ω(ϵt,i ∥W1/2 C + ω 2 ϵt,i ϵt,j ,

(24)

ϵt (P ) + γt b P ∥F + ωϵt (P ))2 . κt (P ) = (∥W1/2 C t sP sbP Proof. See Appendix A.2. Proposition 2 provides residual-certified bounds for the two error sources in numerical route valuation. These bounds are combined next to directly certify route-value differences. Corollary 1. (Shared-error route comparisons). Under Proposition 2, suppose that both routes P and Q use the same shared approximate response and Gram blocks. Define X b P )−1 ]ij − [(S b Q )−1 ]ij βt,ij [(S et (P, Q) = t t F (25) i,j∈P ∪Q + κt (P ) + κt (Q), b P )−1 ]ij is the d × d block associated with locations i and j, where P ∪ Q denotes the union of two routes, [(S t and is interpreted as zero if either location is absent from P . Then   (26) Jt (P ) − Jt (Q) − Jbt (P ) − Jbt (Q) ≤ et (P, Q). Proof. See Appendix A.3. Corollary 1 shows that route preferences can be certified by directly bounding their value differences, without requiring equally accurate estimates of individual route values. Similar inverse-innovation coefficients can yield a reliable comparison even when the individual route values remain less accurately resolved. Define the decision interval by (27) [∆t (P, Q), ∆t (P, Q)] = [Jbt (P ) − Jbt (Q) ± et (P, Q)]. Thus, a positive lower bound certifies that P improves upon Q; a nonpositive upper bound certifies that it cannot improve. Otherwise, the comparison remains unresolved and requires further numerical response refinement. Refinement updates until the decision is resolved or the stopping criterion is met.

4.3

Prefix Screening and Decision Refinement

The preceding intervals compare two routes under specified numerical accuracy. Prefix screening requires another easily acquired bound covering every feasible continuation, including routes not yet generated. We obtain this bound from conditional response errors and then separate geometric exploration from subsequent numerical refinement. A feasible greedy route Q0t is constructed as a fixed reference for screening. For a nonempty prefix P and bP j ∈ / P , let δt,j (P ) be a computable bound (see Appendix A.4) satisfying ||W1/2 (CP t,j − Ct,j )||F ≤ δt,j (P ). Define b P ∥F + δt,j (P ))2 (∥W1/2 C t,j bt,j (P ) = (28) λmin (Rj ) where λmin (·) denotes the smallest eigenvalue. Lemma 1. (Error-aware continuation bound). Let At (P ) contain every location that may appear in a feasible continuation of P , and let rP = ht − |P |. For any feasible continuation T , Jt (P ⊕ T ) − Jt (P ) ≤ TopSumrP {bt,j (P ) : j ∈ At (P )}, where ⊕ denotes concatenation, and TopSumr {·} sums the largest at most r nonnegative entries.

8

(29)

Learnable Graph-Belief Network

Node / edge feature construction

Context update

Graph-factor generator

Graph factors m i ，Ωi M ij ， Wij

Network retraining

Analytical Posterior Inference

Structured graph prior (from Proposition 1) = (

,

)

Posterior update ( ， )

= (

,

)

(Analytical, exact in information form)

Sparse measurements (e.g. RSS / CSI)

Graph-induced full-map prior

( )~ ( ;

,

Decision-Controlled Nonmyopic Planner Same solver for inference and planning

Feasible multi-step route search

PCG solvers

Prefix screening with continuation bounds

=

Posterior mean

Candidate responses ,

) Accumulate data

Certified route comparison & response refinement Next sensing action / transit Acquire new data

Posterior-Compatible Training (Data accumulation + Offline pretraining + Periodic online adaption)

Figure 2 Overall implementation pipeline of GraphBARC. The graph-factor generator maps measurement context

into interpretable Gaussian node and edge factors, which are assembled with new measurement information into the posterior system. Numerical posterior queries provide the map estimate and candidate responses for the decisioncontrolled multi-step planner, forming a closed loop between posterior inference and active sensing.

Proof. See Appendix A.5. Lemma 1 provides an optimistic upper bound on the maximum additional value that any feasible continuation of a prefix can achieve. It relaxes joint innovation effects and motion interactions, yielding a cheap bound that is sufficient for branch pruning without assuming diminishing returns. Define Ut (P ; Q0t ) = ∆t (P, Q0t ) + TopSumrP {bt,j (P ) : j ∈ At (P )}.

(30)

The first term bounds the prefix value relative to the reference; the second bounds its possible additional value. Consequently, Jt (P ⊕ T ) − Jt (Q0t ) ≤ Ut (P ; Q0t ) for every feasible continuation. A prefix with Ut (P ; Q0t ) ≤ 0 is discarded. Otherwise, its successors are generated from the current endpoint. After prefix exploration, current incumbent Qt is initialized as Q0t . A candidate replaces it only when its lower bound is positive. Let Tt contain the unresolved terminal routes after pruning. Define gt = max{0, maxP ∈Tt ∆t (P, Qt )}, with gt = 0 when Tt is empty. Thus, gt measures the largest certified improvement that may still be achieved by an unresolved route. Proposition 3. (Refinement-compatible decision accuracy). Suppose that the certified comparison and continuation bounds are valid, the prefix search completely covers the declared route family, and all exclusions and incumbent replacements are certified. The completed comparison above satisfies 0 ≤ max Jt (P ) − Jt (Qt ) ≤ gt P ∈Pt

(31)

at every completed comparison stage. Previously certified exclusions remain valid after subsequent response refinement. Proof. See Appendix A.6. This proposition separates route coverage from numerical accuracy. An excluded branch cannot exceed the incumbent against which its exclusion was certified, and certified incumbent replacements cannot decrease the exact model value. Consequently, refining the numerical responses does not require reopening excluded branches. Let εdec ≥ 0 be the prescribed tolerance. If no further certified incumbent improvement is available, planning stops when gt ≤ εdec . Otherwise, only the response columns involved in unresolved comparisons are further refined by the solver. Their residual certificates, route-level covariance, and affected Gram blocks are updated accordingly, after which the corresponding decision intervals are recomputed. The prefix search is not repeated. If the numerical budget is exhausted before the decision tolerance is met, the planner returns the current incumbent and its certified decision-gap bound.

9

Graph-Factor Generator

query

Message-passing Block

Neighborhood of node i ()

Graph Attention Block

(from g i( l ) )

g i(l ) Neighbor node states

i

Message

...

Encoder

Outputs Node

m i ，Ωi

i

Head 2

Pool + Fuse Edge

...

Incident Aggregation edge states

Gaussian Factor Heads

Head 1

()

MLP

Sparse observations

Node context

...

...

Multi-head attention

M ij ， Wij

(from g (jl ) )

(from g (jl ) )

keys

values

Edge

...

Node

...

Graph

Head k

Edge context

Deep Unfolded Network

Figure 3 Observation-aware graph-factor Initialization generator. Local message graph aggregate sparse Deep unfolded layer 1 passing andDeep unfoldedattention layer L Correction Preconditioner (0)

(0)

Λx = b

Assemble Linear System

(l = 0) Outputs ... measurement context, and the output heads xproduce Gaussian node factors and edge factors, which jointly define the diag( Λ ) Correction x r p z x r p z map Posterior Mean full-map belief used for analytical assimilation and active sensing. update update update update r update update update update μ

5

...

RHS Stack b Єn  {  1}

t

z (0) p

(0)

...

Gate γ

Network Implementation and Training MLP c

Uncertainty

Gate γ

Correction map

diag(

)

c

Realizing the framework in Sections III and IV requires the learned representation, training objective, and online execution to remain consistent. The network must generate valid Gaussian factors from sparse observations, learn how additional measurements should refine predictions elsewhere, and preserve the fixed-model Deep-Unfolder Posterior Solver Global-Risk Active Planner Analytical Posterior Inference Learnable Graph-Prior Network conditions required by certified route comparisons. We address these requirements through an observationMap-wise uncertainty reduction aware graph-factor generator, a disjoint context-assimilation-prediction training objective, and an online ∆prograph prior cedure that separates periodic graphStructured refreshes analytical measurement updates and numerical decision Graph factors Node / edge (from Proposition from 1) Posterior update Matrix-free solver Graph-factor Risk-frontier construction m ，Ω feature = ( , ) ( ， ) generator refinement. ( , ) ℱ construction M ， W

5.1

i

i

ij

ij

= (

,

)

(Analytical, exact in information form)

Avoid explicit matrix inversion

Structured Graph-Factor Generator Graph-induced

Sparse measurements (e.g. RSS / CSI)

full-map prior

Posterior mean

Receding-horizon beam search multi-step path evaluation

Uncertainty

Nextestimate sensing action / transit ( ; belief , ) The network predicts the factors of the( )~joint rather than directly outputting andiag( independent ) and uncertainty score for each cell. Node and edge Accumulate representations determine the factor parameters, while the data assembled precision matrix determines the full-mapPosterior-compatible mean, covariance, Training and measurement responses, combing (Offline pretraining + periodic online adaption) the representation capability of deep learning with the interpretability of Bayesian inference.

5.1.1

Observation-Aware Graph Encoding

T For a context set Dτ , define the input feature of cell i as ϕi = [pT i , (oi yi ) , oi ], where pi is the cell coordinate, oi = I{i ∈ Dτ } is the binary observation indicator, and yi is the channel observation. For an edge (i, j), the geometric feature is φij = [dij , Φij ], where dij and Φij are the relative distance and direction between the two cells. An observation-aware embedding is formed as T ϕ̃i = LN(fcon (pT i , (oi yi ) ) + femb (oi )),

(32)

where fcon (·) is the feature encoder, femb (·) is the embedding function for the indicator, and LN(·) denotes layer normalization. The node and edge features are further encoded by (0)

gi

= fe1 (ϕ̃i ),

(0)

eij = fe2 (ϕ̃i , ϕ̃j , φij ). (0)

(33)

(0)

Here, fe1/e2 (·) denote the node and edge encoders, and gi , eij ∈ RB with B being the embedding dimension. 5.1.2

Graph Context Extraction

The first stage uses local message passing to encode observation-dependent relations between neighboring cells. Let N (i) = {j | (i, j) ∈ E} be the neighborhood of node. At layer l, (l)

v̄i =

X 1 (l) (l) (0) fv(l) (gi , gj , eij ) |N (i)| j∈N (i)

10

(34)

and the node state is updated by (l+1)

gi (l)

(l)

(l)

(l)

= LN(gi + fu(l) (gi , v̄i )),

(35)

(ℓ)

where fv (·) and fu (·) are the message-passing and node-update networks, respectively. After Lm layers, (0) (L) (L) the edge representation is refined as ẽij = fr ([eij , gi , gj ]). Here, fr (·) is the edge-refinement network. A graph-attention stage then assigns observation-dependent weights to neighboring representations. At attention layer l, node i attends exclusively to its graph-connected nodes: (l+1)

gi

(l)

(l)

= GraphAtten(l) (gi , {gj |j ∈ N (i) ∪ {i}),

(l)

(36)

(l)

where gi provides the query, and the graph-connected nodes {gj |j ∈ N (i) ∪ {i} provide the keys and values. This attention block learns observation-dependent importance weights for graph-connected nodes. By stacking multiple attention layers, measurement information can propagate along multi-hop graph paths while avoiding unrestricted all-to-all attention. 5.1.3

Gaussian Factor Heads

This component converts the learned representations into Gaussian graph factors. Given the final graph (L) attention output g̃i = gi , the node head generates a node prior and a positive-definite precision matrix: mi = fm (g̃i ),

Ωi = Diag(softp(fΩ (g̃i ))) + ϵΩ Id .

(37)

Here, fm (·) and fΩ (·) are the node-mean and node-precision heads, respectively, ϵΩ > 0 is a small constant. The function softp(x) = log(1 + exp(x)) ensures positive entries, and Diag(·) forms a diagonal matrix from a vector. For each edge (i, j), the transformation head produces Mij = Diag(exp(βM tanh(fM (zij )))),

(38)

where zij = [g̃i , g̃j , ẽij ], βM bounds the scaling range, and fM (·) is the transformation head. The edge precision is Wij = Diag(softp(fw (zij ) + w̄tanh(αij ))κ(dij ) + ϵw ), (39) where fw (·) is the edge-precision head, w̄ > 0 is a learnable scale, and ϵW > 0 is a small constant. Here, αij is the attention score from the attention block, and κ(dij ) = exp(−dij /ℓW ) is the distance-decay kernel with decay length ℓW .

5.2

Posterior-Compatible Graph Training

Training must evaluate both the belief generated from sparse context and its response to additional evidence. At each training iteration, the context set is partitioned into three disjoint, nonempty subsets: ˙ B ∪D ˙ P , where ∪˙ denotes disjoint union. The subsets provide context, assimilation evidence, and Dτ =DC ∪D prediction targets, respectively. The graph generator receives only DC , and measurements in DB and DP are not supplied to the graphgeneration forward pass. Let (Λ̂g , η̂g ) = fgraph (DC ) be the natural parameters assembled from the generated −1 factors. The graph-induced mean and covariance are µ̂C = Λ̂−1 g η̂g and Σ̂C = Λ̂g , where the inverse is obtained using differentiable numerical solvers. Additional evidence from DB is assimilated through the analytic Bayesian update (µ̂B , Σ̂B ) = PosteriorUpdate(µ̂C , Σ̂C , DB ). Define the robust mean-fitting loss as d

LH (µ, D) =

1 XX hδH (yi,r − µi,r ) d|D| r=1 i∈D

11

(40)

where δH > 0 is its transition threshold and  2   e , |e| < δH , hδH (e) = 2δH  |e| − δH , |e| ≥ δH . 2

(41)

To score noisy observations consistently with the observation model, define Vi (Σ) = Ei ΣET i + Ri . The marginal predictive negative log-likelihood is LN LL (µ, Σ, D) =

1 X1 ((yi − µi )T Vi (Σ)−1 (yi − µi ) |D| 2 i∈D

(42)

+ log det|Vi (Σ)| + d log(2π)), The final training objective is formulated as Lgra =

i 1h LH (µ̂C , DB ) + LH (µ̂B , DP ) 2 h + λb LNLL (sg(µ̂C ), Σ̂C , DB )

(43)

i + λp LNLL (sg(µ̂B ), Σ̂B , DP ) . The coefficients λb , λp ≥ 0 control the regularization terms, and the operator sg(·) stops gradients. The first term trains the graph model to produce a reliable belief from sparse context alone, while the second encourages the model to support analytical posterior refinement with additional measurements. The network is trained to generate graph factors that are compatible with both sparse prediction and measurement propagation.

5.3

Implementation

GraphBARC represents the current belief by its natural parameters and computes only the inverse actions required for reconstruction, training, and planning. It computes the mean µt and candidate responses Ct,j through Λt µt = ηt and Λt Ct,j = ET j , respectively. Both queries use matrix-free preconditioned conjugate gradient (PCG) iterations with a symmetric positive-definite preconditioner. They share the same numerical solver, differing only in their right-hand sides. Within each planning call, the belief, task weights, noise model, and candidate domain remain fixed. Shared responses and Gram blocks support the certified prefix screening and selective numerical refinement. The planner returns a feasible route and its attained decision gap gt , distinguishing satisfaction of the prescribed tolerance, gt ≤ εdec , from termination at a numerical work limit. The selected route is executed as a batch, while measurements are assimilated sequentially. The network is initialized using the sparse observations D0 and adapted periodically using the accumulated dataset Dt . Between graph refreshes, its factors remain fixed and only newly acquired measurements are assimilated. At a scheduled refresh, the regenerated belief replaces the current information system. The final map is obtained by solving the mean system after the last update. The complete procedure is summarized in Algorithm 1.

6

Experiment Results

This section evaluates the proposed GraphBARC in terms of reconstruction accuracy and sensing efficiency. The experiments are conducted using channel data generated by the Sionna ray-tracing (RT) simulator (Aoudia et al., 2025). In the simulation, we consider an urban environment covering an area of 860 m × 680 m, where seven transmitters (TXs) are randomly deployed at heights ranging from 25 to 40 m. Each TX is equipped with a 16-element antenna array. The simulations use a band-limited signal with a carrier frequency of 3.5 GHz and 12

Algorithm 1 Active Sensing and Inference with GraphBARC. Require: Initial observation set D0 , sensing budget B = (Γ, ℓmax ), lookahead horizon K, and tolerance εdec Ensure: Radio map construction and sampling trajectory 1: Pretrain fgraph (·) with D0 ; assemble Λ0 , η0 2: Initialize t ← 0, ℓt ← ℓmax , n ← 0 and pu t 3: while under the sensing budget B do 4: Set Γt = min{K, Γ − n}; obtain µ̂t b t,j and G b t,ij for all candidates 5: Compute C 6: Construct a greedy route Q0t ; initialize Tt = {Q0t } 7: Generate feasible prefixes P = (j1 , ..., jk ) for k ≤ Γt ; prune those with Ut (P ; Q0t ) < 0; add P to Tt if k = Γt 8: Set Qt ← Q0t 9: while true do 10: For all P ∈ Tt , compute ∆t (P, Qt ) and ∆t (P, Qt ) 11: Remove routes satisfying ∆t (P, Qt ) ≤ 0 12: if ∆t (P, Qt ) > 0 then 13: Set Qt ← P , remove P from Tt ; continue 14:

end if

15: 16: 17: 18: 19: 20:

Compute gt , and take gt = 0 when Tt = ∅ If gt ≤ εdec or the numerical limit is reached, report gt and break Refine response columns, ∆t (P, Qt ) and ∆t (P, Qt ) for P ∈ Tt under higher-precision PCG

end while

Execute the route Qt ; update Dt+1 , ℓt+1 , put+1 Refresh Λt+1 , ηt+1 with analytical Bayesian updates if periodic adaptation is triggered then Train fgraph (·) with Dt+1 ; regenerate Λt+1 , ηt+1

21: 22: 23: end if 24: Set t ← t + 1, n ← n + Γt 25: end while 26: Output µ̂t and Dt

an effective bandwidth of 100 MHz. The ground truth radio map is computed on a 128 × 128 planar grid at a fixed altitude of 50 m. In total, 10 radio maps are generated under different TX location configurations for evaluation. The proposed GraphBARC is compared with the following representative baselines: 1. BAL-EGP (Polyzos et al., 2024): It uses an ensemble of Gaussian processes to reconstruct the radio map. The next location is selected by maximizing the ensemble predictive variance, and the model posterior is updated with new samples. 2. DRUE (Shrestha et al., 2023): It uses two autoencoders to estimate the radio map and uncertainty map. During active sensing, high-uncertainty locations are selected as candidate goals, and A* search is used to plan grid paths toward these goals. 3. Flow Matching (Sun et al., 2026): It uses a pretrained flow-matching UNet for radio map reconstruction. The variance of multiple stochastic radio map reconstructions gives the uncertainty map, which guides active sampling. Let X̂ be the reconstructed radio map (in dB scale). We evaluate the reconstruction performance using the 1 ||X−X̂||1 and RMSE = √1M ||X−X̂||2 . mean absolute error (MAE) and RMSE, which are defined as MAE = M To reflect the energy error, selected experiments additionally evaluate the normalized mean-squared error (NMSE) in the linear power domain, given by NMSE = ||10X/10 − 10X̂/10 ||22 /||10X/10 ||22 . Specifically, 3% of the grid cells are randomly observed for model initialization. All trajectories start from the origin, and each sampling action is restricted to three hops on the eight-connected grid. We set the lookahead

13

Ground Truth

127

Proposed

BAL-EGP

Flow Matching

DRUE

-50

-100 64

-150

RSS (dB)

96

32

-200

0

Noise variance statistic

127

Proposed: uncertainty map

BAL-EGP: uncertainty map

Flow Matching: uncertainty map

DRUE: uncertainty map

1.0

0.6 64

0.4 32

Uncertainty

0.8

96

0.2 Noise variance map

Proposed: MAE map

BAL-EGP: MAE map

Flow Matching: MAE map

0.0 20

DRUE: MAE map

96

15

64

10

32

5

0 0

32

64

96

127 0

32

64

96

127 0

32

64

96

127 0

32

64

96

127 0

32

64

96

127

MAE (dB)

0 127

0

Figure 4 Visual comparison of reconstructed radio maps, normalized uncertainty maps, and spatial MAE distributions

under 15% observation coverage.

horizon K = 4 and εdec = 10−6 . Candidate responses initially use 37 PCG iterations, with refinements of 16 iterations and a maximum of 60. Retraining is performed after every 100 newly collected measurements. Sampling stops when reaching the 15% grid-cell observation budget, including the initial 3%.

6.1

Active Radio Map Reconstruction

We first evaluate the radio-map reconstruction accuracy and the benefits of nonmyopic sensing. Table 1 compares reconstruction accuracy on the common set of cells that remain unobserved by all methods. For GraphBARC, K = 1 reduces to the one-step greedy policy in (13). It is observed that GraphBARC with K = 4 outperforms all baseline methods, achieving the lowest errors across all metrics. Compared with BAL-EGP, it reduces these metrics by 16.2%, 16.1%, and 41.5%, respectively, while its MAE and RMSE improvements over DRUE and Flow Matching exceed 52%. Although Flow Matching exhibits relatively large MAE and RMSE, it achieves the lowest NMSE among the external baselines. Notably, increasing the planning horizon from K = 1 to K = 4 further reduces MAE and RMSE by 7.1% and 7.3%, respectively, demonstrating the advantage of multi-step sensing over one-step greedy acquisition. Table 2 reports the number of observations required to reach the prescribed full-map reconstruction accuracy. For the RMSE target, GraphBARC with K = 4 requires only 1,760 observations, 4.3% fewer than K = 1 and 39.5% fewer than BAL-EGP. For the NMSE target, the corresponding reductions increase to 19.4% and 79.4%, respectively. Flow Matching and DRUE require 1.87 and 4.66 times as many observations, respectively. These results further demonstrate that joint multi-step sensing can improve measurement efficiency under prescribed reconstruction-error constraints. Fig. 4 visualizes the reconstructed radio maps, normalized uncertainty maps, and spatial error distributions. GraphBARC captures the main propagation patterns and spatial variations, although some fine-scale structures remain smoothed. BAL-EGP exhibits more pronounced smoothing, whereas Flow Matching and DRUE recover the central high-RSS regions but incur larger errors in several peripheral and transition areas. The uncertainty maps reveal different spatial characteristics. Flow Matching assigns high uncertainty to the cen14

Table 1 Reconstruction accuracy on common unobserved cells

Scheme

MAE (dB)

RMSE (dB)

NMSE

Flow Matching

7.845

11.475

0.162

DRUE

7.726

11.110

0.292

BAL-EGP

4.307

6.311

0.176

Proposed (K = 1)

3.886

5.711

0.107

Proposed (K = 4)

3.609

5.293

0.103

Table 2 Observations required to meet target reconstruction errors

Scheme

RMSE ≤ 5.5 dB

NMSE ≤ 0.11

Num.

Relative

Num.

Relative

Flow Matching

13,504

7.67×

1,708

1.87×

DRUE

11,140

6.33×

4,248

4.66×

BAL-EGP

2,908

1.65×

4,428

4.85×

Proposed (K = 1)

1,840

1.05×

1,132

1.24×

Proposed (K = 4)

1,760

1.00×

912

1.00×

tral high-power region, where the actual errors are comparatively small, while BAL-EGP and DRUE exhibit localized uncertainty patterns that do not align with their error distributions. The proposed uncertainty map shows partial spatial correspondence with reconstruction errors. Although this correspondence is not exact, it suggests that the estimated uncertainty captures some spatial variation in reconstruction difficulty. Fig. 5 compares RMSE across observation coverage levels on a representative radio map, with all methods evaluated on a common set of unobserved cells. Both proposed variants consistently outperform the external baselines, with the planner K = 4 achieving the lowest RMSE across all evaluated observation ratios. Compared with BAL-EGP, its RMSE reduction increases overall from 11.0% at 10% observation coverage to 29.8% at 35%, while the improvements over DRUE and Flow Matching reach 60.7% and 62.3%, respectively. The proposed K = 4 consistently improves upon K = 1 by jointly evaluating gains over feasible multi-step trajectories, with relative improvements of 6.3% and 5.3% at 10% and 35% observation coverage, respectively. These results consistently support the benefit of nonmyopic sensing over greedy selection.

6.2

Evaluation of Active Sampling Quality

This experiment evaluates whether GraphBARC selects informative measurements beyond its own reconstruction model. To isolate sampling quality from the reconstruction backend, we reconstruct radio maps using three independent common estimators: k-nearest-neighbor (KNN) interpolation, radial basis function (RBF) interpolation, and Gaussian process regression with a Matérn covariance kernel (Matérn-GPR) (Rasmussen and Williams, 2006). All estimators use the measurements collected by each sensing strategy, including its initial observations. We use four neighbors for KNN, local linear RBF interpolation with 128 neighbors, and a Matérn-3/2 kernel for GPR. Fig. 6 first visualizes the sampling trajectories generated by different methods. GraphBARC with K = 4 distributes measurements across broad spatial coverage while prioritizing propagation-critical regions, such as shadow areas and LOS/NLOS boundaries, where spatial heterogeneity often leads to higher posterior uncertainty. BAL-EGP also provides broad spatial coverage, but adapts less to propagation structures. Flow Matching concentrates mainly on the central high-RSS region, resulting in weaker reconstruction in low-RSS and boundary areas, while DRUE emphasizes uncertainty boundaries but leaves larger regions underexplored. These differences illustrate how acquisition strategies influence the spatial distribution of collected measurements.

15

 

506(G%

 )ORZ0DWFKLQJ '58( %$/(*3 3URSRVHGK = 1 3URSRVHGK = 4

      







2EVHUYDWLRQUDWLR





Figure 5 RMSE versus observation coverage on a representative radio map. Table 3 RMSE of independent reconstruction methods using measurements acquired by different sensing strategies

Scheme

KNN

RBF

Matérn-GPR

Random

6.201

5.529

5.675

Flow Matching

8.965

7.225

7.869

DRUE

7.975

6.269

6.657

BAL-EGP

6.566

5.696

5.841

Proposed (K = 1)

5.979

5.520

5.735

Proposed (K = 4)

5.470

5.233

5.332

Table 3 compares the resulting RMSE across the three independent reconstruction methods. It is observed that GraphBARC with K = 4 achieves the lowest RMSE under all three estimators. Compared with random sampling, it reduces RMSE by 11.8%, 5.4%, and 6.0% under KNN, RBF, and Matérn-GPR, respectively. The corresponding reductions over BAL-EGP are 16.7%, 8.1%, and 8.7%. Notably, K = 4 further improves upon K = 1 by 8.5%, 5.2%, and 7.0%, respectively. Flow Matching and DRUE may underperform random sampling because their trajectories are spatially biased, whereas random sampling provides more balanced global coverage. Overall, the consistent improvements across different estimators indicate that the proposed nonmyopic strategy acquires more informative measurements whose reconstruction benefits extend beyond the graph-based model.

6.3

Reliability and Efficiency

This section evaluates reliability and efficiency of the proposed GraphBARC. All experiments are conducted on a workstation equipped with an Intel Core i7-10700K CPU, 32 GB RAM, and an NVIDIA GeForce RTX 4060 Ti GPU. Table 4 evaluates the reliability of GraphBARC with initialization ratios of 1%–4% of the grids, followed by active sensing until the total observation coverage reaches 10% or 15%. GraphBARC consistently outperforms 16

Proposed K = 4

127

BAL-EGP

2500

2000

1500

64 1000

Sampling order

96

32 500

0

0

Flow Matching

127

DRUE

2500

2000

1500

64 1000

Sampling order

96

32 500

0

0

32

64

96

initial samples

127 0

32

new samples

64 start

96

127

0

end

Figure 6 Sampling trajectories generated by different active strategies.

random sampling across all initialization settings, reducing RMSE by 3.5%–13.2% at 10% coverage and 10.3%–12.9% at 15% coverage. Notably, the reconstruction performance exhibits relatively low sensitivity to initialization size at 15% coverage, with RMSE ranging from 4.774 to 4.916 dB across all tested settings. Even with only 1% initial observations, the proposed method achieves RMSEs of 5.704 and 4.774 dB at 10% and 15% coverage, respectively, outperforming random sampling by 13.2% and 12.9%. These results indicate that GraphBARC can be effectively initialized with limited measurements and progressively improve reconstruction through active sensing, without requiring an extensive initial observation set. Fig. 7 validates the numerical decision bounds using 50 frozen belief states from all maps. In Fig. 7(a), the decision regret, evaluated against an independent high-accuracy reference optimum, is covered by the reported upper bound in all states after accounting for reference uncertainty and rounding allowance. All states satisfy the prescribed tolerance, and 47 exhibit regret within the rounding allowance. Fig. 7(b) isolates the benefit of retaining shared response errors when comparing competing routes. The mean error radius decreases by 8.81%, 19.80%, and 33.42% relative to separate route-error bounds when the routes share one, two, and three measurement locations, respectively. These results support the validity of the stopping criterion and demonstrate that shared-error comparisons provide tighter bounds under the fixed learned belief and declared feasible-route family. Table 5 evaluates the computational efficiency of four-step planning over 50 frozen belief states using total runtime, cumulative PCG iterations, generated prefixes, and route-value comparisons. Fixed-Gram uses fixedaccuracy response solves without prefix pruning; Adaptive-Gram adds selective PCG refinement; PrunedGram additionally applies error-aware prefix screening; and Shared-Pruned further exploits shared-error bounds for comparisons. Compared with Fixed-Gram, Adaptive-Gram reduces PCG iterations by 38.2% and runtime by 13.7%, with essentially unchanged search workload. Adding prefix screening further reduces 17

Table 4 Sensitivity of reconstruction to the initialization ratios

10%

Scheme

0.4

MAE

RMSE

MAE

RMSE

Random

4.326

6.569

3.559

5.481

1% + Active

3.742

5.704

3.160

4.774

2% + Active

4.019

6.217

3.162

4.891

3% + Active

4.073

6.336

3.209

4.846

4% + Active

3.879

5.986

3.194

4.916

50/50 paired checks pass

Shared / separate error radius

Reference regret rt /εdec

0.6

15%

47/50 regrets within rounding allowance

0.2 rt = gt

0.0 0.0

0.2

0.4

0.6

1.0000 1.0

0.9119 0.9

0.8020

0.8 0.7 0.6

0.6658 0

1

2

Reported gap gt /εdec

Shared measurement locations

(a)

(b)

3

Figure 7 Validity and tightness of decision-error bounds: a) Reference decision regret rt versus the reported decision-

gap bound gt ; b) Shared-to-separate error-radius ratio versus the number of shared measurement locations.

generated prefixes and route comparisons by 96.3% and 97.6%, respectively, yielding a 53.3% reduction in runtime. These results identify prefix pruning as the primary source of search acceleration. Shared-Pruned slightly reduces the search workload further, but incurs approximately 7% higher runtime than PrunedGram due to the additional bound-evaluation overhead. Nevertheless, it achieves an overall 56.8% reduction in planning time relative to Fixed-Gram, demonstrating the complementary benefits of adaptive response computation and bound-guided pruning.

7

Conclusion

This paper presented GraphBARC, a graph-structured Bayesian framework for nonmyopic active radio map construction with certified decision-error control. Its learned graph-induced belief captures spatial dependencies, enabling analytical posterior updates and information propagation across the map. By evaluating joint map-wide Bayes risk reduction over feasible routes, GraphBARC accounts for measurement redundancy and future sensing opportunities beyond one-step gains. Shared posterior responses, residual-certified route comparisons, and safe prefix screening reduce redundant computation while focusing numerical refinement on unresolved decisions. Under fixed-belief and complete coverage of the declared route family, the planner provides a computable decision-gap bound, with certified exclusions preserved during refinement. Experiments show that GraphBARC reduces mean RMSE by over 16% relative to the evaluated methods cuts core planning time by 56% compared with the fixed-accuracy, unpruned implementation. Its selected measurements also achieve the lowest RMSE among the evaluated strategies under external independent reconstruction methods.

18

Table 5 Runtime and computational workload of four-step planning over 50 frozen states

Scheme

Time (s)

PCG iterations (×10−3 )

Generated prefixes (×10−3 )

Route comp. (×10−3 )

Fixed-Gram

3.344

23.33

1558.3

672.7

Adaptive-Gram

2.886

14.42

1558.3

673.1

Pruned-Gram

1.348

14.42

58.34

15.98

Shared-Pruned

1.443

14.42

58.24

15.90

Future work will extend graph-structured beliefs to dynamic spatio-temporal radio environments and generalize the planner to cooperative multi-UAV sensing. Another promising direction is to learn transferable graph priors for previously unseen environments, where newly acquired observations progressively update the posterior belief and refine graph factors for environment-specific adaptation.

A

Proofs and Auxiliary Bounds

A.1

Proof of Proposition 1

The logarithm of the graph belief in (6) can be written as M

1X (Ei ξ − mi )T Ωi (Ei ξ − mi ) 2 i=1 1 X − (Aij ξ)T Wij (Aij ξ) + C, 2

log qt (ξ; Dt ) = −

(44)

(i,j)∈E

where C is independent of ξ. Expanding the node terms and collecting the quadratic and linear terms give M X X 1 log qt (ξ; Dt ) = − ξ T ( ET AT i Ωi Ei + ij Wij Aij )ξ 2 i=1 (i,j)∈E

+(

M X

T ′ ET i Ωi mi ) ξ + C ,

(45)

i=1

1 = − ξ T Λt ξ + ηtT ξ + C ′ 2 where C ′ absorbs all terms independent of ξ. We next establish positive definiteness. For any nonzero vector z ∈ RM d , define zi = Ei z. Then, X zT Λt z = (zi − Mij zj )T Wij (zi − Mij zj ) (i,j)∈E

+

M X

(46) zT i Ωi zi .

i=1

Because z ̸= 0, at least one block zi is nonzero. The second sum in (46) is strictly positive under Ωi ≻ 0, while the second sum is nonnegative under Wij ⪰ 0. Hence, zT Λt z > 0 for every z ̸= 0, which proves that Λt ≻ 0. Finally, let µt = Λ−1 t ηt and completing the square gives 1 1 − ξ T Λt ξ + ηtT ξ = − (ξ − µt )T Λt (ξ − µt ) + C ′′ , 2 2 19

(47)

where C ′′ = 21 ηtT Λ−1 t ηt is independent of ξ. Since Λt ≻ 0, the normalized density is Gaussian with mean µt = Λ−1 η and covariance Σt = Λ−1 t t t , thereby completing the proof.

A.2

Proof of Proposition 2

b t,j , the lower b t,j and let DP stack the corresponding blocks. Since Λt Dt,j = ET − Λt C Let Dt,j = Ct,j − C t j bound gives T b ∥Dt,j ∥F ≤ ∥Λ−1 (48) t ∥2 ∥Ej − Λt Ct,j ∥F ≤ ϵt,j . Block stacking yields ∥DP t ∥F ≤ ϵt (P ). Because route locations are distinct, ∥EP ∥2 = 1. Hence, P bP ∥SP t − St ∥2 = ∥sym(EP Dt ) − γt I∥2 ≤ ϵt (P ) + γt .

(49)

b P ⪰ RP ≻ 0. A valid explicit choice of spectral lower bounds is The stabilization rule ensures S t sbP = max{λmin (RPt ),

1 b Pt )−1 ||∞ ||(S t

},

(50)

sP = max{λmin (RPt ), sbP − ϵt (Pt ) − γt }. Here, ∥ · ∥∞ denotes the maximum absolute row sum. For the positive-definite numerical matrix, bP ) = λmin (S t

1 1 ≥ . P P −1 b b λmax ((St ) ) ∥(St )−1 ∥∞

(51)

b P ⪰ RP , this establishes sbP . It implies Together with S t λmin (SP bP − ϵt (P ) − γt . t )≥s

(52)

Combining it with SP t ⪰ RP establishes sP . Then −1 b P )−1 = (SP )−1 (S b P − SP )(S b P )−1 . (SP − (S t ) t t t t t

(53)

Taking spectral norms proves the first bound in the proposition. For the Gram blocks, b t,ij = DT WC b t,j + C b T WDt,j + DT WDt,j . Gt,ij − G t,i t,i t,i

(54)

Using ∥AT B∥F ≤ ∥A∥F ∥B∥F and ∥W1/2 Dt,j ∥F ≤ ωϵt,j yields βt,ij in (24). In particular, βt,ij = βt,ji ≥ 0. For the inverse contribution, GP t ⪰ 0 implies

Moreover,

−1 b P )−1 )GP ]| ≤ ∥(SP )−1 − (S b P )−1 ∥2 tr(GP ). |tr[((SP − (S t ) t t t t t

(55)

1/2 P 2 b P ∥F + ωϵt (P ))2 . tr(GP Ct ∥F ≤ (∥W1/2 C t ) = ∥W t

(56)

Combining the last two inequalities with (22) establishes the bound κt (P ) in (24), thereby completing the proof.

A.3

Proof of Corollary 1

b t,ij be a shared Gram-block error, and define the innovation-inverse contribution Let Ft,ij = Gt,ij − G −1 b P )−1 )GP ). ζt (P ) = tr(((SP − (S t ) t t

20

(57)

The shared Gram-error contribution satisfies Jt (P ) − Jt (Q) − (Jbt (P ) − Jbt (Q)) E X D b P )−1 ]ij − [(S b Q )−1 ]ij , Ft,ij + ζt (P ) − ζt (Q), = [(S t t

(58)

i,j∈P∪Q

where ⟨A, B⟩ = tr(AT B) is the Frobenius inner product. Applying the triangle and Cauchy-Schwarz inequalities gives Jt (P ) − Jt (Q) − (Jbt (P ) − Jbt (Q)) X ≤ ∥Vt,ij (P ) − Vt,ij (Q)∥F βt,ij (59) i,j∈P∪Q

+ κt (P ) + κt (Q) = et (P, Q). For the separate route-value allowance at (P ) =

X

b P )−1 ]ij ∥F βt,ij + κt (P ), ∥[(S t

(60)

i,j∈P

the triangle inequality and βt,ij ≥ 0 yield (61)

et (P, Q) ≤ at (P ) + at (Q). This completes the proof.

A.4

Conditional-Response Error and Gram Evaluation

For a nonempty prefix P and j ∈ / P , define KP t,j = EP Ct,j ,

P −1 P BP Kt,j , t,j = (St )

b P = sym(EP C b t,j ), K t,j

b P = (S b P )−1 K bP . B t,j t t,j

(62)

b P . A computable bound is given by bP = C b t,j − C bPB Then C t t,j t,j b P ∥F ) δt,j (P ) = ω(ϵt,j + ϵt (P )∥B t,j b P ∥F + ωϵt (P ) ∥W1/2 C t sP ϵt (P ) + ϵt,j b P ∥F ). ×( + (ϵt (P ) + γt )∥B t,j 2

+

(63)

To prove it, covariance symmetry gives bP ∥KP t,j − Kt,j ∥F ≤

ϵt (P ) + ϵt,j . 2

(64)

The conditioning-coefficient difference satisfies P −1 P bP bP bP bP BP (KP t,j − Bt,j = (St ) t,j − Kt,j + (St − St )Bt,j ).

(65)

Using Proposition 2 yields bP

1

2 (ϵt (P )+ϵt,j )+(ϵt (P )+γt )∥Bt,j ∥F bP ||BP . t,j − Bt,j ||F ≤ sP

(66)

Finally, the conditional-response error decomposes as P bP P P bP bP CP t,j − Ct,j = Dt,j − Dt Bt,j − Ct (Bt,j − Bt,j ).

(67)

Applying the weighted Frobenius norm and the preceding bounds establishes bP W1/2 (CP t,j − Ct,j )

F

≤ δt,j (P ).

For the empty prefix, only the root-response error remains, giving δt,j (∅) = ωϵt,j . 21

(68)

A.5

Proof of Lemma 1

P T P P T Consider a feasible continuation T of prefix P , define CP t,T = Σt ET and St (T ) = ET Σt ET + RT . Since P St (T ) ⪰ RT ≻ 0,   −1 T P Jt (P ⊕ T ) − Jt (P ) = tr (SP (CP t (T )) t,T ) WCt,T X −1/2 2 ≤ ∥W1/2 CP ∥F t,j Rj (69) j∈T X ≤ bt,j (P ). j∈T −1/2

The last inequality uses the conditional-response error and ∥Rj ∥22 = 1/λmin (Rj ). Every feasible continuation contains at most rP locations drawn from At (P ). Replacing its sum by the largest at most rP complete the proof.

A.6

Proof of Proposition 3

For any prefix P excluded by the certified continuation bound, every feasible completion P ′ satisfies Jt (P ′ ) ≤ Jt (Q0t ). Since each incumbent replacement is certified by a positive lower comparison bound, the exact incumbent value is nondecreasing. Therefore, Jt (P ′ ) ≤ Jt (Q0t ) ≤ Jt (Qt ).

(70)

Likewise, any terminal route previously excluded by a certified comparison against an earlier incumbent remains dominated by Qt . By complete route coverage, every remaining terminal route belongs to Tt or has been certified as dominated. For each P ∈ Tt , the valid comparison bound gives Jt (P ) − Jt (Qt ) ≤ ∆t (P, Qt ) ≤ gt .

(71)

Taking the maximum over the declared route family establishes (31). Finally, numerical refinement changes only the approximate responses and their certificates. Previously certified dominance relations therefore remain valid, and excluded branches need not be revisited. This completes the proof.

References Fayçal Aït Aoudia, Jakob Hoydis, Merlin Nimier-David, Baptiste Nicolet, Sebastian Cammerer, and Alexander Keller. Sionna RT: Technical report, 2025. URL https://arxiv.org/abs/2504.21719. Wangqian Chen and Junting Chen. Diffraction and scattering aware radio map and environment reconstruction using geometry model-assisted deep learning. IEEE Trans. Wireless Commun., 23(12):19804–19819, 2024. doi: 10.1109/TWC.2024.3487225. Wangqian Chen and Junting Chen. Learning blockage and reflection geometry for MIMO beam map construction. In Proc. IEEE Int. Conf. Commun. (ICC), pages 2321–2326, 2025. doi: 10.1109/ICC52391.2025.11161713. Xinwei Chen, Xiaofeng Zhong, Zijian Zhang, Linglong Dai, and Shidong Zhou. High-efficiency urban 3-d radio map estimation based on sparse measurements. IEEE Trans. Veh. Technol., 74(10):16488–16493, 2025a. doi: 10.1109/TVT.2025.3573595. Yiran Chen, Qiuming Zhu, Jie Wang, Ziye Jia, Xuan Wang, Zhipeng Lin, Yang Huang, Qihui Wu, and César BrisoRodríguez. UAV-aided efficient informative path planning for autonomous 3D spectrum mapping. IEEE Trans. Cogn. Commun. Netw., 12:1664–1677, 2026. doi: 10.1109/TCCN.2025.3603736. Zhibo Chen, Heng Wang, and Daoxing Guo. 3D radio map estimation based on active measurement trajectory selection. IEEE Wireless Commun. Lett., 14(7):1884–1888, 2025b. doi: 10.1109/LWC.2025.3557556. Yuntong Gu, Xiangming meng, Zhiyuan Lin, Sheng Wu, and Linling Kuang. Generative bayesian spectrum cartography: Unified reconstruction and active sensing via diffusion models. arXiv:2512.20108, 2025. doi: https://arxiv.org/abs/2512.20108.

22

Fabian Jaensch, Giuseppe Caire, and Begüm Demir. Radio map prediction from aerial images and application to coverage optimization. IEEE Trans. Wireless Commun., 25:308–320, 2026. doi: 10.1109/TWC.2025.3583171. Bowen Li and Junting Chen. Radio map-assisted approach for interference-aware predictive UAV communications. IEEE Trans. Wireless Commun., 23(11):16725–16741, 2024. doi: 10.1109/TWC.2024.3446240. Mingxu Li, Yao Shi, Emad Alsusa, Deyou Zhang, Jie Deng, Nanchi Su, and Xiaohu You. End-to-end uav-enabled adaptive 3D radio mapping via joint optimization of sparse sampling and reconstruction. IEEE Internet Things J., 13(11):25100–25113, 2026. doi: 10.1109/JIOT.2026.3676550. Junyi Lin, Tao Wu, Hongjun Wang, Chao Dong, Zhexian Shen, Mingjin Zhang, and Jiannong Cao. UAV-enabled adaptive radio sampling for high-quality radio environment map construction in unknown environments. IEEE Trans. Mobile Comput., 2026. doi: 10.1109/TMC.2026.3737955. Early Access. Wenlihan Lu, Shijian Gao, Miaowen Wen, Yuxuan Liang, Liuqing Yang, Chan-Byoung Chae, and H. Vincent Poor. Bayesian-driven graph reasoning for active radio map construction. In Int. Conf. Wireless Commun. and Signal Process. (WCSP), pages 1–6, 2025. doi: 10.1109/WCSP68525.2025.1010321. Konstantinos D. Polyzos, Alireza Sadeghi, Wei Ye, Steven Sleder, Kodjo Houssou, Jeff Calder, Zhi-Li Zhang, and Georgios B. Giannakis. Bayesian active learning for sample efficient 5G radio map reconstruction. IEEE Trans. Wireless Commun., 23(12):19382–19396, 2024. doi: 10.1109/TWC.2024.3483112. Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. The MIT Press, Cambridge, MA, USA, 2006. ISBN 0-262-18253-X. URL https://gaussianprocess.org/gpml/. Xiaoyan Shao, Wence Zhang, Haohan Li, Zhichao Shao, Zhiguang Zhang, and Xu Bao. A low-complexity channel knowledge map construction based on environmental partitioning and interpolation weight learning. IEEE Internet Things J., 13(11):24044–24056, 2026. doi: 10.1109/JIOT.2026.3672412. Raju Shrestha, Daniel Romero, and Sundeep Prabhakar Chepuri. Spectrum surveying: Active radio map estimation with autonomous uavs. IEEE Trans. Wireless Commun., 22(1):627–641, 2023. doi: 10.1109/TWC.2022.3197087. Hao Sun and Junting Chen. Integrated interpolation and block-term tensor decomposition for spectrum map construction. IEEE Trans. Signal Process., 72:3896–3911, 2024. doi: 10.1109/TSP.2024.3439513. Hao Sun, Shicong Liu, Xianghao Yu, and Ying Sun. Flow matching-based active learning for radio map construction with low-altitude uavs. In Proc. Int. Conf. Wireless Commun. Signal Process. (ICASSP), pages 21406–21410, 2026. doi: 10.1109/ICASSP55912.2026.11463842. Yves Teganya and Daniel Romero. Deep completion autoencoders for radio map estimation. IEEE Trans. Wireless Commun., 21(3):1710–1724, 2022. doi: 10.1109/TWC.2021.3106154. Subash Timilsina, Sagar Shrestha, and Xiao Fu. Quantized radio map estimation using tensor and deep generative models. IEEE Trans. Signal Process., 72:173–189, 2024. doi: 10.1109/TSP.2023.3336179. Xiucheng Wang, Keda Tao, Nan Cheng, Zhisheng Yin, Zan Li, Yuan Zhang, and Xuemin Shen. Radiodiff: An effective generative diffusion model for sampling-free dynamic radio map construction. IEEE Trans. Cognit. Commun. Netw., 11(2):738–750, 2025a. doi: 10.1109/TCCN.2024.3504489. Yixian Wang, Geng Sun, Zemin Sun, Jiacheng Wang, Jiahui Li, Changyuan Zhao, Jing Wu, Shuang Liang, Minghao Yin, Pengfei Wang, Dusit Niyato, Sumei Sun, and Dong In Kim. Toward realization of low-altitude economy networks: Core architecture, integrated technologies, and future directions. IEEE Trans. Cognit. Commun. Netw., 11(5):2788–2820, 2025b. doi: 10.1109/TCCN.2025.3601015. Di Wu, Yong Zeng, Shi Jin, and Rui Zhang. Environment-aware hybrid beamforming by leveraging channel knowledge map. IEEE Trans. Wireless Commun., 23(5):4990–5005, 2024. doi: 10.1109/TWC.2023.3323941. Yong Zeng, Junting Chen, Jie Xu, Di Wu, Xiaoli Xu, Shi Jin, Xiqi Gao, David Gesbert, Shuguang Cui, and Rui Zhang. A tutorial on environment-aware communications via channel knowledge map for 6G. IEEE Commun. Surveys Tuts., pages 1–1, 2024. doi: 10.1109/COMST.2024.3364508. Guoyong Zhang, Xiao Fu, Jun Wang, Xi-Le Zhao, and Mingyi Hong. Spectrum cartography via coupled block-term tensor decomposition. IEEE Trans. Signal Process., 68:3660–3675, 2020. doi: 10.1109/TSP.2020.2993530. Na Zhang, Rui Zhou, Ming-Yi You, and Wenqiang Pu. Adaptive sampling for online uav-aided radio map sensing. In Proc. European Signal Process. Conf. (EUSIPCO), pages 985–989, 2025. doi: 10.23919/EUSIPCO63237.2025. 11226752.

23

Haitao Zhao, Qing Hao, Hao Huang, Guan Gui, Tomoaki Ohtsuki, Hikmet Sari, and Fumiyuki Adachi. Online trajectory optimization for energy-efficient cellular-connected UAVs with map reconstruction. IEEE Trans. Veh. Technol., 73(3):3445–3456, 2024. doi: 10.1109/TVT.2023.3323349. Zhihao Zheng, Limin Xiao, Ming Zhao, and Yunzhou Li. Efficient indoor radio map prediction with improved transformers and active sampling strategies. In Proc. IEEE Int. Workshop Mach. Learn. Signal Process. (MLSP), pages 1–6, 2025. doi: 10.1109/MLSP62443.2025.11204304.

24

Related documents

• Learning Graph Beliefs for Active Radio Mapping With Decision-Certified Multi-Step Sensing#1488509
• Pathwise Information Certificates for Decentralized Adaptive Sensing#1234729
• Pathwise Information Certificates for Decentralized Adaptive Sensing#1227345
• Optimizing Stochastic Gradient Push under Broadcast Communications#1341390
• Enhancing spectrum sensing efficiency in multi-channel cognitive device-to-device networks: Medium Access Control layer strategies and analysis#210797