Abstract
Evaluating the performance of structure learning algorithms for Bayesian networks is straightforward when synthetic ground truth is available. However, in real-world applications where the underlying causal structure is unknown, researchers typically rely on predictive metrics like cross-validation. This paper argues that predictive accuracy is a poor proxy for structural accuracy and introduces Intersection-Validation (InterVal). InterVal leverages the consensus between multiple high-performing algorithms on a full dataset to create an "Agreement Graph," which serves as a proxy for ground truth. By measuring how efficiently algorithms converge toward this consensus on subsampled data, InterVal provides a robust framework for structural evaluation in the absence of a gold standard.
Introduction
In the field of graphical models, learning the "skeleton" or dependency structure of a Bayesian network is a fundamental task. When developing new algorithms, researchers must quantify their effectiveness. Currently, this is achieved through two primary methods: synthetic benchmarks and cross-validation. Synthetic benchmarks use known graphs to generate data, allowing for direct comparison using metrics like Structural Hamming Distance (SHD). However, these benchmarks often fail to capture the complexities of real-world data. Conversely, cross-validation (CV) is the standard for real-world data but measures predictive performance—how well a model estimates a probability distribution—rather than the correctness of the learned structure.
The authors identify a critical gap: predictive accuracy does not imply structural accuracy. Structure learning is significantly more challenging than distribution learning and converges at a much slower rate. As shown in Figure 6, while predictive metrics like Cross Entropy (CE) and Cross-Validation (CV) are highly correlated, the correlation between structural metrics (SHD) and predictive metrics (CE) is often low or inconsistent, particularly at smaller sample sizes.
The Intersection-Validation (InterVal) Framework
To bridge this gap, the authors propose Intersection-Validation (InterVal). The framework is built on the premise that if multiple, theoretically consistent algorithms agree on specific structural features when provided with a large dataset, those features are likely reliable targets for learning.
The Agreement Graph
The core of InterVal is the Agreement Graph. As illustrated in Figure 1, the process begins by running $K$ different learning algorithms on the complete dataset. The Agreement Graph ($C \cap C'$) is formed by identifying the edges and non-edges where all algorithms reach a consensus. This intersection serves as a stable, albeit partial, proxy for the ground truth.
The InterVal Process
- Consensus Building: Generate the Agreement Graph using the full dataset.
- Subsampling: Create multiple smaller subsamples of the original data.
- Structural Measurement: Apply the algorithms to these subsamples and calculate the Partial Hamming Distance (PHD)—the distance between the learned structure and the Agreement Graph.
- Algorithm Ranking: Rank algorithms based on their average PHD across subsamples, identifying which ones approach the consensus most efficiently as sample size increases.
Experimental Validation
The authors validated InterVal using three classic Bayesian Network benchmarks where the ground truth is known: Sachs (11 nodes), Insurance (27 nodes), and Alarm (37 nodes). By generating synthetic data from these networks, they could compare InterVal's rankings against the actual SHD to the true graphs.
Key Findings
- Structure is Harder than Distribution: Experiments confirmed that algorithms converge on the probability distribution (measured by Cross Entropy) far more rapidly than they converge on the correct graph structure.
- Consensus as a Proxy: The Agreement Graph proved to be a remarkably reliable proxy. Even when the algorithms had not yet converged to the full truth, the features they agreed upon were typically correct.
- Reliability Thresholds: The method's accuracy is tied to the "coverage" of the Agreement Graph. If the consensus covers more than 90% of possible node pairs, it provides an excellent approximation of real-world structural performance.
Results and Discussion
On the Alarm and Sachs datasets, the algorithm rankings produced by InterVal achieved a Pearson correlation of nearly 1.0 with the rankings derived from the actual ground truth. Even in the Insurance network, where the agreement graph was sparse (sometimes containing as few as five connected node pairs), the method often maintained a strong positive correlation with true structural distance.
However, InterVal does have limitations. It struggles when the agreement graph is too small (covering less than 80% of node pairs) or when the underlying algorithms are highly unstable. Furthermore, like standard cross-validation, InterVal evaluates performance on subsamples and cannot directly assess the quality of the model learned on the entire dataset.
Conclusion
Intersection-Validation offers a much-needed tool for the structural evaluation of Bayesian networks in real-world scenarios. By shifting the focus from predictive distribution to structural consensus, InterVal allows researchers to rank algorithms based on their ability to uncover the underlying skeleton of a network, even when the ground truth remains hidden. Future work will explore extending this framework to other structural metrics and establishing formal mathematical guarantees for its accuracy in finite-sample settings.
Summary updated