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:
- 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.
- 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