# Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings

arXiv: https://arxiv.org/abs/2204.02902 · HTML: https://mlsanity.com/paper/2204.02902/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 25 references that are in the map.
- First posted on arXiv 6 Apr 2022.

## Builds on (most cited first, 3 of 3)

- [Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis](https://mlsanity.com/paper/2004.14724/) (2020)
- [Parameterized Complexity Results for Exact Bayesian Network Structure Learning](https://mlsanity.com/paper/1402.0558/) (2014)
- [Advances in Bayesian Network Learning using Integer Programming](https://mlsanity.com/paper/1309.6825/) (2013)

## Built on by (most cited first, 3 of 3)

- [Machine learning interatomic potential can infer electrical response](https://mlsanity.com/paper/2504.05169/) (2025)
- [Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy](https://mlsanity.com/paper/2511.08091/) (2025)
- [Exact and Approximate Algorithms for Polytree Learning](https://mlsanity.com/paper/2605.03622/) (2026)

## Abstract (arXiv)

In Bayesian Network Structure Learning (BNSL), one is given a variable set and parent scores for each variable and aims to compute a DAG, called Bayesian network, that maximizes the sum of parent scores, possibly under some structural constraints. Even very restricted special cases of BNSL are computationally hard, and, thus, in practice heuristics such as local search are used. A natural approach for a local search algorithm is a hill climbing strategy, where one replaces a given BNSL solution by a better solution within some pre-defined neighborhood as long as this is possible. We study ordering-based local search, where a solution is described via a topological ordering of the variables. We show that given such a topological ordering, one can compute an optimal DAG whose ordering is within inversion distance r in subexponential FPT time; the parameter r allows to balance between solution quality and running time of the local search algorithm. This running time bound can be achieved for BNSL without structural constraints and for all structural constraints that can be expressed via a sum of weights that are associated with each parent set. We also introduce a related distance called `window inversions distance' and show that the corresponding local search problem can also be solved in subexponential FPT time for the parameter r. For two further natural modification operations on the variable orderings, we show that algorithms with an FPT time for r are unlikely. We also outline the limits of ordering-based local search by showing that it cannot be used for common structural constraints on the moralized graph of the network.