Abstract
Skeleton learning (SL) is a critical first step in causal discovery, identifying undirected dependency graphs before determining relationship directions. However, high-dimensional data and the presence of functional dependencies (FDs) often render traditional SL algorithms computationally prohibitive or inaccurate. We introduce REAL (Reliable and Efficient Anytime Learning), an approach designed for time-sensitive industrial applications. By utilizing FDs to prune the search space and adopting a best-first growth strategy, REAL provides high-precision intermediate results that improve over time. Evaluations on large-scale benchmarks and real-world datasets demonstrate that REAL achieves superior precision and efficiency compared to state-of-the-art methods.
Introduction
Causal discovery often begins with identifying which variables in a dataset are directly related, a process known as Skeleton Learning (SL). Despite its importance, SL faces two significant hurdles. First, the computational complexity of learning a skeleton from high-dimensional data is NP-hard. In critical scenarios, such as diagnosing cloud service outages, engineers require "anytime" algorithms that deliver trustworthy results within minutes rather than hours.
Second, standard SL algorithms typically rely on the "faithfulness" assumption, which assumes that statistical independence directly maps to a lack of edges in the graph. However, real-world data frequently contains Functional Dependencies (FDs)—deterministic relationships like a zip code determining a city. These dependencies violate faithfulness, causing traditional algorithms to produce spurious edges or miss genuine relationships.
Methodology: The REAL Framework
The REAL algorithm addresses these challenges through a three-stage process designed for reliability and efficiency.
1. FD Solver and the Harmony Assumption
Instead of treating FDs as noise, REAL leverages them to reduce the problem size. The authors introduce the Harmony assumption, a robust alternative to faithfulness that allows for deterministic relationships. The FD Solver identifies "root variables" and prunes variables that do not require active learning, significantly narrowing the search space.
2. Best-First Skeleton Growing
REAL initializes with an empty graph and adds edges incrementally. It employs a priority queue to determine the order of variable processing, prioritizing evaluations with lower estimated time complexity. This "best-first" approach ensures that the most reliable and "easy" edges are identified first, providing high-quality intermediate results.
3. Robust Local Evaluation and Post-Processing
To handle unstable Conditional Independence (CI) tests in small samples, REAL uses RobustPCFinder, which utilizes a $k^{th}$ percentile correlation metric. Finally, a post-processing stage applies pruning and the "AND-Rule" to ensure edge symmetry and minimize false positives.
Experimental Evaluation
The algorithm was rigorously tested against 19 large-scale networks from the Bayesian Network Repository (e.g., Pathfinder, Munin) and three high-cardinality real-world datasets: School, BirdStrikes, and FlightDelays.
Key Results
- Precision and Stability: REAL consistently outperformed state-of-the-art algorithms like MINOBS and BLIP in precision and $F_{0.5}$ scores. Its intermediate results are both "trustable" (high precision) and "stable" (persistency), meaning edges do not flicker in and out during execution.
- Efficiency: On the Pathfinder dataset, the FD Solver reduced computation time from 208 to 176 seconds while improving accuracy.
- Real-World Impact: In the BirdStrikes dataset, REAL identified 7 out of 14 expert-verified causal neighbors for the "Effect" variable, a significant improvement over competing algorithms which found only one.
Conclusion
REAL demonstrates that Functional Dependencies can be a mathematical asset rather than a hindrance in causal discovery. By moving from "Faithfulness" to "Harmony," the framework provides a theoretical bridge for handling deterministic relationships. While currently focused on categorical data and simple FDs, REAL offers a powerful anytime solution for complex, high-dimensional skeleton learning. Future work will explore extensions to continuous data and more complex dependency structures.
Summary updated