cs.LGNov 9, 2026

Clique Constraints for Exact Causal Structure Learning

Authors: Xiaoyu He, Pavel Rytíř, Petr Ryšavý, Jakub Mareček

Organizations: AI Center, Czech Technical University in Prague, Karlovo namesti 13, Prague 12135

Abstract

Exact score-based causal structure learning supports explicit structural constraints and optimisation certificates, but its branch-and-cut search can be computationally demanding. We augment exact causal structure learning methods with an upper bound on the maximum clique size of the learned undirected skeleton, enforced at integer candidates through lazy cycle and clique constraints. On static linear-Gaussian Erdős-Rényi and scale-free DAGs, we evaluate callback order, alternative clique-cut policies, incumbent repair, fractional separation, and Big-M bounds. We report causal-recovery metrics jointly with optimality gaps, primal and dual bounds, node throughput, MIPSOL events, and callback cost. Two variants receive particular attention: B3 selects the most violated minimal (k+1)-clique inequality at each callback, whereas C3 repairs an infeasible integer candidate by deleting violating edges and refitting affected regression columns using QR-based least squares. The results do not indicate that clique constraints uniformly accelerate optimisation. However, their benefit depends on graph density, sample size, and cut-management policy, while large collections of correlated constraints can reduce node throughput. Tighter valid Big-M bounds reduced the fixed-budget optimality gap in most tested settings, without necessarily changing SHD or F1 at a fixed time limit. These findings characterize the computational trade-offs of clique-constrained exact causal learning, and identify selective separation and incumbent repair as promising directions.

Figures & tables

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions

    Sep 26, 2026Haijie Xu, Chen ZhangCausal DiscoveryStructural Causal Models

  2. Relaxed Sparsest-Permutation Formulation for Causal Discovery at Scale

    May 7, 2026Sunmin Oh, Sang-Yun Oh, Gunwoong ParkStructural Causal ModelsCausal Discovery

  3. The Statistical Cost of Causal Discovery with Feedback

    Sep 28, 2026Sunmin Oh, Seungsu Han, Gunwoong ParkSample ComplexityCausal Discovery