Reliable and Efficient Anytime Skeleton Learning

Rui Ding, Yanzhi Liu, Jingjing Tian, Zhouyu Fu, Shi Han, Dongmei Zhang

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.

The REAL algorithm workflow, featuring FD solving and best-first skeleton growth.

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.

Simplification of the FD-induced graph to reduce the search space for skeleton learning.

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

Abstract

Skeleton Learning (SL) is the task for learning an undirected graph from the input data that captures their dependency relations. SL plays a pivotal role in causal learning and has attracted growing attention in the research community lately. Due to the high time complexity, anytime SL has emerged which learns a skeleton incrementally and improves it overtime. In this paper, we first propose and advocate the reliability requirement for anytime SL to be practically useful. Reliability requires the intermediately learned skeleton to have precision and persistency. We also present REAL, a novel Reliable and Efficient Anytime Learning algorithm of skeleton. Specifically, we point out that the commonly existing Functional Dependency (FD) among variables could make the learned skeleton violate faithfulness assumption, thus we propose a theory to resolve such incompatibility. Based on this, REAL conducts SL on a reduced set of variables with guaranteed correctness thus drastically improves efficiency. Furthermore, it employs a novel edge-insertion and best-first strategy in anytime fashion for skeleton growing to achieve high reliability and efficiency. We prove that the skeleton learned by REAL converges to the correct skeleton under standard assumptions. Thorough experiments were conducted on both benchmark and real-world datasets demonstrate that REAL significantly outperforms the other state-of-the-art algorithms.
BibTeX
@inproceedings{ding2020reliable,
  author = {Rui Ding and Yanzhi Liu and Jingjing Tian and Zhouyu Fu and Shi Han and Dongmei Zhang},
  title = {{Reliable and Efficient Anytime Skeleton Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6569},
}
Figure