BETA This research page is an early version. Explanatory text, figure selection, and presentation are still being revised.

AAAI 2022

Learning Bayesian Networks in the Presence of Structural Side Information

Ehsan Mokhtarian · Sina Akbari · Fateme Jamshidi · Jalal Etesami · Negar Kiyavash

Proceedings of the AAAI Conference on Artificial Intelligence · 2022

Paper GitHub AAAI

Keywords.

Bayesian networks causal discovery structural side information constraint-based learning

TL;DR.

We show how structural side information can turn Bayesian-network learning from an exponential-scale problem into a polynomial one in important graph classes. RSL recursively exploits either a known clique-number bound or diamond-free structure, with explicit CI-test complexity guarantees.

Why this matters.

Prior structural knowledge is common in scientific applications but is often used informally. This paper converts simple graph-level knowledge into provable computational savings and better structure-learning performance.

Abstract

We study the problem of learning a Bayesian network (BN) of a set of variables when structural side information about the system is available. It is well known that learning the structure of a general BN is both computationally and statistically challenging. However, often in many applications, side information about the underlying structure can potentially reduce the learning complexity. In this paper, we develop a recursive constraint-based algorithm that efficiently incorporates such knowledge (i.e., side information) into the learning process. In particular, we study two types of structural side information about the underlying BN: (I) an upper bound on its clique number is known, or (II) it is diamond-free. We provide theoretical guarantees for the learning algorithms, including the worst-case number of tests required in each scenario. As a consequence of our work, we show that bounded treewidth BNs can be learned with polynomial complexity. Furthermore, we evaluate the performance and the scalability of our algorithms in both synthetic and real-world structures and show that they outperform the state-of-the-art structure learning algorithms.

Main message. A small amount of structural side information can radically simplify Bayesian-network learning—and our recursive algorithms turn that information into both theory and practical speedups.

The paper at a glance

An informal guide to the problem, the idea, and the main results.

Bayesian networks structural priors graph learning algorithmic efficiency

1. The problem

Learning Bayesian networks is difficult because the graph search space is enormous. In many scientific settings, however, we do know something about the structure in advance, and standard algorithms often underuse that information.

2. The key idea

We encode structural side information directly into the learning procedure. That can eliminate large parts of the search space and sharpen what the algorithm needs to consider.

3. Recursive learning with side information

Theory + algorithm

We develop Recursive Structure Learning (RSL) algorithms for two forms of side information: a known upper bound on the clique number and diamond-free structure. For each case, we derive worst-case bounds on the number of required CI tests.

4. Polynomial learning for important graph classes

Theory

As a consequence of the clique-number result, bounded-treewidth Bayesian networks can be learned with polynomial CI-test complexity. The analysis shows explicitly how structural information changes the computational scaling of constraint-based learning.

5. How it works

Formalize the available structural side information.
Use it to constrain the space of candidate graphs.
Adapt the network-learning algorithm to the constrained search space.
Return a learned graph more efficiently than unconstrained search would allow.

What the experiments show

Main empirical message.

Across synthetic and real-world Bayesian-network structures, the RSL algorithms outperform state-of-the-art structure-learning baselines in scalability and structural accuracy. Notably, RSLD remains highly competitive even on graphs that are not exactly diamond-free, showing that the recursive strategy can be useful beyond the idealized structural class.

Where this helps

Good fit

You have prior structural knowledge and do not want to ignore it.
Bayesian-network learning is computationally demanding in your application.
You want a principled way to trade background knowledge for efficiency.

Keep in mind

The two RSL variants exploit different kinds of graph knowledge, giving a practical choice depending on what structural information is available.
The bounded-treewidth consequence links the method to a widely studied graph class while retaining polynomial complexity.

Cite this paper

@inproceedings{mokhtarian2022learning,
  title     = {Learning Bayesian Networks in the Presence of Structural Side Information},
  author    = {Ehsan Mokhtarian and Sina Akbari and Fateme Jamshidi and Jalal Etesami and Negar Kiyavash},
  booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence},
  volume    = {36},
  number    = {7},
  pages     = {7814--7822},
  year      = {2022},
  doi       = {10.1609/aaai.v36i7.20750},
  url       = {https://ojs.aaai.org/index.php/AAAI/article/view/20750}
}