A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables

Summary

The paper introduces DICOLA, a recursive decomposition framework that generalizes divide-and-conquer causal structure learning to settings with latent confounders — a regime existing divide-and-conquer methods do not cover because they critically depend on causal sufficiency. The conceptual move is to extend Xie & Geng's (2008) UIG-based decomposition from DAGs to MAGs by proving that whenever $A \perp\!\!\!\perp B \mid C$ holds, m-separation decomposes "top-down" onto $A \cup C$ and $B \cup C$ (Theorems 1–2) and can be recombined into the global skeleton via a simple merging rule (Theorem 3); Propositions 1–3 then show that the augmented graph $(M)^a$ is a minimal UIG, so Markov-blanket learning yields valid tripartitions. Together this gives a sound-and-complete "divide–learn–merge" template that wraps any sound-and-complete constraint-based learner (FCI, RFCI, FCI$^+$, L-MARVEL, ICD). Empirically the framework reduces CI-test counts and runtime across five base learners on ER random graphs, four bnlearn benchmarks (MILDEW, BARLEY, ANDES, LINK), and an Arabidopsis thaliana dataset, with F1 matching or exceeding the base learner and the honest Appendix D.1 caveat that the acceleration vanishes on dense graphs.

The contribution fills a real gap and the theoretical scaffolding is elegant: reducing the latent case to separation in $(M)^a$ is the right generalization, and the m-separation transitivity results appear reusable beyond DICOLA. Several things limit how strong the paper reads. Theorem 2's proof compresses load-bearing steps (the sequence-to-path reduction inside Lemma 5 and the unstated non-adjacency of the concatenated endpoints $V_1, V_2$); the "sparsest UIG" language overstates the per-edge minimality Proposition 1 formally establishes; and the overall complexity bound silently drops the $O(m n^2)$ UIG-construction term in exactly the sparse regime the paper emphasises. A load-bearing implementation detail — the balancing score selecting among valid tripartitions — is literally missing from the text, and the released code covers only one of the five reported base learners and ships partial data for two of eight settings, so most figures cannot be reconstructed from the repository.

Strengths

• Conceptual contribution. The paper is, to the reviewer's knowledge, the first to lift divide-and-conquer causal-structure learning from the causal-sufficiency setting to MAGs. The reduction to (M)^a-based UIG separation is a clean generalization of Xie & Geng (2008) that inherits soundness and completeness under an oracle.
• Reusable theory. Theorems 1 and 2 establish two-sided "top-down transitivity" of m-separation under a valid tripartition, and Theorem 3 turns that into a constructive merging rule. These are stated in a form that is base-learner-agnostic and will likely be useful outside DICOLA.
• Base-learner-agnostic framework. The divide–learn–merge template plugs into any sound-and-complete constraint-based learner (FCI, RFCI, FCI$^+$, L-MARVEL, ICD), so improvements in the base learner and improvements in the decomposition compound cleanly.
• Breadth of empirical coverage. Random ER graphs at two sizes and two densities, four bnlearn benchmarks including the 724-variable LINK network, and an Arabidopsis case study give the reader a broad initial sense of how the framework behaves as size, sparsity, and latent-variable count vary.
• Honest limitation reporting. Appendix D.1 shows that on ER(40, $d$) the CI-test reduction drops to 0.4% (FCI) / 2.7% (RFCI) as $d$ grows to 6 — the paper does not hide the regime in which its own contribution collapses to the base learner.

Weaknesses

• Load-bearing implementation detail missing. The prose announces a specific balancing score that DICOLA minimizes when several tripartitions are valid, and then the equation itself is absent from the text. Because the score plus its tie-breaking rule determines the decomposition tree, and therefore the entire cost/accuracy trade-off, the method is genuinely underspecified as written.
• Complexity summary drops the term that dominates in the highlighted regime. The overall bound is reported as $O(m k_{\max}^2 2^{k_{\max}})$, but the UIG-construction cost $O(m n^2)$ is the term that dominates precisely when $k_{\max} \ll n$ — the very "well-decomposable" regime the paper markets. A combined bound $O(m n^2 + m k_{\max}^2 2^{k_{\max}})$ would tell the correct asymptotic story.
• **Overclaim of sparsest UIG'.** Proposition 1 formally proves per-edge minimality (no edge of (M)^acan be removed without introducing a spurious separation). The surrounding prose promotes this tothe sparsest UIGandthe maximum number of admissible decompositions among all possible UIGs`, which are strictly stronger claims about global cardinality and about the partial order of UIGs. Either strengthen the proposition or hedge the interpretation.
• Proof compression in Theorem 2. The pivotal concatenate $\pi_1(X, V_1)$ and $\pi_2(X, V_2)$ at $X$ step (i) reduces a sequence-with-possible-repetitions to a path via a straightforward argument in Lemma 5 that is precisely the non-trivial content of the lemma, and (ii) invokes Lemma 5 on $(V_1, V_2)$ without ever establishing that $V_1$ and $V_2$ are non-adjacent, which is one of Lemma 5's preconditions.
• Notation collisions and typos on load-bearing symbols. The local-skeleton definition writes m-separates $X$ and $Y$ in $G$ where the definition earlier fixed $M$, and never scopes the endpoints $X, Y$ to $\mathbf{K}$; the symbol $n$ is used with two different meanings in the complexity analysis vs. the ER experiments (|O| vs |V|); and the ANDES panel is pointed to as Figure 3(b) when the intended panel is 3(c). Individually minor, collectively distracting.
• Metric under-tests the PAG claim. Theorem 4 promises PAG-level correctness, but the reported edge F1 measures only adjacency; PAG marks (>, -, ◦), which carry most of the informative content, are not scored anywhere. A mark-aware metric (arrowhead F1 or PAG-SHD) would materially strengthen the completeness story.
• No dispersion or significance testing. Results are averaged over 50 seeds but the plots show only point estimates. Several of the F1-improvement claims turn on absolute gaps of 0.01–0.03, which is well inside plausible seed noise; error bars or a paired test would let the reader tell real improvements from noise.
• Sensitivity to alpha and to the choice of MB learner is not examined. DICOLA runs many more, smaller CI tests than the base learner and layers MB learning on top of that. Both make the error profile at a fixed alpha = 0.01 genuinely different from the baseline's. The paper's own footnote lists several MB-discovery alternatives; none of them is ablated.
• Baseline scope. All comparators are constraint-based methods. Score-based or hybrid latent-variable methods (GFCI, MAG-MHC, or the Frot–Nandy–Maathuis (2019) approach cited elsewhere) are discussed only in Appendix D.3. This makes the acceleration claim comparatively narrow.
• Real-world validation is qualitative and single-dataset. The Arabidopsis analysis compares a visual block-diagonal pattern to prior biology, with no adjacency-overlap score against the Wille et al. (2004) graph, no baseline (standalone FCI on the same 33 genes), and no identification of the specific bridging loci the text invokes.
• Speed-up trajectory acknowledged only in the appendix. Appendix D.1 candidly reports that the CI-test reduction shrinks to 0.4% / 2.7% at induced-MAG degree 6. This is a substantial narrowing of scope that the abstract, introduction, and conclusion do not reflect.
• Selection bias is excluded. The proof of Theorem 2 uses by assuming no selection bias to rule out undirected edges in the MAG. This is consistent with the assumptions listed in Section 3.2 but is invoked inside the proof rather than lifted to the assumption section, and the future-work paragraph acknowledges the extension is open.

Reproducibility & code

• Only one of the five reported base learners is shipped. The released repository implements DICOLA and wraps FCI (compare_algs/fci_alg.py around causal-learn). RFCI, FCI$^+$, L-MARVEL, and ICD are only referenced through external packages (pcalg, rcd, causality-lab) with no wrappers, no version pins, and no driver script — so the DICOLA+RFCI/FCI$^+$/L-MARVEL/ICD curves in Figures 3, 5–12 and Table 4 cannot be reconstructed from the release as-is.
• No graph-generation code for random structures. Every ER-based result (Figures 3, 5, 6, 7, 8, 13) depends on a DAG-sampling → latent-designation → linear-Gaussian-simulation pipeline that is absent from the repository. Reproducing them requires a full reimplementation of the generative process.
• Two of four benchmark datasets and the real-world dataset are absent. MILDEW and ANDES data are shipped (at n = 2000 with 3 dataset files each); BARLEY and LINK are not, and the Arabidopsis thaliana isoprenoid dataset used in Section 6.2 is not included, nor is any analysis or plotting script for Figure 4.
• Shipped seeds and sample sizes do not match the reported average. The paper reports 50 seeds per setting and sample sizes n ∈ {2000, 3000, 4000}; the shipped example iterates over 3 dataset files at n = 2000 for MILDEW and ANDES only. The 10 × |O| runtime cap is supported by CI_test.py (Max_time) but not enforced by examples.py.
• F1 helper reports skeleton F1, not the mark-aware metric. DiCoLa/utils.py:f1_score_edges scores undirected adjacency and ignores PAG marks, while the paper describes F1-score of the recovered edges without saying which. Either the reported numbers are skeleton-level (in which case the paper should say so), or the shipped helper is not the one that produced them.
• Local-comparison experiment cannot be built. Table 4 requires ER(50, 3) 5-latent data at n ∈ {2000, 3000, 4000} and the MMB-by-MMB baseline (Xie et al., 2024b); neither is in the release.
• Illustrative example not scripted. No driver constructs the 8-variable, 2-latent DAG of Figure 2(a) and steps DICOLA through it, and no visualisation of the decomposition tree is provided; because the exact tripartition sequence depends on unspecified balancing-score tie-breaking, an independent reader may not reproduce Figure 2(d) even given a correct implementation.
• What does reproduce. The core Recursive_Learner.pag_learner matches Algorithm 3, find_decomposition and Sepset.py implement Algorithms 1–2, and the shipped oracle example (oracle_example) exercises the D-sep-based correctness path on MILDEW/ANDES at n = 2000, giving genuine evidence for Theorem 4's soundness-and-completeness statement on the two shipped benchmarks (up to the caveat that F1 is measured mark-agnostically).

Recommended Changes

Essential

• Restore the balancing-score formula and tie-breaking rule. Section 5.1's we choose the tripartition that minimizes the following balancing score: currently has no equation after the colon. State the formula explicitly, and specify what happens when several tripartitions attain the minimum — this determines the entire decomposition tree and is currently unspecified in both the paper and the release.
• Correct the overall complexity bound. Report the combined bound $O(m n^2 + m k_{\max}^2 2^{k_{\max}})$ so the summary is consistent with the two component costs given in the same paragraph.
• Tighten the minimality claim about (M)^a. Either strengthen Proposition 1 to a subset-minimality (edge-containment) result — which would justify sparsest UIG / maximum admissible decompositions — or hedge the surrounding prose to what per-edge minimality actually delivers.
• Fill the two gaps in Theorem 2's proof. (i) Run the shortest-sequence-is-a-path reduction on the concatenated sequence $p$ rather than deferring it to Lemma 5 as straightforward, and (ii) either establish non-adjacency of $V_1, V_2$ or handle the adjacent case separately, since Lemma 5 requires non-adjacency as a precondition.
• Add a mark-aware structural-accuracy metric. Report arrowhead F1 or PAG-SHD alongside edge F1 for at least the main-text settings, so that the completeness claim in Theorem 4 is empirically tested and the released f1_score_edges is either replaced or unambiguously labelled as skeleton-level.
• Ship the missing pieces for reproduction. Add (a) wrappers for RFCI, FCI$^+$, L-MARVEL, ICD (or explicit version-pinned instructions for pcalg, rcd, causality-lab); (b) an ER-graph / DAG generator and linear-Gaussian simulator with fixed seeds; (c) BARLEY and LINK data (or a fetch step from bnlearn) and the Arabidopsis dataset with the Section 6.2 script; (d) a driver that averages the reported 50 seeds and enforces the 10 × |O| runtime cap.
• Reflect the dense-graph limitation in the abstract and introduction. Appendix D.1's 70% → 0.4% finding should not be back-loaded to an appendix; the abstract and Section 1 should state that the acceleration is a sparsity/decomposability contract.

Suggested

• Fix the Figure 3(b) cross-reference to Figure 3(c) for the ANDES-network sentence, and check the manuscript for other panel labels that may have drifted after re-ordering.
• Disambiguate n. Rename the ER argument (e.g., p for the total-vertex count) so the complexity bounds' n = |O| and the experimental n = |V| are visually distinct.
• Fix the in G in the local-skeleton definition to in M, and scope the endpoints $X, Y$ to $\mathbf{K}$ explicitly, since L_K is used heavily in Theorem 3.
• Soften may substantially densify or split it into sparse-DAG (modest densification) vs dense-DAG (large densification) regimes, so the general claim matches the Table 2 numbers for MILDEW/ANDES/LINK.
• List explicit assumptions in Theorem 4. In addition to the CI oracle and the base learner's soundness/completeness, state that FINDDECOMPOSITION returns valid tripartitions (which under the oracle follows from Propositions 1–3).
• Add error bars / a paired significance test on the reported 50-seed averages, so that generally improves or matches the F1-scores of the base methods can be evaluated formally.
• Add a small sensitivity study over alpha (e.g., {0.001, 0.01, 0.05}) and, ideally, an ablation over MB-discovery choices from the footnote (STMB, MMMB, HITON-MB) at one representative setting.
• Quantify the Arabidopsis claim. Report an adjacency-overlap score against the Wille et al. (2004) sparse Gaussian graph and identify the specific bridging loci that instantiate the cross-talk restricted to specific loci claim, or state clearly that the analysis is illustrative.
• Ship a demo script for the Figure 2 example — construct the 8-vertex, 2-latent DAG, run DICOLA under the oracle, and render the decomposition tree so the reader can walk through the framework end-to-end.