Exact Graph Learning via Integer Programming

1. Problem Statement

The paper addresses the fundamental problem of graph learning (also known as causal discovery), which involves inferring the dependence structure among variables in a complex system from observational data.

• Goal: To learn a graphical representation (e.g., Directed Acyclic Graphs (DAGs), Acyclic Directed Mixed Graphs (ADMGs), or Chain Graphs) that encodes the conditional independence relationships of the underlying data-generating process.
• Limitations of Existing Methods:
  • Constraint-based methods (e.g., PC, FCI): Rely on sequential conditional independence (CI) tests. They are sensitive to errors in finite-sample testing (e.g., false negatives leading to incorrect edge removal) and do not guarantee a globally optimal solution.
  • Score-based methods (e.g., GES, NOTEARS): Often rely on restrictive parametric assumptions (e.g., linearity, Gaussianity) or use greedy search heuristics that fail to guarantee global optimality.
  • Existing Exact Methods: Previous exact approaches using Answer Set Programming (ASP) or SAT solvers often scale poorly, typically becoming intractable for graphs with more than 6 nodes due to the factorial growth of variables required to encode all possible paths.

2. Methodology: GLIP (Graph Learning via Integer Programming)

The authors propose GLIP, a nonparametric, exact framework that formulates graph learning as a Mixed-Integer Linear Programming (MILP) problem.

Core Innovation: Minimal-Length Encoding

The central technical contribution is a novel encoding of graphical separation criteria (e.g., $d$-separation, $m$-separation, $c$-separation) that avoids enumerating all possible paths.

• Previous Approach: Encoded every possible path in the graph as a variable, leading to $O(d!)$ variables (where $d$ is the number of nodes).
• GLIP Approach: Instead of tracking individual paths, GLIP tracks the length of the shortest connecting walk between nodes given a conditioning set.
  • It introduces integer variables $l^C_{\{i,j\}}$ representing the length of the shortest path between $i$ and $j$ given $C$.
  • It uses a set of linear constraints to relate these lengths to the edge variables (presence/absence of edges).
  • Complexity: The number of variables grows linearly with the number of input p-values (or triples $(i, j, C)$), rather than factorially. This makes the problem tractable for significantly larger graphs.

The Optimization Problem

The graph learning problem is cast as:
$$\min_{G \in \mathcal{G}_d} \sum_{i,j,C} w_{ijC} | \mathbb{1}_{\text{sep}}(i,j|C, G) - f(p_{ijC}) |$$
Where:

• $\mathcal{G}_d$ is the space of valid graphs (DAGs, ADMGs, etc.).
• $p_{ijC}$ are p-values from conditional independence tests.
• $f(p_{ijC})$ is a thresholded indicator (1 if independent, 0 otherwise).
• The objective minimizes the weighted disagreement between the graph's implied separations and the observed test results.

Supported Graph Classes

GLIP is versatile and supports:

1. Directed Acyclic Graphs (DAGs) and Directed Graphs (DGs) (allowing cycles).
2. Acyclic Directed Mixed Graphs (ADMGs) and Directed Mixed Graphs (DMGs) (handling latent confounders).
3. Chain Graphs (CGs) (handling both causal and associative relationships).
4. Weak Equivalence: It can learn $k$-weak equivalence classes by restricting the size of conditioning sets, reducing computational cost.

3. Key Contributions

1. Exact Nonparametric Learning: GLIP guarantees a globally optimal solution to the graph learning problem without assuming a specific data distribution (e.g., Gaussian) or functional form, relying solely on CI tests.
2. Scalability via Minimal-Length Encoding: By reformulating the constraints to track shortest path lengths rather than all paths, the authors overcome the scalability barrier of previous exact methods (like Eberhardt et al., 2025), enabling exact learning for graphs with up to 14 nodes (in weak learning settings).
3. Theoretical Guarantees: The paper provides rigorous proofs (Theorems 2, 3, 5) demonstrating that the proposed integer programming formulation correctly encodes the graphical separation criteria and that the solution corresponds to a global minimum of the objective function.
4. Open-Source Implementation: The authors released the glip R package, which integrates with the gurobi solver, allowing researchers to apply these methods to real-world data.

4. Empirical Results

The authors evaluated GLIP against state-of-the-art exact (ASP) and approximate (PC, FCI, NOTEARS, R2SORT) methods using simulated and benchmark datasets.

• Runtime Efficiency:
  • Compared to ASP, GLIP is often 10x faster for small graphs ($d < 6$).
  • For larger graphs ($d \ge 6$), GLIP solves a significant fraction of instances within a 600-second time limit where ASP fails or hits the walltime.
  • In weak learning scenarios (limiting conditioning set size), GLIP handles graphs up to 14 nodes, whereas ASP struggles beyond 9 nodes.
• Accuracy:
  • GLIP consistently achieves state-of-the-art performance in Structural Hamming Distance (SHD) and separation distance (SEP) across DAG and ADMG learning tasks.
  • It outperforms greedy constraint-based methods (PC/FCI) in scenarios with high multicollinearity or near-faithfulness violations, where greedy edge removal fails.
  • On benchmark datasets (ALARM, ASIA, CHILD, HEPAR2, SACHS), GLIP often yields lower SHD and better F1-scores than competitors.
• Warm-starting: The authors demonstrate that using a fast approximate method (like PC) to "warm-start" GLIP significantly improves performance, allowing the solver to refine an initial solution within a limited time budget.

5. Significance

This paper represents a major advancement in causal discovery and graph learning:

• Bridging the Gap: It successfully bridges the gap between the theoretical optimality of exact methods and the practical scalability required for real-world applications.
• Robustness: By optimizing globally over the space of graphs rather than greedily removing edges, GLIP is more robust to the noise and errors inherent in finite-sample conditional independence testing.
• Flexibility: The modular nature of the integer programming formulation allows for the easy incorporation of domain knowledge (e.g., "node $v$ must be a sink") and different loss functions.
• Future Direction: The minimal-length encoding technique provides a general framework that can be extended to other graphical models and separation criteria (e.g., $\delta$-separation, $\mu$-separation), potentially unlocking exact learning for even more complex causal structures.

In summary, Kook and Mogensen provide a powerful, theoretically grounded, and practically efficient tool for exact graph learning, overcoming the computational bottlenecks that have previously limited the application of exact methods to small-scale problems.