CS Paper Radar

Exact Bayesian Tracking of Dynamic Network Topologies

Victor M. Tenorio, Elvin Isufi, Geert Leus, Antonio G. Marques

eess.SP ·submitted 2026-09-10 08:57 UTC · v1

Abstract

Tracking the temporal evolution of network topologies is a fundamental challenge in social networks, epidemiology, and sensor systems, among others. This paper develops an exact Bayesian tracker for unweighted, directed graphs using nodal signal observations. This framework yields the full posterior probability distribution over network states at each time step, naturally enabling uncertainty quantification, prediction, and principled decision-making. We model the network dynamics as a Markov process on the Boolean hypercube, where edges transition independently according to a flip probability. For efficient computation, we cast the prediction step as a dyadic convolution, and leverage the Fast Walsh-Hadamard Transform to reduce the computational cost from $\mathcal{O} (4^k)$ to $\mathcal{O} (k 2^k)$, where $k$ is the maximum node degree. When the network transition probabilities are unknown, we develop an Expectation-Maximization framework to learn them from the observed signals. Comprehensive experiments on synthetic and six real-world datasets validate the proposed method and demonstrate its superior tracking accuracy, faster recovery from topological changes, and meaningful uncertainty estimates compared to state-of-the-art and classical baselines.

Comment
Under review

Closest papers

Nearest neighbours by meaning across the whole index.

Beyond Static Graph World Models: Learning Stochastic Latent Dynamics over Evolving Topologies

cs.LG cs.AIcs.SI ·2026-09-23 ·Alex Schutz, Nick Hawes, Victor-Alexandru Darvariu
similarity 0.58
Abstract

Graph-based world models have recently emerged as a means of learning transitions over relational state representations. However, existing approaches are largely limited to fixed-topology graphs or deterministic, fully observable environments. We propose the Graph Dynamics Model (GDM), a world model for graph-structured observations that is designed to handle the more general setting of evolving topologies in stochastic and partially observable environments. The GDM uses a sparse recurrent adjacency matrix to model topology updates and perform message passing, together with a recurrent state-space architecture for modelling stochastic transitions. Furthermore, we identify a gap in the evaluation of graph-based world models, as existing methods do not provide a means of comparing predicted and true distributions over the joint graph state comprising the interdependent topology, node features, and graph features. We therefore introduce the Graph Distribution Distance (GDD) metric, which uses maximum mean discrepancy with a graph kernel to comprehensively compare joint next-state distributions. We evaluate the GDM across several environments, including stochastic and partially observable settings. We demonstrate that GDM outperforms baseline models and displays zero-shot generalisation on large graphs.

0.26

Multi-Source Wasserstein Distributionally Robust Graph Learning

cs.LG ·2026-08-20 ·Chuansen Peng, Yifan Xia, Jinshan Zhong, Xiaojing Shen
theory similarity 0.56
Abstract

Reconstructing complex network topologies from data is a fundamental challenge in cybernetics and graph signal processing, with applications in neuroscience, sensor, and social networks. In practice, target-domain samples are scarce while heterogeneous source-domain data are abundant. Fusing these sources is challenging: Euclidean averaging works for homogeneous sources but degrades sharply as inter-source divergence grows, collapsing distinct geometries into an inflated, biased consensus. We exploit the Wasserstein metric's distribution-preserving properties to counter heterogeneity while preserving each source's intrinsic geometry. We propose MS-WDRO, a multi-source Wasserstein distributionally robust graph learning framework that fuses heterogeneous sources via their weighted Wasserstein barycenter, a geometrically principled nominal distribution, then builds an ambiguity ball around it to hedge residual uncertainty. Minimizing worst-case risk yields a tractable regularized Laplacian estimator solved efficiently via a provably convergent ADMM scheme. We establish non-asymptotic guarantees: a finite-sample concentration bound for the empirical barycenter, a pooling bias lower bound proving naive aggregation is suboptimal, and an out-of-sample excess risk bound decaying at a parametric rate with only logarithmic dependence on source count. To calibrate hyperparameters governing robustness, sparsity, and source fusion, we unroll the solver into a differentiable architecture trained end-to-end, achieving data-adaptive calibration beyond cross-validation while retaining interpretability. Experiments on synthetic benchmarks and the multi-site ABIDE~I neuroimaging dataset show MS-WDRO consistently outperforms seven baselines in graph recovery, sample efficiency, and downstream diagnostic utility, with the largest gains in the sample-scarce regime.

0.11

Theory-Driven Network Backbones for Bipartite Projections

cs.SI cs.DB ·2026-11-12 ·Nikos Salamanos, Paula Gheorghiade, Tom Brughmans, Michele Coscia
similarity 0.55
Abstract · 13 pages, 10 figures, 3 tables

Collecting data, including network data, is subject to measurement error. Network backboning is the process of statistically validating each edge in a network to estimate the probability that the edge is born of noisy measurements. The current backboning literature provides approaches in two classes: structural and statistical. The classes differ in many respects, but they share one commonality: the test used to determine whether to filter out noisy edges is data-agnostic; it does not take into account what the network is representing. However, the nodes and edges of all non-synthetic networks correspond to specific real-world entities, whose dynamics determine how the edge-generating process operates. In this paper, we propose the first in a new class of network backboning algorithms: a theory-driven backboning approach that allows us to encode known dynamics into the backboning process. The resulting backbone embeds the encoded theory and produces a network compatible with it, rather than one that obeys a data-agnostic network process, as in the structural and statistical backboning classes. We specifically focus on the case of projecting and backboning a bipartite structure. We do so by allowing users to specify an Agent-Based Model for the two types of agents (nodes) in the network and by performing Simulation-Based Inference to fit the observed bipartite structure and, as a result, reconstruct the true relationships between the two classes of agents. We test our framework both on synthetic data -- where we have perfect information about the edge-generating process -- and in a case study using archaeological data on amphorae retrieved from different archaeological sites. Our approach improves latent-edge recovery over conventional backboning methods in synthetic experiments and reveals interpretable archaeological patterns despite imperfect model fit.

0.44

Bayesian Evidence Accumulation for Graph-Based Learning in Dynamic Data-Driven Applications Systems

cs.LG cs.CV ·2026-10-26 ·Moises Ponce, Sarah Harkins Dayton, Ioannis Schizas, Vasileios Maroulas
similarity 0.55
Abstract

Graph Neural Networks (GNNs) are widely used in modern machine learning, yet most existing frameworks remain fundamentally static, limiting their applicability in Dynamic Data Driven Application Systems (DDDAS) where observations arrive sequentially under uncertainty. We introduce B-EAGLe (Bayesian Evidence Accumulation for Graph-Based Learning), a probabilistic framework inspired by CBGT-Net (cortico-basal ganglia-thalamic network) that reformulates graph classification as a sequential evidence accumulation process. B-EAGLe combines a GNN encoder with a Bayesian accumulator that incrementally updates posterior beliefs over class labels as new observations arrive, committing to a decision only when sufficient confidence is achieved. Experiments on CIFAR10 demonstrate competitive performance together with principled confidence estimation under sequential observations.

0.19

Generalizing Metropolis-Hastings for DAG Sampling

cs.LG cs.AIstat.CO ·2026-10-21 ·Daniele Nikzad, Mikko Koivisto
similarity 0.55
Abstract

A fundamental challenge in Bayesian network structure learning lies in efficiently approximating the posterior distribution of directed acyclic graphs (DAGs). For large, high-dimensional datasets, the task remains beyond the capabilities of current methods. This work advances Markov chain Monte Carlo algorithms by introducing novel moves that simultaneously resample the parents for multiple nodes of the DAG. At the core of these moves is duet sampling, a new generalization of the Metropolis-Hastings algorithm that selects two proposal distributions from a pool at each iteration. One is used for generating a candidate state of the Markov chain and another for evaluating the return to the current state; both are ingredients of an appropriately crafted acceptance criterion. Pairing different proposal distributions provides additional freedom and enables constructing Markov chains that mix more efficiently than their basic Metropolis-Hastings counterparts, at no additional computational cost. Experiments show that our new moves, both individually and in combination, outperform the previous state of the art, which relies on a more restrictive pool of moves. This advantage persists even when letting the previous methods leverage duet sampling to enhance their performance.

0.20

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

cs.NI cs.LG ·2026-10-27 ·Wangqian Chen, Hao Wang, Yumeng Zhang, Chenghong Bian, Junting Chen +1 more
similarity 0.55
Abstract

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.

0.25

Online Bayesian Node Classification on Inductive Graphs under Distribution Shift

cs.LG stat.MEstat.ML ·2026-09-12 ·Jinwen Xu, Gonzalo Mateos Buckstein, Qin Lu
theory similarity 0.54
Abstract

On evolving graphs, node classifiers must satisfy two key requirements: inductive generalization to newly arriving nodes under distribution shift and calibrated uncertainty for safety-sensitive applications. Standard graph neural networks (GNNs) are typically trained once and address neither requirement. We adapt the Bayesian last-layer (BLL) model by placing random last-layer parameters on top of a deterministic GNN encoder for uncertainty quantification. The categorical softmax likelihood required for classification breaks Gaussian conjugacy, so neither the training posterior nor the test-time streaming update has a closed-form solution. To address both challenges, we introduce a variational Bayesian last-layer (VBLL) objective that jointly trains the encoder and an approximate last-layer posterior by maximizing an evidence lower bound with a Monte Carlo expected log-likelihood. At test time, we freeze the encoder and apply an online Laplace update to the last-layer posterior. This update corresponds to a power-prior Bayesian model with exponential forgetting and a Kullback-Leibler anchor to the training posterior. Across five node-classification benchmarks under distribution shift, online GVBLL is the only method to achieve the best accuracy and negative log-likelihood on every dataset. It improves accuracy by up to 17 percentage points on Cora and 14 percentage points on ogbn-arxiv over the strongest non-GVBLL baseline, while remaining competitive in calibration with MC Dropout, Deep Ensembles, Temperature Scaling, and Gaussian-process classifiers.

0.29

Conditional-path Monte Carlo for rare stochastic dynamics on networks: Details and derivations

cs.SI cond-mat.stat-mechphysics.comp-phphysics.soc-ph ·2026-08-18 ·Thomas Barthel, Jiazheng Sun, Jhao-Hong Peng
similarity 0.54
Abstract · 16+2 pages, 5 figures

The simulation of rare macroscopic events in stochastic network dynamics, such as widespread epidemic outbreaks, cascading failures in communication networks, or the escape from metastable states in many-body systems, is severely hindered by methodological challenges like catastrophic rejection rates, weight degeneracy, genealogical correlations, and critical slowing down inherent to standard forward-time algorithms, splitting methods, and transition-path sampling. Conditional-path Monte Carlo (CPMC) overcomes these limitations by employing non-local Swendsen-Wang-like cluster updates that operate directly on full-system trajectories. Serving as the technical companion to [Sun, Moody, and Barthel, arXiv:2608.16171], this paper provides the rigorous mathematical foundations and algorithmic details underlying the CPMC framework. We formally define the joint path-graph probability weights and derive the transition and uniformization sum rules that guarantee detailed balance. Applying the framework to susceptible-infectious-susceptible (SIS) models, we systematically construct and optimize single-node and edge graph vertex sets specifically designed to prevent lock avalanches and maintain the structural mobility of the epidemic trunk. Furthermore, we detail a dynamic programming scheme to exactly implement complex boundary conditions - including patient-zero and macroscopic outbreak-size constraints - enabling the rejection-free generation of valid trajectories. Finally, we assess the computational complexity of the algorithm, describe parallelization strategies, and validate CPMC against exact solutions for dynamics on small networks.

0.42