PaperlayerView exact revision on arXiv

Source-linked AI summary

Score-Based Learning of Cluster DAGs from Interventions

Gaetano Tedesco, Alex Markham

arXiv:2610.11947v1stat.MLcs.LG

TL;DR

Learning cluster DAGs requires discovering both the variable clusters and the causal edges between them, while existing interventional-coarsening learning uses constraint-based edge tests. COARSE uses intervention signatures to identify clusters and their causal order, then applies a pooled BIC score in local searches. It matches state-of-the-art edge recovery given enough samples and runs its edge phase up to two orders of magnitude faster.

  • Problem

    Learning interventional coarsenings requires recovering clusters and their edges, but existing score-based searches target fine-variable DAGs rather than cluster DAGs.

    Source: §1 · pp. 1–2

  • Method

    COARSE uses intervention signatures to identify the partition and cluster order, then recovers edges with a pooled-BIC local search per block.

    Source: §1 · p. 2, §3 · p. 4

  • Results

    COARSE matches state-of-the-art edge recovery given enough samples, with an edge phase up to two orders of magnitude faster.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The interventional coarsening is identifiable from marginal shifts alone for unknown multi-target interventions, and the procedure is consistent with worst-case polynomial running time under its stated conditions.

    Source: §1 · p. 2, §5 · p. 7

    The guarantees assume oracle shift tests and enough samples for every block MLE to exist; finite-sample shift-test errors can split or merge blocks.

    Source: §3.4 · p. 6

Abstract

from arXiv · show

Graphical approaches to causal abstraction transform a low-level causal directed acyclic graph (DAG) over many measured variables into a smaller, high-level DAG whose nodes cluster the original variables and whose edges summarize the causal relations between clusters. Such cluster DAGs are easier to interpret, but learning them requires finding the clusters and recovering the edges between them. Madaleno et al. (2026) learn the interventional coarsening (the cluster DAG that merges variables the interventions cannot distinguish) in two constraint-based phases: first the clusters, then the edges. We introduce COARSE, the first score-based method for this task: it keeps the two-phase structure but, under linear Gaussian assumptions, swaps the constraint-based edge phase for a score-based one. We show that the interventions themselves identify a causal order over the clusters, and learning the edges reduces to a single local search per cluster under a cluster-level BIC score. We prove that the procedure runs in polynomial time and, provided the variables affected by each intervention are correctly identified, that it is consistent. On synthetic and real-world interventional data, COARSE matches state-of-the-art edge recovery given enough samples, with an edge phase up to two orders of magnitude faster, including on dense graphs with hundreds of nodes.

1 INTRODUCTION

The paper targets interpretable cluster DAGs, which summarize causal relations between groups of measured variables, and introduces COARSE to learn them from interventional data. COARSE uses intervention signatures to order clusters and score-based local searches to recover edges.

1 INTRODUCTION

  • Cluster DAGs group recorded variables into blocks and summarize causal relations between blocks, offering a coarser description than a DAG over individual measurements.The paper motivates this resolution because fine-grained features may not be the units for reasoning, intervention, or communication, and large DAG searches are computationally daunting.Source: §1 · p. 1
  • Prior abstraction work is largely theoretical or assumes a partition, a chosen estimand, or strong parametric assumptions, leaving learning abstractions from data largely open.Madaleno et al. [39] learn interventional coarsening in two constraint-based phases: first clusters, then edges decided by conditional-independence tests.Source: §1 · pp. 1–2
  • Existing score-based searches target a single DAG over fine variables, while cluster DAG learning had only the constraint-based RePaRe method.The paper notes that CI-test reliability can degrade with larger conditioning sets and that errors accumulate across edge decisions.Source: §1 · p. 2
  • Intervention signatures identify a causal order and restrict each block’s candidate parents, enabling BIC-scored local edge searches without searching over orderings.The method uses a BIC pooled over environments; the procedure is consistent and has worst-case polynomial running time under error-free signatures.Source: §1 · p. 2
  • COARSE matches state-of-the-art edge recovery given enough samples, while its edge phase runs up to two orders of magnitude faster.The contribution summary reports these results on synthetic and real-world interventional data.Source: §1 · p. 2
  • COARSE extends interventional coarsening to unknown multi-target interventions, where marginal shifts identify the partition even when the earlier method does not.Under single-target interventions, the resulting coarsening coincides with that of Madaleno et al. [39].Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries establish the graph and distribution concepts used in the paper, then set out local structure search, the interventional data model, and valid coarsenings. They provide the basis for reducing edge recovery to local searches over restricted parent pools.

2.1 Graphs and orders

  • A DAG’s ancestral relation defines a partial order, and its topological orderings place ancestors before descendants.The paper uses linear extensions of partial orders to describe such orderings and the possible nodes preceding each node.Source: §2.1 · pp. 2–3

2.2 Conditional independence and Markov properties

  • The Markov property relates graph separation to conditional independence, while faithfulness requires every distributional conditional independence to follow from the DAG.DAGs are Markov equivalent exactly when they have the same skeleton and v-structures.Source: §2.2 · p. 3

2.3 Local structure search

  • A restricted Markov boundary is a minimal set from a candidate pool that shields a target variable from the rest of that pool.Under the Markov and faithfulness assumptions, a pool containing all parents and no descendants yields the target’s parent set.Source: §2.3 · p. 3
  • Once an order is known, parent recovery reduces to one restricted-boundary search per node; grow-shrink adds and removes candidates until the boundary is stable.Grow-shrink uses conditional-independence queries, while the score-based version replaces each query with a comparison of decomposable local scores and returns the boundary when the score is locally consistent.Source: §2.3 · p. 3
  • The local BIC balances maximized log-likelihood against a penalty proportional to model dimension and log sample size; λ = 1 gives standard BIC.For curved exponential families, the passage states that BIC is decomposable, score equivalent, consistent, and locally consistent.Source: §2.3 · p. 3

2.4 Linear Gaussian model and interventions

  • The data model assumes linear Gaussian distributions across environments, with non-observational environments produced by soft interventions on unknown target sets.Soft interventions change only target conditionals, preserving the DAG; datasets are sampled independently across environments, and targets are unobserved.Source: §2.4 · pp. 3–4

2.5 Coarsenings

  • A coarsening groups DAG nodes into blocks and is valid when its induced edge set is acyclic; valid coarsenings form a refinement lattice.RePaRe searches this lattice using refinement and CI-based edge decisions. For interventional data, equal shift patterns identify the interventional coarsening under single-target interventions and suitable assumptions.Source: §2.5 · p. 4

3 METHOD: COARSE

COARSE derives clusters and a causal order from intervention-induced marginal shifts, then learns edges with a score-based local search for each block. Its guarantees depend on correct shift identification, while finite-sample shift-test errors can affect the recovered partition.

3.1 The interventional coarsening

  • The interventional coarsening groups variables with equal intervention signatures; unlike Madaleno et al. [39], it remains identifiable from marginal shifts under multi-target interventions.Under single-target interventions, the two coarsenings coincide.Source: §3.1 · p. 4

3.2 A causal order from the interventions

  • Under Ass. 9, intervention supports encode ancestry and define parent pools containing all parents and no descendants, but nested supports can still occur between unrelated blocks.Supports fix orientations; the score must decide adjacency.Source: §3.2 · p. 5

3.3 Scoring coarse parents

  • Pooled BIC scores least-squares block regressions; a dependent environment's order-n gain can outweigh every order-log n penalty, while absent dependence leaves only penalties.The likelihood factorizes over blocks, so each block's maximum-likelihood fit is a least-squares regression.Source: §3.3 · pp. 5–6

3.4 COARSE and its guarantees

  • COARSE forms blocks from equal rows of the intervention descendant matrix, estimates supports and parent pools, then runs one GrowShrink search per block.Welch tests are the default for the linear Gaussian setting; general two-sample tests can replace them without changing the algorithm.Source: §3 · p. 4, §3.4 · p. 6
  • With oracle shift tests, COARSE is consistent as sample size grows; its pooled BIC identifies the graph up to its skeleton, while supports fix orientations.Finite-sample shift-test errors can split or merge blocks, and large blocks increase parameter and data demands.Source: §3.4 · p. 6

4 EXPERIMENTS

Experiments evaluate COARSE on synthetic graphs and a causal chamber dataset, measuring partition and edge recovery alongside runtime. With sufficient samples, its edge recovery compares favorably with RePaRe and is substantially faster.

4.1 Setup

  • Synthetic linear-Gaussian ER models use soft shift interventions on unknown targets, 20 seeds per configuration, and Welch tests at α = 10^-4 unless stated otherwise.Partition recovery uses ARI; edge recovery uses precision, recall, and F-score, and runtime is measured on one CPU core.Source: §4.1 · p. 6

4.2 Consistency and scalability

  • At n_e = 10^5, F-score is 0.95 for d = 50, 0.79 for d = 200, and 0.67 for d = 1000; ARI is 0.54 at d = 1000.Under the oracle partition, near-perfect F-scores hold up to d = 500 once n_e ≥ 5 × 10^3, suggesting partition estimation drives much of the larger-graph loss.Source: §4.2 · pp. 6–7, Figure 1 · p. 7

4.3 Comparison against RePaRe

  • F-score reaches at least 0.99 at every d from n_e = 5 × 10^3, with 9× to 510× speed-ups over RePaRe.The comparison uses the oracle partition on ER graphs with ρ = 0.2 and m = 5.Source: §4.3 · p. 7

4.4 Real data: the causal chamber

  • COARSE and RePaRe recover the true partition (ARI = 1) and the same coarse DAG, with 8 of 10 true edges and no false edge.Both score highest at coarse and variable resolutions and above their negative-control null intervals.Source: §4.4 · p. 7

5 DISCUSSION

COARSE combines shift-derived cluster structure with local score-based edge searches, matching RePaRe on edge recovery given enough samples while running faster. Its practical limits include partition errors, score trade-offs, intervention-limited resolution, and assumptions on the causal model and data.

5 DISCUSSION

  • COARSE matches RePaRe on edge recovery given enough samples, runs faster in every configuration, and is up to 510× faster under the oracle partition.On the light-tunnel chamber, it recovers the physical system’s block structure in a fraction of a second.Source: §5 · p. 7
  • At large d, most performance loss comes from partition estimation: multiple-testing burden and low power can misassign variables before edge scoring.The partition stage uses d · m Welch tests, and each missed or spurious shift can move a variable between blocks.Source: §5 · p. 8
  • The method’s resolution is limited by the interventions, while its guarantees assume an acyclic linear Gaussian model, soft interventions, no hidden confounders, and an observational baseline.Without a baseline, neither the partition nor the order is defined; multi-target environments may merge variables that single-target interventions would separate.Source: §5 · p. 8
  • The discussion proposes replacing shift tests or jointly estimating partitions and edges, while target-aware scoring, stability selection, and intervention design are further directions.It also identifies cyclic graphs, baseline-free settings, and nonlinear or non-Gaussian scores as future extensions.Source: §5 · p. 8
  • COARSE targets high-dimensional settings where fine variables are not the desired units of reasoning and searching the fine DAG is computationally daunting.When heterogeneous data are available, the paper says shifts provide the grouping and order, leaving a polynomial skeleton search.Source: §5 · p. 8

Score-Based Learning of Cluster DAGs from Interventions: Supplementary Materials

The supplementary related work situates COARSE among functional and graphical abstractions, data-driven abstraction learning, structure-search paradigms, and methods for interventional data. It emphasizes that jointly learning a partition and abstract DAG remains uncommon, especially with a score-based approach.

A EXTENDED RELATED WORK

  • Functional causal abstraction uses maps between models that commute with interventions, while graphical approaches represent clustered variables with C-DAGs and related graph structures.The cited work develops exact, hierarchical, approximate, and soft-interventional abstractions, alongside graphical results on causal queries and grouping.Source: A EXTENDED RELATED WORK · p. 14
  • Most abstraction-learning methods assume a partition or impose strong parametric structure; jointly discovering the partition and abstract DAG is uncommon, as is score-based treatment.Prior approaches include deep architectures, linear assumptions, optimal transport, multi-environment learning, and information-theoretic methods.Source: A EXTENDED RELATED WORK · p. 14
  • Constraint-based search uses conditional-independence tests, whereas score-based methods optimize decomposable criteria such as BIC; COARSE uses restricted grow-shrink with a coarse multi-environment score.The surveyed methods include greedy equivalence, ordering-based, permutation-based, reinsertion-based, and discrete searches.Source: A EXTENDED RELATED WORK · p. 14
  • Unlike prior interventional searches described here, COARSE handles unknown, possibly multi-target soft interventions, which determine both the identifiability target and the search order.The related work contrasts settings with known hard targets, unknown soft targets, joint target estimation, and invariance across environments.Source: A EXTENDED RELATED WORK · p. 14

B ADDITIONAL THEORY AND PROOFS

The supplementary theory collects graph and probability preliminaries, establishes properties of restricted Markov-boundary search and grow-shrink, and corrects a lattice claim about valid coarsenings. These results provide background and proof tools for the main method.

B.1 Graph and probability theory

  • A path is active when it is not blocked by a conditioning set, and d-separation means that the set blocks every path between the queried node sets.The appendix also recalls graph notation for ancestors, descendants, parents, and topological order.Source: §B.1.1 · p. 15

B.1.2 Graphoids.

  • Gaussian distributions with positive-definite covariance have compositional-graphoid conditional-independence relations, supplying the axioms used in the appendix’s boundary results.The work assumes Gaussian data and treats the resulting relation as a graphoid.Source: §B.1.2 · p. 15

B.1.3 Markov boundary and restricted Markov boundary.

  • Under graphoid assumptions, Markov boundaries exist uniquely; restricting the candidate pool to include all parents and exclude descendants makes the restricted boundary equal the parents.COARSE’s intervention-derived parent pool has this property.Source: §B.1.3 · pp. 15–16

B.2 Grow-shrink algorithm

  • Restricted grow-shrink returns the Markov boundary relative to its pool with O(|Z|^2) oracle queries, and its score version converges to the same set when comparison signs converge correctly.In COARSE, the target is a block, the pool is its intervention-derived candidate-parent set, and the score is pooled BIC.Source: §B.2 · p. 16

B.3.1 The lattice of valid coarsenings

  • Valid coarsenings form a lattice, but only a meet-subsemilattice of the partition-refinement lattice; their join can be coarser than the ambient join.The example’s ambient join induces a directed cycle, while the valid join is the top partition.Source: §B.3.1 · p. 17

B.3.2 Relation to the interventional coarsening of Madaleno et al. [39]

The supplementary results compare signature-based and intervened-ancestor coarsenings, derive order constraints from intervention supports, and detail the block-Gaussian likelihood and its existence conditions. They also characterize the block model’s smooth parameterization.

B.3.2 Relation to the interventional coarsening of Madaleno et al. [39]

  • Under single-target interventions, the signature partition equals Madaleno et al.’s interventional coarsening; with multi-target interventions, it can be strictly coarser and that coarsening is not identifiable from marginal shifts.In the counterexample, all variables share a signature although their intervened-ancestor sets differ.Source: §B.3.2 · pp. 17–18

B.3.3 Validity of the interventional coarsening and causal orders from interventions

  • A coarse edge implies strict inclusion of intervention supports, and those supports define a causal order that restricts candidate parents to include all parents and no descendants.Blocks with incomparable supports cannot be adjacent or ancestors of one another; adjacency is oriented from smaller to larger support.Source: §B.3.3 · p. 18

B.4.1 Data and sample covariances

  • The block-Gaussian primer represents observations as environment-specific data matrices and uses their sample covariances in the model calculations.The observed matrix is organized with variables in rows and samples in columns.Source: §B.4.1 · p. 19

B.4.2 Maximum likelihood estimation

  • The block-recursive Gaussian log-likelihood decomposes across blocks, so maximum likelihood estimation can maximize each block’s likelihood separately using ordinary two-step least squares.The stated factorization of the parameter space supports the block-by-block optimization.Source: §B.4.2 · p. 19

B.4.3 Existence of the MLE

  • The Gaussian MLE exists when each block-family covariance has full rank, with the model’s threshold set by its largest family size.The appendix states that the threshold is no greater than d and is typically much smaller, permitting regimes with ne < d.Source: §B.4.3 · pp. 19–20

B.4.4 Curved exponential family structure

  • The block model is a curved subfamily of centered Gaussians whose parameter-to-covariance map is a diffeomorphism onto a smooth manifold of dimension dim(H).Its block parameters comprise regression matrices and positive-definite residual covariance matrices.Source: §B.4.4 · p. 20

B.5 Pooled BIC score

This appendix establishes the pooled BIC score’s behavior and details COARSE’s partition refinement, local edge searches, consistency, and computational cost.

B.5 Pooled BIC score

  • The pooled score sums decomposable per-environment BICs, and Markov-equivalent coarse DAGs receive equal scores.Each local score depends on a block’s parent set.Source: §B.5 · pp. 20–21
  • The pooled BIC prefers the true coarse DAG’s Markov equivalence class over other coarse DAGs in the large-sample limit.The result assumes environments share the same DAG.Source: §B.5 · pp. 20–21

B.6.1 Partition estimation and refinement

  • Partition refinement splits blocks according to variables’ matching interventional-descendant patterns.The descendant matrix is built by thresholding tests for intervention-related shifts.Source: §B.6.1 · p. 22

B.6.2 Full COARSE procedure

  • COARSE derives each block’s candidate parent pool from support inclusion, without computing a linear extension of the support order.The procedure then searches each block’s estimated parent pool.Source: §B.6.2 · p. 22

B.6.3 Consistency of coarse

  • Under oracle tests, the local GrowShrink searches recover all parent sets with probability tending to one, yielding the true coarse DAG.The argument uses the block-level Markov boundaries and a union bound over blocks.Source: §B.6.3 · p. 23

B.7 Worst-case complexity

  • The edge-search cost is O(|E|q^3d^3), with sample covariance computation costing O(d^2n).The covariance matrices are computed once and cached.Source: §B.7 · p. 23

C ADDITIONAL EXPERIMENTS

The appendix reports additional experiments testing theoretical results and robustness to assumption violations.

C ADDITIONAL EXPERIMENTS

  • Additional experiments test theoretical results and robustness to assumption violations, using one CPU core on an Apple M3 Max with 36 GB RAM.The passage specifies the experimental purpose and hardware.Source: C ADDITIONAL EXPERIMENTS · p. 23

C.1 Experimental details

The experiments assess COARSE across synthetic and real-world settings, test finite-sample variants and tuning choices, and compare partition-recovery cutoffs. Results show that graph density and environment count affect convergence, while cross-validation can approach oracle cutoff performance.

C.1 Experimental details

  • Synthetic ER and scale-free graphs vary expected degree, noise, and intervention targets; the real-world light-tunnel data include five separate or two grouped intervention environments.The light-tunnel datasets contain 104 observational and 103 interventional samples each.Source: §C.1 · pp. 23–24
  • The experiments select COARSE’s α by cross-validation in some studies, compare hyperparameter-selection procedures, and score negative controls at both coarse and fine levels.The negative controls use random DAGs matched by edge count or adjacency count.Source: §C.1 · p. 24

C.2 Finite-sample variants

  • Finite-sample variants address partition errors and large-block parameter costs using cross-validated α, block principal components, or standardized block means.The principal-component variant retains at most k components per block; the mean variant scores q scalar nodes.Source: §C.2 · p. 24

C.3 Graph density and graph family

  • On ER graphs, denser graphs and more environments delay convergence; on scale-free graphs, median ARI and F-score reach 1 by n_e = 2 × 10^3 in every setting.In the hardest ER setting, median ARI is 0.33 at n_e = 10^2.Source: §C.3 · p. 24, Figure 2 · p. 25, Figure 3 · p. 26

C.4 Comparison against RePaRe: full grid

  • Table 3 completes Table 1 with results for every sample size in the tested grid.The supplied passage does not report the table’s cell values.Source: §C.4 · p. 25

C.5 Penalty multiplier

  • At n_e = 5 × 10^3 and above, every tested penalty multiplier reaches an F-score of at least 0.99; λ = 1 is reported as a good default across tested regimes.At smaller sample sizes, stronger penalties can reduce recall.Source: §C.5 · p. 25

C.6 Cutoff rules for the descendant test

  • CV-coarse, the only rule needing neither a level nor the truth, is within 0.04 of the oracle median at n_e = 10^4 and within 0.02 at n_e = 10^5.Source: §C.6 · p. 26

C.7 Multi-target interventions

With multi-target interventions, the interventional coarsening can differ from the single-target partition, and its resolution depends on how target sets intersect. In the estimation study, COARSE’s partition estimates approach the interventional coarsening as sample size grows.

C.7 Multi-target interventions

  • The population comparison evaluates ΠE against ΠI across target-count settings and reports block ratios and hidden-edge fractions.The study uses ER graphs with d = 50 and 200 seeds.Source: §C.7 · p. 26
  • In the native design, k = 2 yields ARI 0.38–0.75 and k = 5 yields ARI below 0.26; overlapping targets can restore resolution, with ARI rising from 0.56 at m = 10 to 0.86 at m = 40 for k = 2 and ρ = 0.2.The hidden-edge fraction falls toward zero in the reported overlap example.Source: §C.7 · pp. 26–27
  • At n_e = 10^5, estimated-partition ARI against ΠE reaches 0.85–0.92, while its distance from ΠI follows the population gap.The estimate converges to ΠE, the partition identified by the paper’s definition.Source: §C.7 · p. 27

C.8 High-dimensional regime: reduced-rank variants

Reduced-rank variants make block scoring feasible when samples fall below family size, but discard information that can produce spurious parents. With enough samples, coarse achieves stronger edge recovery; its Gaussian score is also insensitive to tested noise families in the linear model.

C.8 High-dimensional regime: reduced-rank variants

  • The reduced-rank variants shrink each block before scoring, lowering family size so fits can exist below the original block MLE’s sample threshold.kPC-coarse uses observational principal directions applied unchanged across environments; avg-coarse uses the mean of scaled block variables.Source: §C.8 · p. 27
  • At ne = 10^3, coarse reaches F-scores of 0.96–0.98 with precision 1, overtaking 3PC at ne ≈100 for m = 20 and ne ≈500 for m = 5.For ne ≤30, coarse scores 0.17–0.44 while reduced variants score 0.4–0.8; 3PC is best among them throughout.Source: §C.8 · pp. 27–28
  • At m = 20, reduced variants plateau or decline as sample size grows; discarded within-block directions omit dependence with parents, reducing precision to 0.46–0.66.This misspecification can admit spurious parents, so dimension reduction trades large-sample exactness for scoring below the original family-size threshold.Source: §C.8 · p. 28
  • Above ne = Fj, coarse increasingly recovers exact parent sets, while 3PC retains high recall but more often includes spurious parents.Coarse reaches exact recovery of at least 0.86 from ne/Fj ≈20 and about 1 from ≈45; 3PC recall is 0.96–0.98, but exact recovery is 0.60–0.89.Source: §C.8 · p. 28

C.9 Noise distributions

  • Across five tested noise families, mean edge F-scores differ by at most 0.01 at every (d, ne), and all reach 1 at ne = 5 × 10^4.The oracle partition is fixed, so this experiment does not test the Welch shift test under heavy-tailed noise.Source: §C.9 · p. 28

C.10 Causal chamber: full results

In the light-tunnel causal chamber, the methods select hyperparameters and recover coarse edges with differing partition and adjacency outcomes. Additional experiments compare cutoff rules and how intervention designs affect identifiable resolution.

C.10 Causal chamber: full results

  • In grouped mode, coarse and RePaRe select looser-than-oracle partitions (ARI 0.93) but recover the same 2 of 4 true coarse edges with no false edges; in ungrouped mode, their selected hyperparameters match oracle choices.Table 4 reports selections and coarse-DAG metrics for coarse and RePaRe, alongside variable-level metrics for other methods.Source: §C.10 · p. 28, Table 4 · p. 33
  • In ungrouped adjacency recovery, every method exceeds chance; coarse and RePaRe have the highest precision, 0.86, and tie with UT-IGSP for highest recall.GnIES’s directed F-score is at chance, but its errors are in orientations; Table 5 compares adjacencies against a hypergeometric null.Source: §C.10 · p. 28, Table 5 · p. 34
  • Every data-driven cutoff rule except Bonferroni lands in the flat region of partition ARI, and cross-validation reaches the oracle without ground truth.The cutoff is selected from d·m Welch p-values; the figure compares partition ARI against the per-test cutoff.Source: Figure 5 · p. 29
  • With native multi-target interventions, resolution is lost when k > 1; overlapping targets from a pool of 20 nodes recover the lost resolution.In the native design, more environments refine ΠI faster than ΠE but hide fewer edges; the overlap design plots curves by k against the single-target reference.Source: Figure 7 · p. 30, Figure 8 · p. 31
Loading 2610.11947v1…