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.
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.
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