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.

  • 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.

  • Results

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

  • Takeaways & Limitations

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

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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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.

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.
  • C. The Boolean Hypercube and the WHT: 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.
  • C. The Boolean Hypercube and the WHT: 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.
  • C. The Boolean Hypercube and the WHT: 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.
  • C. The Boolean Hypercube and the WHT: 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.

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.
  • B. Observation Models: 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.
  • B. Observation Models: 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.
  • B. Observation Models: 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.
  • B. Observation Models: 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.

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.
  • C. Problem Formulation: 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.
  • C. Problem Formulation: 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.

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.

  • The posterior factorizes across nodes because edge transitions are independent and observations decompose nodewise.
  • Each node with k_n potential neighbors has 2^k_n binary edge states, indexed by the active-edge pattern.
  • The belief vector assigns posterior probabilities to these states, enabling uncertainty quantification rather than only point estimation.
  • Prediction propagates beliefs through the transition model using the Chapman-Kolmogorov equation before new observations are incorporated.
  • Because transition probabilities depend on XOR state differences, prediction is a dyadic convolution that FWHT converts into pointwise multiplication.
  • Precomputing the transition spectrum enables reuse at every time step and extends naturally to τ-step prediction through spectral exponentiation.

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.

  • Bayesian updating combines the predicted belief with observation likelihoods using Bayes’ rule.
  • Under the observation model, each node’s likelihood depends on its local state, observations, and noise parameters.
  • The likelihood vector contains one likelihood value for each node state, with normalization producing the updated belief.
  • The SEM-family likelihoods use observations restricted to a node’s potential neighbors, including one-hop and degree-normalized variants.
  • The AR model incorporates state-dependent observation variance into its likelihood calculation.
  • Algorithm 1 alternates prediction, likelihood computation, and normalized belief updating for every node and time step.

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.

  • The posterior belief supports point estimates and uncertainty characterization for each node’s connectivity at each time.
  • Marginal edge probabilities are obtained from the expected state and support soft connectivity decisions.
  • Belief entropy measures overall uncertainty, reaching its maximum for a uniform distribution and minimum for certainty in one state.
  • The complete procedure reconstructs the adjacency matrix after FWHT-based prediction, observation likelihood computation, and normalized updates.
  • When the transition probability is unknown, the method uses an EM framework adapted from Baum-Welch to estimate it from observed data.
  • The EM Q-function separates observation and transition terms, while the transition term depends on the expected number of edge flips.

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.

  • Forward-backward recursions compute the posterior distribution of transitions needed for the EM expected sufficient statistics.
  • The forward and backward variables collect values over all 2^k_n states and satisfy dyadic-convolution recursions.
  • FWHT computes both recursions in O(k_n 2^k_n) per time step and per node.
  • Algorithm 2 iterates parameter initialization, FWHT-accelerated forward-backward computation, and the M-step until convergence criteria are met.
  • The expected flip-pattern distribution combines local likelihoods with backward messages before normalization.

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: The closed-form flip-probability update estimates the expected fraction of edges changing state across edges and time steps.Node-specific probabilities are obtained by omitting the average over nodes.
  • Closed-Form Update for the M-Step: Node-specific flip probabilities quantify the average fraction of state changes among each node’s incident edges.
  • EM Algorithm: Algorithm 2 summarizes the full EM-based parameter-learning method.

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).
  • Computational Complexity: The method is practical for k_max ≲ 20, corresponding to approximately 10^6 states per node.
  • Computational Complexity: 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.
  • 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.
  • 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.
  • Performance on Synthetic Data: 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.

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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Statistical structures: For time-varying statistical structures, BET achieves the lowest G-NMSE on every dataset except Intel and outperforms baselines on the paired G-NMSE and F1 metrics.DGD is the next-best method with G-NMSE values from 0.88–0.91.

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.
  • 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.
  • Parameter mismatch: Correctly specifying BET’s flip probability and change period gives the best G-NMSE, while overestimation spreads predictions and underestimation slows adaptation.These effects are evaluated under frequent changes and high observation noise, with matched parameter values best per row.
  • 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.
  • 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.
Loading 2609.11263v1…