Accelerated Random-Sweep Gibbs Sampling for Gaussian Graphical Models via Dual Normal Factor Graphs

• URL: http://arxiv.org/abs/2607.28706v1
• Date: Thu, 30 Jul 2026 15:37:10 GMT
• Title: Accelerated Random-Sweep Gibbs Sampling for Gaussian Graphical Models via Dual Normal Factor Graphs
• Abstract summary: We show that the convergence rate of the random-sweep Gibbs sampler is significantly accelerated in the dual model.<n>We prove that, for all homogeneous models whose graphical representations contain cycles, the convergence rate in the dual domain is universal and independent of the underlying graph topology.
• Score: 2.381405202108335
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the convergence properties of the random-sweep Gibbs sampler for Gaussian graphical models with a thin-membrane prior. We demonstrate that the convergence rate of the Gibbs sampler is significantly accelerated in the dual model, which is obtained by applying the Fourier transform to the local factors of the normal factor graph representing the original model. In both domains, we derive the exact convergence rates for homogeneous $k$-regular graphs. We prove that, for all homogeneous models whose graphical representations contain cycles, the convergence rate in the dual domain is universal and independent of the underlying graph topology. Moreover, we show that the effective convergence rate in the dual domain is governed by the algebraic connectivity of the graph, providing an additional acceleration without increasing the computational complexity per sweep. We further establish an explicit algebraic relation between the covariance structures of the primal and dual models, enabling marginal statistics of the primal model to be recovered directly from those of the dual model. Finally, numerical experiments on several graph families confirm our theoretical results and demonstrate substantial improvements in the convergence rates in various settings.

Related papers

• Spectral Sparsification of Laplacian-Constrained Gaussian and Hüsler-Reiss Graphical Models [2.0391237204597368]
  Graph Laplacians encode graph structures in matrix form.<n>Two related families of probabilistic graphical models can be parameterized by graph Laplacians.<n>We propose to use spectral graph sparsification as a post-estimation operation.
  arXiv  Detail & Related papers  (2026-06-15T13:16:18Z)
• From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models [58.02657021435213]
  We propose a novel Gibbs-based corrector for discrete diffusion models, termed Gibbs-Accelerated Discrete Diffusion (GADD)<n>We show GADD achieves an overall sampling complexity of $mathcalO(mathrmpolylog (varepsilon-1)$, yielding the first such rate for diffusion-based samplers for uniform-rate discrete diffusion models.
  arXiv  Detail & Related papers  (2026-05-26T17:52:28Z)
• Learning Gaussian Graphical Models under Total Positivity via Spectral Graph Sparsification [2.0391237204597368]
  We propose a novel highly-scalable approach for learning Gaussian graphical models from data using spectral sparsification.<n>We show that Spectral-MTP2 retains most of the fit quality of the denser MTP2 baseline, while producing substantially sparser and more interpretable graphs.<n>In simulations and applications to equity returns and gene expression, we observe that Spectral-MTP2 retains most of the fit quality of the MTP2 baseline, while producing substantially sparser and more interpretable graphs.
  arXiv  Detail & Related papers  (2026-05-16T20:59:06Z)
• InfoNCE Induces Gaussian Distribution [7.8922077372145685]
  A loss in contrastive training is InfoNCE and its variants.<n>We show that the InfoNCE objective induces Gaussian structure in representations that emerge from contrastive training.<n>The resulting Gaussian model enables principled analytical treatment of learned representations and is expected to support a wide range of applications in contrastive learning.
  arXiv  Detail & Related papers  (2026-02-27T13:35:58Z)
• Discrete Bayesian Sample Inference for Graph Generation [48.418206985863726]
  We introduce GraphBSI, a novel one-shot graph generative model based on Bayesian Sample Inference (BSI)<n>We state BSI as a differential equation (SDE) and derive a noise-controlled family of SDEs that preserves the marginal distributions via an approximation of the score function.<n>In our empirical evaluation, we demonstrate state-of-the-art performance on molecular and synthetic graph generation, outperforming existing one-shot graph generative models.
  arXiv  Detail & Related papers  (2025-11-04T21:25:51Z)
• Supercharging Graph Transformers with Advective Diffusion [28.40109111316014]
  This paper proposes Advective Diffusion Transformer (AdvDIFFormer), a physics-inspired graph Transformer model designed to address this challenge.<n>We show that AdvDIFFormer has provable capability for controlling generalization error with topological shifts.<n> Empirically, the model demonstrates superiority in various predictive tasks across information networks, molecular screening and protein interactions.
  arXiv  Detail & Related papers  (2023-10-10T08:40:47Z)
• Stable and Transferable Hyper-Graph Neural Networks [95.07035704188984]
  We introduce an architecture for processing signals supported on hypergraphs via graph neural networks (GNNs) We provide a framework for bounding the stability and transferability error of GNNs across arbitrary graphs via spectral similarity.
  arXiv  Detail & Related papers  (2022-11-11T23:44:20Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• An Interpretable Graph Generative Model with Heterophily [38.59200985962146]
  We propose the first edge-independent graph generative model that is expressive enough to capture heterophily. Our experiments demonstrate the effectiveness of our model for a variety of important application tasks.
  arXiv  Detail & Related papers  (2021-11-04T17:34:39Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• The multilayer random dot product graph [6.722870980553432]
  We present a comprehensive extension of the latent position network model known as the random dot product graph. We propose a method for jointly embedding submatrices into a suitable latent space. Empirical improvements in link prediction over single graph embeddings are exhibited in a cyber-security example.
  arXiv  Detail & Related papers  (2020-07-20T20:31:39Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.