# The Dual PC Algorithm and the Role of Gaussianity for Structure Learning of Bayesian Networks

arXiv: https://arxiv.org/abs/2112.09036 · HTML: https://mlsanity.com/paper/2112.09036/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 54 references that are in the map.
- First posted on arXiv 16 Dec 2021.

## Builds on (most cited first, 8 of 8)

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal Networks: Semantics and Expressiveness](https://mlsanity.com/paper/1304.2379/) (2013)
- [A fast PC algorithm for high dimensional causal discovery with multi-core PCs](https://mlsanity.com/paper/1502.02454/) (2015)
- [Towards Scalable Bayesian Learning of Causal DAGs](https://mlsanity.com/paper/2010.00684/) (2020)
- [Large-scale empirical validation of Bayesian Network structure learning algorithms with noisy data](https://mlsanity.com/paper/2005.09020/) (2020)
- [Efficient Sampling and Structure Learning of Bayesian Networks](https://mlsanity.com/paper/1803.07859/) (2018)
- [The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks](https://mlsanity.com/paper/1806.06209/) (2018)
- [Nonparametric causal structure learning in high dimensions](https://mlsanity.com/paper/2106.11415/) (2021)

## Built on by (most cited first, 2 of 2)

- [A Bayesian Take on Gaussian Process Networks](https://mlsanity.com/paper/2306.11380/) (2023)
- [Learning linear acyclic causal model including Gaussian noise using ancestral relationships](https://mlsanity.com/paper/2409.00417/) (2024)

## Abstract (arXiv)

Learning the graphical structure of Bayesian networks is key to describing data-generating mechanisms in many complex applications but poses considerable computational challenges. Observational data can only identify the equivalence class of the directed acyclic graph underlying a Bayesian network model, and a variety of methods exist to tackle the problem. Under certain assumptions, the popular PC algorithm can consistently recover the correct equivalence class by reverse-engineering the conditional independence (CI) relationships holding in the variable distribution. The dual PC algorithm is a novel scheme to carry out the CI tests within the PC algorithm by leveraging the inverse relationship between covariance and precision matrices. By exploiting block matrix inversions we can also perform tests on partial correlations of complementary (or dual) conditioning sets. The multiple CI tests of the dual PC algorithm proceed by first considering marginal and full-order CI relationships and progressively moving to central-order ones. Simulation studies show that the dual PC algorithm outperforms the classic PC algorithm both in terms of run time and in recovering the underlying network structure, even in the presence of deviations from Gaussianity. Additionally, we show that the dual PC algorithm applies for Gaussian copula models, and demonstrate its performance in that setting.