Clique constraints enter exact causal structure learning: no uniform speedup, and gains hinge on graph density and cut management
Synopsis
Exact causal structure learning solves for a globally optimal directed acyclic graph with mixed-integer programming, but its branch-and-cut search is costly. This work adds an upper bound on the maximum clique size of the learned undirected skeleton, using lazy cycle and clique constraints to reject locally over-dense subgraphs at integer candidates. On static linear-Gaussian synthetic graphs, clique constraints do not uniformly accelerate optimization; their benefit depends on graph density, sample size, and cut-management policy, while tighter valid Big-M bounds reduced the fixed-budget optimality gap in most tested settings.
Interpretation
Exact causal structure learning gains a structural prior: the learned undirected skeleton may not contain a clique larger than a set size, where a clique is a set of nodes all pairwise adjacent. Earlier exact score-based methods enforced acyclicity, sparsity, degree restrictions, and prior knowledge through integer or mixed-integer constraints, while the number of admissible structures grows exponentially and solver performance depends on formulation, relaxation strength, and constraint management during search. In a static linear-Gaussian setting, the benchmark uses clique-filtered Erdős–Rényi and scale-free DAGs, with four seeds per graph family and parameter pair, recording structural Hamming distance, F1, relative MIP gap, primal and dual bounds, node throughput, and callback cost.
Clique constraints are added on demand through lazy separation rather than by enumerating all forbidden node subsets in advance. When an integer candidate triggers a MIPSOL callback and its skeleton contains an oversized clique, a lazy inequality is submitted through cbLazy() to reject that candidate; strengthening a fractional relaxation instead requires a valid user cut submitted through cbCut() at MIPNODE. The experiments set the maximum permitted clique size to five and compare two policies: B3 submits only the most-violated minimal clique inequality per callback, while C3 greedily deletes violating edges, refits only the affected regression columns by QR-based least squares, validates the repaired assignment, and submits it through cbSetSolution().
Clique constraints introduce a trade-off rather than a uniform speedup. Large collections of correlated constraints can reduce node throughput; fractional separation did not improve performance in the current implementation, and the sparse non-root variant submitted on average 146.5 and 108.5 user cuts on ER-4-0 and ER-5-0, raising callback time while node throughput dropped substantially. Under a fixed 1,800-second budget, the cycle-only policy had the smallest gap and largest best bound on both ER-4-0 and ER-5-0, while mixed callback orders cut ER-4-0 search nodes from 1,914,601 to 348,106 and 379,203 without improving dual-bound progress.
Perspective
The conclusions are limited to static linear-Gaussian synthetic instances, with clique-filtered Erdős–Rényi and scale-free DAGs, a maximum permitted clique size of five, and a 1,800-second time limit per run; most large instances terminate with a nonzero optimality gap, so fixed-time comparisons concern the best incumbent and bound available at that budget rather than a proven global optimum.
Most runs do not prove optimality within the time limit, so a structural Hamming distance difference at fixed time only indicates a different incumbent quality within that budget and does not imply the constraints reduce the accuracy of the fully optimized model; on binary clique candidates, multiple minimal subsets can tie in violation, so B3 reduces to a deterministic tie-breaking rule and may behave similarly to a first-violated policy; C3's benefit is not consistent across graph families; fractional separation showed no improvement in the current implementation, and the authors propose validating edge-specific bounds, evaluating B3 with fractional-aware scores, and reporting repair acceptance and incumbent-improvement rates for C3.