Bayesian Optimization of the PC Algorithm for Learning Gaussian Bayesian Networks

Irene Córdoba, Eduardo C. Garrido-Merchán, Daniel Hernández-Lobato, Concha Bielza, Pedro LarrañagaCAEPIA 2018 · DOI · OpenReview

Abstract

The PC algorithm is a popular method for learning the structure of Gaussian Bayesian networks. It carries out statistical tests to determine absent edges in the network. It is hence governed by two parameters: (i) The type of test, and (ii) its significance level. These parameters are usually set to values recommended by an expert. Nevertheless, such an approach can suffer from human bias, leading to suboptimal reconstruction results. In this paper we consider a more principled approach for choosing these parameters in an automatic way. For this we optimize a reconstruction score evaluated on a set of different Gaussian Bayesian networks. This objective is expensive to evaluate and lacks a closed-form expression, which means that Bayesian optimization (BO) is a natural choice. BO methods use a model to guide the search and are hence able to exploit smoothness properties of the objective surface. We show that the parameters found by a BO method outperform those found by a random search strategy and the expert recommendation. Importantly, we have found that an often overlooked statistical test provides the best over-all reconstruction results.

Introduction

Learning the structure of a Bayesian network—identifying the "skeleton" of causal influences from observational data—is a notoriously difficult combinatorial challenge. The PC algorithm is a standard constraint-based solution that prunes edges from a dense graph through a series of statistical independence tests. However, its performance is highly dependent on two sensitive hyperparameters: the type of statistical test and the significance level ($\alpha$).

Traditionally, researchers rely on "expert recommendations," such as $\alpha = 0.01$ and Fisher’s Z test. This "one-size-fits-all" approach often fails to account for specific data characteristics, such as high dimensionality or sparsity, leading to biased and suboptimal network reconstructions.

Methods

To address these limitations, the authors propose treating the PC algorithm's performance as a black-box function and optimizing its hyperparameters using Bayesian Optimization (BO).

Optimization Framework

The objective function is the Structural Hamming Distance (SHD), which measures the number of edits required to transform the learned graph into the ground truth. The optimization utilizes the Spearmint framework, employing a Gaussian Process (GP) as a surrogate model to map hyperparameter configurations to expected performance.

Illustration of the Bayesian Optimization process using Gaussian Processes and acquisition functions.

The search space includes the significance level $\alpha$ (log-scaled from $10^{-5}$ to $10^{-1}$) and four statistical tests: Fisher’s Z, Student’s t, a $\chi^2$ test, and a shrinkage-based James-Stein estimator. Predictive Entropy Search (PES) is used as the acquisition function to balance exploration and exploitation.

Experimental Setup

The method was evaluated on synthetic Gaussian Bayesian networks across 32 scenarios, varying node counts ($p \in \{25, 50, 75, 100\}$), average neighborhood size ($n \in \{2, 8\}$), and sample sizes ($N \in \{25, 50, 75, 100\}$). Robustness was ensured through 40 replicas per experiment with varying edge coefficients.

Key Results and Insights

The experimental results demonstrate that BO consistently identifies superior hyperparameter settings compared to both Random Search (RS) and the Expert Criterion (EC).

Comparison of BO, Random Search (RS), and Expert Criterion (EC) in terms of normalized SHD.

Performance and Efficiency

As shown in Figure 2, BO achieves a lower SHD in approximately 10 iterations, surpassing the expert baseline quickly. The reduction in standard deviation over iterations highlights the method's robustness. While experts typically suggest $\alpha = 0.01$, BO frequently found optimal values near $0.025$ when paired with appropriate tests.

The Significance of Test Choice

A critical insight is that the choice of statistical test often outweighs the fine-tuning of $\alpha$, especially in high-dimensional settings ($p > N$). Notably, the James-Stein shrinkage estimator—often overlooked in standard literature—emerged as the most effective test for reconstruction.

Conclusion and Future Work

This study confirms that Bayesian Optimization is a practical and effective tool for tuning the PC algorithm, removing human bias and improving accuracy. Future research will explore scalability to thousands of variables, the impact of different optimization metrics (e.g., True Positive rates), and the application of multi-objective BO to balance accuracy with computational efficiency and graph sparsity.

Summary updated

Abstract

The PC algorithm is a popular method for learning the structure of Gaussian Bayesian networks. It carries out statistical tests to determine absent edges in the network. It is hence governed by two parameters: (i) The type of test, and (ii) its significance level. These parameters are usually set to values recommended by an expert. Nevertheless, such an approach can suffer from human bias, leading to suboptimal reconstruction results. In this paper we consider a more principled approach for choosing these parameters in an automatic way. For this we optimize a reconstruction score evaluated on a set of different Gaussian Bayesian networks. This objective is expensive to evaluate and lacks a closed-form expression, which means that Bayesian optimization (BO) is a natural choice. BO methods use a model to guide the search and are hence able to exploit smoothness properties of the objective surface. We show that the parameters found by a BO method outperform those found by a random search strategy and the expert recommendation. Importantly, we have found that an often overlooked statistical test provides the best over-all reconstruction results.
BibTeX
@inproceedings{cordoba2018bayesian,
  author = {Irene Córdoba and Eduardo C. Garrido-Merchán and Daniel Hernández-Lobato and Concha Bielza and Pedro Larrañaga},
  title = {{Bayesian Optimization of the PC Algorithm for Learning Gaussian Bayesian Networks}},
  booktitle = {CAEPIA},
  year = {2018},
  doi = {10.1007/978-3-030-00374-6\_5},
}
Figure