In machine learning, "structure learning" is the task of discovering the web of dependencies between variables. Traditionally, this has been treated as a search problem: you start with a random graph and use greedy heuristics—like hill-climbing or Markov Chain Monte Carlo—to tweak edges until the model fits the data.
The problem is that these heuristics are prone to getting stuck in local optima. They find a "good enough" graph, but often miss the mathematically best one. A growing body of research has shifted this paradigm, treating structure learning not as a search, but as a global optimization problem. By translating the rules of graph theory into the language of mathematical programming, researchers can now find the exact, globally optimal structure for a wide range of models.
The Graph as a Polytope
The core intuition behind this approach is to treat the existence of an edge between two variables as a binary decision. If we have $N$ variables, we can define a set of binary variables $x_{ij}$ where $x_{ij} = 1$ if there is a directed edge from $i$ to $j$, and $0$ otherwise.
As Tommi Jaakkola, David Sontag, and their colleagues demonstrated in Learning Bayesian Network Structure using LP Relaxations, this allows us to define a "polytope"—a high-dimensional geometric shape—where every vertex corresponds to a valid graph. Finding the best Bayesian Network then becomes a matter of maximizing a scoring function (like the Bayesian Information Criterion) over this shape using Integer Linear Programming (ILP).
This shift from heuristic search to exact optimization ensures that the resulting model is the best possible representation of the data. Franz Pernkopf showed in Exact Maximum Margin Structure Learning of Bayesian Networks that this investment in exact solvers pays off significantly in classification accuracy compared to greedy methods.
Taming the Exponential Explosion
The primary challenge in structure learning is acyclicity. A Bayesian Network must be a Directed Acyclic Graph (DAG), but the number of possible cycles in a graph grows exponentially with the number of nodes. You cannot simply list every possible cycle as a constraint.
Modern approaches solve this using "lazy constraints" or "branch-and-cut" methods. In ExDAG: an MIQP Algorithm for Learning DAGs, Pavel Rytíř and Jakub Marecek describe a process where the solver initially ignores the acyclicity requirement. If the solver proposes a solution that contains a cycle, the algorithm adds a specific constraint to "cut off" that cycle and tries again. This allows solvers to navigate a massive search space without ever explicitly enumerating all possible invalid graphs.
Similar logic applies to computational tractability. Pekka Parviainen and Denis Mauá have developed ILP formulations that enforce bounded tree-width (Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming). By adding constraints that limit the complexity of the graph's "skeleton," they guarantee that the resulting network will allow for fast probabilistic inference.
Beyond Bayesian Networks
While much of this work focuses on DAGs, the framework is flexible enough to handle more complex causal scenarios. For instance, Rui Chen and Tian Gao extended integer programming to Ancestral Graphs, which can model unobserved "latent" variables that confound our observations (Integer Programming for Causal Structure Learning in the Presence of Latent Variables).
The same principles are being applied to logic-based solvers. Matti Järvisalo and Antti Hyttinen have used Answer Set Programming (ASP) and MaxSAT to learn optimal Chain Graphs and Markov Networks (Learning Optimal Chain Graphs with Answer Set Programming). These declarative methods allow researchers to simply state the properties the graph must have, leaving the solver to find the optimal configuration.
The New Frontier: Inverting Graph Neural Networks
Perhaps the most striking application of this idea is in "inverse design." Instead of using a Graph Neural Network (GNN) to predict the properties of a molecule, researchers are now embedding GNNs inside Mixed-Integer Programs to design new molecules from scratch.
By reformulating GNN layers as linear or bilinear constraints, Juan S. Campos and Shiqiang Zhang have shown it is possible to treat the molecular adjacency matrix as a decision variable (Augmenting optimization-based molecular design with graph neural networks). This allows a solver to find the globally optimal graph structure that maximizes a predicted property—like a drug's effectiveness or a material's boiling point—while strictly adhering to physical laws like chemical valency.
Why It Works
The success of this direction relies on the maturity of modern optimization solvers (like Gurobi or CPLEX). These solvers leverage decades of research into pruning search trees and identifying "symmetry breaking" constraints. By framing structure learning as a mathematical program, researchers are essentially "outsourcing" the hard work of search to the world's most efficient algorithms, turning a "black art" of heuristic tuning into a rigorous, exact science.