cbcd.algorithms.cml

Coordinated Multi-Neighborhood Learning (CML; Smith & Zhou 2024, arXiv 2405.15358).

Native, efficient multi-target local causal discovery — the best-in-class local algorithm. Same accuracy as the mmpc-hops local_discovery but far fewer CI tests, via the two-phase neighborhood-coordination skeleton of Algorithm 1 (§III.A):

Phase 1 (union skeleton): FCI-style skeleton over O = NB_T (the union of first-order target

neighborhoods), conditioning only on subsets of O -> reuses region-scoped PCStable. Between-neighborhood edges survive (inducing paths) and coordinate orientation.

Phase 2 (local skeleton): within each target neighborhood, prune edges using first-order neighbours

N1(i) / N1(j) (which include the target’s second-order neighbours) as separators.

Orient: v-structures + Zhang R1-R4, R8-R10, then R_N (within a neighbourhood, circle marks -> tail,

i.e. o-o -> - and o-> -> ->, since there is no latent confounding within a neighbourhood). Returns a local PAG.

First-order neighbourhood N1(t) is the Markov blanket (per the paper), estimated once per node with grow-shrink iamb and memoized — this is where the CI-test economy comes from (grow- shrink is ~20x cheaper than the max-min mmpc, which does unbounded subset enumeration).

Functions

cml(→ cbcd.graph.pag.PAG)

Coordinated Multi-Neighborhood Learning: efficient native local PAG around targets.

Module Contents

cbcd.algorithms.cml.cml(data: numpy.typing.NDArray[numpy.float64] | pandas.DataFrame, targets: collections.abc.Sequence[int], *, ci_test: cbcd.citest.protocol.CITest | Literal['fisherz'] = 'fisherz', alpha: float = 0.05, max_cond_set: int | None = None, background: cbcd.background.BackgroundKnowledge | None = None, var_names: collections.abc.Sequence[str] | None = None, recorder: cbcd.recording.RunRecorder | None = None, run_id: str | None = None) → cbcd.graph.pag.PAG

Coordinated Multi-Neighborhood Learning: efficient native local PAG around targets.

Returns an n_vars-wide PAG with the query neighbourhoods oriented (R_N-simplified) and between-neighbourhood coordination edges retained; nodes outside NB_T are isolated.

Guarantee. Sound + complete under faithfulness, causal sufficiency, and Assumption 1 (no inducing path between two same-neighbourhood nodes routed through a different neighbourhood); completeness is relative to the constructed neighbourhood graph G*_N (Smith & Zhou 2024, arXiv 2405.15358), i.e. every endpoint mark G*_N identifies is committed and no other. Every committed arrowhead/tail is ancestrally correct — verified at the d-separation oracle against the region-restriction of cbcd’s own pc in tests/test_local_discovery_soundness.py (zero wrong-orientation violations across single, disjoint-, and overlapping-neighbourhood queries).

Why it is sound where LocalPC is not. The classic LocalPC unsoundness (a v-structure oriented from a region-restricted skeleton whose separating set is incomplete) is sidestepped because phase 2 searches for separators over N1 = the full Markov blanket — spouses included — of each endpoint, and ranges over all NB_T pairs (between-neighbourhood edges too, not only pairs inside one target neighbourhood). A false edge whose true separator lies outside the union O but inside the endpoints’ MBs is therefore removed before orientation, so it cannot seed a spurious unshielded triple. LOAD’s critique of MB-incomplete local search (algo113, Appendix A) thus does not apply. (Removing the between-neighbourhood pass reintroduces exactly that bug — see the soundness test’s historical note.)

Relation to neighbours in the local-discovery literature (answering the reviewer’s “why not X?” in-code): LDECC (Gupta et al.) is unsound and incomplete for the local CPDAG in general (LOAD algo113, Appendix A), so it is not the champion here. LOAD / SNAP (algo113 / algo151) solve a different problem — they return a valid adjustment set for a treatment/outcome effect, not a local CPDAG/PAG around a query set — so they are not substitutes for CML’s output.

PAG-mode note (latent cell). Although CML returns a PAG, its soundness assumes causal sufficiency. The final rule R_N resolves every within-neighbourhood circle mark to a tail on the premise that there is no latent confounding — hence no bidirected edge — inside a neighbourhood. Under a genuine within-neighbourhood latent confounder that premise fails and R_N commits a tail where the true MAG has an arrowhead (it collapses a <-> to a tail); the tests/test_local_latent_soundness.py battery measures this as a nonzero false-tail rate (730 over the sweep) while cml’s arrowheads stay sound (zero false arrowheads — they come from the FCI collider/rule pass, not R_N). So for the latent cell prefer local_discovery_latent, which makes no within-neighbourhood-sufficiency assumption and whose committed marks (arrowheads and tails) are certified sound by the Possible-D-Sep adequacy guard. Use cml in PAG mode only when within-neighbourhood causal sufficiency is warranted; there its committed marks match global fci/pc (the cell-5 regime, zero violations).