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
Figure 1: Workflow of clique-constrained exact causal structure learning. The solver alternates between branch-and-cut node processing, cycle separation, clique separation, incumbent acceptance, and bound updates until optimality or a stopping limit is reached.
Method
Integer-separation policy
Repair
M
ExDBN
None: the baseline enforces acyclicity but imposes no clique-size restriction.
None
100
Clique
At each infeasible integer candidate, submit lazy cycle constraints and all detected violated clique constraints.
None
100
Clique ⋅ Most-Violated
At each infeasible integer candidate, submit lazy cycle constraints and only the most-violated minimal (k+1) clique constraint.
None
100
Clique ⋅ QR Repair
Use the default Clique integer separation: submit lazy cycle and violated clique constraints.
Delete violation-causing edges, locally refit affected regressions by QR, validate the repaired assignment, and submit it via cbSetSolution() .
100
Clique ⋅M=20
Use the default Clique integer separation.
None
20
Table 1: Compared methods. Integer separation is performed at MIPSOL events through lazy constraints; fractional MIPNODE separation is evaluated separately.
Figure 2: Comparison of the SHD score and number of lazy-constraint submissions between Clique and ExDBN under different time limits setting and various dimensions d . The solid line represents the mean across multiple trials, with the shaded region indicating the standard deviation.
Figure 3: SHD results over the ER and scale-free synthetic graph families. Solid lines and shaded areas denote the mean and standard deviation of multiple runs, respectively.
Figure 4: Comparison between ExDBN and Cliques with maximum clique sizes k∈{3,4,5} under different time limit settings.
Study
Setting
ER-4-0
ER-5-0
Big- M
M=10
16.75% / 2147
11.05% / 2733
M=20
10.03% / 2621
11.39% / 2779
M=50
13.81% / 2412
12.03% / 2755
M=100
17.60% / 2453
11.65% / 2774
Fractional separation
No cbCut
20.20% / 2110
11.66% / 2760
Root exhaustive
20.24% / 2096
11.69% / 2718
Table 2: Big- M and fractional-separation ablation. Each cell reports Gap (%) / nodes per second under the fixed 1,000 -second budget. D2, D3, and D5 submitted no user cuts. D4 submitted 146.5 / 108.5 user cuts on ER-4-0 / ER-5-0, respectively, while spending 41.09% / 47.38% of runtime in callbacks.
Figure 5: SHD on ER-4-0 as the number of variables increases. Clique with M=20 is competitive with ExDBN and the default Clique formulation, but its advantage is not uniform across node counts or sample sizes. Shaded regions show variability across seeds.
Ratio
Metric
Cycle-only
Cycle → Clique
Clique → Cycle
4
Submitted ( 103 )
23.72
18.42
20.16
Nodes ( 106 )
1.915
0.348
0.379
Gap (%)
52.81
59.69
59.91
Best bound
11.234
9.600
9.545
MIPSOL events
532
398
433
5
Submitted ( 103 )
31.18
29.23
29.56
Table 3: Callback-order diagnostics under a fixed budget. All experiments use static Erdős–Rényi synthetic data with p=0 and edge ratios of 4 and 5. Results are averages over seeds 1–4 with d=20 , n=2000 , M=100 , and a 1,800-second time limit. Submitted constraints and explored nodes are reported in thousands and millions, respectively.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
ER-4-0
ER-5-0
SF-5-0
Nodes
Nom.
Real.
R2
Nodes
Nom.
Real.
R2
Nodes
Nom.
Real.
R2
11
80.00%
75.45% / 77.27%
0.847 / 0.875
11
100.00%
57.58% / 58.18%
0.737 / 0.808
11
100.00%
70.18% / 70.38%
0.890 / 0.884
15
57.14%
56.90% / 56.90%
0.928 / 0.923
15
71.43%
62.82% / 63.33%
0.897 / 0.916
15
71.43%
55.57% / 55.60%
0.875 / 0.874
20
42.11%
41.97% / 42.01%
0.900 / 0.897
20
52.63%
48.31% / 49.25%
0.907 / 0.926
20
52.63%
43.87% / 42.63%
0.874 / 0.879
25
33.33%
33.33% / 33.33%
0.910 / 0.913
25
41.67%
41.16% / 41.16%
0.929 / 0.930
25
41.67%
35.05% / 35.28%
0.866 / 0.865
30
27.59%
27.59% / 27.59%
0.909 / 0.908
30
34.48%
34.03% / 33.93%
0.918 / 0.921
30
34.48%
29.90% / 30.06%
0.875 / 0.881
Appendix
Table S4: Synthetic-data density and linearity. Nom. is the nominal skeleton density, and Real. is the mean realized skeleton density after clique-free filtering. Each entry is reported as n=200 / n=2000 . All values are means across the available generated instances.
Edge Ratio
dmax
Target Edges
Max Capacity
2
5
10
10
3
7
21
21
4
9
36
36
5
11
55
55
Appendix
Table S5: Theoretical limits for complete network saturation. The maximum node number dmax represents the upper bound where an edge ratio r can force a 100% nominal skeleton density.
Figure S6: Timing points in branch-and-bound search. For each integer candidate, the callback first performs cycle and clique separation and may submit lazy constraints. After control returns to Gurobi, the solver continues branch-and-bound search until a subsequent candidate, bound update, or termination event.
Event Type
Description
Callback Action
MIPSOL
Triggered when the solver finds an integer candidate, originating either from a branch-and-bound node or an internal primal heuristic.
cbLazy() may reject the candidate by appending valid lazy constraints.
MIPNODE
Triggered when a continuous LP relaxation is available at a branch-and-bound node. The solution is typically fractional.
cbCut() may submit globally valid user cuts; root-node diagnostics are also logged.
Appendix
Table S6: Operational distinction between MIPSOL and MIPNODE events.
Figure S7: Relative MIP gap and F1 score for Clique and ExDBN across time limits and dimensions d . Lines show averages over seeds and shaded regions report variability across runs.
Improvements
Methods
Experiments
Reduce redundant searches
A. Delayed Separation
Reduce clique separation, increase solving nodes per sec and close gap.
C. Repair Incumbent
Repair an infeasible MIPSOL, locally refitting support with ridge/QR.
Control adding constraint number
B. Controlled Cut Addition
First oversized cliques (original), First size-min-k+1-clique, most-violated size-min-k+1-clique.
Inspect the fractional MIPNODE relaxation and submit valid violated clique inequalities through cbCut() .
E. Big- M Relaxation
M∈{10,15,20,25,50,100} and edge-specific Mij linking bounds.
Appendix
Table S7: Improvements and experimental directions. Variants B1 – F2 , B3 , C3 , and E2 are systematically compared in the main manuscript.
Figure S8: Edge-limit stability trajectories and empirical plateaus across dimension regimes. Panels (a) and (b) trace the global continuous optimization dynamics, while the unified data subtable (c) catalogs the exact minimal degree boundaries ( dmax ) beyond which additional metric relaxation yields marginal structural variation. Asterisks ( ∗ ) denote approximate plateaus resolved to two decimal places. These thresholds are descriptive diagnostic references and do not represent formal asymptotic convergence guarantees.
Collection of generated B&B nodes; a root-to-node path records the branching decisions.
Node queue
Q ; MIP_NODLFT
Unexplored B&B nodes remaining in the solver queue.
Current node
v∈T
The B&B subproblem currently processed. Its LP relaxation can be fractional.
Callback
MIPSOL ; MIPNODE
User code at solver events. MIPSOL inspects integer candidates; MIPNODE inspects fractional relaxations.
Incumbent
zinc ; MIP_OBJBST
Best globally feasible integer solution found so far.
Appendix
Table S8: Notation used throughout the paper. The table consolidates optimization terminology, statistical-model notation, and graph, method, and evaluation notation.
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/δ)) 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
Haijie Xu, Chen Zhang
Department of Industrial Engineering Tsinghua University Beijing, China
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.
Sunmin Oh, Sang-Yun Oh, Gunwoong Park
Department of Statistics, Seoul National University, South Korea · Department of Statistics and Applied Probability, University of California Santa Barbara, CA, USA · Scientific Data Division, Lawrence Berkeley National Laboratory, CA, USA +2
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 p variables, maximum SCC size smax, and maximum external-parent count dB, any estimator requires order smaxlog(ep/smax)+dBlog(ep/dB) 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 or dB 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.
Sunmin Oh, Seungsu Han, Gunwoong Park
Department of Statistics; Institute for Data Innovation in Science, Seoul National University, Korea · Department of Operations Research and Financial Engineering, Princeton University, USA · Department of Statistics; Interdisciplinary Program in Artificial Intelligence; Institute for Data Innovation in Science, Seoul National University, Korea.