Exact Graph Learning via Integer Programming

Lucas Kook, Søren Wengel Mogensen

In the world of data science, we often want to know more than just how variables correlate; we want to know how they cause one another. This task, known as causal discovery or graph learning, is notoriously difficult. Most algorithms either take shortcuts (greedy searches) that might miss the best solution or make rigid assumptions about the data (like assuming everything is Gaussian).

A new paper by Lucas Kook and Søren Wengel Mogensen, titled "Exact Graph Learning via Integer Programming," introduces a framework called GLIP that breaks these trade-offs. It offers a way to find the globally optimal graph structure without being tied to specific distributions.

TL;DR

GLIP is a nonparametric framework that treats graph learning as a mathematical optimization problem. By using a novel "minimal-length encoding," it can find globally optimal causal structures (DAGs, mixed graphs, and chain graphs) significantly faster and for larger systems than previous exact methods.

What Problem Does This Paper Address?

Inferring the dependence structure of a complex system is usually done in one of two ways:

  1. Constraint-based methods: These use statistical tests to find independencies (e.g., "Is smoking independent of cancer given genetics?") and piece the graph together. They are flexible but can be led astray by a single incorrect test result.
  2. Score-based methods: These assign a "score" to every possible graph and try to find the one with the best fit. Because the number of possible graphs grows exponentially with the number of variables, most of these methods use "greedy" heuristics that aren't guaranteed to find the absolute best graph.

Previous "exact" methods—which guarantee finding the highest-scoring graph—relied on a technique called Answer Set Programming (ASP). However, these were computationally "heavy" because they tried to track every possible path between nodes, causing them to stall on graphs with more than six variables.

Methods

The authors propose Graph Learning via Integer Programming (GLIP). Here’s how it works:

  • Integer Programming (IP) Formulation: They translate the rules of graphical separation (like d-separation) into a set of linear constraints. The goal is to minimize the total "disagreement" between the graph's structure and the results of conditional independence tests.
  • Minimal-Length Encoding: This is the paper's core innovation. Instead of creating variables for every possible path between nodes (which is factorially large), they only track the shortest connecting path. If a shortest path exists, the nodes are connected; if not, they are separated. This reduces the number of variables to a manageable size, allowing the solver to handle larger graphs.
  • Nonparametric Flexibility: GLIP doesn't care if your data is linear, Gaussian, or highly non-linear. It simply takes p-values from any conditional independence test as input.
  • Broad Support: Unlike many tools that only handle Directed Acyclic Graphs (DAGs), GLIP supports Acyclic Directed Mixed Graphs (ADMGs)—which account for unobserved "latent" variables—and Chain Graphs.

Datasets

The authors evaluated GLIP using:

  • Simulated Data: Randomly generated Erdős-Rényi graphs and linear additive noise models to test accuracy against a known "ground truth."
  • Synthetic Benchmarks: Classic datasets from the causal discovery literature, including ALARM (37 nodes), ASIA (8 nodes), CHILD (20 nodes), HEPAR2 (70 nodes), and SACHS (11 nodes). For larger benchmarks, they used subsets of nodes to test the algorithm's performance.

Key Insights and Ideas

  • The "Aha!" Moment on Paths: You don't need to prove that every path is blocked to show two variables are independent; you just need to show that no shortest path exists. This shift from "all paths" to "minimal length" is what unlocks the scalability.
  • Global Error Correction: One of the most interesting findings is that GLIP can actually "fix" errors made by individual statistical tests. Because it looks for the globally optimal graph, it can overrule a single noisy p-value if that p-value is inconsistent with the rest of the graph's structure.
  • Warmstarting: The authors found that starting the IP solver with a graph generated by a fast, approximate algorithm (like the PC algorithm) significantly speeds up the search for the global optimum.

Key Results

  • Speedup: GLIP is often three orders of magnitude faster than previous exact ASP-based methods.
  • Scalability: While previous exact methods struggled beyond 6 nodes, GLIP can solve for the Markov equivalence class of graphs with up to 9 nodes and "weak" equivalence classes (using smaller conditioning sets) for up to 14 nodes within a 10-minute window.
  • State-of-the-Art Accuracy: On benchmark datasets like ALARM and CHILD, GLIP consistently matched or outperformed popular approximate methods like FCI and NOTEARS in terms of Structural Hamming Distance (SHD).

Limitations and Future Work

Despite the improvements, the "curse of dimensionality" still looms. GLIP is an exact method, and for very large systems (e.g., 50+ nodes), the search space remains too vast for current IP solvers to guarantee optimality in a reasonable timeframe.

The authors suggest several paths forward:

  • Heuristic IP: Using the IP framework as a high-quality heuristic for very large graphs when an exact solution is out of reach.
  • New Separation Criteria: Extending the minimal-length encoding to other types of graphical separation, such as $\sigma$-separation or $\delta$-separation.
  • Improved Solvers: Leveraging more advanced features of modern IP solvers (like Gurobi) to further push the node limit.

For researchers looking to try this out, the authors have released the glip package for R, making these advanced causal discovery tools accessible to the broader scientific community.

Summary updated

Abstract

Learning the dependence structure among variables in complex systems is a central problem across medical, natural, and social sciences. These structures can be naturally represented by graphs, and the task of inferring such graphs from data is known as graph learning or as causal discovery if the graphs are given a causal interpretation. Existing approaches typically rely on restrictive assumptions about the data-generating process, employ greedy oracle algorithms, or solve approximate formulations of the graph learning problem. As a result, they are either sensitive to violations of central assumptions or fail to guarantee globally optimal solutions. We address these limitations by introducing a nonparametric graph learning framework based on nonparametric conditional independence testing and integer programming. We reformulate the graph learning problem as an integer-programming problem and prove that solving the integer-programming problem provides a globally optimal solution to the original graph learning problem. Our method leverages efficient encodings of graphical separation criteria, enabling the exact recovery of larger graphs than was previously feasible. We provide an implementation in the openly available R package 'glip' which supports learning (acyclic) directed (mixed) graphs and chain graphs. From the resulting output one can compute representations of the corresponding Markov equivalence classes or weak equivalence classes. Empirically, we demonstrate that our approach is faster than other existing exact graph learning procedures for a large fraction of instances and graphs of various sizes. GLIP also achieves state-of-the-art performance on simulated data and benchmark datasets across all aforementioned classes of graphs.
BibTeX
@inproceedings{kook2026exact,
  author = {Lucas Kook and Søren Wengel Mogensen},
  title = {{Exact Graph Learning via Integer Programming}},
  booktitle = {WU},
  year = {2026},
  doi = {10.48550/arxiv.2601.20589},
}
Figure