Causal Discovery over Clusters of Variables in Markovian Systems
Authors: Tara Vafai Anand
Adèle H. Ribeiro
Jin Tian
George Hripcsak
Elias Bareinboim
Venue: NeurIPS 2025 poster ()
Keywords: Causal Inference
Primary area: probabilistic_methods

Abstract: Causal discovery methods are powerful tools for uncovering the structure of relationships among variables, yet they face significant challenges in scalability and interpretability, especially in high-dimensional settings. In many domains, researchers are not only interested in causal links between individual variables, but also in relationships among sets or clusters of variables. Learning causal structure at the cluster level can both reveal higher-order relationships of interest and improve scalability. In this work, we introduce an approach for causal discovery over clusters in Markov causal systems. We propose a new graphical model that encodes knowledge of relationships between user-defined clusters while fully representing independencies and dependencies over clusters, faithful to a given distribution. We then define and characterize a graphical equivalence class of these models that share cluster-level independence information. Lastly, we present a sound and complete algorithm for causal discovery to represent learnable causal relationships between clusters of variables.

Causal Discovery over Clusters of Variables in Markovian Systems
Tara Anand
Adèle H Ribeiro
Department of Biomedical Informatics Columbia University
Institute of Medical Informatics
University of Münster
tara. anwandcolummia.ee...
adele ribeiroumii -mennster
Jin Tian
Mohamed bin Zayed University of Artificial Intelligence jin. tian@mbzuai. ac ae
George Hripesak
Elias Bareinboim
Department of Biomedical Informatics
Causal Artificial Intelligence Laboratory Columbia University ebêcs. columbia edu
Columbia University gh138cumc. columbia. edu
Abstract
Causal discovery methods are powerful tools for uncovering the structure of re- lationships among variables, yet they face significant challenges in scalability and interpretability. especially in high-dimensional settings. In many domains, researchers are not only interested in causal links between individual variables, but also in relationships among sets or clusters of variables. Learning causal structure at the cluster level can both reveal higher-order relationships of interest and im- prove scalability. In this work, introduce approach for causal discovery over clusters Markov causal systems. We propose a new graphical model that encodes knowledge of relationships between user-defined clusters while fully representing independencies and dependencies over clusters, faithful to given distribution. We then define and characterize graphical equivalence class of these models that share cluster-level independence information. Lastly, we present a sound and complete algorithm for causal discovery to represent learnable causal relationships between clusters of variables.
Introduction
Causal discovery, where observational data are used to uncover causal relationships between variables, is task of interest in many domains [13 19]. The goal in causal discovery is to data to learn as much information as possible about the underlying causal diagram, a graph that illustrates assumptions about the presence and direction of causal and confounding relationships between variables in system. One approach to causal discovery has been through constraint-based methods, where independence information, combined with logic regarding graphical properties, used determine structural properties of the graph, and constraints on possible causal diagrams that could correspond with the dataset [22] 13 [8]. Among constraint-baat based algorithms, PC is foundational algorithm for Markovian systems, where causal sufficiency, or the absence of latent confounding, is assumed [19] and there several extensions of this algorithm [1.5] 17]. FCI is the comparable algorithm for non- Markovian settings where unobserved confounding is permitted 266 20 and of which there are also
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Z1
Z1 Z2
X1
X1
11
X
W
W
(a) Gc,
(b) G1
(c) Pc.
(d) Gc
(e) G2
(1) Pc2
Figure I: DAGs (b) and (e) in the classes represented by C-DAGs(a) and (d). respectively. (c): an attempted graphical equivalence class for (a) after applying collider search test given distribution from G1- (f): an attempted graphical equivalence class for Gc, after applying a modified collider search test requiring X YiZ, and applying orientation rule, given distribution from G2-
several extensions
Typically, the data constraints are insufficient for uniquely identifying causal diagram. Instead, the graphical object of interest, and the output of causal discovery algorithms, an equivalence class of causal diagrams that fully encodes the data constraints.
In both Markovian and non-Markovian systems, however, existing algorithms are often computation- ally prohibitive with many variables and prone to errors in practice [8]. One approach to improve scalability in high eigh-dimensionl settings is to group variables into clusters and infer relationships between these clusters. In the context of diagrams constructed from knowledge used for identification of causal effects, Cluster Directed Acyclic Graphs (C-DAGs) [ are introduced as causal diagrams defined over clusters, allowing the visual representation of a nigh-dimensional system to be simplified and the requisite knowledge for graph specification lessened. In a C-DAG, nodes are clusters of vari- ables, and edge exists if variable in cluster causally influences variable in another. C-DAGs are assumed to be constructed based on partial knowledge of causal and confounding relationships between variables across clusters, oblivious variable-level relationships within clusters.
In this work, we address causal discovery over clusters of variables. We assume that the underlying causal model is a Markov DAG over individual variables V {Vi,....K, ....,) with no latent variables. Given a predefined partition of V into clusters C = (CI..... C we aim to learn causal rela- tionships between these clusters based on observed conditional (in) inieeeeneeneees between clusters encoded in the distribution P(C) P(C Cx) without access to variable-level relationships.
One might attempt to simply treat each cluster as multivariate random variable and apply existing [8]. However, consider the DAG G₁ and its corresponding C-DAG Gc, in Figure ((b) and ((a) respectively. Assuming probability distribution faithful to G1, PC will correctly construct the skeleton X Y, but observing the independence JL Y will lead to the collider structure Pc, in Figure [(c) clearly misrepresenting the true causal directions. In fact, X.IL
causal discovery algorithms like PC
we have both X JL Y and X Y Z according to G.. No DAG structures over clusters X Z Y simultaneously capture both independencies. This implies the need for
graphical object to represent (in (in)dependence information between clusters. Suppose we revise our collider test to only assign collider to triplet (X, Z, Y) when X IL Y and X KK Y/Z. Consider G2 and its C-DAG Ge, in Figure I(e] and I(d) respectively. In this context, our modified collider test allows correct determination of the collider structure X Z < Y (and other colliders). Applying the standard orientation rule that for triplet X + Z W, Z - W should be oriented as - W to reflect that (X, Z, W). yet oriented, must be non-collider again results in misdirected edge.
These somewhat surprising results illustrate the complexities of representing causal and independence relationships over clusters and show that naively applying existing algorithms like PC over clusters can lead to incorrect orientations. PC over individual variables learns a Markov equivalence class of causal diagrams with the same conditional (in den)ddeeneencees [19 20 9 22). represented completed partially directed acyclic graph (CPDAG) 66, 21 Analogously. for clusters, the goal is to recover Markov equivalence class reflecting the same (in)dependencies between clusters.
Summary of Contributions Our contributions are as follows:
1. In section 2 we define a new graphical object, oC-DAG (Definition 7) that, in addition to causal relations, explicitly represents all (in)dependence information over clusters. We define a new criterion for d-separation in aC-DAGs (Definition 8) which we show is sound and complete for extracting conditional (in (in)dependencies over clusters (Theorem M
2. section 3 we define Cluster Completed Purtially Directed Acyelic Graphs, or aC- CPDAGs, to represent Markov equivalence class of aC-DAGs (Definition 10 We

---

introduce a learning algorithm for sound and complete causal discovery over clusters to learn an aC-CPDAG by testing conditional (in)dependencies over clusters (Algorithm(]) I
1.1 Related work and Preliminaries
In the literature. clusters are mainly used as an intermediate step in learning a graphical equivalence class over variables. Typically, clusters of nodes sharing some properties are learned, then structures within or between these clusters are learned, and ultimately integrated into a graph over variables representing a class of DAGs [21 12
3 25 Prior approaches that learn structures over clusters either group variables heuristically based on structural similarity [10], assume clusters with strict internal structural constraints
16 . including where structures such as those in Figure [ are
disallowed [1 24), or consider only two clusters [23]. In contrast, we consider user-defined partition of variables and learn a structure representing cluster-level equivalence class.
Notation. A single variable is denoted by (non-boldface) uppercase letter X and its realized value by small letter x. A boldfaced uppercase letter X denotes a set (or a cluster) of variables. We use kinship relations, defined via edges in the graph. We denote by Pa(X)c- Ch(X) An(X)c. and De(X) c. the sets of parents, children, ancestors, and descendants in graph G, respectively. A triplet (Vi, Vi., V2) is active if 1) Ví is a collider and Vi or any of its descendants are in Z or 2) V/ a non-collider and is not in Z. A path p is said to be active given (or conditioned on) if every triplet on p is active relative to Z. Otherwise, is said to be inactive. Given a graph G, X and Y are d-separated by Z if every path between X and Y is inactive given Z. We denote this d-separation by (X IL Y Z) Learned Equivalence Classes. A completed partially directed acyclic graph (CPDAG) 9 can have either directed (-+ or undirected (-) edges. Directed edges are common for all members of the Markov equivalence class represented by the CPDAG whereas undirected edges are variant. A triplet of vertices (X, Y, Z) is unshielded if X and Z are not adjacent to cach other. If X and Z are adjacent to another, the triplet is said to be shielded. In consecutive triplet (X, Y), 0 is a definite collider if edges from X and Y are into it (X + Z + Y). is a definite non-collider if at least one edge is out of it (X < Z - Y.
Z - Y) or both edges undirected and the triplet is unshieleded (X - Z - -Y. Otherwise, Z has a non-definite status. Cluster DAG or C-DAG (M Given DAG G(V, E) and partition C (Ci,.... C&} of V, construct graph Gc Ec) over C with a set of edges Ec defined as follows: An edge C, + Cj is in Ec if exists some V, C, and V3 E C, such that V; Pu(V,) in G. If Gc(C, Ec) contains no cycles, then we say that C is an admissible partition of V. We then call Ge a cluster DAG, or C-DAG, compatible with G. The definition of d-separation over C-DAGs extends from that over variables and is elaborated on in Appendix A and [I]
2 oC-DAGs: a new graphical object for encoding causal relationships and (in)dependencies over clusters
2.1 Representing (in)dependence information over clusters
In DAGs, marginal and conditional (in)dependencies align consistently with structural edges and arrowhead orientations between variables. As d-separation rules familiarly show, for an unshielded triplet X, Z, Y. a collider structure exists if and only if X Y and X Jr Y Z. A non-collider structure exists if and only if X J. Y and X JI Z It is only possible for X Jr Y and X y. YIZ if the triplet shielded. The last combination of independence information, X 1 Y and X JL Y such that X and Y are adjacent as well as Z and Y, never occurs. With C-DAGs, ambiguity is introduced and the correspondence between graphical structure and independence information changes. Consider G, and G2 in Figure 2(a) which are both colliders over the clusters (X, Z, Y), but are each associated with distinct independence information. G3 and G. illustrate analogous behavior for non-colliders, whether chain or fork. Therefore, neither collider nor non non-collider structures over clusters can be singularly associated with specific independencies or dependencies, unlike with variables. Fortunately, the converse is true: certain independence tests can singularly inform structure, and we can leverage this property for learning over clusters in some cases. However, new representation is needed to ensure complete representation of independence information for structural inference.
3

---

Independence
Information
Y
X
Y
X
1 Y
Marginally Active Marginally Inactive
Structure over Clusters
Z
X
Z
X
Y
Z
X K Y
X il Y
Z2
Z2
Non-collider Collider
Conditonally Active
L Y z
4/
1
G1
G2
X
Z2
Conditionlly Innetive
Z
Zí
Z
X L Y
X
G3
X
G4
(b) Independence-are ares for marginal/ conditional independdence/éependenee combinations.
(a) Example DAGs representing non-colliders and colliders with possible independence information for clusters.
Figure 2: Graphical Structures and Representations of Independence Information.
2.2 A novel representation of independence information
We introduce a new semantic representation called "independence arcs" to graphically encode known independence information. These arcs explicitly convey independence information between variables, decoupled from ancestral relationships. We note that while the terms of "edges" and "arcs" are often used interchangeably to refer the connections between nodes in graph, we use the term "independence arc" to refer to a novel symbolic representation of an arc drawn between two edges of a cluster graph. The form and representation of the are conveys information about the conditional and marginal (in (in)deppendeciss of the triplet of which these two edges are part. This is in contrast to what we consistently refer to as edges, meaning the connections between nodes graph.
Figure ) shows the three new independence are markings and their meanings, defined formally in Definition 2 A break in the independence are indicates marginally inactive triplet, while an are without any break represents a marginally active triplet. A dashed are indicates a conditionally inactive triplet, while solid line indicates conditionally active triplet. Under this new representation, edges preserve their semantics with regards to conveying parent-child relationships between nodes, and independence information of a triplet determined exclusively through the independence arc.
Independence ares annotate both unshielded triplets, (C., Ck. Cj), where Cg is adjacent to both C; and Cj, and C₁ and Cj are not adjacent, and shielded triplets, (C,, C C3),, where C₁2 is adjacent to both C/ and C and C₁ and C²2 are adjacent. To determine the are for shielded triplet, we introduce the concept of manipulation of a shielded triplet where one edge of the triplet is removed so that the triplet can become unshielded, and the are describes the behavior of this induced unshielded triplet.
Definition 1 (Manipulation of a shielded triplet). Given shielded triplet over clusters (C,, Ck Cÿ), its manipulation involves removing the edge between C, and C, corresponding to removal of any edges between variables in these clusters. After manipulation, the shielded triplet becomes unshielded and this manipulated unshielded triplet is referenced as (Ce, Ck. C₁) -C.C..
Example 1: Consider Figure 3 Triplet (A, B. E) in Gc, is shielded. To manipulate the triplet, the edge A - E is removed, corresponding to removing the edge A - Fiz in G.. This manipu- lated unshielded triplet in Gc, is referred to as (A, B, E) -AE The complete process for adding independence ares to a graph is described below Definition 2]
Definition 2 (Independence Ares). Consider graph Gc over clusters C (Co.... Cn). For any unshielded triplet (C,, Ck. C₁) (or manipulated unshielded triplet (C,, Ck. C,) C,C,, let equal (possibly empty) set of clusters c (C)) (C., C2)) such that C₁ IL C,|S, such set exists. For a triplet (C,, Ck. C₁), an independence arc, A.,,C. E A can be drawn from some point on the edge between C; and C₁ to some point the edge between C₁ and C₁ in the following way: of
1. A marginally connectii independence Consequently, C, y C,(S ' Cb and C, L C,Cs
is drawn if and only if Cs S.
2. A iunditionally-connettin independence arc of -1l is drawn if and only if Cs $ S and C, J C,IS U Ct-
3. never-connecting independence are of -I|- is drawn if and only if Ct E S and
C IL UUJSUCK Ct.

---

XI
A1 B1
C1
22
B
WI W/
Q1
E1
Y1
Y/
CIFl
E2 E3 D1
E
A
Y33 RR1
R
(a) G1
(b) Gc,
(c) G2
(d) Gc.
Figure 3: G1 is DAG in the class of Gc, C-DAG (with Independence Arcs). Independence arcs encode (in)dependencies between clusters, for example that A J. D and A D.C. Gc, is a C-DAG (with Independence Ares and Separation Marks, or aC-DAG) and G2 is compatible DAG. Shielded triplets are annotated according to the behavior of their respective manipulated triplets.
Example 2: Consider DAG G1 in Figure 3 Unshielded triplets (A, B, C). (E, B, C), and (C, D E are marked with a -onnnecilyyconneeting arc, as are manipulated unshielded triplets (E, A, B) EBB and (A, B, E) AB, A conditionally caaiiiiionnllycooecttnnng are is drawn for (B, C. C,D). Never-connecting ares are added to triplets (A, E, D) and (B,E, D), and manipulated unshielded triplet (A, E, B) AAB
Lemma 1. In a Markov C-DAG with independence arcs, a conditionall-commett are always implies a collider structure.
independence
While collider structure X + Z + Y in C-DAG does not necessarily imply that X J.L. Y and X j YIZ, lemma I notes that the converse is true. Independence ares allow for d-separations to be read in new way, unrelated to edge connections. For an isolated triplet with clusters (C,, Ck. Cj), the triplet active (d-connecting) relative to the (possibly empty) set of cluster vertices Z if a) (C,, Ckyy C2) is marked with
independence arc and C $ Z or b) (Ci, C2, Cj is marked independence are and Cx E Z. Otherwise, (C,, C2 C₁) is d- separated relative to Z. In a larger graph, we introduce the notion of arc trajectories, or the sequence of independence ares corresponding to a path between two variables. Arc trajectories can be analyzed to determine if two variables are connected or not.
with a anditionalll-cconnctii
Definition 3 (Are Trajectory). Given a graph for some path over clusters (C,, C2, Cz.... C.). the are trajectory refers to the sequence of independence ares for each triplet along the path, a Ca.,....
C.C, I.C.))
Example 3: Consider the example in Figure 3 To determine if A and D are d-separated (A Jl D) in Gc,, we first identify all simple paths between A and D, of which there are three: A -> B - C D, A B E D. and A E D. The trajectory corresponding to the first path is AA,.B.C.BBBC.DD consisting of a marginally-connecnieo are. Because there is no conditioning set in the query, only AA.B. AA.B.C indicates an active triplet but not AB.C.D, and therefore A and D are not connected along this path. For the second path, the are trajectory is (AA,B,E. AB,ED) AA,BEE never-connecting arc, so A and D are not connected by this path either. The last path has the are trajectory AA. and its only independence are never- never-conn.cting. Therefore, we can conclude that A I. D. By similar analysis, we can conclude that A L DIC.
are and a conditionally-commecii
marginally-conneetingg arc, but AB, E is
With some simple examples, we illustrate that determining d-separations by independence arcs can sometimes be more complex. Consider Figure 3 From G2. the following independence information is clear: X J W and Ax z. W is conditionally-conncciio
are, Z H. Y/W, and Az, Az,w.y V.Y. Y is arc. Then the arc trajectory in Gc, from X to Y might lead us to believe that X L Y/W, but this is not true. Independence ares indicate information with regards of clusters, but alone, may misrepresent d-separation for paths over clusters. We enrich independence ares with a new semantic representation to denote unexpected independencies. We introduce a new symbol, Cc. which we call "separation mark." This mark annotates an independence are of triplet to indicate a cluster (specified by the subseript of the separation mark) further along on a path that, by independence arcs, would appear to have d-connection to the variables in the triplet, but is actually separated. This notion is formalized in definition 5 First, we define a supporting concept below.
triplet
Definition 4 (A (Anaogouss Paths). Given C-DAG Ge and compatible DAG G, we define simple path in G over variables, p= = (V1, V22 Va,.., Vmn to be considered analogous to a path in Gc over clusters PC = (C1, C2, C3 ..., C,)) (and pc analogous to p) if and only if the following hold: f)r
5

---

every variable Vi on P. V₁ is in some cluster C₁ on pc. for every cluster C3 on pc, there exists some variable V E Cj where Vj is on p. and for any variable Vn E C,, there does not exist any variable that appears after Vn on p that is in cluster before C2 pc.
In Fig. 3 the path over variables Pe- = (A1; B1, C1, D1) in G1 is analogous path for the path over clusters P.- = (A, L,,,,CC C, D) in Gc but the path over variables p', = (A1, B1, F1, E2, Es, D1) is not analogous to Po. since E is not on Pe but 3V. E E on py, and PV. E C on plu, but C is on Pe- Definition 5 (Separation Marks), Let G be a DAG, and let Gc denote a possible C-DAG G. Consider a path pC in Gc over clusters (C1, C2, C3,,..g Cn) and its corresponding are trajectory such that:
a =
1. there is are C.,, Ci+2 E a that is a never-connecting arc,
2. there is no d-connecting path p in G over variables relative some set of clusters Z, analogous to PC,
3. there exists d-connecting path pl in G over variables relative to some set of clusters Z' that is analogous the path p'C = (C1..... Cn-1) in Gc, and
4. there exists a d-connecting path p" in G over variables relative to some set Z" clusters that is analogous to the path Pc = (C2,.... Cn) in Gc., Then, a separation mark, Qc, is placed on the are Ac., 2.C., I,C.,, and a separation mark, Dc., is placed on the arc A2,,C
Example In Figure 3 we identify where a separation mark is needed by traversing paths of length greater than 3 in Gc, and compare to the paths over variables in G2. For example, traversing the path (X, Z, W, Y) in Gc, and comparing to G2. we see that there is no path between any variable in X and variable in Y. We place separation mark with the subscript Y, as in Øy, on the independence are of Ax,z. This indicates that when traversing a path starting at X where Ax,z. w in the are trajectory associated with the path, Y is separated from X (in addition to any nodes past Y on the path). We place a mirroring separation mark, 2x. along are trajectory Az, to reflect the reverse. Gc2 in Figure @ shows the C-DAG with independence arcs and separation marks. Further discussion on separation marks can be found in Appendix C
Separation marks indicate separations on paths masked by the clusters and independence arcs. Connections may also be masked if conditioning on descendant of a collider within cluster, where the descendant is in a different cluster from the collider. We introduce a new connection mark, which, like separation marks, annotates independence arcs. Specifically, a connection mark, @c, on an independence are Ac..c,.c denotes that the triplet (C;, Ck, C₁) is activated by conditioning on Ct due to some variable V₂ E C. being a descendant of some collider variable V22 E Ck.
Definition 6 (Connection Marks). Let G be a DAG and let Gc denote a possible C-DAG for G with independence arcs. Consider a triplet over clusters in Gc, (Ci, Ck2 Cÿ), and its corresponding independence arc, A.,,c. If Ac,,c,, is a never-connecting or conditionally independence arc, and there exists a path p in G over variables through the triplel (V.,.., Vk,, V2 such that V, C. V& Ck. and V; E Cj then VV₁ E C& and on p. where V2 a collider, let D be the set of clusters that are children of C2 and which include descendants of all colliders along the path, (D= = UfCa : Vi E Ca} where Va & {C,, C2. C₁} and Va E Ch((V))). Then the connection mark @D is added to C.C,C
Example 5: Consider again Figure 3 Collider Y2 in the triplet (Yi, Y2, Ys) in Gy not discemnibe in triplet (W, Y. R) in Gc., which is marked by never-connecting independence arc. However, conditioning on Q renders and W dependent. The connection mark @o is placed along are Aw,Y Y.R. R. as shown. Further discussion connection marks can be found in Appendix C
2.3 OC-DAG Definition and Properties
With the introduction of the new symbolic representations of independence arcs, separation marks, and connection marks we can fully define a new graphical model for C-DAGs with independence arcs, which we call cC-DAGs, for short. The "a" prefix will be used indicate graphical representations making use of the new semantics of independence ares, separation marks and connection marks. Definition 7 (aC-DDG (C-DAG with Independence Ares)). Given DAG G(V, E) and a partition C= (C,, Cn) V, construct graph Ge(C. C, Ec, A) over C.
An edge C, + Cj is in Ec if exists some Vi E C, and V3 E C, such that V, E Pa(Vi) in G:

---

The set of independence ares A is defined over all triplets (C,, C22 Cj), by Definition 2
For each are trajectory in Gc, separation marks are added according Definition 5
For each path in Gc, connection marks are added according to Definition 6
If for all pairs of clusters C₁ Cj where there exists un edge C, - C, there is no directed path C, -.... Cs then say that C is an admissible partition of V. We then call Ge cluster DAG with independence ares, or an aC-DAG, compatible with G.
As with the definition of C-DAGs, oC-DAGG assume acyclicity over clusters. Specifically, we disallow what we define as apparent directed cycles (or just apparent cycles). where edges over clusters give the appearance of cycle such that for some pair of clusters {C; Cý} there exists an edge C, - C and directed path C + + C, While Definition 7 takes as input DAG, we also note that construction of an aC-DAG could alternatively take as input C-DAG and probability distribution P(C) where P(C) is faithful to the true data-generating process. Knowledge would inform edge directions and P(C) would inform independence ares, separation marks and connections marks; the aC-DAG is still considered an object constructed from knowledge, rather than one that is learned.
D-separation over aC-DAGs can be determined according to the criteria below. In the theorem that follows, show these d-separation rules are sound and complete in oC-DAGs.
Definition 8 (d-separation over aC-DAGs.). A path pc in oC-AAG, Gc, is said to be d- separated (or blocked) by a set of clusters Z C C if and only if its corresponding are trajectory a contains independence arc Ac,,c,.C that is:
1. a murginally-connectinn independence are and (a) Cj is in Z or (b) there exists separation mark Oc, on Ac.,c..CC, where C₁ is on pc-
2. conditionally-commecti dant Co of C₁ (with directed and connecting path Cj- + - Ca) in Z. and for any connection mark @c, on Ac, C,, Cg is not in Z or (c) there exists separation mark on A...cu.c,, oc2 where C₂ is on PC-
and (a) C2 is not in Z nor is any true descen- independence
3. never-connecting independence are and for connection mark cc, on Ac,, C2 & Z.
Theorem 1. [Soundness and completeness of d-separation in aC-DAGs.] In an oC-DAG Ge, let (X, Z, Y) E C. X and Y are d-separated by Z. in Gc if and only for any DAG, G, compatible with Go. X and Y are d-separated by Z in G. (X 11 Y Z)Ge = (X 1.Y. Y Z)
This d-separation definition informs how (in)dependencies can be read over clusters in an aC- DAG. The novel graph of an aC-DAG represents knowledge of both connections between and (in)dependence information over clusters. In the next section, we build on the a-CDAG semantics introduced here to define a new graphical object foundational for learning over clusters.
3
cC-CDDASs and learning
3.1
Equivalence classes of aC-DAGs
As with other causal discovery algorithms, our approach to learning over clusters will result in graphical equivalence class of compatible models, specifically an equivalence class of aC-DAGs. This equivalence class will represent the class of graphs, over clusters, that share the same independence structure induced, and the associated graphical object is analogous to a CPDAG, which uniquely represents a Markov equivalence class over variables. We define this novel graph as a cluster CPDAG, or aC-CPDAG. In this section, we define the relationship of this object to aC-DAGs and describe how aC-CPDAGs can be learned from observational distribution.
Two DAGs, G1 and G2 with the same vertices are Markov equivalent if for any three disjoint sets of vertices X, Z, Y, X and Y are d-separated by Z in G2 if and only if X and Y are d-separated by Z in G2. We extend similar notion for clusters and aC-DAGs in Definition g From the definition of d-separation for oC-DAGs, we know that such separations are discernible from independence ares, separation marks and connection marks, which leads to the theorem following the definition. In aC-CPDAGs, it may not always be possible to determine the independence ares associated with each manipulated unshielded triplet within shielded triplet. In this case, is possible for any are to exist, and all corresponding graphs included in the equivalence class represented by the aC-CPDAG.
7

---

Uw
Eww
Z
Z
Z
Z1
22
Z3
Eww
X
YI
X
YI
X
W
W
R1
R
R1
R
Q1
Q1
(a) G1
(b) Gc,
(c) G2
(d) Gc2
(e) Pc
Figure 4: G1 and G2 are DAGS in the classes aC-DAGs Go, and Gc respectively, Gc, and Gc2 are in the Markov equivalence class of aC-CPDAG, Pc. In Pc, Ro is applied to (X, R, Y), and then 11 applied to (X, R, Q). Lastly, 3g is applied to (X, Z, Y) with descendant W.
Definition 9 (Cluster Markov Equivalence), Two aC-DAGs, Gc, and Gc. (with the same partition over the variables V) are cluster Markov equivalent for any three disjoint sets of clusters X,Z,Y, X and Y are d-separated by Z in Gc, iff X and Y are d-separated by Z in GC. Theorem Two aC-DAGs, Ge, and Gc, (with the same partition C over the same set of variables V) are cluster Markov equivalent if and only if they share the same: 1) adjacencies, 2) independence ares, 3) separation marks and 4) connection marks.
Figure illustrates example DAGs and aC-DAGs in the same cluster Markov equivalence class. Markov equivalent aC-DAGs share some unshielded colliders, namely those marked by a conditionally-coonnttin arc. This characterization of equivalent aC-DAGs leads to the definition of the cluster CPDAGs (oC-CPDAGs). As with partially directed acyclic graph, an aC-CPDAG may contain both directed and undirected edges and does not contain any directed cycles. As with aC-DAGs, an aC-CPDAG defined over user-defined partition of clusters C over the variables V. Definition 10 (aCluster CPDAG). Let [Ge] be the Markov equivalence class of an arbitrary aC- DAG, Gc. The cluster completed partially directed acyclic graph (aC (aC-CPDAG) for [Gc], denoted P. is defined such that:
1. P has the same adjacencies as Ge (and therefore any member of [Gc])
2. directed edge P isf shared by all oC- &C-DAGs in [Ge]; otherwise the edge is undirected.
3. An independence are is in P iff shared by all aC-DAGE in [Ge]; otherwise there is no arc.
4. P has the same separation and connection marks as Gc (and any member of (Gel).
3.2 A Constraint-Based Learning Algorithm for cC-CPDAGs
Given definitions of the relationships between aC-DAG and DAG, and aC-CPDAG and an aC-DAG, we can develop an approach for the reverse process of constructing an aC-CPDAG from (in)dependencies in an observational dataset. Algorithm I Causal Learning Over Clusters (CLOC), defines this procedure. CLOC assumes that an available distribution P(C) (or data representing it) is faithful the true aC-DAG (see definition and that partition C admissible. Figure illustrates an cC-CPDAG learned by the algorithm.
Definition 11 (Faithfulness for oC-DAGs). Given an aC-DAG, Gc, and probability distribution over the clusters, P(C). that is generated by an SCM consistent with any causal diagram compatible with Gc, we say that P(C) is faithful Ge if (X 1L Y
(X LYZ) P(Gc)
CLOC has three phases. In the first, edges between pairs of nodes, X and Y, are removed from complete graph with undirected edges if there exists some separating set of clusters such that (X Y|S). Independence ares are added and colliders are determined from conditionally-comet connecciingnnniii ares (Lemma]) D). In the second phase, separation marks, and connection marks are added. In the final phase, five orientation rules are evaluated until none apply. Rules 1, 3 and 4 extend from PC, leveraging independence ares to determine where the logic is sound. Rule 2 extends precisely, and Rule is our contribution. This algorithm gives us an aC-CPDAG, which represents the cluster Markov equivalence class of aCCDAAGs compatible with the distribution P(C). We review rules below with proofs in Appendix B. After, we demonstrate that the orientation rules and the learning algorithm are sound and complete for learning causal relations between clusters. Note that in the orientation rules, asterisks indicate either arrowhead tail is possible.

---

Lo: If - Z Y and Ax,z,Y is ceciitionalll-coonecitii then orient the triplet as X - Z t- Y
81 X -Z-Y, Y. and are not adjacent, and Ax,2, Z. is marginally-coomeetingg then orient the triplet as X + Z Y.
2: X Z - Y and X Y, then orient X Y as X Y.
Algorithm 1: CLOC: Algorithm for Learning an aC-CPDAG
Input: Admissible partition C (Ci...., C.), P(C)
Output: aC-CPDAG, P
1. Determine skeleton, separation sets, independence ares, and identifiable colliders by Algorithm 2
2. Add the separation and connection marks by Algorithm
Apply the orientation rules until none apply.
Algorithm 2: CLOC: Adjacencies and Independence Ares
Input: Partition C [Ci,... (0,,,....,. C
16 for every shielded triplet (X, Z, Y) in P with adjacent to some W and X not adjacent to W do
Output: aC-CPDAG, P
Form complete graph over C with undirected edgesas for X, Y C do
if Az. is
cettiiioalll-oonncctt Ax. Y.W is then
and
S _ C Y) do if P(y 8. = P(y s) then SepSet + S, SepFlag + True, break
17
Z E SepSet(X, W) then -) marginally-connecting are
Mark (x. Z, Y) -XY in P with
if SepFlag = True then Remove the edge between X, Y in P
18
else
Mark (X, H,Y, Y) XY in P with
never-connecting are
for every unshielded triplet (X, Z, ) in P do i & SepSet(X, Y) and X L Y IZ (e, Y) then
clse A w is marginally-comneciin and
Ax Y, w not then
10
Mark (X, Z. Y) in P with
if Z & SepSet(X, W) and X J. W Z SepSet(X, Y) then
cuniitionally-conneen
are, and orient as
Mark (X, Z, Y) 3y--Y in with a conditinnally.coneede
X Z
23
arc, and orient
11
else Zf (X, Y) then
X + Z +
12
Mark (X, Z, Y) in P with
marginally-conneccingg are
if E SepSet(X, W) then Y)-XX
Mark (x, Z, Y) -XY in P with
13
else
marginally-connecci
14
Mark (X, Z. Y) in P never-connecting
are
26
else
Mark (X, Z, Y) -XY in P with
never-connecting are
Algorithm CLOC: Separation and Connection Marks
Input: Admissible partition C (CI..., P(C)
Output: aC-CPDAG. p
for each path p (Co.... C.) E do
for each triplet (X, Z. Y) do if Ax,2, is conditionally or never connecting are and 3 some W such that Z W, X and W not adjacent, Y and W are not adjacent then
tength(p) (p) 2 4 and are trajectory a for p is only 9 marginaa/condiiioonlll.com conneciinnn ares (with no marks dc. where C. E p) then
Let K UKC, Acz.c..cy a is conditionally-comeetnng
10
Let Wz +- (W
W exists in P)
if C. 1L C. K (SepSet Co. C.) (p)) then
Let S be the power set of Wz \0 for each subset D E S do
For shortest subpath p' (C.,... C₃) S.s.t. length(p') 2 and C, Il C, KU (SepSel(CCo, (p) Add @c, to Ac, Add 0c, to Ac,
i y. Y D SepSet(X, Y) then Add OD to Ax.2.Y
14
Mg: If - W Y, X and Y are not adjacent, W Z, and Ax. N.W.Y marginally- connecting, then orient W Z as W + Z.

---

Smacuae sarving Ditaace Number Clarars
Conditee incppencecc 1013 fumbbrr
10:
120
(a)
(b)
(c)
Figure 5: Plots comparing the (a) Structural Hamming Distance, (b) runtime, and (c) number of mnddtiionllinnependdee tests for CLOC (blue) compared to the PC-then-cluster approach (orange).
R1 X Z Y. X W Y, X and Y are not adjacent, W *-* Z. and Ax,w,Y is marginally-comnectingg then orient W Y as W Y.
33: Xf *-* Z x Y, Z - W, X and W are not adjacent, Y and W are not adjacent, and Ax,Z,Y never-connecting or conditionally-comnettig with connection mark @D such that W E D, then orient Z - W as - W.
Theorem 3. /Soundness and Completeness of Orientation Rules and CLOC) The five orientation rules and the procedure of CLOC are sound and complete.
4 Experiments
We show performance CLOC in comparison to 'PC-then-Cluster" approach, where PC over the entire set of variables is run with variables then grouped by the partition, yielding a graph over clusters. We generate random C-DAGs (3, 5, 6. 7. clusters), and random DAGs (4, 8, 32, 64, 128, 256 variables) compatible with the C-DAGs. A Gaussian distribution (1000, 3000, 10000, 30000 samples) faithful to the DAG is drawn, over which (C-then-Cluste and CLOC are run. Runtime, conditional independence test counts, and structural hamming distances between the resulting graphs of each method and the true C-DAG are shown in Figure Design details, implementation code, and additional results included in Appendix D PC requires exponentially more independence tests relative to CLOC. Runtime is also improved for CLOC. More efficient multivariate independence tests can lead to greater runtime improvements for CLOC. The structural hamming distances of the graphs generated by PC and CLOC differ in expected ways (see discussion in Appendix D)
5 Conclusions
In this work, we address the need for causal discovery over clusters Markov causal systems. We introduce aC-DAGs, which capture both causal directions and (in)dependence information over clusters, setting the stage for introduction of aC-CPDAGs, an equivalence class of aC-DAGs and the graphical object representing the class of cluster graphs with shared (in dinddeeenesncis and orientations. We then propose a sound and complete algorithm, CLOOC to learn this new graphical equivalence class from data, capturing much of the information that could be learned from variables, with fewer independence tests and faster runtime. Limitations the approach include assumptions of causal sufficiency and faithfulness which may not apply for all applications. Users are required to have knowledge of a partition of variables into clusters that does not induce a cycle, which is non-negligible, while feasible for many applications including in clinical and biological domains, where partitions often arise naturally and may correspond to laboratory panels, gene sets, microbiome groups, neuroanatomical regions, or demographic blocks. While tests over clusters may have lower statistical power or be slower than those over individual variables, this can be effectively mitigated by advances in multivariate testing (e.g., Mantel Test), and modern machine learning- based methods that reliably assess independence between multivariate distributions. The foundational work introduced here sets the stage for improved scalability and makes possible causal discovery for sets of variables.
10

---

Acknowledgements
This research supported in part by the NSF, ONR, AFOSR, DoE, Amazon, JP Morgan, The Alfred P. Sloan Foundation, the United States National Library of Medicine grants (T15LM007079, ROILM006910).
References
[1] Tara V. Anand, Adèle H. Ribeiro, Jin Tian, and Elias Bareinboim. Causal effect identification in cluster dags. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 22172-12177 AAAI Press, 2023. doi: 10.1609/aaai. w37..00.64113313333
[2] S A Andersson, D Madigan, and M D Perlman. A characterization of (M)arkov equivalence classes for acyclic digraphs. Annals of Statistics, 24:505-541, 1997.
[3] Bryan Andrews, Peter Spirtes, and Gregory F. Cooper. On the completeness causal discovery in the presence of latent confounding with tiered background knowledge. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4002-4011, PMLR, 26-28 Aug 2020. URL htttps//proocedding mlr
www.annweeaaaaaeeommmmmama http://100//addeee22a..aa.. press/v108/
[4] Shaofan Chen, Yuzhong Peng, Guoyuan He, Hao Zhang, Li Cai, and Chengdong Wei. Cdse: Causal decomposition based on spectral clustering. Information Sciences, 657: 119985, 2024. ISSN 0020-0255.
doi: https://doi. 10. com/ http:///iiieeeee....ea////////// http::://wwwww.ienceeeeeeeeeeeee http://wwwoaoootoot..//oo///////
URL
[5] Wei Chen, Yunjin Wu, Ruichu Cai, Yueguo Chen, and Zhifeng Hao. Cesl: A causal structure 2021. URL
learning method from multiple unknown enviromments. ArXiv,
https://api. semanticscholas htt.aaarrrrrg/oorsssiii::2/
244346148
[6] David Maxwell Chickering. Learning equivalence classes of bayesian-networf structures. Journal of Machine Learning Research, 2:445-498, 2002. doi: 10.1162/1332330766000000
[7] Diego Colombo, Marloes Maathuis, Markus Kalisch, and Thomas Richardson. Learning high- dimensional directed acyclic graphs with latent and selection variables. Annals of Statistics ANN STATIST, 40, 04 2011. doi: 10.12 1214//1 1-AO9940
[8] Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers in Genetics, 10, 2019.
[9] Meek. Causal inference and causal explanation with background knowledge, In P. Besnard and Hanks, editors, Uncertainty in Artificial Intelligence 11, pages 403-410. Morgan Kaufmann, San Francisco, 1995.
S.
[10] Xueyan NIu, Xiaoyun Li, and Ping Li. Learning cluster causal diagrams: An information- theoretic approach. In Lud De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 4871-4877. International Joint Conferences Artificial Intelligence Organization. 7 2022. doi: 0.24963/jcai.202224775 URL https:///oi..oo org/10g.//111 10. 2492349933// jjaaiiccaaiaa 2022/675 220422/61..222222/6755 Main Track.
[11] Pekka Parviainen and Samuel Kaski. Learning structures of bayesian networks for variable groups. International Journal Approximate Reasoning, 88: 10-127, 2017. ISSN 0888-61 13X. doi: https://ooi.rr//10.101100 ija.. 006. URL httph: wwwp://wwwww/cccoo// wwweeeedieeeccc.ncccc.r.... com/
[12] Sepideh Pashami, Anders Holst, Juhee Bae, and Slawomir Nowaczyk. Causal discovery using clusters from observational data. In Proceedings of the FAIM' 18 Workshop on CausalML, Stockholm, Sweden, July 2018. FAIM. URL URL/https:// ltttps://urn..... kb. se/ www.resolvvrrrnuunn.. se:hh: din:diiva-9225 Refereed Conference Paper.
[13] Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, NY,
USA, 2nd edition, 2000.

---

[14] Adèle H. Ribeiro and Dominik Heider. dcfci: Robust causal discovery under latent confounding. unfaithfulness, and mixed data, 2025. /ttp wwtp://....bb.......//// 06542
[15] Fabrizio Russo and Francesca Toni. Shapley-pc: Constraint-based causal structure learning with shapley inspired framework, 2025. URL
11582
[16] Eran Segal, Dana Pe' er, Aviv Regev, Daphne Koller, and Nir Friedman. Learning module networks. Journal of Machine Learning Research, 6(19):557-588, 2005. URL/ttpp://jmlr org/papers/vbt setp//egaa55500 html
[17] Arjun Sondhi and Ali Shojaic. The reduced pe-algorithm: Improved causal structure learning in large random networks. Journal of Machine Learning Research, 20(164): 2019, URL
http://jmlr. org/papers/vv2017- 601.mmll
[18] Spirtes, N Glymour, and Scheines. Causation, Prediction, and Search. MIT Press, Cambridge, MA, 2nd edition, 2000.
[19] Peter Spirtes, Clark N Glymour, and R Scheines. Causation, Prediction, and Search. Springer- Verlag, New York, 1993.
[20] Peter Spirtes, Christopher Meek, and Thomas Richardson. Causal Inference in the Pres- ence of Latent Variables and Selection Bias. Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, pages 499-506, 1995. ISSN 0717-6163. doi: 10.1007/51339--014-0777
[21] Chandler Squires, Annie Yun, Eshaan Nichani, Raj Agrawal, and Caroline Uhler. Causal structure discovery between clusters of nodes induced by latent factors. In Bernhard Schölkopf, Caroline Uhler, and Kun Zhang, editors, Proceedings of the First Conference on Causal Learning and Reasoning, volume 177 of Proceedings of Machine Learning Research, pages 669-687, mlr wttppss//////squueesssseeeee
PMLR, 11-13 Apr 2022. URL ttttps://proceetie
html
[22] Thomas Sadanand Verma and Judea Pearl. An algorithm for deciding if set of observed independencies has causal explanation. In D. Dubois, M.P. Wellman, B. D' Ambrosio, and P. Smets, editors, Proceedings the Eighth Conference on Uncertainty in Artificial Intelligence, pages 323-330. Morgan Kaufmann, Stanford, CA, 1992.
[23] Jonas Wahl, Urmi Ninad, and Jakob Runge. Vector causal inference between two groups of variables. In Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence, AAAAAI23AAAAAT2//AAAAAA. doi: (01.60//aaaa..3711.02.....
AAAI Press, 2023. ISBN 978 --7-1-57735-880000 1609 aaai v37110.
URL https
7
[24] Jonas Wahl, Urmi Ninad, and Jakob Runge. Foundations of causal discovery on groups of variables. Journal of Causal Inference, 12(1 200)3020300 2024. doi: doi:
https:/tt::///ii org/ 10. 1515/jciiiiiee 1a155//jiii222233 200--022000000 0041
[25] Raanan Yehezkel and Boaz Lerner. Bayesian network structure learning by recursive autonomy identification. Journal of Machine Learning Research, 10(53):157711570, 2009. http/
/ wwwelr.org//ppeeee paaapersvio//aee v11/yyeeeeeel09a...m html
[26] Jiji Zhang, On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16):183--189, 11 2008.
[27] Yujia Zheng, Biwei Huang. Wei Chen, Joseph Ramsey, Mingming Gong, Ruichu Cai, Shohei Shimizu, Peter Spirtes, and Kun Zhang. Causal-learn: Causal discovery in python. Journal of Machine Learning Research, 25(60):1 2024.
12

---

List of Appendices
Additional Background
13
Proofs
13
Further discussion DDG semanties
18
On separation marks, connection marks, and graph interpretation)
18
On relaxing the assumption of acyclicity
19
On the special case of clusters of size
20
D Experimental details and additional results
20
D.I Experimental Setup
20
D.2 Additional results
21
Complexity Analysis
22
A
Additional Background
A.1 d-Separation in C-DAGs
The definition of d-Separation in C-DAGs, introduced in [1, provided below.
Definition 12 (D-Separation in C-DAGs). A path p in a C-DAG Gc is said to be d-separated (or blocked) by set of clusters Z C. C if and only if contains a triplet
1. C Cm Cj such that the non-collider cluster Cm is in Z,
2. C + C. C such that the collider cluster C. and its descendants are not in Z.
A set of clusters Z is said to d-separate two sets of clusters X, Y C C, denoted by (X IL Y Z) if and only if blocks every path from cluster in X to cluster in Y.
This definition, in the context of triplet (C,, C.., C₃) reflects that C, and C, are d-separated by Cm if and only if all paths over variable through the clusters of the triplet are d-separated by the set of variables cluster C.n-
B Proofs
Lemma 1. In Markov C-DAG with independence arcs, conditionally.comecting independence are always implies a collider structure.
Proof. Consider unshielded triplet Ck, C2)) such that Ac,,c.,c, is conditionally- connecting independence arc. This implies that C, IL C, \ CRi C, V C₁IC& US where S separating set for C; and C,. Then there must exist some path, p = V...., Ve....V, where V, C, Vi E Ck. and V, C,, such that every non-endpoint node is collider. In Markovian cases, this can only occur if there is only one non-endpoint. Therefore, Vi, must be the only non- endpoint node follows that no additional variable in C₁ can act as a cause of any variable in C, or Cj. Therefore, langleCi, Ck. C2) must follow collider structure.
p such that V& is collider. Moreover, due to the admissibility of the partition,
Theorem 1. /Soundness and completeness of d-separation in oC-DAGs.] In an cC-AG Gc. let (X, Z, Y) C. X and Y are d-separated by Gc if and only for any DAG, G, compatible with Gc. X and Y are d-separated by Z in G. (X Al Y Z) = (X 1 Y Z)c.
13

---

Proof. First we prove the soundness of d-separation by showing that if X and Y are d-separated by Z in Gc, then, any DAG, G, compatible with Gc, X and Y are d-separated by Z in G. We show by contradiction. Assume X and Y are d-separated by Z in Gc but in some compatible DAG, G, there exists a path p between a variable X X and Y E Y that active when the set of variables contained in cluster Z are conditioned on. By the preservation of paths and adjacencies, no connection is destroyed through clustering, so p in G is contained in a path PC of Gc between clusters X and Y. Since X and Y are d-separated by Z in Gc. PC is blocked, and X and Y are not adjacent. Therefore, by definition [8] there is at least one triplet of clusters in PC that indicates a block on the path. Let this triplet be (C,, Cm: C3), and let its associated independence are be Ac.,cmm.C, where C. is distinct from X and Y. Consider the subpath Pij of p contained in the triplet (C;, Cm. Cj) in pc. Since is active by assumption, every subpath of p is active, including Ptj. The triplet (C;, Cm, C2) indicates a block on the path either if 1) Ac,,c such that C2 E Z. 2) if Ac. C,. is a marginally-connectiin are where Cm E Z. 3) if Ac..c..c. a conditionally-connectim
is never connecting are with no connection marks Sc,
are such that Cm & Z and with no connection mark @c, such that Ca & Z or 4) if there is a separation mark Oc, on Ac, C,, such that C₂ is on pc. In case 1, Pij cannot be a connecting path or collider path so Pıj would be inactive. In case 2. Pij cannot be a collider path, and since C.. E Z. Piy cannot be active. In case 3, Pij cannot be connecting path and since C., & Z and for any connection mark @c., Ca & Z. Pij cannot be active. In case 4, definition are such that C. & Z, or if Ac,.c...
5 states that if Ac..c...c, is a marginally-connectiin a conditionally-connin con.eccingnnnnnggggooo are such that C. E Z. then P.y may be active, but since Ac, C, is marked with separation mark Zc_, there must exist some sub-path Piz of p from some V; E C, to some V2 E C, such that C, is on PC that is inactive. Therefore, p must be inactive, there is a contradiction, and we conclude that if X and Y are d-separated by Z in Gc. then, in any DAG, G, compatible with Gc, X and Y are d-separated by Z in G.
is
Then, we prove the completeness of d d-separation by showing that if X and Y are d-separated by Z in a DAG G, then X and Y are d-separated by Z in a compatible oC-DAG Gc. We prove by contradiction. Assume all paths from some X E X to some Y E Y are blocked by Z in some DAG G. but X and Y are not d-separated by Z in Gc, i.e. (X A Y|Z) If all paths from any X X to any Y E Y are inactive by Z, then by preservation of paths and adjacencies, X and Y are not adjacent in Gc. No connections are destroyed through clustering so any p in G is contained in path pc of Gc between clusters X and Y. Because X JL Y Z in Gc. by Definition 8 there must exist some path Pc such that 1) for any triplet (C,, C... C2) on pc, the independence are Ac.,cm..C marking it must not be marked by a separation mark Øc, where C₁ is on pc, 2) for all Ac..c...c,
ares C. & Z, 3) for all conditionally connecting ares C. E Z, or C, is marked with a connection mark @c, and C. or true descendant in Z, 4) for all never-connecting arcs, C...c. is marked by a connection mark &c, and C2 or true descendant is in Z.
For all paths from some X E X to some Y E Y in G to be blocked, there must exist at least one triplet, (V,, Vm, Vj), contained either within I cluster (i.e. (V., Vnn V2) E Cm)) or between 2 (i.e. (V. Vm)) E Cm. Vj E C or V; E C, (Vm, Vj) E Cm) or 3 clusters (i.e. V; E C,, Vm E &C.. Vj E C2) on pc. that is blocked.
1. If the blocked triplet is a non-collider, V + VM -V or + be in Z, which implies that C, E Z. As there could be multiple paths through cluster, the triplet over clusters, (C,, Cm, C,)) could still be marked by any independence arc.
V.-VV V. + Vg. then Vm must
(a) If Ac..cm..c is a marginally-conneetino there is contradiction with the implications of (X J Y/Z)
are or never-connecting arc, since C. E Z.
(b) If Ac..c..c., is a conditionalll-coomeeii path, p', over variables through the triplet from some some V E C, V/ E Cj through Cm that is a collider path. Because C. E Z, either there is no X E X or YE Y on p' there must be another triplet, Vy, V,, V... on p' that is blocked.
are, then then there must exist a different
2. If the triplet is a collider, V/- + Vm + Vy. then Vm nor any of its descendants, Va can be in Z, implying that C. & Z and Ca & Z where Va E Cd and Ac. is marked with the connection mark @c,,
(a) If Ac. is over variables through the triplet from some some V/' E C, to V E C, through C.n.
are, then there must exist a different path, p'.
14

---

that is a connecting path. Because Cm & Z. either there is no X E X or Y E Y yn or there must be another triplet, v4 Vr V. on p' that is blocked.
(b) If Ac, C.....C is a conditionalll--comeeiii Cm & Z. and there is a connection mark &C.,, Ca & Z, there is a contradiction with the implications of (X J. G|
are or a never-connecting arc, because
For any path p' with blocked triplet (V,, Vr, Vw., either one of the conditions above leading to contradiction (case la or 2b) applies, or there is a contradiction because a separation mark must exist along the path pc. By definition [ the separation mark would be required because by assumption, all paths between any X E X and Y E Y are blocked by Z in G, so it is not possible for there to be Pc Gc. However, p a d-connecting path relative to Z analogous to P'c (C;. ..... C,) and p' is a d-connecting path relative to Z analogous to PC (Cm..... C.... so by definition 5 the criteria is met and a separation must be placed.
a d-connecting path relative to Z in G anallgous
If X and Y are d-separated by Z in G. it is also possible that there is no path from any X E X to any Y E Y, and Z would equal the empty set. In this case, by preservation of adjacencies, for any triplet (C;; Cm, C2) along Pc, there must be some Vi E C; adjacent to some Vm E Cm. and some V%2 E Cm adjacent
some V2 E Cj. Then, there must exist some such triplet where Vnn is not adjacent to V", If for all Vn and V", in Cm. Vn and V", are not adjacent, then Ac. must be marked with sever-connecting are in Gc with no connection mark, and there would be contradiction with the implications of (X y Y ZZ) Otherwise, because X and Y are d-separated by Z in G, there must exist some connecting subpaths of pc, C.,... Cn and C,+1,..., C,, + 1 such that C, IL Cn+1. which, by definition 5] necessitates a separation mark and then there would be contradiction with the implications of (X I Y|Z)
Theorem 2. Two aC-DAGs, Gc, and Go, (with the same partition C over the same set of variables V) are cluster Markov equivalent if and only if they share the same: 1) adjacencies, 2) independence ares, 3) separation marks and 4) connection marks.
Proof. The proof follows directly from the definitions of cluster Markov equivalence, and d-separation for aC-DAGs. Because d-separation is determined solely by the independence arcs, separation marks, and connection marks in a graph for a series of adjacent clusters, two aC-DAGs with the same adjacencies, independence arcs, separation marks, and connection marks will necessarily lead to the same d- sesparrttions between clusters and will therefore be cluster Markov equivalent.
Theorem 3. [Soundness and Completeness of Orientation Rules and CLOC] The five orientation rules and the procedure of CLOC sound and complete.
First we prove the completeness of the arc assignment procedure, the soundness of the collider search and each of the five orientation rules. We then establish orientation completeness by showing that, whenever no more rules can be applied, there exist two Markov-equivalle orientation of any undirected edge. The proof for the soundness and completeness of CLOC follows. First, we introduce two remarks complementing lemmal] [ and an additional associated lemma.
aC-DAGs that differ in
Remark 1. In a Markov C-DAG with independence arcs, a marginally-commecting inleependence are always implies a non-collider structure.
Proof. We prove by contradiction. Consider an unshielded triplet (C,, Ck, C2) such that Ac,, is a manginally-connection necessarily leads to a contradiction. By definition of have C, f C,IS C2: C, 11 C2 S where S is a separating set for C2 and Cj. Assume that the structure over clusters forms a collider, C₁- + C2 + C,. There are two possible cases: either there is no path at all between C, and C, through C₁. or such path exists. If no such path exists, then the dependence implied by the marginally-conneetino to contradiction. If there exists a path between C; and C, through Ct, then, since C, is assumed to point to Cg, there must be a pair of nodes V, C, and V E C₁ on p such that VÚ2 + Vi. By the admissibility of the partition, an edge of the form V, < V is not allowed. To preserve the marginal independence are AC,,Cu.C. every subsequent
independence arc. We show that orienting the triple as C, + C + C wwrgiinally-conncttie
independence arc, we
independence are Ac,,c, cannot hold, leading
dependence implied by the marginally-connectinn edge between Vi, Vi++1 E C₁ along the path y must be of the form V/2 + V2+1- Ötherwise, collider would be introduced, rendering the path inactive and violating the assumed marginal dependence, leading to a contradiction. Now, because C2 + C,, there must also exist some Vj E C, and some
15

---

Vi E C2 such that V < V3 where V is on Because of the assumption of the admissibility of the partition, there can be no edge V' + V,, Then there must exist a collider and there a contradiction. Therefore, the triplet (Ci, Cū, Cj) must be non-collider.
In Markov C-DAG with independence arcs, never-connecting independence arc could imply either a collider or a non-collider structure.
Remark 2.
Proof. Consider a triplet (C,, Cs. Cý) such that C,,, is a never-connecting independence are. This implies that C; IL C S Cg: C IL C where S is separating set for C, and C, Then either there is no path from any V2 E C, to some V3 E C, through Ck. or every such path p must include at least 4 nodes, p V ...g Vkg Vog...., V2 where V, E C. VE, Vay. E Ck. and V2- E Cj, such that there is at least one collider triplet and at least one non-collider triplet on Consider the latter case. Let p be a path of exactly 4 nodes (V, Vk,, Vkg: Vj} such that V; C,, VE,, Vhg E Ck and V E Cj Either Vs, is collider node and Vkg is a non-collider node or Vh, is a non-collider V
node and Vi, is a collider node. In the first case, V; - Vv, t Vkaa + V2 or V; + Vis, < In the second case, Vi + Va, + Vi, + V or V; < Vk, + Vig Vj. Then (C;, Cj, Cÿ) may be either a collider or a non-collider. Adding any additional node, Vk,+1, to p either creates additional collider or an additional non-collider, but still allows for collider and non-collider structures over clusters. Now consider where there is no path from any V2 E C, to some V, C, through Cx. Then the direction of any edge V; - V& or V/ Vj can be variant such that (C,, Ck. C2) may be either a collider or a non-collider.
Lemma For a distribution P(C) over clusters C = (C,...., C.)) such that for every tripler (C,, Ck, Cj), Ac,,c. CC..C.CC is not a never-connecting independence arc, the orientation rules reduces to Meek's 's rules [9] and the PC algorithm 19
Proof. The proof follows from noting that modifications to Rules and require independence ares aligning with the independence information typically associated with colliders and non-colliders over variables, and from lemma I. and remarks T and 2 The absence of gever-connecting ares ensure triplets exhibit expected behavior with regards to structure and observed independencies and dependencies. When there are no never-connecting ares, Rule reduces Rule 1, as all triplets marked with conditionally-commectiio
ares must be a collider, and any descendant of that collider is part of non-collider triplet, so will be oriented by Rule 1. When there are no never-connecting ares and there is no background knowledge, Rule 4 never applies, following from Meek, 1995 [9. L
The procedure in Algorithm 2 for assigning independence ares is sound and complete. The procedure for assigning independence ares to unshielded triplets follows directly from the definitions of the arcs. We show that the procedure for identifying ares for manipulated unshielded triplets is sound and complete, below.
Proof. Consider shielded triplet (X, Z. Y) and manipulated unshielded triplet (X, Z, Y -XY In isolation, no independence are can be assigned to (X, Z, Y) XY as the information flow through the manipulated unshielded triplet cannot be isolated from edge X -Y. Therefore, to determine for a manipulated unshielded triplet, at least one more node must be connected to the corresponding shielded triplet. Call this node W such that W is adjacent to Y, Y W and W is not adjacent to X. With this structure, there are two paths between X and W. Let pı = (X, Y, W) and let P2 (X,Z, Y, W). If independence ares Ax,Y, Y w and Az, Y.YY exist, we show that the XY can be determined if and only if Az,Y. is conditionally-
independence are for (X, Z, Y) -XY connecting and Ax,Y, is not, or if Az,Y, is marginally-commecting and Ax,Y YXYY is not.
If Az, Y w is cendiiiionally-connettte I and Ax,Y.w is either connecting or never-connecting, then P1 is blocked conditional on Y. On P2, triplet (Z, Y, W) is active when conditioning on Y. Then, if X JL W|Y, Ax. Z.Y must be X IL W Y, .Ax,,,Y must be never-connecting, because if Ax.z, were conditionally.connede then Y + Z and there would be a contradiction.
and Ax,Y,w w.w is not, then Z - Y and W + Y by lemma or never-connecting. If Ax.Y w is marginally-
If Az, v. w is marginally-connecting and Ax, is not, then Ax Y is either conditionally- or never-connecting, then P1 is blocked with no conditioning set. On p2, triplet (Z, Y, W is active with no conditioning
connecting or never-connecting. Ax,Y, w is conditionally-connettoo
16

---

set. Then, if X Y W, Ax.z,Y must be marginally comjectin.... If T W/Z, Ax,z,Y must be conditionally and if X IL wiz, Ax,z,Y must be never-connecting,
Therefore the independence are for (X, Z, Y) -XY X) can be determined if Az,Y Y. w is conditionally- connecting and Ax.Y EX.Y.W is not, or if Az.Y is now show that when these criteria do not hold, it impossible determine the independence arc for (X, Z. Y) -XY If Y w is never-connecting, then, whether Ax.z, is marginally-connectiin conditionally cwwiiincnlly-cooncciinngggg or never-connecting, p2 will always be inactive. Therefore Az.y. w. cannot be determined. If Yz, Y.W and Ax,Y.W are conditionally-cooneei be conditioned on so that p1 is inactive, but then P2 will also be blocked. If Az, Y W and Ax. Y w are
and AA,
not. We
then to isolate p2, should
then to isolate P2. Y needs to be conditioned on to block P1 but then errginaall-connecting
p2 will also be blocked. whether Ax,z,Y Z. never-connecting, will always be inactive. Therefore Az,Y, Y.Y.W cannot be determined.
conditionalll-comeetiio
or
Ro: If - - and Y is conditonallly-comecting, then orient the triplet as X 4 Y
Proof. The proof of soundness follows directly from lemma]
1: If - Y, X and are not adjacent, and Ax,z, v is marginally-commecting then orient the triplet as Z Y.
Proof. The proof for soundness follows directly from Remark
Re 1f - Y and X Y, then orient X Y as X Y.
Proof. The soundness of the rule comes from observing that if X < Y, a cycle would be induced, violating the admissible partition criteria of aC-DAGs.
R3 If < Y.X W Y, Y.X X and Y are not adjacent, W- Z, and Ax w.y marginally- connecting, then orient W Z as W + Z.
Proof. The soundness of the rule comes from observing that if W Z. then by two applications of rule 2, Y + W, X + W. and then there would be collider at W. Since Ax. A.Y is marginally connecting, there is contradiction by remark I
2s: If - - W Y, and Y are not adjacent, W x-x Z, and Ax. W.Y porginally-connece/o then orient W Y YY
Proof. The soundness of the rule comes from observing that if W +- Y. then to avoid cycle, it must be that X + W. Then, however, there would be a collider at W, but Ax, is marginally connecting, there is contradiction.
g3 X Z Y, Z W. X and W are not adjacent, Y and W are not adjacent, and Ax,z,Y is never-connecting or conditionalll--comcctig with connection mark @p such that W E D, then orient Z W as Z W.
Proof. The soundness of the rule comes from the definition connection mark, @D, where any cluster W E D must be descendant of collider, such that Z + W.
Next prove orientation completeness for Rules 1-5.
17

---

Lemma 3. Rules 1-5 collectively are complete in the sense that all orientations determined from successive application are valid and result in all possible orientations.
Proof. In the case that there are no never-connecting ares, by lemma 2 the rules are complete following Meek 1995 [9] If there is one more never-connecting arc, the orientation rules of CLOC result fewer orientations, as never-connecting ares always imply ambiguous orientations by remark 2. For any edge between C; and C left undirected by successive applications of Rules 1-5, either the edge is part of a triplet marked with a marginally connecting or conditionally connecting arcs, or it is part of a triplet marked with never-connecting arc. In the former case, by lemma 2 the cluster Markov equivalence class includes at least one model with C; + C2 and at least one with C₁ + Cj. In the latter case, by remark 2 there exists at least one model in the cluster Markov equívalence class with C; + Cj and at least one with C, < Cj.
Because CLOC and the orientation rules only make use of cluster level independence and dependence information, all marginal and conditional independencies for given triplet are already evaluated. For given triplet C., Ck, J, by theorem T C and Cj can only be dependent if 1) they are adjacent, 2) they are not adjacent and Ac,.c conditionally connecting, and C₁ is in the conditioning set, or 4) they are not adjacent, Ac, C,,C, is never connecting, and there exists some descendant of a variable-level collider within C₁ in cluster C. where C., is in the conditioning set. Cases 1, 2, and 3 are covered by the skeleton and collider search phases. Rule 5 captures conditional dependencies created by case 4, such that orientations for non-one ooientree triplet can be made to reflect the dependence. As orientations of Rule 5 follow a non-standard pattern relative to Rules 1-3, we can consider information determined by Rule to be form of background knowledge introduced to the graph. Then, with Rule 4, and given the admissibility assumption of the partition, the proof for completeness extends directly from Meek 1995, where the PC algorithm with background knowledge is proved to be complete in that any subsequent orientations that can be determined following Rule must be valid and complete.
is marginally connecting. 3) they are not adjacent, A,,.c,,cc,
Finally, we prove Theorem by showing that CLOOC does return an aC-CPDAG.
Proof. An aC-CPDAG must reflect the cluster Markov equivalence class of aC-DAGs for a given partition. This means that all cluster level independencies and dependencies must be represented, all directed edges are non-variant and all undirected edges are variant. The proof for non-variant directed edges and variant undirected edges follows from lemma 3 To represent all independencies and dependencies, we must ensure that all adjacencies, independence arcs, separation marks, and connection marks are determined. The proof for valid adjacencies follows directly from the proof for skeleton construction of Spirtes et. al 1993 [19]. The procedure for determining independence ares follows from definition 2 where for each triplet, searches for variables in or not in the separating set for any given pair of variables X and Y allows for determination of the appropriate arc. The procedure for determining separation marks follows from definition [ where independence tests are performed to identify where the closest pair of clusters, appearing to be dependent, are in fact independent. Lastly, the procedure for determining connection marks follows from definition 6 where independence tests are performed to determine if any combination of possible descendants render two variables dependents such that the set of clusters are necessarily descendants. Therefore, by theorem 2 the aC-CPDAG completely represents cluster Markov equivalence class.
Remark 3. CLOC is complete with background knowledge.
Proof. The proof follows directly from the completeness of CLOC including the orientation rule (Rule 4) for background knowledge.
C Further discussion on cCDDA semanties
C.1 On separation marks, connection marks, and graph interpretation
In this section, we extend the discussion the interpretation and semantics of aC-DAGs.
We first further explore separation marks and connection marks. We note that separation marks can be placed on any independence are that signifies connection: marginally arcs, or
18

---

conditionally- connectiin ares. Separation marks can not be placed on conneccnnn ares, as there is no connection for the separation mark to dispute. When a separation mark is found on marginally-connecting arc, a marginal connection is disputed. When a separation mark is on conditionally-ccomeetin arc, the connection, conditional on the center node of the triplet marked by the independence arc, is disputed. Since paths can be traversed in two directions, and independence statements can be read in two ways (X IL Y, Y TL X), separation marks come in pairs.
Connection marks are read in way distinct from separation marks. The subscript of a connection mark indicates the directly connected nodes or sets of nodes that, when conditioned on, create a connecting triplet where there otherwise is not one. Any true descendants of the nodes in the subscript of the connection mark are understood to also create the connection, where a true descendant is identified by true connecting path over clusters (see d-separation criteria, Def. g Connection marks can only be placed along never-connecting independence ares. This because a marginally active triplet can not have new connection created due to conditioning on descendant of a collider because the triplet already active. If the center node of the triplet marked by a marginally-connectie independence are is conditioned on, any descendant of collider that is conditioned on would still fail to create a new connection as the independence are necessitates there are non-colliders along any path the collider may appear on, which would be conditioned on, so the path would be blocked. As conditionally conneccinnnnnnninngggg. ares require a collider, any true descendant will create a connection, following expected behavior, so there is no need to explicitly denote a connection mark. Lastly, note that the subscript of a connection mark can be a set of sets of clusters. Each set of cluster denotes one way that the triplet can be made active, and it is noted that path through cluster with multiple colliders on it would need multiple descendants (possibly in different clusters) to be conditioned on for the triplet over clusters be active.
There are certain graph semantics and attributes that require new interpretation for aC-DAGs. In particular, we can create a more refined class of descendants and ancestors, informed by connections through the clusters. In C-DAGs, similarly as in DAGs and other graphs, directed path from some node Co to C, is a sequence of distinct vertices (Co,..,, ..., C,,) such that for 0 < S n 1, C, is a parent of C++1 in Gc. In aC-DAGs, applying this same definition yields what we define as an apparent directed path, since even with the described pattern of edges, it is possible to have independence ares and separation marks that describe a break or block which contradicts the notion of directed path. By contrast true directed path in an oC-DAG from some node Co to C, is defined as a sequence of distinct vertices (Co. C..) such that for 0 S i S n - 1, C, is parent of C in Gc and where every are the corresponding are trajectory is with no separation marks. Then, CA is called a true ancestor of CB and C3 true descendant of C if CA- CB or there is a true directed path from CA CB. We contrast these terms with what we call apparent ancestors and apparent descendants where there may only be an apparent directed path from CA to Cg. In aC-DAGs, we use the notation AnGe (MGe(CD) (CB) and Dege (C.) to refer to the sets of true ancestors of Cg and true descendants of C in Gc, respectively.
C.2 On relaxing the assumption of acyclicity
In our definition of aC-DAGs (and by extension for aC-CPDAGs), we require that there is no apparent cycle over clusters, that is where for some pair of clusters C,, Cj. where there exists an edge C, + Cj. there is no directed path C; + - C,. We believe this is reasonable assumption in the context of clusters as the user intentionally defines the partition over variables, likely because these variables represent together some semantically meaningful entity or are otherwise similar in some ways, such that knowledge of potential cycle is available. However, we also note that in some cases, such an assumption may not be feasible, and it is easy to construct an example where the underlying graph over variables is acyclic, but a certain partition over the variables creates an apparent cycle. In such case, aC-DAGs have the representational capacity to differentiate between true cycle and an apparent cycle, as is clear by the discussion above differentiating between true and apparent ancestors and descendants. Specifically, if the assumption of acyclicity over clusters is relaxed (assuming an acyclic distribution over variables), then where there is an edge C, + C, and some directed path C, - .... - C₁ there will necessarily exist some independence are or separation mark along the path C, - .... + C. that denotes that Cj is not a true ancestor of C, and therefore there is no true cycle. In this context, properties such as d-separation extend soundly for cC-DAGs. However, the relaxation of the assumption of no apparent cycles over clusters does have implications in the context of structure learning. In particular, rules that leverage this assumption of acyclicity are
19

---

Lo Z0
Z
Z
X
X1
X1
(c)
Clustered
(d) aC-CPDAG,
(a) DAG G1
CPDAG, P
CPDAG, Pe
P
Figure 6: (a) is a DAG and (b) is the CPDAG that comes from G₁. Following the procedure in
definition 13 (c) the clustered CPDAG that comes from P. This object reflects orientations that
are determined from tests on P(V). By contrast, (d) is the aC-CPDAG that corresponds to G1.
All edges are undirected X JL Y; X Z and the edges cannot be oriented as, by Remark 1 the cluster level dependencies and independencies align with the representations of X
Y.
X + Z + Y, and X + + Y.
no longer valid, such Rule 2 and Rule 4. Rule 3 depends upon the validity of Rule 2 and therefore also becomes invalid. An area of future work to determine sound extension of or different rules that allow for sound and complete learning over clusters when the acyclicity assumption is relaxed. In Appendix D we show analysis on the number of wrongly-oriented edges when CLOC is run on cyclic partition.
C.3
On the special case of clusters of size 1
We note that when clusters include at most variable, CLOC reduces to PC, following Lemma Independence ares, separation marks, and connection marks all become redundant. When clusters have more than variable, and there are no never- cevercconnn arcs, the orientation rules also reduce to PC, however the graphical object still requires separation and connection marks to fully represent conditional independences and dependences. When clusters have at most variable, this no longer the case. For any triplet (C,; Ck, Cy) such that Cg is of size the cluster), the alignment of the edge orientations and marginal and conditional independencies and dependencies will be aligned as the case is for variables. For simplified representation in aC-DAGs and aC-CPDAG, independence arcs and connection marks could be removed for these triplets. The interpretation of this object is that wherever there an omitted independence arc, the behavior for the triplet is as anticipated. If there exists another triplet in the graph (C,, Cg: go Cw) such that C not of size the independence arc, with the appropriate separation mark. would be required. If all clusters in an aC-DAG or aC- CC-CPDAG include at most variable, then the simplified representation holds for all triplets and the result would be DAG or CPDAG respectively.
(i.e. there is only one variable in
1, is possible separation mark is required for Ck, C,), in which case
D Experimental details and additional results
D.1 Experimental Setup
All experiments were run on a machine with CPU: Intel 19 Chip, 32 GB of RAM. and macOS operating system. single core was used for the experiments. Algorithms are implemented Python and implementation of CLOOC and experiments are available at: https://githuh..com http://ggtuuu..oomaaaaaa.aaaaaaa Tanaaaandannnn....
In simulations, compare two approaches developing clustered graphical equivalence class. The first approach consists of applying PC to the distribution over variables, P(V), and then imposing clusters. The clustering procedure is shown below.
Definition 13 (Clustered CPDAG.). Given a CPDAG, P over variables V, and partition C {C,,..., C,. V,, construct a graph Pc over C as follows.
An edge C, + Cj is in Pa if there exists some V. E C, and some V3 E Cj such that E Pa(V,) in P
edge C, Cj is Pe for all Vi E C, that are adjacent to some Vj E Cj there an undirected edge between V, and Vy, i.e. V1 Vg.
We note that the graphical object created by the procedure above, which we refer to as a clustered CPDAG, determined by the Se-then-Clusted approach, is distinct from cC-CPDAG. In particular,
20

---

Structural Hamming Distance Cluster Count
A: True CLOC output vs. True PC-then-Cluster
Estimated PC Cluster output vs.
+ B: Estimated CLOC output vs. True
Hamming Distance
Structural
Cluster count
Figure Green: comparison CLOO output, estimated from a simulated Gaussian dataset, compared to the oracle for the corresponding data-generating process. Orange: comparison of the PC-then- Cluster approach output, estimated from a simulated Gaussian dataset, compared to the oracle for the corresponding data-generating process. Blue: Comparison of the oracle solutions by CLOC and the PC-then-Cluster approach.
edges that may in fact be variant a cluster Markov equivalence class may become oriented the clustered CPDAG, due to some feature of the distribution over variables. For example, in Figure 6 the distribution over variables, P(V) allows the collider over (Z2, Z3. Y1) to be learned, allowing for orientation between Y and Z to be possible for the clustered CPDAG. Subsequent applications of Rule 1 of the PC algorithm allows for orientation the edge Z1 - X1, so that an orientation between X and Z is possible. By contrast, the aC-CPDAM is learned from the distribution P(C) where cluster-level independence tests reveal X f Y: Y The cluster Markov equivalence class for this information includes graphs with the orientations X X + Z + Y, so no orientations in the aC-CPDAG can be made.
Y. X < Z Y, and
For the experiments in the main body of the paper, we compare the methods of CLOC and the PC-cluster approach, as there is no other comparable method outputting an equivalence class over clusters. For the latter method,
use the built-in implementation of PC in the python package causal-Icarn 27 The output is a CPDAG, which is then clustered by the procedure described in definition 13 using the defined partition variables into clusters. In our implementation of CLOC the multi-variate conditional independence test used iterates over pair-wise tests variable level independence tests with early stopping when dependence is determined implying dependence over clusters.
D.2 Additional results
We show additional experimental results in Figure 7 comparing oracle (ground truth) results by the PC-then-cluster approach with CLOC, we can note information that is lost by using only cluster-level information rather than variable-level information. As is illustrated Figure [ orientations beyond those representing the cluster Markov equivalence class are possible when the (variable-level) Markov cquivalence class learned by leveraging P(V). In Figure The blue line shows how much of this sort of information, translating orientations aligning with P(V), is lost when only P(C) is used. We expect this number to non-zero. This tradeoff in orientation capacity can be weighed against improvements in required number of conditional independence tests and runtime, as demonstrated in the main body.
The green and orange lines compare, for each method of CLOC and the PC-then-cluster approach, the structural hamming distance between a graph estimated from a data sample as compared to ground truth equivalence class. We note that we see similar structural hamming distances for CLOOC compared to the PC-then-Cluster approach, which reflects similar robustness of our proposed method to noise in data samples, despite larger conditioning sets.
21

---

Average Wrong Orientations Cluster Count
4.0
Average Wrong Orientations
30-
2.5
1.-
10
Figure 8: Average number of misoriented edges for graphs with 5, 6, 7, and clusters with inadmissi- ble (cyclic) partitions across 100 runs.
We also analyses to show the impact of violations the assumption about acyclic partition. Specifically, for random graphs with acyclic partitions, corresponding to aC-DAGs, we generate a different partition over the graph that induces a cycle. Using the parent-child relationships of the true DAG, we assess how many wrong orientations (where an edge that is oriented contradicts true direction) determined by rumning CLOC with the inadmissible partition. We show results averaged over 100 simulations each for cyclic partitions 5, 6, 7, and 8 clusters. The results are shown in Figure S
E
Complexity Analysis
The skeleton construction requires, for each pair of clusters (X, Y), searching for conditional
independence given subsets of their neighboring clusters. The number of possible conditioning sets grows combinatorially with degree d, the maximum degree of any cluster, so there are O
possible subsets to check per pair. For a graph with n clusters and (2) = O(n²) pairs, there are a total of (nn2dd) tests. Independence arcs are then determined for each triplet (X, Z, Y). The number of unshielded triplets for which an additional test is needed is bounded by ((dd). The number of shielded triplets for which an additional test is needed is bounded by ((dd²), ), as four nodes are involved in these tests. The search for separation marks, we should note, is not necessary for determining graphical orientations. However, to create complete aC-CPDAG on which subsequent analyses can done, separation marks are necessary. Assuming a longest path length L, the search bounded by (ndd)). Connection marks' search can also be expensive and the marks are informative for edge orientations. practice, the size of the conditioning set W can be bounded save costs. In the worst case, each triplet is evaluated for all subsets of neighbors of Z. yielding ((nd22"). The last algorithmic component of evaluating the orientation rules until none apply requires searching over all triplets, bounded by (ndd). In total, the complexity is bounded by O(n2d + d²)). Where clusters are created such that inter-cluster density is relatively sparse and intra-cluster density high, CLOC will show the greatest complexity benefits relative to PC.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
Justification: See Summary Contributions in the introduction specifying contributions and scope. The abstract summarizes this.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification:
See Conclusions section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification: Assumptions are stated in the main body. Proofs are found in the appendix. Guidelines:
23

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: Details of the proposed algorithm are provided in the main body. Experimental details are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
24

---

Details of the experimental approaches, data used, etc are provided in the appendix of the paper. Open access to the code expected be made available in the future.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
public/guides
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //wpps.ccppublll./. ptce/ublic/gguu www.c//gwgge//eeeeeeeeeee httiii//guiiee//deeuubbbiii ssioicllccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All such specifics are provided in the Experiments section and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are provided in relevant plots in Experiments section and appendix, with approrpiate discussions.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
25

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: These details are in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///aaaarrss..cppbpbb//aaaaa
Answer: [Yes]
Justification: The research conforms.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The positivie societla impact discussed throughout the paper. We believe
there is no negative societal impact of the work as it does not pose any surveillance, privacy, security risks etc.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out
26

---

that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The research does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All relevant work is cited throughout the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wtwp:ts...ppssiiiiia.a.. www.sweetehhe....m com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets are released.
27

---

Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects research was conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects research was conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs are not part of the research or methods of this work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy for what should or should not be described.
28


Reviews:
[{"review_id": "461JEZ9TkB", "reviewer": "Reviewer_GBnh", "summary": "This paper addresses the challenge of causal discovery in high-dimensional settings by proposing an approach based on clustered variables. The authors introduce Cluster Directed Acyclic Graphs (C-DAGs), where nodes represent clusters of variables rather than individual variables, simplifying causal discovery in complex systems.", "questions": "See the weaknesses above.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "​​Strengths:​​\n\n- The paper introduces a novel approach to handling causal relationships between variable clusters, improving the scalability for high-dimensional data.\n- The authors provide soundness/completeness for d-separation in the cluster of variables in Markovian systems.\n- By reducing complexity through clustering, the method could make causal discovery more feasible in domains with many variables.\n\n​​Weaknesses:​​\n\n-  One of my concerns is that while clustering improves scalability, it might introduce statistical challenges. As the number of conditional independence tests grows (with increasing clusters or conditioning sets), the risk of the statistical hypothesis errors​​ escalates, and the conditional independence on the small conditional set should be more trustworthy than the one with have larger one. The paper does not sufficiently address how their method mitigates these errors, which could undermine the reliability of learned structures.\n-  Moreover, can you compare the proposed method with the PC algorithm and other causal discovery algorithms without using the cluster by, for example, learn the full causal structure and then inferring the causal graph.\n- The approach assumes a predefined partition of variables. Can you provide some real-world examples?", "was_revised": true, "final_justification": "The response has addressed my concerns, and I would like to keep the score of acceptance.", "rebuttal": "Thank you for your thorough evaluation and constructive feedback. We appreciate the recognition of our contributions to causal discovery over clusters and address the specific concerns below.\n \n***W1:*** \n> One of my concerns is that while clustering improves scalability, it might introduce statistical challenges. As the number of conditional independence tests grows (with increasing clusters or conditioning sets), the risk of the statistical hypothesis errors escalates, and the conditional independence on the small conditional set should be more trustworthy than the one with have larger one. The paper does not sufficiently address how their method mitigates these errors, which could undermine the reliability of learned structures.\n\nCausal discovery over clusters, as implemented in CLOC, significantly reduces the number of conditional independence tests compared to variable-level discovery (see Figure 7, Section C.2), leading to greater robustness by minimizing error propagation that can undermine the reliability of the inferred structure. While tests over clusters may have lower statistical power than those over individual variables, this can be effectively mitigated by advances in multivariate testing (e.g., Mantel Test), and modern machine learning-based methods that reliably assess independence between multivariate distributions. Having said that, we appreciate the concern and feel this discussion is indeed very relevant, which will be reflected in the manuscript; thank you for sharing. \n    \n\n***W2:***\n > Moreover, can you compare the proposed method with the PC algorithm and other causal discovery algorithms without using the cluster by, for example, learn the full causal structure and then inferring the causal graph.\n\nThe question asked is unclear to us, so we are happy to elaborate on it further. For now, we would say that there are currently no algorithmic approaches that learn a graphical representation over clusters, as CLOC does; therefore, there is no gold standard against which to compare. A direct comparison between the output of CLOC and that of PC is not meaningful, as they operate over different kinds of entities (clusters vs. variables). If the remark is suggesting to learn the causal structure over variables and then infer the cluster graph, this is what we do with the PC-then-cluster approach, which represents the closest comparator. However, as discussed in Appendix C, the object resulting from PC-then-cluster is a clustered CPDAG, which is distinct from and not the object of interest for CLOC, which is an αC-CPDAG. Alternatively, if the reviewer is asking if our proposed method could be another structural learning algorithm where there are no clusters (where clusters are all of size one variable), we discuss this in Appendix B.3 (our algorithm reduces to PC in this case and therefore works as expected). \n    \n***W3:*** \n>The approach assumes a predefined partition of variables. Can you provide some real-world examples?\n\nThere are many cases where groupings of variables are natural, and there is, in fact, clarity as to which variables should be clustered together. Medicine represents one domain where this is common; a cluster might be a group of related blood tests in the form of a laboratory panel, related genes, related microbes in a microbiome analysis, anatomical regions in neuroimaging, or demographic information. \n\nWe hope the above response clarifies the statistical robustness of CLOC, its comparison to PC, and the realistic applications of the approach."}, {"review_id": "6klJncpRdP", "reviewer": "Reviewer_RGBk", "summary": "The authors introduce αC-DAGs, a novel graphical representation that augments cluster DAGs (C-DAGs) with three annotations: independence arcs, separation marks, and connection marks. These additions allow αC-DAGs to fully encode conditional independence relationships over clusters, which is not possible with standard C-DAGs. The paper establishes soundness and completeness of a new d-separation criterion for αC-DAGs (Theorem 1). It then defines αC-CPDAGs as a representation for Markov equivalence classes of αC-DAGs. The CLOC algorithm is proposed for learning αC-CPDAGs from observational data, leveraging constraint-based methods and five orientation rules (R0-R5), which are proven sound. Experiments on synthetic data (up to 256 variables and 8 clusters) show that CLOC matches the cluster-level accuracy of the standard PC algorithm applied to the full variable set and then aggregated, while requiring fewer conditional independence tests and less computational time.", "questions": "-Why are clusters of nodes ultimately integrated into a graph over variables representing a class of DAGs? Why is there no other structure or cycle?\n\n-How sensitive is CLOC to misspecified partitions? You should have done an obligation study.\n\n-How did you perform multivariate CI tests?", "limitations": "As the authors mentioned, users are required to have knowledge of a partition of variables that does not induce a cycle, which is very limiting in practice. \n\nThere is an experimental or theoretical analysis of how high-dimensional CI tests impact CLOC performance.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The αC-DAG representation and the associated d-separation criterion are, to the best of my knowledge, new contributions. The paper has formal definitions and theorems (e.g., soundness and completeness of d-separation in αC-DAGs) and proofs (which I have not read). They also provided the CLOC algorithm, which is well-specified, and the orientation rules are motivated and proven sound.\n\nWeakness:\n\nThe approach relies on user-provided clusters or partitions that must form a DAG. The paper does not address how such a partition is obtained in practice. If the partition is misspecified (e.g., clusters are not acyclic), the method fails, right? This limits practicality, especially since cluster-level relationships might be unknown a priori, and the user has no idea if there is a cycle or not.\n\nTheorem 3 shows soundness but leaves open whether the αC-CPDAG always captures the full equivalence class. This is a critical gap because without completeness, the learned graph might be less informative than possible. Right?\n\nExperimental comparison overlooks recent methods for cluster-level causal discovery techniques; why is no other comparison provided?\nAlso, there is no real-world validation. I also expected to see an obligation study on misspecified clusters or partitions.\n\nThe presentation was a bit hard to follow for me with many notations and definitions. I am not sure if you can relax some notations to improve readability.", "was_revised": true, "final_justification": "Thank you, authors, for the rebuttal. It answered most of my concerns. However, the manuscript should be updated as promised.", "rebuttal": "Thank you for taking the time to read our paper and for acknowledging the novelty and soundness of our contributions. We comment on the concerns raised in the sequel. \n\n***W1:*** \n> The approach relies on user-provided clusters or partitions that must form a DAG. The paper does not address how such a partition is obtained in practice. If the partition is misspecified (e.g., clusters are not acyclic), the method fails, right? This limits practicality, especially since cluster-level relationships might be unknown a priori, and the user has no idea if there is a cycle or not.\n\nThank you for raising this important point. Our method indeed assumes a user-provided, admissible partition over variables, and if the partition is misspecified (e.g., the cluster graph contains cycles), the method may fail to recover a correct C-DAG. Two points are worth making in this context. \nFirst, we believe this requirement is both meaningful and practical in a range of real-world settings. For instance, in clinical and biological domains, partitions often arise naturally: clusters might correspond to laboratory panels (e.g., blood tests), gene sets, microbiome groups, neuroanatomical regions, or demographic blocks. In many of these domains, temporal or biological ordering provides good reason to assume acyclicity at the group level. Our framework is designed to formalize, allow for, and exploit such domain knowledge whenever available.\nSecond, and more broadly, we emphasize that this is the first algorithm for learning C-DAGs -- a class of models that combines coarse-grained structure with interpretability and modularity. As with the early days of PC/FCI, and in the structure learning literature, strong assumptions often enable tractable solutions to foundational problems. Over time, these assumptions can be relaxed, and robustness added, but progress begins with principled starting points. We are still trying to improve these algorithms more than three decades after they were proposed.\nWe appreciate the reviewer’s concern and agree that developing methods for verifying or learning the cluster-level structure is a compelling open challenge. We hope this work serves as a foundation for that line of research.\n\n***W2:*** \n>Theorem 3 shows soundness but leaves open whether the αC-CPDAG always captures the full equivalence class. This is a critical gap because without completeness, the learned graph might be less informative than possible. Right?\n\nWe agree that completeness is important for ensuring the most informative learned graph. After submitting our main manuscript, we did manage to prove CLOC’s completeness, as detailed in Lemma 2 and Remark 5 in Appendix A. We will update the theorem description in the main body of our paper accordingly.\n    \n***W3:*** \n>Experimental comparison overlooks recent methods for cluster-level causal discovery techniques; why is no other comparison provided? Also, there is no real-world validation. I also expected to see an obligation study on misspecified clusters or partitions.\n\nTo our knowledge, there are currently no causal discovery techniques that learn a graphical object over clusters. Such a graphical equivalence class has not been previously defined, and is one of the major contributions of this work. As discussed in Section 1.1, related work is limited to methods that either use clusters as an intermediate step for variable-level causal discovery or target narrow scenarios, such as those with only two clusters. These approaches are not designed for the general, cluster-level causal discovery setting that CLOC addresses and therefore do not offer a meaningful basis for comparison. Other related works have simply identified the challenges of learning over clusters, without proposing an algorithm to address these challenges as our work does. We agree that conducting a sensitivity analysis on misspecified partitions would be valuable and have done so. We include more details in response to Q2. \n\n***W4:*** \n>The presentation was a bit hard to follow for me with many notations and definitions. I am not sure if you can relax some notations to improve readability.\n\nWe apologize if parts of the paper were difficult to follow – that was certainly not our intention. We aimed to keep the formalization as concise as possible while introducing the key components needed to define the framework and support our main results (e.g., different levels of coarsening over the original causal DAG, the appropriate equivalence class, a modified notion of separation, faithfulness, proper invariances, etc). We appreciate the reviewer’s comment and understanding, and will make every effort to improve the clarity and readability of the notation, should the paper be accepted and an additional page be made available (as in previous years).\n\n***Q1:***\n >Why are clusters of nodes ultimately integrated into a graph over variables representing a class of DAGs? Why is there no other structure or cycle?\n\nWe agree that alternative representations, potentially involving cycles, could offer greater flexibility and support arbitrary clusterings. However, this setting introduces significant challenges that require extensive learning over individual variables, thereby counteracting the computational and robustness advantages of cluster-level discovery. Enforcing acyclicity at the cluster level is a mild yet effective assumption that ensures scalability and interpretability without reintroducing the complexity of variable-level learning. Having said that, we think there is space for broader exploration and we take the reviewer’s note as an intriguing suggestion. \n    \n***Q2:*** \n>How sensitive is CLOC to misspecified partitions? You should have done an obligation study.\n\nCLOC can be sensitive to misspecified partitions that induce a cycle. Aside from this requirement, variables can be partitioned in any way. We have conducted additional experiments illustrating the extent of the sensitivity to inadmissible partitions. We include some results in the table below, which will be included in the updated manuscript. In words, the table shows, for different numbers of clusters in the graph, the impact of specifying the partition such that a cycle is induced. We evaluate this by the structural hamming distance (SHD) of the graph determined by the oracle using the true partition compared to the graph determined by the oracle using the misspecified partition, and report an average over 200 iterations of random graphs. We compare this to the SHD of an oracle graph of the initial partition specified to a context where a variable is arbitrarily moved from one cluster to another, to illustrate the relative degree to which a change is expected. As discussed in the response to W1, the goal is to integrate prior knowledge in the form of an admissible partition; there are many use cases where such prior knowledge is feasible, and these are the intended use cases of CLOC. \n\n| # Clusters      | # Nodes | Avg SHD (SD) - Cyclic     | Avg SHD (SD) - Acyclic     |\n| :---:        |    :----:   |          :---: |           :---: | \n| 5 | 32 | 1.495 (1.248) | 1.240 (1.183) |\t     \n| 6 | 64| 1.720 (1.442) | 1.930 (1.454)  |               \n| 7 | 128\t| 3.100 (1.857) | 2.800 (1.779) |                                            \n| 8 | 256\t| 3.570 (2.354) | 3.265 (2.430)|                                                                     \n\n          \n***Q3:*** \n>How did you perform multivariate CI tests?\n\nMultivariate CI tests were performed using an approach of iteration through pairwise correlations between variables with early stopping when a dependence is found, an approach appropriate for the Gaussian distribution. This is discussed in Appendix C.1.\n    \n***PF:*** \n>Experiment figures are difficult to read at 100\\% zoom; consider larger fonts for labels and numbers. No legend for the plots! Line 65 : slearn -> learn. Be consistent with the definitions in the preliminary. Why is the keyword \"Definition.\" in the middle of line 80, while it was not used before? You should either make a new paragraph or be consistent.\n\nThank you for these notes. We will make the suggested formatting edits."}, {"review_id": "5ObzFtQS91", "reviewer": "Reviewer_rfuq", "summary": "The paper tackles the problem of learning Cluster-DAGs (C-DAGs) from observational data, where a C-DAG is defined as the clustering of a low-level probabilistic causal model. The authors highlight how the connection between $d$-separations and conditional independence relations does not typically hold when considering clusters of variables. To this end, they introduce the novel notion of *independence arcs*, i.e., an arc connecting two edges of a C-DAG. The authors show how conditional independences between clusters can be expressed as a function of paths composed of independence arcs. Using this result, they design a constraint-based method — named CLOC — to recover C-DAGs from data, up to an equivalence class analogous to the Markov Equivalence Class for DAGs.", "questions": "The scope and the contributions of the work are sufficiently clear, and I do not have particular questions for the authors.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The paper well-motivates the introduction of their method, showing how naively applying causal discovery algorithms, such as PC, might not return the ground-truth C-DAG.\n- The introduction of independence arcs is interesting, novel, and correctly captures conditional independences among clusters.\n- Under the commonly adopted faithfulness assumption, the CLOC algorithm provably returns the equivalence class of the ground-truth C-DAG with the corresponding independence arcs, i.e., an $\\alpha$ CP-DAG in the terminology of the authors.\n\nWeaknesses:\n- The work shares the limitation of existing works on C-DAGs, by assuming that the clusters are provided. A practitioner does not know how variables are causally related, but must know how to cluster them.\n- The notation of independence arcs is quite confusing, and figures such as Figure 3 are difficult to interpret. For instance, overlapping symbols in Figure 3d — see for instance between clusters $\\mathbf{W}, \\mathbf{Y}$ — make it quite unreadable.", "was_revised": true, "final_justification": "The authors sufficiently discussed the identified weaknesses of their paper, which constituted minor points in an overall positive evaluation of the work.", "rebuttal": "Thank you for reading our paper and acknowledging the significance and contributions of our work. We appreciate the reviewer feedback and provide a few notes below. \n\n***W1:*** \n>The work shares the limitation of existing works on C-DAGs, by assuming that the clusters are provided. A practitioner does not know how variables are causally related, but must know how to cluster them.\n\nIt is true that, like with existing work on C-DAGs, our algorithm requires a pre-specified partition of variables. C-DAGs, where the context is identification and inference, provide an alternative to constructing a complete causal diagram, and the assumption of a known partition over variables is a less stringent requirement than knowing the full causal diagram over all variables (while there are tradeoffs). In our work, with a focus on the task of learning, we believe the assumption of a known partition can offer improvements in scalability such that knowledge of the partition is a meaningful tradeoff. It is true that the approach may not be applicable in all cases if knowledge of a partition proves infeasible. However, we believe this requirement is both meaningful and practical in a range of real-world settings. For instance, in clinical and biological domains, partitions often arise naturally: clusters might correspond to laboratory panels (e.g., blood tests), gene sets, microbiome groups, neuroanatomical regions, or demographic blocks. In many of these domains, temporal or biological ordering provides good reason to assume acyclicity at the group level. \n\nIn other words, C-DAGs offer a relaxation over DAGs, albeit not universally applicable to all modeling scenarios, and the current work on learning presents a possible relaxation/different type of tradeoff compared to other competing methods. Having said that, we agree that the proposed method does not constitute a universal solution to all learning problems in causality. \n\n**W2:** \n> The notation of independence arcs is quite confusing, and figures such as Figure 3 are difficult to interpret. For instance, overlapping symbols in Figure 3d — see for instance between clusters \\mathbf{W}, \\mathbf{Y} — make it quite unreadable.\n\nWe acknowledge that the independence arcs can result in dense graph visuals and apologize for having to use such notation. Having said that, we note that this notation is made out of necessity, since familiar graph edges are incapable of representing both ancestral relationships between clusters and the conditional independence information between, and both of these types of information are important for structure learning and downstream tasks. This realization and the operationalization of the additional kind of arcs constitute a key contribution of this work. Still, we will revise the discussion and figures to improve the readability of the notation and make this point clearer; thank you."}, {"review_id": "4FXqlFwmN9", "reviewer": "Reviewer_2UQT", "summary": "This paper introduces a new graphical model, the αC-DAG, designed to learn causal relationships between predefined clusters of variables from observational data. It incorporates independence arcs, separation marks, and connection marks to represent conditional independence patterns among clusters and defines a custom d-separation criterion. The authors also propose αC-CPDAGs to capture equivalence classes of these graphs, along with a corresponding learning algorithm called CLOC. They prove the soundness of the framework and show that CLOC performs more efficiently than a PC-then-cluster baseline on synthetic data.", "questions": "1. How sensitive is the method to small errors or noise in the cluster partition? Would a few misclassified variables significantly distort the learned structure?\n2. Can the approach be extended to support overlapping or hierarchical clusters, which are common in domains like text modeling?\n3. In cases where conditional independence tests produce conflicting results (due to statistical noise or small samples), how are contradictory arc annotations resolved?\n4. Does the graphical formalism still maintain interpretability and scalability when applied to systems with dozens or hundreds of clusters?", "limitations": "1. The approach assumes causal sufficiency at the cluster level. These assumptions are strong and often unrealistic in practical settings, particularly when latent confounding or weak interactions exist across clusters.\n2. The algorithm requires the cluster partition to be given and acyclic, which may not always be feasible. No method is proposed to validate, refine, or learn the partition itself.\n3. The symbolic structure of αC-DAGs (e.g., independence arcs, separation marks, connection marks) adds considerable complexity. The usability of such graphs in practical decision-making or downstream tasks like intervention planning is not demonstrated.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. The paper introduces a novel graphical model, the αC-DAG, and its equivalence class representation, the αC-CPDAG, specifically designed to capture causal relationships between predefined clusters of variables. The framework adds expressive symbolic elements—independence arcs, separation marks, and connection marks—that allow for a more nuanced encoding of conditional independencies at the cluster level.\n2. The authors establish sound and complete d-separation semantics for αC-DAGs, define a precise notion of cluster-level Markov equivalence, and prove the correctness of their orientation rules and learning algorithm.\n4. The experiments demonstrate meaningful comparisons against a standard PC-then-cluster baseline. Results show that the proposed approach achieves comparable accuracy.\n\n\nWeaknesses\n1. The method assumes a provided clustering of variables that is both acyclic and accurate. This assumption directly encodes structural information, which contradicts the premise of discovering causal structure from observational data. As a result, the learning process becomes more of a structural summarization under a fixed partition than genuine discovery.\n2. The graphical formalism of αC-DAG blends causal relationships and statistical independencies into a single representation. While this increases expressive power, it also blurs the distinction between mechanistic causality and observed conditional dependence, potentially complicating the interpretation and soundness of orientation rules derived from such hybrid semantics.\n3. The model relies heavily on conditional independence tests to annotate arcs and guide structure learning. However, multivariate CI tests are known to be statistically unstable, especially with small samples or non-Gaussian distributions, and the framework does not incorporate any robustness measures or uncertainty modeling.", "was_revised": true, "final_justification": "This paper introduces a new graphical model, the αC-DAG, designed to learn causal relationships between predefined clusters of variables from observational data. Although the response may not address the concerns about the strong assumptions relied upon and the difficulty of constraining real-world systems, it did demonstrate the plausibility of the current assumptions. Therefore, I decided to slightly increase my score.", "rebuttal": "We thank the reviewer for their time in reading our paper. We believe a few misunderstandings may have contributed to a somewhat harsh evaluation, and kindly ask the reviewer to reconsider our work in light of the clarifications below.\n\n**W1** \n>The method assumes a…clustering…that is both acyclic and accurate. This assumption directly encodes structural information, which contradicts the premise of discovering causal structure from observational data. As a result, the learning process becomes more of a structural summarization under a fixed partition than genuine discovery.\n\nWhile CLOC relies on a given partition, this form of limited background knowledge is integrated with data-driven learning. The partition informs structure, but is weaker knowledge than even ordering; performing discovery is still required. For concreteness, consider a simple graph of 3 clusters where the true graph is an unshielded triplet. In this case, knowledge of acyclicity provides no useful information. The collider test remains necessary; if the structure is not a collider, the partition doesn’t indicate if the triplet forms a direct chain, a reverse chain, or a fork.   \n\n**W2** \n>The graphical formalism of αC-DAG blends causal relationships and statistical independencies into a single representation. While this increases expressive power, it also blurs the distinction between mechanistic causality and observed conditional dependence, potentially complicating the interpretation and soundness of orientation rules derived from such hybrid semantics.\n\nIndependence arcs in αC-DAGs encode conditional independencies, which come from knowledge. In αC-CPDAGs, arcs (and edges) are learned from data. The goal of causal discovery is to leverage independencies from data and graphical properties to establish causal relationships. In other causal graphs (DAGs, CPDAGs, ADMGs, PAGs), edge orientations encode both causality and independencies, as these are intrinsically linked. This key observation from Spirtes, Glymour, Schines, and Pearl started the literature of structure learning. Therefore in our cluster context, an accurate representation of independence is critical, and one of the key results established in our paper with independence arcs and separation/connection marks. We prove soundness of our orientation rules and show the logical alignment of our semantics with the standard graphical properties on which the orientation rules depend.  \n\n**W3** \n>The model relies heavily on conditional independence tests to annotate arcs and guide structure learning. However, multivariate CI tests are known to be statistically unstable, especially with small samples or non-Gaussian distributions, and the framework does not incorporate any robustness measures or uncertainty modeling.\nCausal discovery remains a challenging task, primarily due to high computational complexity and reliance on the accuracy of statistical tests. As the number of variables increases, causal discovery at the variable-level quickly becomes infeasible, even with large datasets. Our work shows that this computational burden can be alleviated by discovery over clusters, which reduces the dimensionality of the problem. This shift allows focus on the challenge of accurately inferring statistical associations, a task that becomes more tractable with larger sample sizes and modern statistical/machine learning techniques. We also show that our method maintains robustness compared to methods leveraging tests over variables alone (Figure 7, Appendix C.2) and emphasize that this is the first algorithm for learning C-DAGs. As in the structure learning literature, leveraging imperfect statistical tests often enables tractable solutions to foundational problems. Over time, these methods are improved, but progress begins with principled starting points. We appreciate the reviewer’s concern, and agree that developing stable multivariate CI tests is a compelling open challenge, which we hope this work helps motivate.\n**Q1** \n>How sensitive is the method to small errors or noise in the cluster partition? Would a few misclassified variables significantly distort the learned structure?\n\nPartitions can be created however a user wishes, as long as a cycle is not induced. Therefore, it is difficult to say what would constitute errors or noise in a partition, except to say that a certain partition induces a cycle. CLOC is sensitive to cyclic partitions, as our assumptions state. We conducted additional experiments illustrating the extent of this sensitivity (see table in response to RBGk, omitted here due to space constraints). \n\nWe believe there are meaningful real-world settings where knowledge of an admissible partition is available. For instance, in medicine, partitions often arise naturally: clusters might correspond to laboratory panels (e.g. blood tests), neuroanatomical regions, or demographic blocks. Temporal or biological ordering provides good reason to assume acyclicity over groups. \n \n**Q2**\n>Can the approach be extended to support overlapping or hierarchical clusters, which are common in domains like text modeling?\n\nWe have not yet explored overlapping clusters, as the nature of the solution changes substantially in this context. However, overlapping variables is an interesting and practical challenge that we hope to see further explored. The question/suggestion is appreciated. \n\n**Q3** \n>In cases where conditional independence tests produce conflicting results (due to statistical noise or small samples), how are contradictory arc annotations resolved?’\n\nIt should be noted that algorithms like PC, on which our approach is based, do not note or aim to resolve conflicts that might appear. Each conditional independence test is assumed correct, and propagates; tests that might contradict earlier results are never conducted. Further in CLOC, each independence arc pertains to the triplet of clusters that it annotates, and a single pair of independence tests determines the arc, such that there could be no conflicts. For edges and separation/connection marks with possibly contradicting evidence in the data, CLOC proceeds as standard PC, assuming all previous tests are correct, so there are no conflicts to resolve although there could be errors. \n\n**Q4**\n>Does the graphical formalism still maintain interpretability and scalability when applied to systems with dozens or hundreds of clusters?\n\nThere is nothing in principle that prevents the application of our proposed graphical formalism and algorithm to systems with dozens or hundreds of clusters. While interpretability is often a matter of design choices and domain expertise, scalability is not inherently guaranteed. Learning a causal graph is a super-exponential problem in the number of nodes. Thus, as the number of cluster-nodes increases, the computational complexity can grow rapidly. Although clustering helps reduce dimensionality compared to working with individual variables, learning a graph over many clusters can still entail significant computational and statistical challenges.    \n\n**L1**\n>The approach assumes causal sufficiency at the cluster level. These assumptions are strong and often unrealistic in practical settings, particularly when latent confounding or weak interactions exist across clusters.”\n\nWe acknowledge that causal sufficiency is a strong assumption. Solving this first step has laid a strong foundation for addressing problems where latent confounding exists. Having said that, the latent confounding case is much more involved and substantially harder to discuss without a thorough understanding of the Markovian case.  \n\n**L2**\n > The algorithm requires the cluster partition to be given and acyclic, which may not always be feasible. No method is proposed to validate, refine, or learn the partition itself.\n\nLearning admissible partitions is certainly a task of interest to us, but it is beyond the scope of this work. A given acyclic partition can be considered a specific form of background knowledge that is integrated into the learning process. As discussed in the response to Q1, there are many use cases where such knowledge is reasonable given the domain.\n\n**L3** \n> The symbolic structure of αC-DAGs (e.g., independence arcs, separation marks, connection marks) adds considerable complexity. The usability of such graphs in practical decision-making or downstream tasks like intervention planning is not demonstrated.\n\nWe agree that the symbolic structure of αC-DAGs introduces additional notation and complexity. However, this is a deliberate design choice motivated by scalability and interpretability. In high-dimensional domains such as drug safety, social science, or genomics, conventional DAGs or PAGs are often impractical to elicit, interpret, or reason over.\nBy introducing coarse-grained structures (grouping variables into meaningful clusters such as drug classes, social determinants, or anatomical regions), αC-DAGs dramatically reduce the effective dimensionality. While the use of symbolic marks adds some complexity, it enables a compact and expressive representation of high-level causal relationships across clusters. This can make the analysis of such systems tractable where it would otherwise be infeasible. \nAdditionally, αC-DAGs need not be directly parsed by humans for all use cases. They can serve as intermediate representations for downstream tasks like interventional or counterfactual inference and can support quantitative reasoning in automated systems.\nαC-DAGs introduce a new point in the tradeoff between expressiveness, interpretability, and scalability. In cases where variable-level DAGs are impractical to learn or use, structured coarse representations may provide a valuable and feasible alternative."}]

Author rebuttal:

Meta-review: The paper focuses on an interesting and timely problem in causal discovery, learning (equivalence classes of) causal graphs over clusters of variables, from observational data. The paper is well-written and the theoretical results are rigorous and novel. As mentioned by some of the reviewers, this approach has the potential of helping in scaling up causal discovery by considering clusters of variables instead of individual variables. On the other hand, a limitation of the approach is that the clusters need to be given a priori and it needs to be accurate, which can limit the applicability of the method.

During the discussion, the reviewers have reached a general consensus for recommending an acceptance for this paper based on the above-mentioned strengths and a well-discussed rebuttal by the authors. Overall I agree with their recommendation.
Decision: Accept (poster)