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

Sep 26, 2026

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

We study fully online fixed-confidence causal discovery without any historical observational data. Starting from zero samples, the learner sequentially selects interventions to recover both the causal DAG and its edge weights under a linear-Gaussian structural equation model. We establish an instance-dependent lower bound for any (ε,δ)(ε,δ)-correct algorithm and propose FOCUS, which adaptively allocates interventions through an online max--min game. A key contribution is a computable concentration inequality for the accumulated KL divergence involving causal parameters shared across interventions. We prove that FOCUS is (ε,δ)(ε,δ)-correct and that its expected stopping time matches the lower bound in its Θ(log⁡(1/δ))Θ(\log(1/δ)) dependence up to an instance-dependent constant. Experiments demonstrate improved structure and edge-weight recovery and confirm the predicted stopping-time trend. Our codes are available on https://anonymous.4open.science/r/FOCUS_code-76E5
May 7, 2026

Relaxed Sparsest-Permutation Formulation for Causal Discovery at Scale

Despite the growing availability of large datasets, causal structure learning remains computationally prohibitive at scale. We revisit sparsest-permutation learning for linear structural equation models and show that exact Cholesky factorization is unnecessary for structure recovery. This observation motivates a support-level relaxation that searches for sparse triangular factors over a precision-support screening graph. The relaxed formulation can be efficiently evaluated via masked zero-fill incomplete Cholesky factorization, enabling scalable comparison of candidate orderings. At the population level, we establish soundness for Markov equivalence class (MEC) recovery under no-cancellation and sparsest Markov representation assumptions, as well as robustness to ordering misspecification. Motivated by these guarantees, we introduce SCOPE, a sparse-Cholesky pipeline that provides a scalable implementation of the relaxed formulation. Experiments on synthetic and real datasets demonstrate that SCOPE matches the MEC recovery accuracy of substantially slower baselines, while achieving significantly reduced runtime and scaling to 10k variables.
Sep 28, 2026

The Statistical Cost of Causal Discovery with Feedback

What determines the unavoidable sample cost of learning cyclic causal structure? For cyclic linear non-Gaussian models, we study exact condensation recovery from observational data: identifying the strongly connected component (SCC) partition and all edges between components. We establish the first information-theoretic lower bounds on sample complexity for this target. For pp variables, maximum SCC size smax⁡s_{\max}, and maximum external-parent count dBd_B, any estimator requires order smax⁡log⁡(ep/smax⁡)+dBlog⁡(ep/dB)s_{\max}\log(ep/s_{\max})+d_B\log(ep/d_B) samples in the worst case over a regular model class. These bounds distinguish the costs of SCC membership and external-parent selection. Under principal invertibility and without correlation faithfulness, we establish a population block-exogeneity principle that identifies unknown root SCCs through residual independence and inclusion minimality. A sparse-adjustment characterization shows that small adjustment sets suffice to identify SCCs and their direct external parents, without regressing on all previously recovered variables. These characterizations yield BlockExo, which attains a structurally matching sample bound without knowing smax⁡s_{\max} or dBd_B under suitable conditions. Simulations support the structural dependence of our sample bound and demonstrate BlockExo's sample-efficient recovery in comparisons with other methods for cyclic causal discovery.