Bayesian Network Induction via Local Neighborhoods

Dimitris Margaritis, Sebastian ThrunNeurIPS 1999 · OpenReview

Learning the structure of a Bayesian Network (BN) from data is a notoriously difficult task. Historically, researchers have relied on two primary approaches, each with significant drawbacks. Constraint-based methods look for statistical independencies to build the graph; while theoretically sound, they often suffer from exponential execution times and are highly sensitive to errors in statistical tests. Conversely, score-based (hill-climbing) methods search the space of possible graphs to maximize a score like data likelihood. While fast and popular, they frequently produce overly dense networks that excel at prediction but fail to capture the true causal relationships between variables.

To bridge this gap, Margaritis and Thrun introduce the Grow-Shrink (GS) algorithm, a novel approach that achieves polynomial time complexity while producing compact, causally accurate models by focusing on local network neighborhoods.

The Grow-Shrink (GS) Algorithm

The core innovation of the GS algorithm is its localized approach to structure discovery, which operates in two main stages: identifying the Markov Blanket and then orienting the edges.

1. Identifying the Markov Blanket

For every variable $X$ in the dataset, the algorithm first identifies its Markov Blanket. In a Bayesian Network, a node's Markov Blanket consists of its parents, its children, and its "spouses" (other parents of its children). This specific set of nodes is unique because it completely "shields" $X$ from the rest of the network, rendering it conditionally independent of all other variables.

A node X and its Markov Blanket (shaded nodes), which includes its parents, children, and spouses.

The algorithm finds this blanket through two phases:

  • Growing Phase: Variables are iteratively added to a set $S$ if they demonstrate a statistical dependency with $X$.
  • Shrinking Phase: Because the growing phase might capture variables that are only indirectly related, the algorithm then removes variables from $S$ that are rendered independent of $X$ given the presence of other variables in $S$.

2. Induction and Orientation

Once the local Markov Blankets are known for all variables, the algorithm pieces the global structure together:

  • Identifying Direct Neighbors: It prunes the blanket to isolate only the direct parents and children.
  • Orienting Edges: It uses "V-structures" (patterns like $Y \rightarrow X \leftarrow Z$) to determine the direction of causality.
  • Removing Cycles: Because Bayesian Networks must be Directed Acyclic Graphs (DAGs), the algorithm employs a heuristic to break any cycles that may have formed due to noisy data.

3. The Randomized Variant

To handle very large or dense networks where the exhaustive "Shrinking" phase might still be computationally expensive, the authors also propose a Randomized GS. Instead of exhaustive conditional independence testing, it uses a user-defined number of random tests and Bayesian evidence accumulation to update the probability of an edge existing. This makes the algorithm "anytime" and significantly more robust to noise.

Experimental Validation and Key Results

The authors evaluated their algorithm using synthetic datasets generated from controlled 5x5 rectangular grid networks with varying branching factors. They compared the GS algorithm against standard hill-climbing algorithms using both Data Likelihood and BIC (Bayesian Information Criterion) scores.

Structural Accuracy vs. Predictive Performance

A key insight from the paper is the distinction between a model's predictive power and its structural truth. A model can be excellent at predicting values (achieving low KL-divergence) while being entirely wrong about the underlying causal structure. The GS algorithm prioritizes the most parsimonious (simplest) structure, which is crucial for scientific discovery and causal inference.

Edge errors versus the number of samples, comparing GSBN variants against Hill-Climbing methods.

The results demonstrated that the GS algorithm significantly outperformed hill-climbing in terms of structural accuracy. As seen in the evaluations, hill-climbing methods often produced edge error rates exceeding 100%—meaning they added more false edges than there were true edges in the underlying graph. In contrast, both plain and randomized GS maintained low edge and directionality errors. Despite this strict focus on sparse, causal structure, GS achieved predictive performance (KL-divergence) comparable to the dense networks produced by hill-climbing.

Furthermore, the Randomized GS showed a dramatic speed advantage. While the plain GS execution time grew exponentially as the network became denser, the randomized version remained relatively flat and efficient.

Limitations and Future Directions

While highly effective, the approach has limitations. The problem of removing the minimum number of edges to break cycles is NP-complete; the heuristic used by GS is fast but may not always find the optimal causal fix. Additionally, like most constraint-based methods, the algorithm relies on the "faithfulness assumption"—assuming the data perfectly reflects the underlying graph's independencies—which may not hold in environments with deterministic relationships or hidden variables. Future optimizations could include ordering variables based on mutual information during the "Growing" phase to further speed up blanket identification.

Summary updated

Abstract

In recent years, Bayesian networks have become highly successful tool for di(cid:173) agnosis, analysis, and decision making in real-world domains. We present an efficient algorithm for learning Bayes networks from data. Our approach con(cid:173) structs Bayesian networks by first identifying each node's Markov blankets, then connecting nodes in a maximally consistent way. In contrast to the majority of work, which typically uses hill-climbing approaches that may produce dense and causally incorrect nets, our approach yields much more compact causal networks by heeding independencies in the data. Compact causal networks facilitate fast in(cid:173) ference and are also easier to understand. We prove that under mild assumptions, our approach requires time polynomial in the size of the data and the number of nodes. A randomized variant, also presented here, yields comparable results at much higher speeds.
BibTeX
@inproceedings{margaritis1999bayesian,
  author = {Dimitris Margaritis and Sebastian Thrun},
  title = {{Bayesian Network Induction via Local Neighborhoods}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1999},
  url = {https://openreview.net/forum?id=B1b5Mu-uZr},
}
Figure