Clique Constraints for Exact Causal Structure Learning
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
| Method | Integer-separation policy | Repair | |
|---|---|---|---|
| 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 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 | Use the default Clique integer separation. | None | 20 |
| Study | Setting | ER-4-0 | ER-5-0 |
|---|---|---|---|
| Big- | 16.75% / 2147 | 11.05% / 2733 | |
| 10.03% / 2621 | 11.39% / 2779 | ||
| 13.81% / 2412 | 12.03% / 2755 | ||
| 17.60% / 2453 | 11.65% / 2774 | ||
| Fractional separation | No cbCut | 20.20% / 2110 | 11.66% / 2760 |
| Root exhaustive | 20.24% / 2096 | 11.69% / 2718 |
| Ratio | Metric | Cycle-only | Cycle Clique | Clique Cycle |
|---|---|---|---|---|
| 4 | Submitted ( ) | 23.72 | 18.42 | 20.16 |
| Nodes ( ) | 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 ( ) | 31.18 | 29.23 | 29.56 |
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
| ER-4-0 | ER-5-0 | SF-5-0 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Nodes | Nom. | Real. | Nodes | Nom. | Real. | Nodes | Nom. | Real. | |||
| 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 |
| Edge Ratio | Target Edges | Max Capacity | |
|---|---|---|---|
| 2 | 5 | 10 | 10 |
| 3 | 7 | 21 | 21 |
| 4 | 9 | 36 | 36 |
| 5 | 11 | 55 | 55 |
| 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. |
| 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. |
| F. Stronger Clique Cuts | Top-3-size-min-k+1-cliques, Top-5-size-min-k+1-cliques, All-unique-size-min-k+1-cliques (adding constraints). | |
| Strengthen the LP relaxation and dual bound | D. Fractional Separation | Inspect the fractional MIPNODE relaxation and submit valid violated clique inequalities through cbCut() . |
| E. Big- Relaxation | and edge-specific linking bounds. |
| Concept | Notation / Gurobi term | Definition |
| Branch-and-bound | B&B | Tree-search for mixed-integer optimization; nodes define subproblems whose continuous relaxations supply bounds. |
| Search tree | Collection of generated B&B nodes; a root-to-node path records the branching decisions. | |
| Node queue | ; MIP_NODLFT | Unexplored B&B nodes remaining in the solver queue. |
| Current node | 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 | ; MIP_OBJBST | Best globally feasible integer solution found so far. |
Causal Structure Learning
Causal structure learning infers directed relationships among variables from observational, interventional, or time-series data.
See all 135 papers