PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Bayesian Tracking of Dynamic Network Topologies

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

arXiv:2609.11263v1eess.SP

TL;DR

Dynamic topology tracking requires inference over changing binary graph structures, whereas existing approaches can mismatch discrete unweighted graphs or provide only point estimates. The paper introduces BET, an exact Bayesian state-space tracker with Boolean-hypercube dynamics, FWHT-accelerated prediction, and EM learning of unknown transition probabilities. Experiments report superior tracking accuracy, faster adaptation to topology changes, and meaningful uncertainty estimates across synthetic and real-world settings.

  • Problem

    Dynamic topology inference needs a discrete probabilistic treatment because common approaches can yield point estimates or mismatch binary unweighted graph structure.

    Source: §I · p. 1

  • Method

    BET treats the unweighted adjacency matrix as a hidden Markov state, computes exact posteriors from graph signals, accelerates prediction with FWHT, and learns unknown transition probabilities using EM.

    Source: §I · p. 1

  • Results

    Experiments demonstrate superior tracking accuracy, faster adaptation to topology changes, and meaningful uncertainty estimates compared with state-of-the-art and classical baselines.

    Source: §VIII · pp. 12–13

  • Takeaways & Limitations

    The framework is suited to real-time monitoring of network evolution in social-network, epidemiological, and adaptive signal-processing applications.

    Source: §VIII · p. 13

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper addresses dynamic topology inference for binary graphs by introducing an exact Bayesian tracker that uses graph-signal observations and represents uncertainty over network states. It also develops FWHT acceleration, EM parameter learning, and broad empirical validation.

I. INTRODUCTION

  • The full paper adds observation models, FWHT acceleration, EM adaptation, edge-probability uncertainty quantification, and extensive real-world validation beyond the preliminary conference version.The experiments include six real-world datasets according to the paper context.Source: §I · p. 1
  • Existing RLS, online optimization, Kalman, and tensor methods can produce continuous point estimates, require thresholding or batch processing, or mismatch binary unweighted graph structure.The paper motivates placing a prior directly over the Boolean space of binary adjacency matrices.Source: §I · p. 1
  • BET models the unweighted adjacency matrix as a hidden discrete Markov state and computes the full posterior distribution over network states from graph signals.This supports uncertainty quantification, prediction, and principled topology decisions.Source: §I · p. 1
  • The FWHT reduces prediction complexity from O(4^k) to O(k2^k) by exploiting XOR-shift-invariant transitions and dyadic convolution on per-node Boolean states.Rows are represented as binary vectors on the Boolean hypercube, with k denoting the maximum node degree.Source: §I · pp. 1–2
  • An EM framework generalizes Baum-Welch to learn unknown transition probabilities from observed signals.The extension adapts forward-backward recursions and expected sufficient statistics to the Boolean hypercube.Source: §I · p. 2

C. The Boolean Hypercube and the WHT

The method represents per-node edge states on the Boolean hypercube, whose XOR-group structure makes network transitions shift-invariant. This enables dyadic-convolution prediction and FWHT acceleration while retaining tractable independent-edge dynamics.

C. The Boolean Hypercube and the WHT

  • The prediction step becomes a dyadic convolution on the Boolean group, whose convolution theorem converts the operation into pointwise multiplication in the WHT domain.The WHT is self-inverse up to scaling.Source: C. The Boolean Hypercube and the WHT · p. 3
  • The FWHT computes the transform in O(k2^k) operations instead of O(4^k) naive matrix-vector multiplication.This computational reduction is the key efficiency mechanism of the proposed method.Source: C. The Boolean Hypercube and the WHT · p. 3
  • Each node’s admissible incoming-edge state is a binary vector in {0,1}^k, and the Boolean hypercube uses componentwise XOR as its group operation.The base topology restricts candidate neighbors and can be expanded to the complete graph for the unconstrained setting.Source: A. Dynamic Network Model · pp. 3–4, C. The Boolean Hypercube and the WHT · p. 3
  • The model assumes edges are created and destroyed independently, with unknown transition probabilities optionally learned through EM.The independent model preserves exact and scalable inference, although real networks may exhibit edge memory.Source: A. Dynamic Network Model · p. 4
  • Independent edge flips make the transition probability depend only on the XOR flip pattern δ=u⊕v, not on the initial or final states.This XOR-shift invariance is the structural property used for acceleration.Source: A. Dynamic Network Model · p. 4

B. Observation Models

The observation models connect graph signals to unknown topology through nodewise SEM formulations and an autoregressive model. Their nodewise structure supports tractable per-node inference, including a diagonal approximation for correlated filtered noise in the AR case.

B. Observation Models

  • The paper considers SEM and autoregressive observation families relating input signals z_t and output signals y_t to the network structure.These models provide the likelihood information used to infer hidden edge states.Source: B. Observation Models · p. 4
  • The SEM family uses graph shift operators, including one-hop adjacency and degree-normalized adjacency, with per-node observation means linear in the local edge state.The input signal is restricted to each node’s potential neighbors.Source: B. Observation Models · p. 4
  • The AR model uses y_t=(I−αA_t)^−1z_t+w_t under a stability condition based on the spectral radius.It is intended for diffusion or autoregressive processes such as epidemics and sensor diffusion.Source: B. Observation Models · p. 4
  • Rearranging the AR model creates state-dependent filtered noise with non-diagonal covariance, so the tracker retains marginal variance through a standard diagonal approximation.The approximation enables per-node tractability and is evaluated with the other observation models.Source: B. Observation Models · p. 4
  • Controlled input signals can be designed to isolate topology information, such as using canonical basis signals to isolate adjacency columns.Examples include pilot signals in wireless networks and broadcasts from a leader robot.Source: B. Observation Models · p. 4

C. Problem Formulation

The problem formulation seeks the posterior distribution of each node’s network state given all observations to date. It also permits estimating unknown transition probabilities and performing multi-step prediction.

C. Problem Formulation

  • For each node and time t, the tracker computes the posterior distribution of its edge state conditioned on the observation history H_t.The state-space model supplies the transition kernel and observation models.Source: C. Problem Formulation · p. 4
  • The posterior fully characterizes the network state and supports MAP or posterior-mean estimates, entropy, marginal edge probabilities, and other quantities.These outputs provide both point estimates and uncertainty information.Source: C. Problem Formulation · p. 4
  • When the transition probability p_c is unknown, the framework estimates it with the paper’s EM procedure.The same formulation also supports multi-step prediction beyond filtering.Source: C. Problem Formulation · p. 4

IV. BAYESIAN TRACKING ON THE BOOLEAN HYPERCUBE

The tracker represents each node’s incoming-edge configuration as a probability distribution over Boolean-hypercube states. Independent edge transitions and nodewise observations factorize the posterior, while FWHT-accelerated dyadic convolution makes prediction efficient.

D. Update Step via Likelihood Weighting

The update step converts observations into state-wise likelihoods and combines them with predicted beliefs through Bayes’ rule. The likelihood construction accommodates multiple observation models using node-local signals and noise parameters.

E. State Estimation and Uncertainty Quantification

The posterior belief is a complete probability mass function from which the tracker derives state estimates, marginal edge probabilities, and uncertainty measures. The framework also introduces EM-based learning when the transition probability is unknown.

B. Forward-Backward Algorithm with FWHT

The EM E-step uses forward-backward recursions to compute posterior transition statistics over the Boolean-hypercube state space. Because these recursions are dyadic convolutions, FWHT reduces their per-node, per-time-step cost.

C. Closed-Form Update for the M-Step and EM Algorithm

The M-step updates transition probabilities from expected edge flips, with node-specific estimates available by removing the average over nodes. The complete EM procedure is summarized in Algorithm 2.

Closed-Form Update for the M-Step

EM Algorithm

VI. COMPUTATIONAL COMPLEXITY ANALYSIS

The tracker has per-node, per-timestep complexity O(k_n2^k_n), achieved through FWHT-based prediction, and remains practical for maximum degrees around 20. Experiments evaluate runtime and tracking performance under synthetic graph dynamics, with undirected results requiring an approximation.

Computational Complexity

  • FWHT prediction and likelihood evaluation yield O(k_n2^k_n) per-node, per-timestep complexity, compared with naive O(4^k_n) matrix-vector multiplication.The overall tracker costs O(N · k_max · 2^k_max · T), while EM learning costs O(M · N · k_max · 2^k_max · T).Source: §VI · p. 7
  • The method is practical for k_max ≲ 20, corresponding to approximately 10^6 states per node.Source: §VI · p. 7
  • At k_n = 20, the proposed tracker takes approximately 2.9 seconds per timestep versus over 42 hours for the naive approach, exceeding 50,000× speedup.Measured runtimes follow the theoretical O(k · 2^k) curve; both theoretical curves are anchored at k = 10.Source: §VI · p. 7, Figure 1 · p. 7

Experimental Evaluation

  • Synthetic evaluations use RGG and ER graphs, while tracking metrics include G-NMSE, S-NMSE, and F1 score averaged across independent runs.The benchmark compares BET with RLS, RRLS, GTKF, RGFI, DGD, and GKF.Source: A. Performance on Synthetic Data · pp. 7–8

Performance on Synthetic Data

  • In undirected benchmarks, BET uses post-hoc symmetrization that produces marginal edge probabilities but not a posterior over symmetric adjacency configurations.Directed-graph inference is exact, whereas the undirected adaptation is approximate; GTKF and RGFI are excluded from directed comparisons because they enforce symmetry.Source: A. Performance on Synthetic Data · pp. 8–9
  • Under random topology dynamics, BET maintains the lowest error and adapts within a few samples, whereas RLS-based methods and GTKF show higher variance and slower convergence.The undirected experiment uses RGG graphs with N = 20, p_c = 0.01, T_c = 1, and direct one-hop observations.Source: A. Performance on Synthetic Data · p. 8, Figure 2 · p. 8

B. Ablation Studies

Ablations show that BET remains accurate across changing dynamics, noise levels, graph topologies, and observation models, while EM learns transition probabilities under varying observation quality. Comparisons with RLS and DGD further show robust tracking and faster recovery after topology changes.

Synthetic dynamics

  • BET maintains low G-NMSE across dynamics regimes, degrading gradually as flip probabilities increase or change periods shorten rather than failing sharply.For pc ≥ 0.2, RGG graphs outperform ER graphs because spatial locality aids prediction under frequent changes.Source: B. Ablation Studies · p. 9

Noise robustness

  • BET remains robust down to approximately 12 dB SNR, with graceful degradation at lower SNR and particular Laplacian robustness on RGG graphs.The probabilistic update weights informative and noisy observations differently.Source: B. Ablation Studies · p. 9

Topology sensitivity

  • At moderate dynamics, ER and RGG perform comparably, whereas high dynamics favor RGG because smaller, more stable candidate neighborhoods improve state concentration and transition-prior accuracy.ER graphs have greater degree variance, making beliefs harder to concentrate when multiple edges flip simultaneously.Source: B. Ablation Studies · p. 9

EM parameter learning

  • EM converges to the true pc = 0.05 from initializations spanning pc ∈ [0.01, 0.50], requiring one iteration at SNR ≥ 12 dB but multiple iterations at SNR ≤ 10 dB.The experiment uses 100 synthetic ER graphs with varying topologies.Source: B. Ablation Studies · p. 9, Figure 4 · p. 10

Variant comparison

  • BET avoids the AR inverse problem that causes RLS (Inv) and DGD to diverge, while RLS (Dir) is the only alternative variant that successfully learns the structure.BET remains robust by modeling the observation likelihood directly without matrix inversion.Source: B. Ablation Studies · p. 9

Real-world graphs with synthetic dynamics

  • BET tracks realistic Karate and Florentine topologies accurately and recovers faster than RLS after topology changes because posterior mass concentrates on the new structure instead of retaining stale observations.On Florentine, BET maintains error close to 0; on denser Karate, nonzero error is expected under simultaneous edge changes.Source: C. Real-World Graphs with Synthetic… · pp. 9–10

Recovery visualization

  • On Florentine Families, both methods reach F1 = 0.966 immediately after change, but BET returns to F1 = 1.0 by t = 26 while RLS remains at 0.966.The comparison uses a shorter change period Tc = 15 to stress-test recovery speed.Source: C. Real-World Graphs with Synthetic… · p. 10

Statistical structures

E. Robustness to Model Misspecification

BET remains robust under several violations of its transition-model assumptions, but performance is sensitive to misspecified flip and change-period parameters. Its posterior uncertainty also reflects topology changes, tracking error, and calibration quality.

Refractory dynamics

  • BET remains nearly invariant to refractory-period violations, maintaining G-NMSE ≈0.176 across R ∈{0, 2, 5, 10, 20}.The refractory setting makes dynamics slower than assumed, allowing the observation likelihood to concentrate the posterior on the correct state.Source: E. Robustness to Model Misspecification · p. 11

Correlated flips

  • BET’s exact posterior update handles higher observation activity more robustly than baselines without diverging under correlated flips.In unconstrained cascades, BET’s G-NMSE increases from 0.18 to 0.26, a 44% degradation; under rate-controlled cascades, performance remains essentially flat across cascade probabilities.Source: E. Robustness to Model Misspecification · p. 11

Parameter mismatch

Entropy tracking

  • Posterior entropy spikes by 17–20 bits at topology changes and decays over 30–40 timesteps under high noise and frequent changes.The decay captures prolonged recovery as noisy observations gradually concentrate belief on the new topology.Source: F. Uncertainty Quantification · pp. 11–12

Error awareness and calibration

  • BET’s uncertainty estimates are decision-relevant: high entropy aligns with higher tracking error, while predicted edge probabilities match empirical frequencies with ECE = 0.053.The calibration result supports interpreting a predicted edge probability as an approximate empirical presence frequency.Source: F. Uncertainty Quantification · pp. 11–12

Related papers

Loading 2609.11263v1…