Discovering the underlying structure of a graphical model—whether it is a Bayesian network, a causal graph, or a Markov random field—is a fundamental challenge in machine learning. The goal is to find an arrangement of edges that best explains the observed data according to a statistical score like the Bayesian Information Criterion (BIC) or the Bayesian Dirichlet equivalent uniform (BDeu) metric.
However, this task is notoriously NP-hard. The number of possible graph structures grows super-exponentially with the number of variables. To make matters worse, structural requirements like acyclicity are global properties: adding a single edge between two nodes can inadvertently create a cycle involving variables on the other side of the network.
Traditionally, researchers relied on greedy heuristics, such as hill-climbing or constraint-based local searches, to navigate this space. While fast, these methods frequently get trapped in local optima, leading to structurally inaccurate models that miss the true data-generating distribution.
To bypass these limitations, a powerful paradigm has emerged: recasting structure learning as an exact discrete optimization problem. By mapping graphs to geometric polytopes and logical constraints, researchers can leverage high-performance mathematical programming solvers to find the globally optimal network architecture with provable mathematical guarantees.
Mapping Graphs to Polytopes
The core insight behind exact structure learning is that the discrete choice of selecting edges or parent sets can be represented as a vector of binary decision variables. This transforms a combinatorial search space into a bounded geometric space known as a polytope.
For instance, let every possible parent set for a given node be represented by a binary indicator variable. If a node selects a specific set of parents, its indicator is set to $1$; otherwise, it is $0$. The total score of the network is simply the linear combination of the scores of these individual choices. As shown by Jaakkola et al., the structure learning problem can then be framed as finding a vertex on this polytope that maximizes the scoring metric, subject to global structural constraints.
By formulating structure learning as an Integer Linear Program (ILP) or Mixed-Integer Linear Program (MILP), the search space can be navigated using exact branch-and-bound algorithms. This mathematical framing provides two massive advantages over heuristics:
- Global Optimality: Solvers are guaranteed to find the mathematically best-scoring graph rather than a "good enough" local neighbor (Chen et al.).
- Anytime Bounds: Even if the solver is stopped early due to time limits, it provides a quantifiable "optimality gap," giving practitioners a strict upper bound on how far the current model is from the theoretical optimum (Peharz et al.; Parviainen et al.).
This exact framework has proven vital for applications where model accuracy is paramount, such as clinical data imputation (Rancoita et al.) and analyzing the sensitivity of scoring metrics to prior hyperparameters (Correia et al.).
Taming Global Constraints
The primary challenge in this paradigm is enforcing global graph properties using linear inequalities. For Directed Acyclic Graphs (DAGs), preventing cycles requires ensuring that no subset of nodes forms a closed loop. A naive formulation requires an exponential number of constraints to eliminate every possible cycle.
To make exact optimization practical, researchers have developed sophisticated constraint-generation techniques. Cussens et al. introduced efficient cutting-plane algorithms that start with a relaxed problem and dynamically add cycle-elimination constraints only when a solver proposes a solution containing a loop. More recently, Rytíř et al. utilized a "lazy constraint" approach within a Mixed-Integer Quadratic Programming (MIQP) framework to scale exact learning to complex dynamic Bayesian networks.
Beyond acyclicity, exact optimization allows practitioners to enforce strict complexity bounds directly within the optimization loop. For a graphical model to be useful for downstream tasks, exact probabilistic inference must be fast. This requires the graph to have a low treewidth (a measure of how close the graph is to being a tree). Parviainen et al. and Mauá et al. developed polynomial-sized MILP formulations that explicitly bound the network's treewidth during the structure learning process itself, ensuring that the discovered optimal models remain computationally tractable.
Beyond Standard DAGs
The flexibility of discrete optimization means it is not restricted to standard Bayesian networks. It can be extended to handle unobserved latent variables, undirected networks, and domain-specific dependency pathways.
Latent Variables and Ancestral Graphs
In real-world causal discovery, researchers rarely measure every relevant variable. Unobserved confounders can introduce spurious correlations. To model these systems, researchers use Maximal Ancestral Graphs (MAGs). Chen et al. formulated the first exact score-based integer programming method for MAGs, introducing "bicluster inequalities" to tightly constrain the search space. To further accelerate this process, Ryšavý et al. developed a compact MIQP branch-and-cut algorithm that dramatically reduces structural error rates compared to traditional constraint-based causal discovery algorithms like the PC algorithm.
Logic-Based Solvers
For undirected graphical models, such as chordal Markov networks or chain graphs, standard linear programming relaxations can sometimes struggle. In these domains, researchers have successfully swapped out ILP solvers for declarative logic frameworks like Maximum Satisfiability (MaxSAT) and Answer Set Programming (ASP). As demonstrated by Corander et al., Berg et al., and Sonntag et al., mapping structural requirements and statistical scores to logical constraints allows high-performance logic solvers to navigate the search space without the massive memory overhead typically associated with dynamic programming.
Specialized Domain Networks
Because constraints are modular, researchers can easily inject domain-specific rules. For instance, in oncology, reconstructing the chronological order of genetic mutations from patient data is critical. Lagergren reduced the problem of learning these oncogenetic progression networks to a bounded subhypergraph optimization problem within an MILP framework, providing a robust, mathematically grounded alternative to custom heuristic search algorithms.
The Frontier: Inverting Graph Neural Networks
Recently, the principles of exact discrete optimization have expanded from learning graphs from data to optimizing graph structures through trained deep learning models. This is particularly prominent in computer-aided molecular design, where the goal is to find a molecular graph that maximizes a specific physical property (such as boiling point or binding affinity) predicted by a Graph Neural Network (GNN).
[ Binary Adjacency Matrix ] ──> [ MIP-Encoded GNN Layers ] ──> [ Global Property Maximization ]
│ │
└─────────── Subject to Physical Valency Constraints ──────────────┘
To achieve this, McDonald et al. and Zhang et al. demonstrated that GNN architectures (like GCN and GraphSAGE) can be embedded directly into mathematical programming frameworks. By reformulating non-linear activation functions (like ReLUs) and aggregation layers as linear "big-M" or bilinear quadratic constraints, the adjacency matrix of the graph becomes a collection of binary decision variables.
This allows a mixed-integer solver to perform "inverse design," searching the space of all possible graphs to find the globally optimal molecule that satisfies both the GNN's learned representations and physical valency laws. To overcome the severe computational bottleneck caused by graph isomorphism symmetries, Campos et al. introduced novel symmetry-breaking constraints into the MIP formulation, yielding massive speedups in solver convergence and solidifying discrete optimization as a cornerstone of exact structural design.
Key Foundational Work
Bayesian network learning with cutting planes (2011) — contributed 2 concept elements to this direction.
Learning Bayesian Network Structure using LP Relaxations (2010) — contributed 1 concept elements to this direction.