Bayesian network learning with cutting planes

By James Cussens. 2011

270 citations recorded by the source corpus.

The problem of learning the structure of Bayesian networks from complete discrete data with a limit on parent set size is considered. Learning is cast explicitly as an optimisation problem where the goal is to find a BN structure which maximises log marginal likelihood (BDe score). Integer programming, specifically the SCIP framework, is used to solve this optimisation problem. Acyclicity constraints are added to the integer program (IP) during solving in the form of cutting planes. Finding good cutting planes is the key to the success of the approach—the search for such cutting planes is effected using a sub-IP. Results show that this is a particularly fast method for exact BN learning.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

Citations in the corpus

Gradient-Based Neural DAG Learning (2019, methodology): “There exists certain score-based approaches which uses integer linear programming (ILP) (Jaakkola et al., 2010; Cussens, 2011) which internally solve continuous linear relaxations.”
DAGs with NO TEARS: Continuous Optimization for Structure Learning (2018, methodology): “Notwithstanding, there are algorithms for solving (4) to global optimality for small problems (Ott and Miyano, 2003; Singh and Moore, 2005; Silander and Myllymaki, 2006; Xiang and Kim, 2013; Cussens, 2012; Cussens et al., 2017).”
DAG-GNN: DAG Structure Learning with Graph Neural Networks (2019, methodology): “Many exact and approximate algorithms for learning DAG from data have been developed, including score-based and constraint-based approaches (Spirtes et al., 2000a; Chicker-ing, 2002; Koivisto & Sood, 2004; Silander & Myllymaki, 2006; Jaakkola et al., 2010; Cussens, 2011; Yuan & Malone, 2013).”
Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings (2020, background): “Other related works include structure inference in probabilistic graphical models [9, 62, 59], and graph generation [36, 47], which have a different goal from ours.”
Learning Sparse Causal Models is not NP-hard (2013, methodology): “…eﬃcient approximations to minimal Bayesian networks through greedy search (Chickering, 2002), or methods that employ specialized heuristics or solver techniques to make exact learning feasible from 30, up to even 60 variables if the graph is suﬃciently sparse (Yuan and Malone, 2012; Cussens, 2011).”
On Structure Priors for Learning Bayesian Networks (2019, methodology): “We choose eight data sets that are large enough for applying the InterVal method (at least 1000 data points), but still permit learning a globally optimal DAG with GOBNILP when assuming an maximum indegree of three (Splice, Mushroom, Krvs-Kp, Optdigits) or four (remaining data sets).”
A survey of Bayesian Network structure learning (2021, unknown): “The GOBNILP algorithm (Cussens, 2011) represents the problem by binary integer variables, called family variables denoted 𝐼(𝑷𝒂(𝑋) → 𝑋) , each family variable representing a possible parent set 𝑷𝒂(𝑋) for node 𝑋 where 𝑷𝒂(𝑋) ⊆ 𝑿\{𝑋} .”
BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery (2021, methodology): “Also included are two methods designed speciﬁcally for Gaussian DAGs, the greedy directed acyclic graph search with equal error variance (GDSEEV) method [38], and the main method (‘Ghoshal’) from [21].”
Optimization Models for Machine Learning: A Survey (2019, methodology): “Mixed-integer programming formulations of the Bayesian network structure learning have been proposed [13] and solved by using relaxations [124], cutting planes [15, 51, 77], and heuristics [100, 216].”
Towards Scalable Bayesian Learning of Causal DAGs (2020, background): “tti, Guido Consonni, Marco L. Della Vedova, and Stefano Peluso. Learning Markov equivalence classes of directed acyclic graphs: An objective Bayes approach. Bayesian Analysis , 13(4):12351260, 2018. [3] David Chickering. Optimal structure identication with greedy search. Journal of Machine Learning ”
Efficient Sampling and Structure Learning of Bayesian Networks (2018, methodology): “Interesting directions may also come from the ILP method of Cussens (2011) and Cussens et al. (2017), if the solver manages to complete and the number of parents in the maximally scoring DAG is less than the low limit needed for their input score tables.”
Bayesian Networks for Variable Groups (2015, background): “Although the problem is NP-hard (Chickering, 1996), there exist plenty of exact algorithms (Cussens, 2011; Jaakkola et al., 2010; Silander and Myllymäki, 2006) as well as theoretically sound heuristics (Chickering, 2002; Aliferis et al.”