A unified approach to estimation and control of the False Discovery Rate in Bayesian network skeleton identification

Angelos P. Armen, Ioannis TsamardinosESANN 2011

Abstract

Learning the structure of Bayesian Networks (BNs) typically begins with identifying the undirected skeleton. While standard approaches focus on controlling the False Positive Rate (FPR), this metric can be misleading in sparse networks where the False Discovery Rate (FDR) is a more critical measure of reliability. This paper introduces a unified framework for both estimating and controlling FDR during skeleton identification. By utilizing a maximal p-value proxy for conditional independence tests, the framework applies the Benjamini-Hochberg procedure for control and Storey’s estimator for post-hoc analysis. Evaluation across six benchmark networks reveals that while the method provides strong control in certain structures, its performance is highly sensitive to network topology and the inherent dependencies between conditional independence tests.

Introduction

In the field of graphical models, identifying the "skeleton" of a Bayesian Network—the set of undirected edges representing direct dependencies—is a foundational task. Traditional constraint-based learning algorithms rely on conditional independence (CI) tests to prune edges. These algorithms typically aim to control the False Positive Rate (FPR), the probability of incorrectly including an edge. However, in the common case of sparse networks, a low FPR can still result in a high False Discovery Rate (FDR), where a significant proportion of discovered edges are spurious. Controlling FDR is often more desirable for researchers who need high confidence in their reported findings.

Methodology

The core challenge in applying FDR control to BN skeleton identification is that standard algorithms do not directly produce p-values for the absence of a link. To address this, the authors propose a unified framework based on two key pillars:

  1. The Maximal P-value Proxy: The p-value for the absence of an edge between two nodes is upper-bounded by the maximum p-value obtained across all CI tests performed for that pair. This proxy allows skeleton identification to be treated as a multiple testing problem.
  2. Control and Estimation: The framework employs the Benjamini-Hochberg (BH) procedure to maintain the FDR below a target threshold $q$. Simultaneously, it uses Storey’s estimator to provide an "any-level" estimate of the FDR for any given p-value threshold $t$, facilitating flexible post-hoc analysis.

Results and Discussion

The framework was tested on 100 samples from six benchmark networks: Alarm, Barley, Hailfinder, Hepar II, Insurance, and Win95pts.

Performance Across Network Structures

The results highlight a significant disparity between FPR and FDR across different network types. As shown in Figure 4, while FPR might appear controlled at low levels for most networks, the corresponding FDR can be alarmingly high. For instance, in the Hailfinder and Barley networks, the FDR remains above 0.3 even at very small p-value thresholds. This underscores the necessity of FDR-specific control mechanisms and demonstrates that FDR is a far more informative error metric for sparse structures.

FPR (a) and FDR (b) across various benchmark networks as a function of the p-value threshold t.

Estimation Bias and Conservatism

A key finding is the "conservatism trap." Because the method relies on an upper bound (the maximal p-value), the resulting FDR estimates are often higher than the actual error rates, leading to a positive bias. However, this conservatism is not universal. Figure 6 illustrates that for networks like Barley, Hailfinder, and Win95pts, the estimator can actually exhibit negative bias at small thresholds, meaning it underestimates the true error. This suggests deeper issues with how CI tests behave in these specific structures.

FDR estimation bias across benchmark networks. Positive values indicate conservative estimates.

Conclusion and Future Directions

While providing a robust theoretical foundation for FDR management in BN learning, the proposed unified approach reveals the complexities introduced by network structure and test dependencies. The violation of independence assumptions in CI tests and the looseness of the maximal p-value bound remain primary hurdles. Future work will focus on refining these bounds and developing methods that account for the inherent dependencies in graphical model structure learning to eliminate current inaccuracies.

Summary updated

BibTeX
@inproceedings{armen2011unified,
  author = {Angelos P. Armen and Ioannis Tsamardinos},
  title = {{A unified approach to estimation and control of the False Discovery Rate in Bayesian network skeleton identification}},
  booktitle = {ESANN},
  year = {2011},
}
Figure