The Complexity of Bayesian Network Learning: Revisiting the Superstructure

Robert Ganian, Viktoriia Korchemna

Overview

Bayesian Network Structure Learning (BNSL) is a notoriously difficult computational problem that remains "hard" even when the network's potential structure appears simple. This paper identifies new "islands of tractability" by shifting focus from vertex-based graph parameters to edge-based ones (such as the feedback edge set). Furthermore, the authors demonstrate that changing how scores are represented can dramatically lower the complexity barrier, offering new theoretical pathways for efficient learning.

The Challenge of BNSL and the "Superstructure"

The primary goal of BNSL is to find a Directed Acyclic Graph (DAG) that best represents the conditional dependencies between a set of random variables, typically by maximizing a specific "score" function.

While BNSL is a cornerstone of probabilistic modeling, it is NP-hard. To find practical solutions, researchers look for "tractable fragments"—specific versions of the problem that become efficient if certain parameters of the input are small. This approach falls under the umbrella of parameterized complexity. Specifically, researchers often analyze the superstructure: a graph containing all potential edges between variables.

Previous theoretical work was largely discouraging: BNSL was shown to be "W[1]-hard" (meaning it is highly unlikely to be efficient) even when the superstructure had a very simple backbone, such as a low treewidth or a small vertex cover. The authors of this paper set out to determine if any structural properties of the superstructure actually make the problem easy to solve.

Redrawing the Complexity Landscape

Most common graph parameters (like treewidth or vertex cover) are based on removing vertices to simplify a graph. A core insight of this paper is that for BNSL, edge-based parameters are the real key to tractability.

Complexity landscape of BNSL with respect to various graph parameters.

While BNSL is hard for treewidth, it becomes easy—specifically, Fixed-Parameter Tractable (FPT)—when parameterized by the number of edges you need to remove to make the graph a tree (the feedback edge set).

To prove these boundaries, the authors employed several sophisticated tools from theoretical computer science:

  • Parameterized Complexity Analysis: Categorizing versions of BNSL based on whether the "exponential explosion" of the problem is confined entirely to a specific parameter $k$, rather than the total number of variables $n$.
  • Kernelization: For the "feedback edge number" parameter, they developed data reduction rules that can shrink a massive problem instance down to a "kernel" of size $16k$ in polynomial time.
  • Dynamic Programming (DP): Designing leaf-to-root DP algorithms that traverse a "tree decomposition" of the graph to find optimal structures.
  • Matroid Theory: Using weighted matroid intersection algorithms to prove certain cases of "Polytree Learning" are solvable in polynomial time.

Key Insights and Results

The Power of Locality

The authors introduce a new parameter: the Local Feedback Edge Number (lfen). Instead of looking at the total number of "extra" edges in the whole graph, lfen looks at how many extra edges "interfere" with any specific vertex. They successfully prove that BNSL is FPT for this more relaxed, localized parameter.

Representation Matters

Most theoretical work assumes a "non-zero representation" (where you list every possible parent set and its score). The authors show that if you use an additive representation (where the score of a parent set is just the sum of scores of individual parents), the problem becomes significantly easier. Under an additive representation, BNSL becomes FPT even for treewidth.

Hardness Boundaries and Polytrees

To draw a precise line between what makes the problem easy versus hard, the authors showed that BNSL remains W[1]-hard for treecut width, an edge-cut counterpart to treewidth.

Additionally, they discovered that while BNSL with additive scores is FPT for treewidth, the simpler task of Polytree Learning with additive scores is actually solvable in polynomial time (using matroid intersection). This matches the intuitive expectation that simpler networks should be easier to learn.

Limitations and Future Work

This is a purely theoretical complexity study; the results are proven mathematically rather than tested on empirical benchmarks.

  • Explicit vs. Oracle Scores: The results assume that the score functions are provided explicitly in the input. Future work should explore how the complexity changes if scores are provided by a "black box" oracle.
  • Theoretical vs. Practical: While the data reduction rules are mathematically "safe," they have not yet been implemented to see how much they speed up real-world BNSL heuristics.
  • Broadening lfen: The authors suggest that their newly introduced local feedback edge number parameter might be a valuable tool for solving other hard graph problems beyond Bayesian networks.

Summary updated

Abstract

We investigate the parameterized complexity of Bayesian Network Structure Learning (BNSL), a classical problem that has received significant attention in empirical but also purely theoretical studies. We follow up on previous works that have analyzed the complexity of BNSL w.r.t. the so-called superstructure of the input. While known results imply that BNSL is unlikely to be fixed-parameter tractable even when parameterized by the size of a vertex cover in the superstructure, here we show that a different kind of parameterization - notably by the size of a feedback edge set - yields fixed-parameter tractability. We proceed by showing that this result can be strengthened to a localized version of the feedback edge set, and provide corresponding lower bounds that complement previous results to provide a complexity classification of BNSL w.r.t. virtually all well-studied graph parameters. We then analyze how the complexity of BNSL depends on the representation of the input. In particular, while the bulk of past theoretical work on the topic assumed the use of the so-called non-zero representation, here we prove that if an additive representation can be used instead then BNSL becomes fixed-parameter tractable even under significantly milder restrictions to the superstructure, notably when parameterized by the treewidth alone. Last but not least, we show how our results can be extended to the closely related problem of Polytree Learning.
BibTeX
@inproceedings{ganian2021complexity,
  author = {Robert Ganian and Viktoriia Korchemna},
  title = {{The Complexity of Bayesian Network Learning: Revisiting the Superstructure}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=vY2HsMWG2b_},
}

Loading related content...

Figure