Abstract: To learn a Bayesian network structure from data, one popular approach is to maximize a decomposable likelihood-based score. While various scores have been proposed, they usually assume a uniform prior over the space of Directed Acyclic Graphs (DAGs). This paper demonstrates that the uniform prior is not neutral, but rather biases the learning process toward overly complex, dense structures. We investigate alternative structure priors and propose a new Search Space Penalty (SSP) to improve the accuracy of learned networks.
Introduction
Learning the structure of a Bayesian Network (BN) is a fundamental problem in machine learning, typically treated as a model selection task. Researchers aim to find a Directed Acyclic Graph (DAG) $G$ that maximizes a score, often composed of a likelihood term and a structure prior $P(G)$. While significant effort has been devoted to refining likelihood-based scores like BDeu and BIC, the structure prior is frequently ignored, with practitioners defaulting to a uniform distribution over all possible DAGs.
This paper, presented at AISTATS 2019, argues that this "uniform" assumption is a mistake. Because there are exponentially more dense graphs than sparse ones, a uniform prior over the space of graphs places the vast majority of its probability mass on complex models. This inherent bias can lead to the discovery of spurious edges, particularly when data is limited.
Rethinking Structure Priors
The authors explore several alternatives to the uniform prior, focusing on those that favor sparsity and are computationally tractable:
- Modular Priors: These priors decompose node-by-node, allowing for efficient integration into existing scoring frameworks. Examples include the Edge prior (penalizing each edge), the Fair prior (balancing mass across different indegrees), and the Data prior (scaling penalties based on sample size).
- Search Space Penalty (SSP): A novel, non-modular prior designed for scenarios where the scoring function cannot be easily modified. It defines the probability of a graph as inversely proportional to the size of the search space it belongs to, effectively penalizing models that allow for a high maximum number of parents.
- Analytical Counting: By generalizing Robinson’s recurrence formula, the authors mathematically demonstrate how different priors distribute probability across graph complexities.
As shown in the figure above, the uniform prior (Unif) is heavily biased toward graphs where nodes have many parents, whereas the Fair and Edge priors provide a much more balanced or sparsity-favoring distribution.
Key Insights: The "Uniform" Fallacy
A central finding of the study is that uniform is not neutral. Mathematically, a uniform prior over DAGs is biased toward graphs where nodes have approximately $n/2$ parents. In the context of BNs, which are typically expected to be sparse, this is a very strong and often incorrect assumption.
Furthermore, the authors identify a "Utopian Trap." In experiments where a prior was given the exact number of parents for every node in the true graph, it actually performed worse on small datasets than general sparsity priors. This occurs because forcing a model to find a specific number of parents when the data is insufficient leads to the inclusion of spurious edges, which is more damaging to accuracy than being overly conservative.
Experimental Results
The effectiveness of these priors was tested on synthetic benchmarks (e.g., Alarm, Insurance, Water) and real-world datasets from the UCI repository. The primary metric used was the Structural Hamming Distance (SHD), which measures the number of edge insertions, deletions, or reversals required to transform the learned graph into the true graph.
Major Findings:
- Error Reduction: On small-to-medium datasets, sparsity-favoring priors (Fair, Edge, Data, and SSP) consistently achieved lower SHD than the uniform prior. The Fair prior emerged as the most robust and reliable choice across various settings.
- Score Sensitivity: The BDeu score, which is prone to overfitting, benefited significantly from these priors. Conversely, the BIC score is inherently conservative enough that the addition of a sparsity prior had a negligible effect.
- SSP Performance: The Search Space Penalty proved to be a viable and effective alternative to modular priors, outperforming the uniform prior in most scenarios.
Conclusion
The choice of structure prior is a critical but often neglected aspect of Bayesian Network learning. By moving away from the biased uniform prior and adopting sparsity-favoring alternatives like the Fair prior or the Search Space Penalty, researchers can significantly improve the quality of learned models, especially in data-scarce environments. While these priors help identify the correct network skeleton, future work remains to address the deeper challenges of causal orientation and computational scaling for very large networks.
Summary updated