Structure Learning for Bayesian Networks over Labeled DAGs

Antti Hyttinen, Johan Pensar, Juha Kontinen, Jukka CoranderPGM 2018 · OpenReview

Abstract

Graphical models based on labeled directed acyclic graphs (LDAGs) allow for representing context-specific independence relations in addition to regular conditional independencies. Modeling such context-specific independence (CSI) is crucial for accurate causal discovery and predictive modeling. This paper presents the first principled methods for learning the structure of LDAGs, including a constraint-based algorithm and an exact score-based approach.

Introduction: The Challenge of Context-Specific Independence

Standard Bayesian Networks (BNs) are powerful tools for representing conditional independence. For instance, a BN might encode that variable $X$ is independent of $Y$ given $Z$. However, real-world systems often exhibit Context-Specific Independence (CSI), where independence only holds for specific values of a parent variable. For example, $X$ might be independent of $Y$ when $Z=0$, but dependent when $Z=1$.

Labeled Directed Acyclic Graphs (LDAGs) extend standard BNs by adding labels to edges. These labels specify the contexts (values of parent variables) in which an edge "disappears," representing a CSI relation. While more expressive, LDAGs are significantly harder to learn due to a search space that is an order of magnitude larger than that of standard BNs.

Overview of LDAG structures and their corresponding Conditional Probability Table (CPT) partitions.

Methodology

The authors propose two novel algorithms to address the LDAG learning problem:

1. LPC Algorithm (Constraint-based)

The LPC algorithm adapts the classic PC algorithm to the LDAG framework. It begins with a skeleton search that identifies underlying connections by testing independencies within specific contexts. A key contribution is the derivation of new orientation rules (R0-R4). These rules leverage CSI to orient "causal" edges that would otherwise be indistinguishable in a standard BN due to Markov equivalence. The algorithm operates under a new "LDAG-faithfulness" assumption.

2. Exact Score-based Learning

This approach uses the Bayesian Information Criterion (BIC) to score candidate LDAGs.

  • Local Score Calculation: Finding the optimal labels for an edge involves partitioning the rows of a Conditional Probability Table (CPT). The authors employ a branch-and-bound search to find the optimal partition efficiently.
  • Global Search: The local scores are integrated into a global search using Gobnilp, an integer linear programming solver, to find the globally optimal DAG structure.
  • Strong Regularity: To mitigate overfitting—a common issue given the flexibility of LDAGs—the authors introduce "strong score pruning" and mixed BIC penalties.

Key Insights: Breaking Markov Equivalence

One of the most significant advantages of LDAGs is their ability to "break" Markov equivalence. In standard BNs, many different graph structures represent the same set of conditional independencies and cannot be distinguished from data alone. By observing context-specific independence, researchers can identify unique causal directions that were previously hidden.

An LDAG showing a labeled edge (Y to X with label Q=0), illustrating how context-specific labels can represent complex dependencies.

Experimental Results

The methods were evaluated on both simulated and real-world datasets:

  • Simulated LDAGs: In 10-node binary LDAG simulations with 50% label probability, the LPC algorithm correctly oriented 71% of edges with zero reversals. Standard PC algorithms performed significantly worse, with higher reversal rates and lower accuracy.
  • Predictive Accuracy: Exact LDAG models showed superior performance when data was scarce (e.g., 100 samples), achieving lower KL-divergence to the true distribution compared to standard BNs.
  • The Alarm Network: The score-based method successfully scaled to the 37-node Alarm benchmark, calculating 2.5 million local scores in approximately 7 hours. This demonstrates the feasibility of exact LDAG learning for moderately sized networks.

Conclusion and Future Work

This research provides a principled foundation for learning LDAGs, offering tools that outperform standard BNs in both structure discovery and predictive modeling. Future work includes scaling these methods to larger graphs through heuristic searches and extending the framework to handle latent variables.

Summary updated

Abstract

Graphical models based on labeled directed acyclic graphs (LDAGs) allow for representing context-specific independence relations in addition to regular conditional independencies. Modeling such con...
BibTeX
@inproceedings{hyttinen2018structure,
  author = {Antti Hyttinen and Johan Pensar and Juha Kontinen and Jukka Corander},
  title = {{Structure Learning for Bayesian Networks over Labeled DAGs}},
  booktitle = {PGM},
  year = {2018},
  url = {https://openreview.net/forum?id=sUO_WOihMDq},
}
Figure