Scalable Bayesian Structure Learning for Gaussian Graphical Models Using Marginal Pseudo-likelihood

• URL: http://arxiv.org/abs/2307.00127v4
• Date: Wed, 27 Aug 2025 16:23:37 GMT
• Title: Scalable Bayesian Structure Learning for Gaussian Graphical Models Using Marginal Pseudo-likelihood
• Authors: Reza Mohammadi, Marit Schoonhoven, Lucas Vogels, S. Ilker Birbil,
• Abstract summary: We develop continuous-time (birth-death) and discrete-time (reversible jump) Markov chain Monte Carlo (MCMC) algorithms that efficiently explore the posterior over graph space.<n>The algorithms scale to large graph spaces, enabling parallel exploration for graphs with over 1,000 nodes.
• Score: 2.312692134587988
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bayesian methods for learning Gaussian graphical models offer a principled framework for quantifying model uncertainty and incorporating prior knowledge. However, their scalability is constrained by the computational cost of jointly exploring graph structures and precision matrices. To address this challenge, we perform inference directly on the graph by integrating out the precision matrix. We adopt a marginal pseudo-likelihood approach, eliminating the need to compute intractable normalizing constants and perform computationally intensive precision matrix sampling. Building on this framework, we develop continuous-time (birth-death) and discrete-time (reversible jump) Markov chain Monte Carlo (MCMC) algorithms that efficiently explore the posterior over graph space. We establish theoretical guarantees for posterior contraction, convergence, and graph selection consistency. The algorithms scale to large graph spaces, enabling parallel exploration for graphs with over 1,000 nodes, while providing uncertainty quantification and supporting flexible prior specification over the graph space. Extensive simulations show substantial computational gains over state-of-the-art Bayesian approaches without sacrificing graph recovery accuracy. Applications to human and mouse gene expression datasets demonstrate the ability of our approach to recover biologically meaningful structures and quantify uncertainty in complex networks. An implementation is available in the R package BDgraph.

Related papers

• SIGMA: Scalable Spectral Insights for LLM Collapse [51.863164847253366]
  We introduce SIGMA (Spectral Inequalities for Gram Matrix Analysis), a unified framework for model collapse.<n>By utilizing benchmarks that deriving and deterministic bounds on the matrix's spectrum, SIGMA provides a mathematically grounded metric to track the contraction of the representation space.<n>We demonstrate that SIGMA effectively captures the transition towards states, offering both theoretical insights into the mechanics of collapse.
  arXiv  Detail & Related papers  (2026-01-06T19:47:11Z)
• QGraphLIME - Explaining Quantum Graph Neural Networks [0.48998185508205744]
  Quantum graph neural networks offer a powerful paradigm for learning on graph-structured data.<n>QuantumGraphLIME treats model explanations as distributions over local surrogates fit on structure-preserving perturbations of a graph.
  arXiv  Detail & Related papers  (2025-10-07T08:39:13Z)
• Two Birds with One Stone: Enhancing Uncertainty Quantification and Interpretability with Graph Functional Neural Process [27.760002432327962]
  Graph neural networks (GNNs) are powerful tools on graph data.<n>However, their predictions are mis-calibrated and lack interpretability.<n>We propose a new uncertainty-aware and interpretable graph classification model.
  arXiv  Detail & Related papers  (2025-08-23T17:48:05Z)
• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  This work revisits the definition of the reservoir in the Multiresolution Reservoir Graph Neural Network (MRGNN)<n>It proposes a variant based on a Fairing algorithm originally introduced in the field of surface design in computer graphics.<n>The core contribution of the paper lies in the theoretical analysis of the algorithm from a random walks perspective.
  arXiv  Detail & Related papers  (2025-07-17T10:02:57Z)
• Learning the hub graphical Lasso model with the structured sparsity via an efficient algorithm [1.0923877073891446]
  We introduce a two-phase algorithm to estimate hub graphical models. The proposed algorithm first generates a good initial point via a dual alternating direction method of multipliers. It then warms a semismooth Newton (SSN) based augmented Lagrangian method (ALM) to compute a solution that is accurate enough for practical tasks.
  arXiv  Detail & Related papers  (2023-08-17T08:24:28Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression. Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates. The proposed approach is implemented in the R package probe.
  arXiv  Detail & Related papers  (2022-09-16T19:15:50Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders. Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector. We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-12-15T01:45:32Z)
• Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds [7.428782604099876]
  A major obstacle to practical applications of Gibbs distributions is the need to estimate their partition functions. We present a novel method for reducing the computational complexity of rigorously estimating the partition functions.
  arXiv  Detail & Related papers  (2021-11-14T15:42:02Z)
• Gaussian Graphical Model Selection for Huge Data via Minipatch Learning [1.2891210250935146]
  We propose the Minipatch Graph (MPGraph) estimator to solve the problem of graphical model selection. MPGraph is a generalization of thresholded graph estimators fit to tiny, random subsets of both the observations and the nodes. We prove that our algorithm achieves finite-sample graph selection consistency.
  arXiv  Detail & Related papers  (2021-10-22T21:06:48Z)
• Dual Optimization for Kolmogorov Model Learning Using Enhanced Gradient Descent [8.714458129632158]
  Kolmogorov model (KM) is an interpretable and predictable representation approach to learning the underlying probabilistic structure of a set of random variables. We propose a computationally scalable KM learning algorithm, based on the regularized dual optimization combined with enhanced gradient descent (GD) method. It is shown that the accuracy of logical relation mining for interpretability by using the proposed KM learning algorithm exceeds $80%$.
  arXiv  Detail & Related papers  (2021-07-11T10:33:02Z)
• Regularization of Mixture Models for Robust Principal Graph Learning [0.0]
  A regularized version of Mixture Models is proposed to learn a principal graph from a distribution of $D$-dimensional data points. Parameters of the model are iteratively estimated through an Expectation-Maximization procedure.
  arXiv  Detail & Related papers  (2021-06-16T18:00:02Z)
• Bayesian graph convolutional neural networks via tempered MCMC [0.41998444721319217]
  Deep learning models, such as convolutional neural networks, have long been applied to image and multi-media tasks. More recently, there has been more attention to unstructured data that can be represented via graphs. These types of data are often found in health and medicine, social networks, and research data repositories.
  arXiv  Detail & Related papers  (2021-04-17T04:03:25Z)
• Learning non-Gaussian graphical models via Hessian scores and triangular transport [6.308539010172309]
  We propose an algorithm for learning the Markov structure of continuous and non-Gaussian distributions. Our algorithm SING estimates the density using a deterministic coupling, induced by a triangular transport map, and iteratively exploits sparse structure in the map to reveal sparsity in the graph.
  arXiv  Detail & Related papers  (2021-01-08T16:42:42Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Estimation of sparse Gaussian graphical models with hidden clustering structure [8.258451067861932]
  We propose a model to estimate the sparse Gaussian graphical models with hidden clustering structure. We develop a symmetric Gauss-Seidel based alternating direction method of the multipliers. Numerical experiments on both synthetic data and real data demonstrate the good performance of our model.
  arXiv  Detail & Related papers  (2020-04-17T08:43:31Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)
• 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.