Causal Discovery over High-Dimensional Structured Hypothesis Spaces with  Causal Graph Partitioning
Authors: Ashka Shah
Adela Frances DePavia
Nathaniel C Hudson
Ian Foster
Rick Stevens
Venue: Accepted by TMLR ()

Abstract: The aim in many sciences is to understand the mechanisms that underlie the observed distribution of variables, starting from a set of initial hypotheses. Causal discovery allows us to infer mechanisms as sets of cause and effect relationships in a generalized way---without necessarily tailoring to a specific domain. Causal discovery algorithms search over a structured hypothesis space, defined by the set of Directed Acyclic Graphs (DAG), to find the graph that best explains the data. For high-dimensional problems, however, this search becomes intractable and scalable algorithms for causal discovery are needed to bridge the gap. 
    In this paper, we define a novel causal graph partition that allows for divide-and-conquer causal discovery with theoretical guarantees under the Maximal Ancestral Graph (MAG) class. We leverage the idea of a superstructure---a set of learned or existing candidate hypotheses---to partition the search space. We prove under certain assumptions that learning with a causal graph partition always yields the Markov Equivalence Class of the true causal graph. We show our algorithm achieves comparable accuracy and a faster time to solution for biologically-tuned synthetic networks and networks up to ${10^4}$ variables. This makes our method applicable to gene regulatory network inference and other domains with high-dimensional structured hypothesis spaces.

Published in Transactions on Machine Learning Research (03/2025)
Causal Discovery over High-Dimensional Structured Hy- pothesis Spaces with Causal Graph Partitioning
Ashka Shah Deportment of Computer Science University of Chicago
shahashka@uchioonpo
Adcla DePavia
adepania Chechiaaoaucccc
Committee Compulational and Applied Mathematics University of Chicago
Nathaniel Hudson
hudsona @uchiccgo...o..oooooo edu
Department of Computer Science University of Chicago
Ian Foster Department of Computer Science
foster@uchicago.c edu
Universily of Chicago
Rick Stevens
stevens Ceceessass.c uchicago.coo edu
Department of Computer Science University of Chicago
Reviewed OpenReview: http:///oursiieeee////////sss/fs
Abstract
The aim in many sciences is understand the mechanisms that underlic the observed dis- tribution of variables, starting from set of initial hypotheses. Causal discovery allows us infer mechanisms sets of cause and effect relationships in generalized way without necessarily tailoring to specific domain. Causal discovery algorithms scarch over a st structured hypothesis space, defined by the set of Directed Acyclic Graphs (DAG), to find the graph that best explains the data. For high-dimensional problems, however, this search becomess intractable and scalable algorithms for causal discovery are needed to bridge the gap. In this paper, we define novel causal graph partition that allows for divide-and-conquer causal discovery with theoretical guarantees under the Maximal An- cestral Graph (MAG) class. We leverage the idea of superstructure or existing candidate hypotheses to partition the search space. We prove under certain assumptions that learning with causal graph partition always yields the Markov Equiva- lence Class of the true causal graph. We show our algorithm achieves comparable accuracy and faster time to solution for biologically-tuned synthetic networks and networks up to t0 variables. This makes our method applicable to gene regulatory network inference and other domains with high-dimensional structured hypothesis spaces. Code available at https://githe.. com/ com/shahashka/caa causal discovery viw.vvaaaaaaeeee wia_aaatttiioinngggggggggma
set of learned
1 Introduction
Causal discovery aims find mcaningful causal relationships using largo-scale observational data. Causal relationships are often represented graph, where nodes are random variables and directed edges are cause- effect relationships between random variables (Spirtes al., 2000b). Causal graphs have high expressive

---

Published in Transactions on Machine Learning Research (03/2025)
power they allow to investigate complex relationships between many variables simultancously-man them relevant for many problems in science, economics, and decision systems (Pearl, 1995).
Exploring the graph search space to find the causal graph is an NP-hard problem. Causal discovery algorithms have benefited from some performance enhancements and parallel strategies (Ramsey, 2015; Laborda et al., 2023; Lee Kim, 2019). Recent work explores a distributed divide-and-conquer version of causal discovery by partitioning variables into subsets, locally estimating graphs, and merging graphs to resolve a causal graph. Existing diviid-anddconquee methods do not provide theoretical guarantees for consistency; meaning in the infinite data limit they do not necessarily find the Markov Equivalence Class of the true causal graph. Existing algorithms also rely on an extra learning step to merge graphs which can be computationally expensive. Finally, these algorithms ignore the violations to causal assumttions when learning on subsets of variables (Spirtes et al., 2000b; Eberhardt, 2017).
To address these limitations in litcrature, we propose causal partition. causal partition a graph partition of the hypothesis space, defined by superstructure, into overlapping variable sets. A causal partition allows for merging locally estimated graphs without an additional learning step. We can efficiently create a causal partition from any disjoint partition. This means that causal partition can be an extension to any graph partitioning algorithm.
We are interested in causal discovery for high-dimensional scientific problems; in particular, biological net- work inference. Biological networks are organized into hierarchical scale-free sub-modules (Albert, 2005; Wuchty et al., 2006; Ravasz, 2009). The causal partition allows us to leverage the inherent, interpretable communities in these networks for scaling.
Our contributions are as follows: (A) We define a novel causal partition which leverages a superstructure and extends any disjoint partition. (B) We prove, under certain assumptions, that learning with causal partition is consistent without an additional learning procedure. (C) We show the efficacy of our algorithm on synthetic biologically-tuned networks up to 10,000 nodes.
2 Related Work
Causal discovery algorithms are categorized into two types: (i) Constraint-based algorithms use conditional independence tests to determine dependence between nodes (Spirtes et al., 2000b;a), and (ii) Score- based algorithms greedily optimize score function over the space of potential graphs (Chickering, 2002; Hauser & Bühlmann, 2012). To address the intractable search space for causal discovery, many "hybrid" methods first constrain the search space with a constraint- based method, and then greedily optimizing the subspace using score-based method (Tsamardinos et al., 2006; Nandy et al., 2018). Perrier et al. (2008) formalize this approach by defining the superstructure G = (V, where for a true causal graph G = (V, (V, E S E. The superstructure can be found using a constraint- based method like the PC algorithm, which is sound and complete. The superstructure can also be informed by domain knowledge e.g., for gene regulatory networks genos that are functionally related likely constrain underlying regulatory relationships (Cera et al., 2019). Incorporating prior knowledge into causal discovery allows us to infer which hypotheses or known relationships are best supported by data.
Another approach to scaling causal discovery algorithms is the divide-and-conquer approach. In this ap- proach, random variables are partitioned into subsets. Causal discovery is run on each subset in parallel before a final merge to resolve a graph over the full variable set. Huang & Zhou (2022) and Gu & Zhou (2020) use hierarchical clustering of the data to obtain disjoint partition of variables. Similarly, Li et al. (2014) partition the node set using the Girvan-Newman community detection algorithm. Similar to our work, Zeng & Poh (2004) use overlapping partition, however, they do not provide any theoretical guarantees for learning. Tan et al. (2022) use an ancestral partition to restrict candidate parents for exact causal discovery using dynamic programming. Laborda et al. (2023) employ ring-based distributed parallelism. Our work differs from these because we use a superstructure G to partition nodes into overlapping subsets using a novel causal graph partition with theoretical guarantces. The cansal partition avoids any additional lcarning step to combine subsets. We show that causal partition can be an extension to any disjoint partition, allowing us to learn effectively on graphs of varying topologies. Finally, Zhang et al. (2024) also leverage
2

---

Published in Transactions on Machine Learning Research (03/2025)
Table
Table of Relevant Notation
Symbol
Description
G H
Underlying true causal graph represented by a DAG.
CPDAG representing MEC of G"
Superstructure.
X
The complete observed data matrix (of dimensionality x p).
X
Observational data for the yth random variable; also used to denote nodes in graphical models.
X5,
Directed edge from random variables (nodes) X, to Xj. Consistent causal learner that outputs an PAG on subsets S. Partition over node set V, where S C V. The outer vertex boundary of a of nodes Nodes X and X3 are adjacent in some graph G'.
of
( S
(S)
X² Nor X3
superstructure to partition the variable set and define causal partition with similar properties ours. However, the variable set can only be partitioned into two subsets using an optimal edge cut, meaning the scaling potential of this algorithm is limited. Our work has constraints the number of subsets, and result we can scale up to 10,000 variables.
3 Background
3.1 Causal Discovery
Causal discovery considers set of data sampled from the joint distribution of random variables X (X1,..., where is the number of random variables in the system. Each random variable X; E R" is defined as a real-valued column vector where each value an individual observation for random variable X,. We assume these relationships can be represented by a Directed Acyelic Gruph (DAG). This DAG is a tuple G (V. E*) where is the node (or vertex) set made up of p nodes corresponding the random variables, and Fx CVx x V is the set of directed edges between nodes. For each directed edge (X,,x)) E E*, we refer to the source node of the edge (X;) the "cause" and the target node of the edge (X,) as the "effect". The joint distribution of random variables is given by probability density function that factorizes as:
P(X = II (x)Pa
(1)
Where Ga (X)) is the set of parents of node in G Nodes that are d-separated in G* imply a conditional Z d-separates from Y in DAG G*, then the random variables and are conditionally independent given Z. We assume access to only observational data. In this setting, causal discovery algorithms only estimate a graph within the Markoe Equivalence Class (MEC) of G The MEC of causal graph G consists of the set of DAGs that share the same conditional independence relationships and therefore d-separalion criteria. A Completed Partially Directed Acyolic Graph (CPDAG) is the graph class that represents the MEC of a DAG. In this paper we denote the MEC of the true DAG G as the CPDAG H* In particular H' has the same adjacencies and unshielded colliders (triples with the following structure j + where and & are not adjacent) as G (Zhang, 2008a). As a helpful reference, we include relevant. definitions in Table 1
independence in P. Let X, Y E and C V
3.2 Graph Classes for Latent Variables
While the causal graph can represented by a DAG, we consider alternative graphical representations that consider latent (unobserved) variables. Namely, we consider two well-studied graph classes: (i) Marimal Ancestral Graphs (MAGs) and (ii) Partial Ancestral Graphs (PAG) (Richardson & Spirtes, 2003; Zhang, 2008a).
3

---

Published in Transactions on Machine Learning Research (03/2025)
Definition 3.1 (mixed graph, MAG). A mixed graph G consists of set of nodes V and set of directed edges E. C V x V and set of bi-directed edges B XV.. If XX), E E we say there is directed edge between X, and Xj and we write X; + X,, If X3] E B we say there is a bi-directed edge and write X2 ++ Xg. A mized graph is called a marimal ancestral graph (MAG) if it contains no almost directed cycles and there is no inducing path between non-adjacent nodes.
An almost directed cycle is a cycle that contains both directed and bi-directed edges, An inducing path is defined as follows:
Definition 3.2 (Inducing path). Given L C V, an inducing path relative to L between vertices u and u is a path II = {u, (i,....................... "k; & such that every non-endpoinl node in II {V \ L. is a collider on II and an ancestor of at least one of or v.
Some examples of inducing paths are illustrated in Figure 1. exlended to m-separation in mixed graphs (Zhang, 2008a). The graph class that characterizes the Markov Equivalence Class of MAGs, governed by m-separation, is the partial ancestral graph (Richardson & Spirtes, 2003).
The idea of d-separation in DAGs can be
Definition 3.3 (partial mixed graph, PAG). A partial mixed graph can contain four kinds of edges: -,, -,, and >-> and therefore has three kinds of end marks for edges: arrowhead (>), lail (-) and circle (o). Let [M] be the Markov equivalence class of an arbitrary MAG M. The partial ancestral graph (PAG) for [M], PAG[M], is a partial mized graph such that (t) PAG[M] has the same adjacencies as M (and any member of (M)) does; (ti) A mark of arrowhead is in PAG(M] if and only if it is shared by all MAGs in [M]; and (iii mark of tail is in PAG[M] if and only if it. shared by all MAGs in [M].
We will prove, that under certain assumptions, we can reconstruct the CPDAG representing the MEC (H*) of the true DAG (G*) from PAGs estimated on subscts of variables.
3.3 Causal Discovery on Subsets of Variables
We now describe the problem setup for learning over subsets of variables. Column wise subsets of X are marked with subscript: e-g.; for a subset of nodes S, the corresponding subset of data Xss = (X") hes. The presence of latent variables outside the subset S complicates our learning procedure. We must use MAGs rather than DAGs to represent graphs estimated on subsets of variables to ensure consistency of our algorithm. To this end we define latent projection, as used by Zhang (2008a), of the true graph G* onto subset of nodes S. An example is shown in Fig. 1.
Definition 3.4 (Latent MAG). Let G be DAG with variables V and S C V, where V contains selection variables. The latent MAG L (G,S) is the MAG that contains all nodes in S and satisfies:
S and u + uu-UEC G u UEE (M,
2. (projected edge) E L (G, if there is an inducing path between u and u relative to V\S in G The edge is directed u + v if u is an ancestor to u in G*. The edge is directed v + u if v is an ancestor to u G Otherwise the edge is bi-directed u ++ v.
Latent projections are well-studied objects in the causal discovery literature, see (Verma & Pearl, 2022; Faller et al., 2023; Richardson et al., 2023; Zhang, 2008a) for further definitions. A ground-truth DAG G induces a latent MAG I [MAG(G",S) on subset S. The Markov equivalence class of this MAG is denoted (G"AGGG",5)) S)).
Next, we assume that the structure learner employed on each subset is a complete and consistent PAG learner, even in the presence of confounder variables. Algorithms known to satisfy these assumptions include the seminal FCI algorithm (Zhang, 2008b).
Additionally, we will as "wild card" end mark. For example moans that the end mark at u can be any of three outlined the Defn. 3.3.
Thhere no selection bias in our setting, since data sampled from the full vertex set V which retains causal sufficiency.
4

---

Published in Transactions on Machine Learning Research (03/2025)
Examples of Latent MAGS and Inducing Paths
X
X
2
X
X
5
X4
aa)
(b)
(c)
Nodes in subset S
Edges G
Edges in
Latent projection
Projected edges (G*,
inducing path
M. (G",S)
Figure 1: Examples of latent MAGS (MA Inducing paths II relative to V V S are highlighted in green. (a) For 22 E S, any edge (2) in G an inducing path relative V between 21 and 22. (b) an inducing path relative to V between and because all non-endpoiul nodes on the path are in V'S. (c) HI is an inducing path relative to S between iı and is; because every uon-endpoinl either V VAS (nodes 22, or is in S and is collider on the path and is ancestor of at least one of Iι or (node x3).
Assumption 1. We have consistent structure learning algorithm s that operates data matriz X for subset of rondom variables S V. When the distribution P sotisfies foithfulness, then in the infinite data limit
(Xss) = PAGIL
In particular, by definition of the latent MAG and latent PAG operators, Assumption 1 implies the output of s satisfies several properties.
Lemma 1. Given s satisfying Assumption
For any Zt, T. E S, the output af (Xs) has an edge between æy and Ij if and only there is an inducing path in G relative to V \ between them.
2. For any triple Ix, Ti, Us E S that form an unshielded collider in G as Is - &- 2k, the oulput st (Xs) will have an edge between xa and æj as well as Ty and The and both of these edges will have an arrowhead at x---
3. For any u, E S such that Nat if u (d) with an arrowhend at a in (Xs), then - in G
The proofs for Lemma are deferred to Appendix B. These properties, at a high level, allow us to determine the alignment the adjacencies and the unshielded colliders in locally estimated graphs af (Xs) to the underlying DAG G These will be important for resolving the CPDAG H* using locally estimated graphs.
3.4 Defining Causal Partition
Here, we outline the properties of our novel causal partition, which admits dlivide-and-ooquue algorithm estimate H CPDAG corresponding G* by learning over subsets. Since learning on the entire variable initial structure over the entire variable set
set with (Xy) be computationally intractable, to help partition V into subsets. We first assume access to an initial superstructure G.
Assumption We have access superstructure G = (V, F.,, on undirected graph, that constranns the true graph G*. This means all edges in G* are in G, but not all edges in G are necessarily in G*
This assumption required prove identifiability of H* rather it allows to define the causal partition when the superstructure is fully connected, and therefore, when can exploit the communities in the superstructure enable scaling.
5

---

Published in Transactions on Machine Learning Research (03/2025)
Now consider some overlapping partition {Si,..., ,Sy of V, and the output {x) Using As- sumption 1, we show that given partition with a particular structure defined below, one can recover H* from (Xs,
Definition 3.5 (Causal Partition). We say an overlapping partition (Si...., Sx} is causal with respect superstructure G and ground-truth DAG G* if, given any learner of satisfying Assumption 1, all of the following hold:
(i) The partition is edge-covering with respect to the superstructure G.
(i) For any verlices u, such that + and u NG v, there cxists some subsel Ss such that E S and of (Xs) does not contain an edge between u and v.
(10) For any unshielded collider - in G", there erisls some subsel S; such that {u, v, S St.
particular, property (ii) in Definition 3.5 crucial to the aivide-anddconquer strategy proposed in this work, as it allows the algorithm identify and discard projected edges learned on a subset S (as in Defn 3.4) by comparing the output (Xs,) to results on other subsets. In Section 5.1, we show that given a superstructure satisfying Assumption 2, simple and computationally tractable procodure yiclds causal partition satisfying all above properties.
4 Guarantees in the Infinite Data Limit
Now we prove that given any causal partition {Si,..., SN) with respect to DAG G* and superstructure G, one can recover H a CPDAG corresponding to G*, Our main theorem states that Algorithm recovers H* from local output (Xs.))
Theorem 1. Given superstructure G satisfying Assumption 2, a learner of satisfying Assumption 1, and SN causal partition with respect to G and G", let H* denote the output of Algorithm 1
H ScrreennG fo/ (Xs.))
Then H salisfies the sollowing properties: (i) Vu, v E V, u ~M- v if and only if ~G- v; (ti) For ony unshielded collider u-+ +- in H", holds that u u u w in G* and (tii) For ony unshielded collider a-> in G", u ~H- and ~H- and both edges have arrowhead at in H*
Property (t) in Theorem 1 states that H contains the same adjacencies as G Properties (ti) and (iit) combine to imply that an unshielded collider u - v +- w appears oriented in H if and only if that unshielded collider exists in G These combined properties ensure that H is the CPDAG that represents the MEC of G
The proof of Theorem 1, included in Appendix B, relies the fact that by definition of causal partition, for any u, not adjacent in G", there must be subset S, such that u, St and the local output s/ (S.) does not contain an edge between and v. This allows us to "screen" projected edges from true edges edges that are not consistent across all locally estimated graphs.
We note that Screen is computationally lightweight. The dominant cost is O(N m' d), for N the number of partitions, m' the total number of learned edges, and the maximum degree in the learned graph. Of note, m' < p² for p the number of random variables, and in real-world applications learned graphs tend be sparse typical instances have m' < p² (Barabási, 2013).
We highlight that because only assume access to observational data, we only recover cause-effect relationships contained in the Markov equivalence class of G and therefore our guarantees relate to learning H' a CPDAG representing the MEC of G*, In Section 8, we discuss potential extensions of our framework for settings where both interventional and observational data are available, which might allow one to further reduce the size of the learned equivalence class.
5 A Practical Algorithm for Causal Discovery with a Causal Partition

---

Published in Transactions on Machine Learning Research (03/2025)
Here, describe practical procedure for causal discov- ery motivated by the idealized results studied in Section 4. We discuss how partitions satisfying Defn. 3.5 can be effi- ciently constructed, and detail a full end-to-end algorithm for causal discovery.
Algorithm 1: Screen G, (H:)
Input: superstructure G, set of PAGS {H, = (St, E
Result: H¹ (V, E²) CPDAG E'
Initialize V U. E Ecandidates U Bi
1/ Discard edges not superstructure. Beandidatas t- Brandidatra O {u au WN v); foreach u, v
5.1 Efficient Creation of a Causal Partition
(u + Ecandidates vi s.t. S; 2 (a,e); A(SA), # then // If an edge between u and e appears in the output on all subsets, add undirected edge to output graph.
The causal partition structure, described in Defn. 3.5, is crucial to the guarantees Theorem in the infinite data limit. While the first property of causal partition- edge coverage with respect superstructure G easy to ensure, it not obvious how to satisfy properties (ii) and (iii) without knowledge of the ground truth G*. Here we present simple and intuitive method for constructing causal partitions. This construction efficient and adapts to ar arbitrary superstructure topologics.
E - U
// Orient unshielded colliders foreach i [N' foreach Unshielded ++ 24 w H, do u and w E" then discard < [u v,v w/
9
10
orient 4- {u > 0. (- w/
11
E" - [E* discard) U Urient;
Given a graph EV, and S S V, let QS) denote the outer vertex boundary of set S G:
12
return 11 (V,E*)
(S) {u V(G) \S 8: Eu E S such that v ~g 4n
where v ~g any of (u, v), (v, u) or {u, v) E E.
Given any initial vertex-covering partition of the super- structure G, we consider the overlapping partition formed by expanding subsets via the addition of vertices from the outer boundary.
Definition 5.1. Let {Si...., S be vertez-covering partition of graph G. The causal exponsion of 1S....,SNy with respect to G is defined as (S)....,8%, ..y) with subsets S S; (..)
As the name suggests, show that causal expansion satisfies the properties of causal partition. The proof is deferred to Appendix B.
Lemma 2. Given G superstructure satisfying Assumption 2, (S } verter- verter-covering partition of G. Then the causal erpansion ( Sy is causal partition with respect to G and G*.
This simple construction, illustrated in Fig. 2, offers several advantages. Firstly, this method can be any vertex-covering initial partition (St....,y'l Graph partitioning algorithms form an extensive field (Girvan & Newman, 2002; Clauset et al., 2004; Schaeffer, 2007; Malliaros & Vazirgiannis, 2013; Harenberg et al., 2014), and depending on the topology of different partitioning may be more appropriate to a specific superstructure. The causal expansion allows a user first partition the superstructure G using whatever method most appropriate the application, and then easily derive a corresponding causal partition.
The causal expansion is computationally efficient, both to construct and in its incorporation into the full causal discovery procedure, described in Algorithm 2. Given an initial partition {Si,..., SN), constructing its causal expansion takes time linear in the size of the superstructure G. In Appendix E, we discuss how connectivity properties the initial partition {Si...., Sn dictate the size of the largest subset.
Algorithm 2: causal wwtpddddssovvvvveooe
(daapent) [S
Input: set of variables V, matrix of observations X,
superstructure G
Subsets in expansive causal pattiion S)
Result: Gout (V, CPDAG
(Di.... Dx) <-
/ construct causal expansion
S, D, U (D:uu(D))(( S <is N);
{Gs, = (N return Gout + Screen(G, (G,,)):
Figure 2: Expansive causal partition (%) made from initial disjoint partition S2).

---

Published in Transactions on Machine Learning Research (03/2025)
Now, we describe our divide-and-conquer causal discovery algorithm with an expansive causal partition described in Section 5.1. Algorithm 2 requires set of variables V, data matrix X and superstructure G. In Section 6.3 we also study the case where G is derived from data using the PC algorithm. Any causal learner can be plugged into st but for consistent learning we require that the assumptions for sf allow for causal insufficiency (confounders may be present) and causal faithfulness. Any graph partitioning algorithm can be plugged into disjoint_partttion partition. A complexity analysis of divide-and-conquer with an expansive causal partition is shown in Appendix D. In the next sections we show the use of this practical algorithm random and biologically-tumed networks with synthetic data.
6 Empirical Results on Random Networks
In this section we describe experiments for evaluating Algorithm 2 on synthetic random networks with finite data. For causal discovery on subsets (i.c., 2 we evaluate with four different algorithms: (1) Peters-Clark (PC) (Spirtes et al., 2000b), (2) Greedy Equivalence Search (GES) (Hauser & Bühlmann, 2012), (3) Really Fast Causal Inference (RFCI) (Colombo et al., 2012), and (4) DAGMA (Bello et al., 2022). Note that only RFCT is a PAG learner that satisfies Assumption 1. The other algorithms are DAG learners that assume causal sufficiency; still we include them in this evaluation because (a) they are popular causal discovery bench- marks, and (b) even with the violation to causal sulficiency, we observe good performance with the causal partition. For details on how the DAG subgraphs are merged see Appendix F. For disjoint disjoint_partition in Algorithm 2 we use greedy modularity based community detection (Clauset et al., 2004). We benchmark our algorithm with another divide-and--oonuer method PEF (Gu & Zhou, 2020).
For evaluation, we use the following metrics: (1) True Positive Rate (TPR) of correct edges in the estimated graph, G, compared to the edges in G"; and (2) Structural Hamming Distance (SHD), which is the number of incorrect edges. An incorrect edge is any edge in G that is missing in G or any edge in & that is not in G Additionally for larger networks we include (3) False Positive Rate (FPR); and (4) Time.
Default parameters: We use the following parameters by default unless stated otherwise. The graph topology is constructed by generating two scale-free networks using the Barabási- generative model (Barabási & Bonabean, 2003); both graphs have p = 50 nodes each, with one graph being constructed with a m = I edge per node and the second graph being constructed with m = 2 edges per node (edge connections are established via preferential attachment as per the generative model). We use n 100, 000 samples from the joint, multivariate Gaussian distribution (details on the DAG and data generating process are in Appendix F.1). The fraction of additional edges in perfect superstructure G is 10% of the edges in G (all edges in G are undirected). For causal discovery on subsets we set s to PC, GES, RFCI or DAGMA. Finally, for disjoint_ disjoint_partitioon partition in Algorithm 2 we use greedy modularity (Clauset et al., 2004) from the networkx Python library. The parameter scttings for ed and cach partitioning algorithm are detailed in Appendix F.2 and F.3. No Partitin
Dejoint GES
Edge Cover
Expansive Coussl
RFCI
DAGMA
0.4
0.76
0.75
0.50
0.2
0.50
0.25
0.55
10
10
10
10
10
10
10"
10"
PC
GES
RFCI
DAGMA
80
60
60-
SHD
40
40
20
70
20
10
10"
10
10
10"
10
10
10"
10
10"
10"
10
Samples
Samples
# Samples
Samples
Figure 3: Experiment increasing the number of samples n. Error bars are 95% confidence intervals.
8

---

Published in Transactions on Machine Learning Research (03/2025)
6.1 Number of samples
In this experiment, we test the consistency of Algorithm 2 with increasing samples n. We use a perfect superstructure and add a fraction 10% extra extrancous odges that are not G Results are shown in Fig. 3. As the sample size increases, we the convergence of No Portition with the MEC of G*. This empirically supports
theoretical result that Algorithm 2 is consistent in the infinite data limit, Interestingly, even when the af docs not permit latent variables (as in PC, GES, DAGMA), we still see convergence of No Partition with Expansive Causal. We also show results for an Edge Cover partition; this partition only accounts for edge coverage of G ((i) in Defn 3.5). We see the Edge Cover partition performs comparably to the Expansive Causal partition. This implies that of the properties of a causal partition described in Defn. 3.5, edge coverage appears be the most important. With the exception of the PC algorithm, we also outperform the benchmark PEF.
6.2 Density of superstructure G
No Parttonn
-
Digjoint GES
Edge Cover
Expansive Cousal
PEF
PC
RFCI
DAGMA
1,0
0.8
0.8
0.8
0.8
0,6
0.2
0.4
0.4
0.4
PC
GES
RFCI
DAGMA
75
100
80
SHD
50
80
40
60
25
20
60
Praction of Extraneous Edges
Fraction of Extraneous Edges
Fraction of Extraneous Edges
Fraction of Extranoous Edges
Figure 4: Experiment increasing fraction of extraneous edges in a perfect superstructure.
No Portiton
-20- Digjoint
Edge Cover
+
Expansive Causal
- PEF
GES
RFCI
DAGMA
0.5
0.8
0.7
1pR
0.4
0.8
0.5
0.6
0.5
X
X- 26
0.6
0.2
0.4
0.5
0.8
0.2
0.4
0.5
0.8
0.2
0.4
0.5
0.8
0.2
0.4
0.6
0.8
GES
RFCI
DAGMA
60
90
SHD
70
100
80
30-
40
80
50
70
20
50
02
0.4
0.8
0.8
0.2
0.4
0.8
0.8
0.4
0.6
0.4
0.8
Sign (a)
Significance (a)
Significance (o)
Signtflcance (o)
Figure Increase in density of the imperfect superstructure by increasing the significant level a of the PC algorithm.
This experiment assumess a perfect superstructure G. We increase the fraction of extraneous edges in and not in G In Fig. 4, we see comparable learning of Edge Cover, Exponsive Causal, and No Partition. This means that although G* increasingly obscured by G, and even though partitioning is done on G, we can still estimate close to the MFC H*
9

---

Published in Transactions on Machine Learning Research (03/2025)
6.3 Imperfect superstructure G
In this experiment we use the PC algorithm to estimate the superstructure G. Since the superstructure now relies on the data, it is imperfect and does not include all edges in G We vary the "perfection" of the superstructure by increasing the the significance level a of the PC algorithm. A larger a means a denser superstructure and a structure that is more likely to include more edges in G". Results are shown in Fig. 5. We turn off the superstructure screening step, as Screen, for this experiment. For the GES and DAGMA causal learning algorithms, Expansive Cousal outperforms Edge Cover slightly unlike in previous experiments. Still, the edge coverage property of the causal expansion accounts for most of the improvement in accuracy compared to disjoint partition. The causal partition may provide additional benefits to learning when the superstructure G' is imperfect.
Distribution subset sizes by partition algorithm
disponnt
10
edge
exparsive cansal
Rrsquency
100
200
300
400
Subset
(a) Subset. Sizes
(b) Subset of the topology
Figure 6: Topoloogiaa structure of 10,000 node graphs defined by case (A). This network has 10,000 nodes. The nodes are divided into 100-node subsets, of which there are 100. generate the edges the network, we first generate Barahasi-A Albert scale-free graph on each 100-node subset, and then randomly add edges connecting these subsets together. (a) Distribution of subset sizes for each partitioning algorithm. (b) Example communities extracted from the 10,000 node network. These three communities account for 3% of the total nodes and 2.81% of the total edges. The size of the node is proportional to its degree.
6.4 Number of Nodes
In this experiment we highlight the scalability of algorithm by evaluating networks with 10,000 nodes. We test two network structure cases here: (A) one hundred communities each with 100 nodes with a Barabasi-Albert scale-free topology; this is identical to the preceding experiments, except with more communities, and (B) hicrarchical scale-free graphs which are characterized by highly connected hub nodes that are preferentially attached other hubs. This is similar gene regulatory networks (Yu & Gerstein, 2006), but these structures are more sparse than typical biological networks. For both networks we obtain 10,000 samples from the multivariate Gaussian distribution. Unlike the preceding experiments, in this experiment show results for when the sample size is equal to the mumber of variables: = p.
In Table 2 we show results for (A) across cach divide-and-conquer method and different causal discovery algorithrs S. Time to solution for the divide-and-conquer methods (Disjoint, Expansive Causal, Edge Cover, and PEF) includes partitioning into subsets. The time to solution is bounded by the compute time of the largest subset (sce Appendix D). The distribution of subset sizes shown in Fig. 6a. As a result, many algorithms did not complete in 24 hours with No Partition (PC, RFCI, DAGMA) and PEF (PC, RFCT). For PC, RFCI and DAGMA our Edge Cover algorithm generally outperforms other methods in SHD
10

---

Published in Transactions on Machine Learning Research (03/2025)
Table Average time and accuracy results on 10,000 node graphs with 10,000 edges comprised of 100 scale free networks each of size 100 (averaged over over networks). The number of samples is 10,000. Dash (-) indicates the algorithm not complete
hours. This experiment was run with 2x AMD EPYC 7713 CPU @2GHz with total of 128 cores and 256 GB of RAM.
Structure Learner
Partitioning Algorithm
SHD +
TPR f
FPR +
Time (min) +
No Partition
857.2 + 35.6
0.930 = 0.002
9.0c-6
11.695 + 0.230
Disjoint
4382.8 = 201.8
0.650 = 0.011
1.0e-5
0.119 = 0.005
GES
Edge Cover
1306.4 + 35.4
0.895 1 0.002
1.3e-5
0.148 1 0.007
Expansive Causal
1550.6 + 54.3
0.947 + 0.003
1.5e-5
0.163 1 0.009
PEF
3775.8 119.3
0.697 0.01
3.7e-5
103.767 + 3.067
Partition
Disjoint
8519.2 = 227.0
0.322 + 0.007
4.9c-5
4.891 + 8.716
PC
Edge Cover
7050.8 195.0
0.433 + 0.004
6.3e-5
10.343 11.363
Expansive Causal
8683.0 + 401.0
0.504 + 0.014
7.4e-5
450.744 +: 187.366
PEF
No Partition
Disjoint
10294.0 191.5
0.491 = 0.013
6.5e-5
0.715 + 0.311
d RFCI
Edge Cover
9683.4 + 288.4
0.691 + 0.005
8.9e-5
5.430 + 4.210
Expansive Causal
9924.5 113.8
0.647 0.003
9.0e-5
107.788 11.204
PEF
No Partition
Disjoint
3722.6 = 274.7
0.694 = 0.015
1.0c-6
1.172 + 0.107
of DAGMA
Edge Cover
925.6 = 240.8
0.925 + 0.019
2.0e-6
2.502 + 0.234
Expansive Causal
1828.0 + 36.5
0.858 + 0.006
3.0e-6
3.593 1 0.607
PEF
4135.6 1 84.6
0.667 + 0.005
3.1e-5
122.405
1 5.736
and TPR while incurring a small cost in compute time compared to the fastest algorithm Disjoint. This further supports the claim that Edge Cover may be sufficient for many problems. For GES, however, we see the increased benefit of the Expansive Causal partition compared to Edge Cover for the TPR. Since No Partition runs in few minutes this network, it may be unclear why partitioning is needed. In the next example will see how the compute times increase dramatically when the network has much more complex community structure.
Table 3: Average time and accuracy results 10,000 node hierarchical scale-free graphs with ~ 10,000 edges (averaged over 5 networks). The number samples n is 10,000. We show results only for GES, This experiment was run with AMD Zen 3 (Milan) 7543P CPU @2.8 GHz with 61 cores and 512 GB of RAM.
Partitioning Algorithm
SHD
TPR
FPR
Time (hrs.) 1
No Partition
333.0 + 36.8
0.976 + 0.003
3.0e-6
25.46 + 17.24
Edge Cover
1214.6 + 40.6
0.913
0.004
9.0e-6
1.84 0.02
Expansive Causal
987.2 + 27.1
0.928
0.002
7.0e-6
11.96 + 5.72
Edge Cover 100 Comms
3506.4
563.9
0.752 0.040
1.4e-5
0.04 = 0.02
Expansive Causal 100 Comms
2510.8 + 72.3
0.821 0.002
8.0e-6
1.97 1 0.28
In Table we show results for (B) with o GES. The subsets of this network are larger and more dense compared to (A) (see Fig. 6b compared Fig. 7b); the GES algorithm takes significantly longer on this network topology. Our Expansive Causal achieves faster time to solution compared to No Partition while
11

---

Published in Transactions on Machine Learning Research (03/2025)
Distribution of subset sizes by partition algorithm
20
Rreqeecyy
exparsive_ceee causal
odge. cover fixed, comm expansive causal comm
20
2000
Subset size
Subset Sizes
(b) Subset of the topology
Figure 7: Topological structure of 10,000 node graphs defined by case (B): 10,000 node hierarchical scale-free
network (a) Distribution of subset sizes for each partitioning algorithm. (b) Example communities extracted from
the 10,000 node network with the Disjoint partition. These three communities account for 25% of the total nodes and 20.5% of the total edges. Each community has a set of hub nodes that connected to large number of other nodes (as seen by the large clusters of nodes in the visualization).
maintaining the second highest accuracy score. Compared to No Partition, Expansive Causal provides 2.13x speedup and Edge Cover provides 13.8x speedup. Note that PEF did not converge hours."
In Expansive Causal 100 Comms and Edge Cover 100 Comms we set the number of subsets to one hundred and ensure the size of the largest subset is smaller for each partitioning algorithm (Fig. 7a). We see significant speedup (12.9x for Expansive Causal 100 Comms and 606x for Edge Cover 100 Comms) compared to No Partition. However, this does come at cost to accuracy as seen in Table 3. We present an initial study of the subset size, speedup, and accuracy trade off in Appendix G. No Partition achieves the best accuracy, particularly with respect to SHD and FPR, however now the compute time is close to 25 hours, motivating the need for partitioning. Finally, we note that given = p for these experiments limitations we see for Expansive Causal are due to the statistical problems that arise in this data sctting, We leave understanding the sample inefficiency of partitioning algorithms to future work.
probable that the
We conclude that our methods Expansive Causal and Edge Cover provide faster time to solution large graphs, are relatively robust to dense and imperfect superstructures, and provide comparable accuracy compared to No Partilion.
7 Empirical Results on Synthetically Tuned E.coli Networks
This section contains results for biological networks. We use the topologies of E. coli biological networks due to their availability and popularity. To better benchmark the algorithms, we leverage a prozimilyy based topology generative model from the literature proposed by Hufbauer et al. (2020). The model was designed with the goal of generating structures with the following properties: (i) small-world (ti) exponential degree distribution (i.c., scale-free), and (tit) presence of inherit community structures. Coincidentally, these properties are also relevant. for real-world biological networks (Barabasi & Olivai, 2004; Koutrouli et al., 2020), thus we take advantage of this generative method. We seed this tuning algorithm with the known coli regulatory network roconstructed from experimental data in Fang et al. (2017) to generate synthetic networks with E. coli-like topology. See Fig. 8b for a visualization the highly connected hub nodes of an example tuned network. We impose a random causal ordering on the topology and generate data from the DAG using the multivariate Gaussian distribution described in Appendix F.1.
4PFF does not leverage initial superstructure to partition, as result the time partitioning longer than our proposed methods which use an artificial superstructure.
12

---

Published in Transactions on Machine Learning Research (03/2025)
A comparison of all algorithms is shown in Table 4 for o' GES. Expansive Causal provides 1.7x speedup compared to No Porlition. While there is significant. speedup, we note the decrease in accuracy for all divide-and-conquer algorithms. Still compared to other methods based on partitioning shown here, using a causal partition accelerates causal discovery and provides the best trade off in accuracy. We expect that scaling up to larger gene set sizes (e.g., 10a genes for eukaryotic cells) will be severely expensive for methods without partitioning since these networks are more dense and complex than those evaluated in Section 6.4.
Distribution of subset sizes by partition algorithm
disjoint
odge cover
uh
Frequency
5-
400
600
2000
Subset size
(a) Subset Sizes
(b) Subset of the topology
Figure 8: Topological structure of synthetically- partitioning algorithm. (b) Example communities extracted from the 2,332 node network with the Disjoint partition. These three communities account for 40.7% of the lotal nodes and 40% of total edges.
coli network. (a) Distribution of subset sizes for each
Table 4: Results for synthetically-tumed E.coli network made up of 2,332 nodes and 5,691 edges. n=10,,00 samples. We show results only for a = GES. This experiment was run with an Intel(R) (eon(R) Gold 6242 CPU 2.80GHz with 64 cores and 192 GB of RAM.
Partitioning Algorithm
SHD 4
TPR.
FPR 4
Time (hrs) +
No Partition
805
0.859
8.5e-5
11.8
PEF 1,766
0.692
8.3e-5
22.3
Disjoint
3,903
0.479
1.2e-4
23.9
Edge Cover
1,791
0.698
1.1e-4
7.1
Expansive Causal
1,717
0.701
6.4e-5
6.9
8 Conclusions & Future Directions
We propose a divide-and-conquee causal discovery algorithm based on a novel causal partition. Our al- gorithm leverages a superstructure-iie. a known or inferred structured hypothesis space. We prove the consistency of our algorithm under assumptions for the causal learner and in the infinite data limit using the Maximal Ancestral Graph (MAG) class. Unlike existing works, our algorithm allows for the merging of locally estimated graphs without an additional learning step. Motivated by complex scientific application space, also show example for gene regulatory network inference for small organism (E.coli), This example shows the applicability of our work to real-world networks, but we leave evaluation of our method on larger organisms (e.g, eukaryotes) to future work.
One limitation of our work the reliance on a perfect superstructure to create a causal partition. Although in Scction 6.3 we empirically explore the impact that using imperfect superstructures generated by the PC algorithm has on the learned output, more experiments (including other methods of generating superstruc- tures) needed to fully characterize the impact of learning when the superstructure does not constrain
13

---

Published in Transactions on Machine Learning Research (03/2025)
the edge set of the true causal graph. Further, while the divide-and-conquee method developed in this work can substantially reduce the runtime of performing causal discovery on large variable sets, characterixing the trade-off between timn-savings and sample complexity remains an area of open work. An important open question for future research is how the partitioning described in this paper impacts the sample efficiency of causal discovery algorithms. As discussed Section 4, another interesting direction for future research is extending the divide-and-conquer framework presented in this paper to the setting where both interven- tional and observational data are available. There exist causal discovery algorithms which can leverage a mixture of observational and interventional data (such as the I-FCI and 4-FCI algorithms) (Kocaoglu al., 2019; Jaber et al., 2020). If one uses one of these algorithms to perform local learning the variable sub- sets, then this might allow one to strengthen the guarantees presented in this work beyond only recovering cause-ellect pairs in the MEC of G Given these limitations and open questions, we believe that this work provides a meaningful contribution to causal discovery at scale and to knowledge discovery for domains with high-dimensional structured hypothesis spaces.
Acknowledgments
The authors thank Valerie Hayot-Sasson for her help with running simulations. The authors thank Bryon Aragam for helpful discussions. AS is supported by the Exascale Computing Project (17-SC-20-SC), a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration. This research used resources of the Argonne Leadership Computing Facility. Argonne National Laboratory's work on the Exploration of the Potential for Artificial Intelligence and Machine Learning to Advance Low-Dose Radiation Biology Research (RadBio-Al) project supported by the U.S. Department of Energy, Office of Science, Office of Biological and Environment Research, under contract AC0-0-0006C11133. AD gratefully acknowledges the support of NSF DGE 2140001.
References
Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 770.688. IEEE, 2015.
Réka Albert. Scale-free networks in cell biology. Journal of cell science, 118(21):4947-4957, 2005.
Albert-László Barabási. Network science. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371(1987):20120877 2013.
Albert-László Barabási and Eric Bonabcau. Scale-free networks. Scientific american, 288(5):60 2003.
Albert-Laszlo Barabasi and Zoltan N Oltvai. Network biology: understanding the cell's functional organi-
zation. Nature reviews genetics, 522):101-113, 2004.
Kevin Bello, Bryon Aragam, and Pradeop Ravikumar. DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyelicity Characterization. In Advances in Neural Information Processing Systems, 2022.
Alanna Cera, Maria K Holganza, Ahmad Abu Hardan, Irvin Gamarra, Reem S Eldabagh, Megan Deschaine, Sarah Elkambawy, Exequiel M Sisso, Jonathan J Foley IV, and James T Arnone. Functionally related genes cluster into genomic regions that coordinate transcription at distance in saccharomyces cerevisiae. Msphere, 4(2):10-1128 2019.
David Maxwell Chickering. Optimal structure identification with greedy scarch. Journal of machine learning research, 3(Nov):507-55) 2002.
Aaron Clauset, Mark EJ Newman, and Cristopher Moore. Finding community structure in very large networks. Physical review E, 7066):06611,, 2004.
Diego Colombo, Marloes H Maathuis, Markus Kalisch, and Thomas S Richardson. Learning nigh-dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pp. 294-321 2012.
14

---

Published in Transactions on Machine Learning Research (03/2025)
Anthony C Constantinou, Zhigao Guo, and Neville K Kitson. The impact of prior knowledge causal structure learning. Knowledge and Information Systems, pp. 1 1-50, 2023.
Frederick Fberhardt. Introduction to the foundations of causal discovery. International Journal of Data Science and Analytics, 3:81 91, 2017.
Philipp M Faller, Leena Chennuru Vankadara, Atalanti A Mastakouri, Franccsco Locatello, and Do- minik Janzing. Sell-compatibility: Evaluating causal discovery without ground truth. ar preprinl arXiv:2307.00 09552, 2023.
Xin Fang, Anand Sastry, Nathan Mih, Donghyuk Kim, Justin Tan, James T Yurkovich, Colton J Lloyd, Ye Gao, Laurence Yang, and Bernhard O Palsson. Global transcriptional regulatory network for es- cherichia coli robustly connects gene expression to transcription factor activities. Proceedings of the Na- tional Academy of Sciences, 114.,,1144 114(38):10286 10291, 2017.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821-7826, 2002.
Jiaying Gu and Qing Zhou. Learning big Gaussian Bayesian networks: Partition, estimation and fusion. The Journal of Machine Learning Research, 21(1):3340 63700, 2020.
Steve Harenberg, Gonzalo Bello, La Gjeltema, Stephen Ranshous, Jitendra Harlalka, Ramona Seay, Kan- chana Padmanabhan, and Nagiza Samatova. Community detection in large-scale networks: a survey and empirical evaluation. Wiley Interdisciplinary Reviews: Computational Statistics, 6(6):426 439, 2014.
Alain Hauser and Peter Bühhmann. Characterization and greedy learning of interventional Markov equiv- alence classes of directed acyclic graphs. The Journal of Machine Learning Research, 13(1):2409 2464, 2012.
Jireh Huang and Qing Zhou, Partitioned hybrid learning of Bayesian network structures. Machine Learning, 111(5))1695 1738, 2022.
Emory Hufbauer, Nathaniel Hudson, and Hana Khamfroush. A proximity-based generative model for online social network topologies. In 2020 International Conference on Computing, Networking and Communica- tions (ICNC), pp. 648-66 653. IEEE, 2020.
Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Charactcrization and learning. Advances in neural information processing systems, 33:9551 9561, 2020.
Murat Kocaoglu, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. Characterization and learn- ing of causal graphs with latent variables from soft interventions. Advances in Neural Information Pro- cessing Systems, 32, 2019.
Mikaela Koutrouli, Evangelos Karatzas, David Paez-Espino, and Georgios A Pavlopoulos. A guide to conquer the biological network era using graph theory. Fronliers in bioengineering and biotechnology, 8:34, 2020.
Jorge D Laborda, Pablo Torrijos, José M Puerta, and José Gámez. ring-based distributed algorithm for learning high-dimensional bayesian networks. In Eurroeon Conference on Symbolic and Quantitative Approaches with Uncertainty, pp. 123-135. Springer, 2023.
Thuc Duy Le, Tao Hoang, Jiuyong Li, Lin Liu, Huawen Liu, and Shu Hu. A fast pe algorithm for high dimensional causal discovery with multi-core pcs. IEEE/ACM transactions on computational biology and bioinformatics, 16(5):1483-1493 2016.
Sangmin Lee and Scoung Bum Kim. Parallel simulated anncaling with a greedy algorithm for bayesian network structure learning. IEEE Transactions on Knowledge and Data Engineering, 32(6):1157-1166, 2019.
15

---

Published in Transactions on Machine Learning Research (03/2025)
Shuohao Li, Jun Zhang, Kuihua Huang, and Chenxu Gao. A graph partitioning approach for bayesian
network structure learning. In Proceedings of the 33rd Chinese Control Conference, pp. 2887-288822 2887-2892. TEEE, 2014.
Fragkiskos Malliaros and Michalis Vazirgiannis. Clustering and community detection in directed networks: A survey. Physics reports, (3395)) 142, 2013.
Preetam Nandy, Alain Hauser, and Marloes H. Maathuis. High-dimensional consistency in score-based and hybrid structure learning. The Annals of Statistics, 46(6A):315133)) -183,, 2018.
Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669-68 688, 1995.
Eric Perrier, Seiya Imoto, and Satoru Miyano. Finding optimal Bayesian network given a super-structure. Journal of Machine Learning Research, 9(1)), 2008.
Joseph D Ramsey, Scaling up greedy causal search for continuous variables. ar preprint orXin:1507.0774.. 2015.
Erzsébet Ravasz. Detecting hierarchical modularity in biological networks. Compulational Systems Biology, pp. 145-160, 2009.
Thomas Richardson and Peter Spirtes. Causal inference via ancestral graph models. Oxford Statistical Science Series, pp. 83 105, 2003.
Thomas S Richardson, Robin J Evans, James M Robins, and Πlya Shpitser. Nested markov properties for acyelic directed mixed graphs. The Annals of Statistics, 51(1):334438) 361, 2023.
Satu Elisa Schaeffer. Graph clustering. Computer science review, 1(1):27-64, 2007.
Justin R Smith. The design and analysis of paraliel algorithms. Oxford University Press, 1993.
Pater Spirtes, Clark Glymour, Richard Scheines, Stuart Kauffman, Valerio Aimale, and Frank Wimberly. Constructing bayesian network models of gene expression networks from microarray data. 2000a.
Peter Spirtes. An anytime algorithm for causal inference. In International Workshop Artificial Intelligence and Slalistics, pp. 278 285. PMLR, 2001.
Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, Prediction, and Search. MIT press, 2000b.
Xiangyuan Tan, Xiaoguang Gao, Zidong Wang, Hao Han, Xiaohan Liu, and Daqing Chen. Learning the structure of bayesian networks with ancestral and/or heuristic partition. Information Sciences, 584:719 751, 2022.
Ioannis Tsamardinos, Laura E Brown, and Constantin F Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Machine learning, 65:31 78, 2006.
Thomas S Verma and Judea Pearl. Equivalence and synthesis of causal models. Probabilistic and causal inference: The works of Judea Pearl, pp. 221-236. 2022.
Peng Wang, Zirui Zhou, and Anthony Man-Cho So. A nearly-linear time algorithm for exact community recovery in stochastic block model. In International Conference Machine Learning, pp. 10126-10135 PMLR, 2020.
Stefan Wuchty, Erszôbet Ravasz, and Albert-LászI6 Barabási. The architecture of biological networks. Complex systems science in biomedicine, pp. 165 181, 2006.
Haiyuan Yu and Mark Gerstein. Genomic analysis of the hierarchical structure of regulatory networks. Proceedings of the Nalional Academy of Sciences, 103(40):14422-1473 2006.
16

---

Published in Transactions on Machine Learning Research (03/2025)
Behrooz Zarebavani, Foad Jafarinejad, Matin Hashemi, and Saber Salchkaleybar. cuPC: CUDA-based par- allel PC algorithm for causal structure learning on GPU. IEEE Transactions on Parallel and Distributed Systems, 31(3):530 542, 2019.
Yi-feng Zeng and Kim-leng Poh. Block learning bayesian net structure from data. In Fourth International Conference on Hybrid Intelligent Systems (H)SS04), pp. 14 19. IEEE, 2004.
Hao Zhang, Yixin Ren, Yewei Xia, Shuigeng Zhou, and Jihong Guan. Towards effective causal partitioning by edge cutting of adjoint graph. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Jiji Zhang. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9(7), 2008a.
Jiji Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, (72(16-17)1873-1888 2008b.
Appendix
A Definitions
Definition A.1 (Collider path). Given path P = (X1...., X&)) on mixed graph G, non-endpoint verter X; is collider path P if both edges adjacent to X; the path have directed bi-directed edge pointing to X,. Examples include X,-1 + X,,X; & Xi+1 and Xi-1 + Xs, X; t X4t1. A non non-endpoint verter which is not collider is said to be a non-collider on that path.
B Deferred Proofs
B.1 Deferred Proofs from Section 3.3
Here we prove the propertics in Lemma 1.
1. For any Ti, E S, the output (Xs) has edge between x; and Ty if and only if there is an inducing path in G relative to V \ S between them.
Proof. We begin by noting that by definition, ii and zy are adjacent in (G* S) if and only if there is an inducing path in G relative to V VAAa S between them (Zhang, 2008a). Moreover, by has the same adjacencies as any member of ILMAG S)], and therefore the same adjacencies as MM .S). Thus F, and Vj are adjacent of (Xs) if and only if there is an inducing path G relative to V S between them.
definition the PAG (Xs) = (G
For any triple F4, Ty, 2y E that form an unshielded collider in G as H, + Iy + Ikj the output d( will have an edge between x; and øj as well as xy and Th, and both of these edges will have an arrowhead at Tz.
Proof. We first note that for Fz,, By, #x) S S, the edges as - my and Fe >> Iy are inducing paths in G* relative to V 8 and thus the pairs Fy Ty and Te Ty are adjacent in both L MAG (G", () and (Xs). To show that both edges will have the edges have arrowheads at Iy in every [L (G*, S)]. By property (1) of Definition 3.4, both edges will have arrowhcads at Fy in I MAG "G*, S). Given {a,, form an unshielded collider in G*, all sets that d-separate x; from Ik in G* do not contain Ij. Thus given {ai, Iz, 4x C S, all sets that m-separate z; form Øg in MAG (G* do not contain Ij. and thus the collider is unshielded in L MMAG (Yhhann, 2008a).
arrowhead at xy in e (Xs), it thus remains to show
By definition of the MEC of MAG, every element MA S)] has the same unshiclded colliders, so every element in MA" S)] has arrowheads at z (Zhang, 2008b). Thus the PAG (Xs) P A. SS) has arrowheads at de both edges.
17

---

Published in Transactions on Machine Learning Research (03/2025)
3. For any u E S such that G v, if u (a)) with an arrowhead at in (Xs), then - in G*.
Proof. Given u N v for G* a DAG, either u + u in G or v in G Assume for the sake of contradiction that v + w in G By the definition of PGG an arrowhead at v in of (Xs), it holds that u and v are adjacent with an arrowhead at v for every element of [L MAG (G' (G*, ,)) By definition of the latent MAG, and in I, I.MAG (G*,
given u (Xss) v with
(Zhang, 2008a). In particular, u and v are adjacent with an arrowhead
adjacent with an arrowhead at v u in G", (2) ance. (v) and there is inducing path in G* between and relative to V V\S. S, or (3) there is some other inducing path between and v but u & ancg- (v) and & ancg- (u). If either (1) or (2) hold, then v + u in G would imply the existence of a cycle in G", contradicting the assumption that G is a DAG. Moreover (3) cannot hold, as given u NG* v it must that either u ancg. (v) or v E ancc- (u). Thus in all three cases we arrive at a contradiction, and so we conclude that A u G", and thus that + v in G
in I T. .)) implies that one of the following hold: (1)
B.2 Deferred Proofs from Section 4
In this section, we consider superstructure G satisfying Assumption 2, learner a satisfying Assump- tion 1, (SI,..., } a causal partition with respect to G and G*, and H the output of Algorithm on G, (Xs)) We begin by proving property (i) in Theorem Lemma 3. For any V E V, u ~u- v if and only ~g. V.
Proof. Consider any u, V such that u ~a- v. Because G satisfies Assumption 2, ~G v. By the definition of causal partition, (Si:..., Sx} is edge-covering with respect to G and thus 7i E [N] such that u, v E Sr. Moreover, given u, E S,, the edge between the two nodes in G is an inducing path with respect to V S, and so by statement (1) in Lemma 1, u (Xs))) u +- E Ecandidases- Moreover, for any subset Sj 3 u, the edge between u and t in G* is an inducing path with respect to V \ Sy. so u # V E Ej for all j such that u, v E Sy. Thus an edge between u and v will be added to E", so u -H- V.
Thus u ~g v and u (Xx;)s) v so
Conversely, consider any u, U, E V such that a Aa. If u HG v, or Ai E [N] such that a (Xs,))) s U, then Fcandidates will not contain an edge between and and thus neither will E". If ~a v and 3i E [N) such that u (Xxs) V, then Ecandidates will contain an edge between u and However because ( SN is causal partition, by property (ii) of Definition 3.5 there exists some j [N] such that u S, and u and v do not have an edge between them in Eg the edges of output (S,). Thus no edge between u and v will added to E*, We thus conclude that u ~ and only if ~a- v.
In order to prove property (ii) of Theorem 1, we will use the following lemma:: Lemma 4. For all u, U E V such that u - u in H", it holds that u - in G*.
Proof. If the output H contains directed edge u - v, then Lemma 3 implies u ~a- u and the definition of Algorithm 1 implics 3i E [N] such that u -> v is part of an unshielded collider u + v f+ w in (Xs,). Given u ~G- v, by statement (3) of Lemma the fact that u (Xx)))) v and of (Xx.) contains an arrowhead at implies that uuvvin in G
We now prove property (ii) of Theorem 1. Lemma For any unshielded collider u - <- w in H", holds that u + v +- w in G*
The proof follows directly from application of Lemma
We conclude with the proof of property (iii):
Lemma 6. For any unshielded collider u + u + G*, a ~yr and ~g- w and both edges have an arrowhend at v in H
18

---

Published in Transactions on Machine Learning Research (03/2025)
Proof. Given any unshielded collider - v <- w in G*, Lemma 3 implics that u ~ v, ~He w, and A w. It thus remains to show that the v-structure edges are oriented correctly in H By the definition of a causal partition, 3i such that {u, u, w] _ S.. Thus by statement (2) in Lemma 1, u +ー v and wo ++ in sf (Xs.). Thus the condition in Line 5 is satisfied so both u - v and w + v will be added to E", and thus the edges are oriented correctly H
B.3 Deferred Proofs from Section 5.1
Throughout this section, we assume superstructure G satisfies Assumption 2. Consider (S ,N} be vertex-covering partition of G and denote by (S'....,K' J the causal expansion of (Si...., SN) with respect to G.
In order to prove Lemmaa 2, we introduce several auxiliary lemmas. Proving that the causal expansion satisfies properties (i) and (iii) of Definition 3.5 is straightforward. These arguments are contained in Lemmas 7 and respectively:
Lemma 7. The overlapping partition (S),..., S'y is edge-covering with respect to superstructure G.
Proof of Lemma 7. Consider any u such that aa Because the original partition (S ,N} is vertex-covering, 3i E [N] such that u St. Moreover, Ng v E neighbors(u) S. U Oon = S% ]
Lemma 8. Given any unshielded collider in G", u + - w, there erists i E [N] such that fu, w) S S.
Proof of Lemma 8, As the original partition {Si,..., SN} is vertex-covering, 3i E [M] such that v E S. Moreover as G satisfies Assumption 2, ~ u and w Ng v. Thus by definition of the expansive causal partition, {u, U, w) C S.
Proving that the causal expansion satisfies properly (ii) of Definition 3.5 is more involved. We first establish the following helper lemma:
Lemma 9. Consider any S SCV and any u, E S such that t.. in DAG G Then any path II C S such that [en > 1 is not an inducing path between u and in G relative to V\S. S. Moreover, any path II = (u, 91, 92. .,, 9k-1, qk. v) such that either (u, 92,32 S S or 99.-1, v} S S is not an inducing path between u and u in G relative to V V.
Proof of Lemma 9. Both conditions on imply the existence of non-endpoints q, adjacent along path II. By definition of an inducing path, q and o' must both therefore be colliders on II. This implies that the edge between q and d' in path II must have arrowhead at both q and of in G However G is DAG and cannot contain bi-directed edges, so q and q' cannot both be colliders on II, and IT is therefore not an inducing path.
We now use Lemma 9 to prove that the causal expansion satisfies property (ii) of Definition 3.5: Lemma 10. Given any u fo- v, there exists i E [N] such that such that v E St and u + * V.
Proof of Lemma 10. Consider some u, v E V such that u za- v and u Aa v. Recall that by Assumption 1, for any subset Sy AAS))) and only if there is an inducing path between u and v in G* relative to V Sy. Thus to prove Lemma 10, it sulfices to show that Di E [N] such that no inducing path exists between u and in G* relative to V S. By Lemma 9, any path II in G* of length greater than 1 such that II C S cannot be such an inducing path. As u Åg- all paths between u and in G have length at least 1. Thus to prove Lemua 10, it suffices to show that Di E [N] such that no inducing path II with lIn[V), \ S + 0 exists between u and v in G relative to V VAS.
By Lemma 7, 3i E [N] such that u, E S). For any u E S C V, denote by dista- (u, S) the shortest-paft distance from u any node dout (S). In other words, dist (u, Oo is the minimum number of edges between a node and any node w o S. Note that for any E S, disto- (u, Sm 1.
19

---

Published in Transactions on Machine Learning Research (03/2025)
Examples of Non-Inducing Paths
P
4
42
4
9
(a)
(b)
Nodes subset $
Edges G"
Edges in
Ancestral
non-inducing path
Nodes in V
relationships
Figure 9: Examples of non nou-inducing paths. The example in (a) illustrates the case described in Lemmna 9. This path is not inducing because qi, 92 are non-endpoint paths 8, but they are not both colliders on the path. The example in (b) illustrates Case 2 in the proof of Lemma 10. The definition of an inducing path requires that q be an ancestor of u and qu be an ancestor of u, but this implies the existence of a cycle G contains u, q. U, and 94- Thus this path cannot exist.
We consider four cases, parameterized by the distance from the endpoints u, to So Note that these four cases cover all possible positionings of and v within Sy. Thus to prove Lemma 10, we must show that each case implics the existence of some S' (S)....... 3 not necessarily equal to Sii, such that u (s)) v.
Case 1. max (dista- (u, Oout Oout-S)), distor (v, oot > 2
Case 2. dista- (u, dout 5 dist.: (v, So) = 2.
Case 3. distig- (u, Sout 5 2, and dista- (v. Oour
Case 4. disti (u, Oout St dista (v, S1) =.
We now show that in each case, there exists some 5' E
such that a Af((s)) v.
implies that for any path II between u, v either II S% that II contains a prefix {u, Qı, 92) S S, that II contains suffix {9--1, 4k, v} S St. In all of these cases, Lemma 9 implies that 1l is not inducing path between and in G* relative to V SS. Thus u ux (S()))
Case 1. max (disto (u, SQ), dista- (v, 0our S
Case 2. distg- (u, dout dist (v, S) = implies that for any path II between u, U, either II S S or that II contains a prefix {u, q1} S S² and suffix {q,, v) S S. If S 5% then is not an inducing path.
Consider the case when II contains prefix {u, Q1 S and suffix (2k,0) S and assume for the sake of contradiction that II is an inducing path between and in G relative to V S. Both qi and qs are non-cndpoint vertices on II n S.. They must therefore be colliders on II as well as ancestors of at least one of or v. Since qi be a collider on II, it must be that - so u E ancg- (gi), where
ancg-(x) {2 E V z is an ancestor of x in G*}.
Moreover, qi must be an ancestor of either v, and because ancestor of u this would imply the existence of a cycle in G Thus it must be that 91 E ance- (v). However, we similarly conclude that as q be collider on II, it must be that l +- uso E ancg- (gx). Moreover must be an ancestor of either u or and qa cannot be an ancestor of as G is acyelic, so (a E ancc-(()) (u).
anca- (q1) it cannot be that @i is an
However we have thus concluded that E anco- (q1), di anc (v), anc (qx), and q E anc (u). This implies the existence of a cycle in G", and thus cannot occur. Thus we conclude that no such path II can be inducing path between and in G* relative to V \ S% Thus (f
20

---

Published in Transactions on Machine Learning Research (03/2025)
Case 3. Recall that by definition of the expansive causal partition, S S; U (S.) for original vertex- covering partition {Si,..., ,N), where the outer boundary dout 0o,t(S) is defined by the edges in superstructure G. Given distc (u, Sy) = 1, 3z & S such that u ~G- 2. Moreover, as G satisfies Assumption 2, this implies V ~G 2. Thus by definition of the expansive causal partition it must be that V E S As the original partition (St...., ,Sr] is verlex-covering, this implies Aj E [M] {i] such that V E S.. Moreover, as u NG 0, this implics u, v E 5 and that in Sj, dist(w,, oott (S)) 2 and dist(a, (u, Oout (St)) 2 1. If dist(u, Sout (S)) > 2 or du, dorr (5)) > 1, then either Case 1 or Case respectively imply that u * v, which would conclude the proof. It thus remains to consider the case where dist(v, dout dout (5))) = 2 and dist(u, Sout
Oout( (S))) = We thus have the following setup: by assumption of Case 3, dista- (u, Sour St) = and dista- (v, oou 1. Then by the above arguments, we have shown j * i such that dist.- (v, Dont 2 and dist.. (u, Ooy 1. Assume by way of contradiction that (S) and (8; Thus by Assumption 1, there must exist II; and inducing path between u and o with respect to V S and IT an inducing path between u and v with respect to Syy
As distg- (u, St) 2, II must contain a prefix {u. & II n S; where qi * v. By definition of an inducing path qe must be a collider on II in G", so ance- (g:); and qe must be ancestor of either u. As G is acyelic and ancc. (qi), qi cannot be an ancestor of and must therefore be an ancestor of vi qi E ancc- (v).
Similarly, as dist (v, Sy = 2, N must contain a suffix {g,0) o} S Sy such that oj # u. Moreover by an analogous argument to the above, V E anco. (4j) and qj E ancg-u. u.
We have therefore concluded the following: 3q, qj V such that u e ancg-(q.). q E (ncc.(u), v ancg. (q;): and Oj ancc- (u). However this implies the existence of cycle in G*, which contradicts the assumption that G is DAG. Thus it cannot hold that both (S)) v and u (S)) U, so we conclude 38' E (S S such that u ) V.
Case 4. Given distg- (u, St) = dista- (v, S) = 1, 32 & S such that u ~g- 2. As superstructure G satisfics Assumption this implics u ~a z and thus by definition of the expansive causal partition, implics u E S \ S.. As the original partition was vertex-covering, this implies 3j + such that u E Sj. Thus by definition of the expansive causal partition, St and disto- (u, S 2 2. Moreover as ~g U, E S as well.
If disti- oor St) > 2, then Case 1 implies u ( V. If distg (u, Sj) = 2 and diste- (v, Sy) = 2, then Case 2 implies u (s)) v. If dista- (u, Sor = 2 and dista- (v, Dour 1, then the argument in Case implies the existence of + j such that either u * v or u ( v.
We have thus concluded in each case that 3S' E (S,....,, 3 such that u A u and so the statement of Lemma 10 holds.
Lemma 2 follows directly from Lemmas 7, 8, and 10.
C Finite Sample Effects
While the theoretical results in Section only apply to the infinite data regime, this section we discuss heuristics for addressing the effects of lcarning with finite samples and describe a practical algorithm for real-world causal discovery problems. In the finite data setting, there two key ways that finite samples cause divergence from the idealized assumptions studied in Section 4: (1) the superstructure may be im- perfect and (2) the result of learning over local subset may not be a latent projection and therefore the merged graph may contain cycles. We describe our finite sample screening procedure in Algorithm 3. In score and discard, we resolve cycles by discarding the edge corresponding to a the lowest score, where the score is related to the lieelioel of the data with and without each edge in the cycle.
Imperfect Superstructure: : In real-world causal discovery applications, one may wish to learn a super- structure G from data (Constantinou et al., 2023). Several algorithms for learning superstructure from
21

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 3: Screen_Finite
Finite Data(G, P (H X)
Input: a superstructure G, set PAGS {H. (St, E.) a matrix of observations
Result: H' = (V. E") PAG
Initialize = - S1; Ecandidates +- U E -
foreach u, such that {u x) E Bcandidates do
// If an edge between " and v appears in the learned output on all subsets containing u and v, add edge to output graph.
if vi s.t. S: 2 v), ~(8,) then
// If edge appears oriented in output, add oriented edge to E" if Di such that E, 3 {u + b} then
4
5
E" E
6
else
7
L E + EUfuooo))
H' + -V)
while H" contains eycle C do
10 H² < acore and discard HI", ,, (St,...,SW)) X))
11 return π (V. F"):
data exist; many, including the PC algorithm, are more easily parallelized than greedy score-based learners and thus can be run on the global variable set in reasonable time (Zarcbavaní et al., 2019; Le et al., 2016) However, when the superstructure G learned from data, it may be imperfect, i.e. there may exist edges G which are not in G. If the superstructure is missing a large fraction of the ground-trute edges, the step in Screen, which discards edges not in the superstructure may significantly reduce the rate of true positive edges returned by the algorithm, with the effect growing more severe with more imperfect superstructures. Thus in the finite sample limit, if working with superstructure which is suspected to be highly imperfect, one option is to simply omit the step in Screen, which discards edges not in the superstructure. In Sec- tion 6.3, we examine the impact of learning imperfect superstructures from data, and show while imperfect superstructures do impact learning significantly, the expansive causal partition is most effective out of all partition schemes.
When the result of learning over subset is not latent projection, the algorithm presented in Section 4 may fail to return DAG. In particular, even if the output sf (Xs,) is DAG on every subset S,, the output of Screen may contain cycles. However, it is possible to localize these cycles; if the output (Xs.) is a DAG on every subset S,, then any cycle in the output of Screen(G, (e/ (Xs;) ) will have some edge (u, v) such that one of the two endpoints lies in the overlap of partition {S....., Sx). i.e. di / j such that {u, v} n (S, S, *
Potential cycles:
Using this observation about the location of all cycles in the output of Screen, adopt the following procedure. If the output of Screen contains a cycle, find all edges in that cycle which intersect with the overlap of partition {S,,.... SrJ. We then rank these edges using scoring function and discard the lowest-ranked edge. While a variety of edge scoring functions may be deployed for this step, in this work we assess edges using the log-likelihood induced by the linear structural equation
W (C) X, t
X,
(2)
where (GG) denotes the weighted adjacency matrix of a DAG G and e NNO of) denotes additive Gaussian noise. Then joint distribution of (X,...X,, Xp) is a multivariate Gaussian distribution A/ Σ) where Σ = WWT. The log-likelihood under this model is
[(W Σ
log(o,))
|| XW,I1
(3)
20
22

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 4: score_ _nnd____d_____ _idcadd
Input: a graph G, list of edges comprising a cycle in G, {S.)am) partition of the nodes of G, a matrix of observations X
Result: modified copy of G' which does not contain cycle C
V + N (S,
// overlapping nodes
É + ++0:
// /vverlapping edges
foreach (u, EC do
if VEEV or u V then
v(,
+ arg min MEE loghikeelthodd_ccree G,X);
(r)
return G;
Algorithm 5: (ogglkeellhoodsscr((........
Input: a node i, node j, graph G, a matrix of observations X
Result:
a score based on the likelihood of graph given the data the presence and absence of edge (i,j)
// least squares estimates of Eq. 2
M/(G")) < LSE(X,, G
Σ + cxv // covariance matrix of X
// log-likelihoods from Eq.
lūj 1(WiG"")) E)
40 t 1(1 Σ)
score + 4i lo
return score
In order to score edge (i,j), compare the log-likclihood at the least squares estimates (LSE) of the regression coefficients (Wi)) in Eq. 2 of two different DAGs: Gtú which contains edge (i,j), and GD. in which we remove edge (i,j) so that is no longer a parent of j. Edge (i,j) is then scored by how much including as parent of increases the likellidd of X, under the linear structural equation. The likelihood based score is outlined in Algorithm 5. The full procedure for cycle resolution is outlined in Algorithm 4.
In the case when the detected cycle has length two, i.c. there exist edges (i.j) and (J, ú),, we adopt the methodology of Gu & Zhou (2020) and use the risk inflation criterion (RIC) to determine whether discard one both of the edges forming the cycle. In this setting compare three models: Giu in which i is parent of j, God in which j is parent of i, and G in which neither edge appears. We then compute the RIC score for each model, which balances the log-likelihood with a sparsity-promoting term penalizing the total edges in the graph. If the model Go out-performs both Ghu. and G..,, then both edges are removed from the graph. If at least one the models G.,, GDA out-performs GO, then the better- perterrierfominnggg edge is retained and the other odge is discarded. For further details on using the RIC score to assess edges, we direct readers to Gu & Zhou (2020).
D Computational Complexity of the
Method
The motivation for the divide-anddcooquue method developed in this work is that existing causal discovery algorithms' computational complexity grows prohibitively large as the number of variables in the dataset increases. The computational cost of the dividc-and-conquer method includes the expense of producing the initial partition (D constructing the causal expansion {D, doue (D,) running some causal discovery algorithm each of the subsets D, U amn (D,); and merging the results using Algorithm 1.
23

---

Published in Transactions on Machine Learning Research (03/2025)
For most reasonable choices of partitioning algorithms, the dominant cost in the divide-and-conquer pro- cedure will be running causal discovery on each subset in the expansive causal partition. A key aspect of the divide-and-conquer method's speedup is that the problem of running causal discovery on each subset of the expansive causal partition is embarassingly parallelizable. For any causal discovery algorithm, let F(-) describe the worst-case runtime as a function of the number of random variables the input, and let p denote the number of random variables in the global dataset. Running causal discovery on N subsets in par- allel on a machine with N processors reduces the dominant cost from F(p) to max F[[D:] |Oouc In settings where P < N processors are used, the wall-clock time for performing the parallelized causal discovery on subsets using P processors is given by Brent's law (Smith, 1993) 5 and is
Sour (D))))
N E F(ID,) + | (D.)I)
1 P
o max F(IDa) + 10o (D.)) + .E[M]
For all causal discovery algorithms satisfying Assurnption known to the authors at the time of publication, the computational complexity F(-) is dramatically super-lineal such that F( (ou((D))) < F(p), as shown below for the FCI algorithm.
As example, we describe the computational complexity of the full divide-and-comquue procedure in a simplified setting. Consider a variable set V of cardinality p, and assume the superstructure G reflects strong community structure. Specifically, consider the stochastic block model setting: each variable in V belongs to one of two equally-sized hidden communities and that for any two variables u, E V, G contains an edge between u and u with probability Zin if u and belong to the same community, and probability qout if they belong to different communities. We consider regime where these communities can be efficiently recovered with high probability: assume
Tin = a/P,
Yout 3/p
for ax, 3 > O and va- vB sufficiently large. This regime is well-studied, and in this setting known clustering algorithms exactly recovery the underlying partition with high probability in nearly-linear time Opp (p)) (soc c.g. Abbe & Sandon (2015); Wang et al. (2020)). Employing these clustoring algorithms, with high probability we recover an initial partition D1, D2 such that |Di| [22 = p/2. Moreover, in expectation Oout (Di)l Omaa( (ma)) [2)] p3/4, so conditioned on exact recovery the size of the clusters in the causal expansion are (1/2 + 3/4)p in expectation.
We consider running causal discovery using the FCI algorithm, which satisfies Assumption 1. While the FCI algorithm does not perform every pairwise conditional independence test, in the worst case its runtime still scales exponentially with the size of the input variable set, e.g. F(p) = d for c E (1, (Spirtes, 2001). When run in parallel on two processors, the wall-clock time will be exponential in the size of the subsets of the expansive causal partition: conditioned on exact recovery, for any fixed E (0,1- 8/44, D, U dona (D.)) S (1/2+ + 3/4+ + 8)p with high probability. This corresponds to reducing runtime from d to (1/2+//4455) The complexity of merging the results of the causal discovery outpul using Algorithm 1 is a function of the number of learned edges and maximum learned degree. In the SBM setting, with high probability its runtime is O(p(p + g)p²) = a(a(a + p))))
In total, the time to run the sovide-and-ooquue procedure when parallelizing the causal discovery step is
o (plog" + (1/2-8/4448) + +a(a + B)pp)
with high probability. In the large variable regime, the exponential term c1//2+8/4+5)p dominates the runtime of the divido-and-conquer procedure. We compare this with the runtime of the FCI algorithm on the global variable set, which is O(CP). For small values of B, the divide-and-conquer method reduces runtime compared with the runtime of FCI on the global variable set from di to R Vep, which represents considerable computational savings in the regimes of interest when is large. This small-3 regime corresponds to the setting where few intra-cluster edges are present.
The first term the expression the dominant cost in time if the probelm is run on N processes. The second term the time if the problem is run in serial divided by the actual number if processes available P
24

---

Published in Transactions on Machine Learning Research (03/2025)
E Controlling Maximum Subset Size
A key factor in accuracy-timing tradc-offs is controlling the size of the largest subset in the partition. Here we observe that the largest. subset produced by the causal expansion in Section 3.4 is governed by specific connectivity properties of the initial partition on which it is built. In particular, for graphs with strong community structure, if the initial partition is strongly correlated with community structure, then the resultant subsets in the causal expansion will not be much larger than any of the subsets in the input.
For the causal expansion defined in Section 3.4, the maximum size of any subset is controlled by the sizes of the subsets in the input partition and their corresponding vertex expansion values. For any set S such that [S] S /1, the vertex expansion of S in graph G is defined as
A(S) Dout (5) |S|
If the input expansion ..,, Sy} satisfics |S I VV/2 for all i E [M), then the size of subsets (S,,..., ,''. in the causal expansion is controlled as
S - NE
max
max (1 + h(S,)) JE[N]
In particular, the superstructure has strong community structure and the initial partition (Si,..., SN is constructed appropriately, then the subsets of the causal expansion will not be dramatically larger than those the initial partition. See Appendix G.
F
Experimental Setup
F.1 DAG generation
Ground truth DAGs, G are syuthetically created using a Barabasi-Albert scale-free model (Barabási & Bonabeau, 2003). A random topological ordering is imposed on the nodes that the graph is acyclic. Data is generated assuming a Gaussian noise model: (X1..., Xp) ((X1,..., Xp)W)T +e where ~ (N0,, W is an upper-triangular matrix of edge weights where Waj * 0 if and only if > j is an edge in G*. The variance o² is uniformly sampled from (0, 1]. Each column vector X; represents the data distribution for a variable corresponding to a node i in G For our experiments we create graphs (p=50) with two communities, where each community has a Barabasi-Albert scale-free topology and communities are connected using preferential attachment. Any cycles created by this are removed to ensure the graph is a DAG.
F.2 Partitioning Algorithm Parameter settings
this section we describe the parameter settings for the partitioning algorithms: Disjoint, Edge Cover, Expansive Causol and PEF. The Disjoint partition networkx. grrezyggred.... wwweggrrrreeedeeeee wwy.mudduarit.... For networks with 100 communities of size 100 nodes, we set the best_r and cutoff both to 100. For all other experiments do not set those parameters. These parameters are also used for the Edge Cover and Expansive Causal partitions, and there are no additional parameters that need to be set here. For PEF, the minimum size of each community is set in order to select the optimal partitioning, For networks with 100 communities of size 100 nodes, this is set to 1% of the size of the node set. For all other experiments this is set to 5% of the size of the node set.
F.3 Causal Discovery Algorithm Parameter settings
In this section we describe all the parameter settings for the causal discovery algorithm a used for local learning. The four algorithms we chose are GES, PC, RFCI, and DAGMA. For GES, PC, and RFCI we use the implementations in the pealg library. For PC and RFCI the significance level a was set 0.001. For GES, fixedGaps which controls which edges are added in the greedy search set all the edges not in the superstructure, maxDegree is not limited, and adaptive is set to "triples". For DAGMA, used the
25

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm
1000
Algorithm
Rundime (sec)
60-
No Partfion
Exparsive Causal
750
Expansive Causal Cover Disjsin
Edge Cover
Runtime
500
Disjont
20
250
x
0.8
8
TPR
200
400
800
800
1900
200
4.0
600
800
1000
Size of Largest Subeet
Sizo of Largest Subset
Figure 10: Left: Accuracy and time trade-off for 1,000 node hierarchical scale-free graphs with 1,000 samples. Right: Accuracy and lime trade-off for 1,000 graph with ten communities of size 100 with scale-free lopology with 1,000 samples. We see that certain subset sizes take unexpectedly long for GES learner.
LinearModel with L2 loss. During optimization lambda1 was set to 0.02, while all other parameters were set to the default. These parameters were consistent across all experiments.
F.4 Details merging DAG subgraphs
Causal discovery algorithms GES, PC and DAGMA do not satisfy Assumption 1 and instead output a DAG (for the PC algorithm we randomly choose graph in the MEC). Despite this, we still employ screen operation when merging subgraphs in a similar manner to Algorithm 1. However, given there are no consistency guarantees over the observed subset of nodes for these algorithms, it is possible that after merging the resultant directed graph contains cycles. Therefore for these algorithms we employ the algorithm discussed in Appendix C which accounts for the presonce of cycles. For these learners Algorithm now takes in a set DAGs instead of PAGs and returns DAG.
G Time and Accuracy trade offs
The computational bottleneck for divido-and-conquer algorithms is the size of the largest subset: max; [S,] for partition Sw This is because expect causal discovery algorithms converge to an estimated graph faster for smaller variables sets (the graph space defined by a smaller variable set is smaller). However, we observe that the convergence of GES appears to bo a function of both size of the subsct, and the topology of G Fig. 10 (left) shows the time to solution and TPR as the size of the biggest subset increases. For this study, we use 1,000 node hierarchical scale-free graph. This equivalent to the types of graphs Section 6.4. To control the size of the subsets we fix the number of communities and resolution for the greedy modularity disjoint partition the largest subset. Here, we see expected scaling behavior as the size of the largest. subset increases does the time solution. The largest time to solution is for the non-partitioned method on the entire 1,000 node graph. This means that partitioning the graph always enables some scaling. The Expansive Causal and Edge Cover partitions are extensions of each Disjoint partition. We observe that for our proposed partition methods (Expansive Causal Partition and Edge Cover) we do not increase the size of the largest subset significantly (this aligns with notes in Appendix E), and we benefit from a significant boost in accuracy. In the same study but with 1,000 node graph with 10 communities, each with size of 100 and scale-free topology. This is equivalent to the types of graphs in Section 6.1 through Section 6.3, but with more communitics. Here, we observe good scaling when the size of the largest partition is small and close to the size of the natural communities. However beyond this, the time to solution increases to be even larger than the non- non-partion partitiidd method. This suggest that certain 'bad' subsets incur a longer convergence time for the GES causal discovery algorithm. We hepothesize this is related to violation of causal sufficiency of these subsets subsets that contain more confounders (unobserved common causes) outside may result in sub-optimal convergence in the GES learner. Note that this result is not due to our causal partition
sweep through five different disjoint partitions, increasing size of
Fig. 10 (right)
26

---

Published in Transactions on Machine Learning Research (03/2025)
the divide-and-conquer methodology, but rather because of the use of the GES learner in this setting. Still, since can control the size of the subsets with the disjoint partition we can still achieve accuracy and time benefits with GES as shown in our empirical results.
27


Reviews:
[{"review_id": "ZVKVNjiTys", "reviewer": "Reviewer_wGWB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nThe manuscript is **clearly written and includes all relevant details** in the background section to understand their proposed *causal partition* (although I have some comments to further improve clarity in the next section). At the end of the introduction section, the authors accurately state their contributions without overstatement; while the idea of divide-and-conquer has already been implemented in the causal discovery literature, **the proposed *expansive causal partition* is a novel approach with guaranteed consistency** (albeit under certain assumptions that I will discuss later). The authors include extensive **ablation studies** to analyze the effects of (i) sample size, (ii) the quality of the superstructure, (iii) number of nodes and graph topology, (iv) graph partitioning methods, and (v) underlying structure learning methods on the quality of the final learned DAG, measured by metrics such as true/false positive rates (TPR/FPR), structural hamming distance (SHD), and computation time. By looking at Figures 3-5 and Tables 1-3, a practitioner can gain lots of insights about the circumstances in which the proposed algorithm outperforms simpler baselines (for example, in most cases, using an edge covering partition—a simpler variant of the causal partition—could achieve similar TPR and SHD while reducing computation time). The authors provide the **computational complexity** of their method and conduct **large-scale experiments with 10,000 nodes**, as well as more biologically informed experiments on a synthetically tuned E. coli network, which shows the applicability of their method at scale.\n\n### Weaknesses \n\n* A critical limitation I would like to see fixed before acceptance is the **oversimplified data-generating process (DGP) in all experiments**. All experiments, including the \"biologically-tuned\" E. coli network, employ linear link functions with additive Gaussian noise of equal variances. This is one of the simplest possible DGP choices and contradicts the practical spirit of the work I mentioned above. This limitation becomes especially problematic for imperfect superstructures (Appendix C), where a score-based approach is taken to eliminate cycle-inducing edges and assumes a correctly specified linear likelihood model with known variance. Such an assumption rarely holds in practice. I suggest the authors incorporate more complex DGPs, potentially drawing inspiration from benchmarks like SynTReN [1] for more biologically plausible data generation.\n\n* The second limitation is **Assumption 2, requiring a superstructure that constrains the true causal graph**. While a fully dense graph is a trivial choice here, using that would make the causal partition equivalent to the no-partition case. The authors suggest using the PC algorithm to obtain a non-trivial superstructure. However, this appears to be a circular argument—if the graph is high dimensional and necessitates a divide-and-conquer approach, running PC on the complete variable set should become impractical. I appreciate the authors providing some practical solutions for imperfect superstructures. However, their recommendation to use PC on the entire variable set is questionable and requires further justification.\n\n[1] Van den Bulcke, Tim, et al. \"SynTReN: a generator of synthetic gene expression data for design and analysis of structure learning algorithms.\" BMC bioinformatics 7 (2006).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission addresses the problem of learning Markov equivalence classes of causal graphs in high-dimensional settings, such as biological networks, where current state-of-the-art causal discovery algorithms may require hours or days to learn the structure. The authors propose a divide-and-conquer approach to reduce the runtime to seconds or minutes. Their method assumes that a non-trivial superstructure of the underlying causal graph is given and uses a novel graph partitioning technique, called _causal partition_, to divide the large graph into smaller subsets. Their practical algorithm enables the use of any arbitrary structure learning method (e.g., PC, GES, FCI) on each subset and then merges the results to obtain the final DAG. Under certain assumptions, including the consistency of the underlying structure learning method, the authors prove consistency of the proposed divide-and-conquer approach. They provide an extensive set of synthetic experiments on large graphs (up to 10,000 nodes) to demonstrate their performance compared to other divide-and-conquer methods such as PEF (Gu & Zhou, 2020). Additionally, they present ablation studies to assess the impact of sample size, imperfect superstructure, and other factors on the final results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I provide less critical questions/suggestions here. Please see the **Weaknesses** in the previous part for more critical comments.\n\n**Methodology and Experiments:**\n\n1. Please clarify in the main paper whether the divide-and-conquer algorithm supports recursive/hierarchical partitioning.\n\n2. An ablation study on the optimal number of partition subsets ($N$) would be valuable.\n\n3. Please include the optimal SHD (i.e., SHD range for correct MEC) in Figures 3-5.\n\n4. How does the merging process work for other partitions like disjoint and edge cover? Is it similar to the expansive causal partition? Please clarify this in the paper. \n\n5. How do you create an edge cover partition?\n\n6. Why do you only include the GES algorithm in Tables 2 and 3? As you already mentioned, GEC does not satisfy Assumption 1. Why did you not include RFCI, which satisfies the assumption?\n\n7.  In Appendix C, under the \"Imperfect Superstructure\" paragraph, it is mentioned that the PC algorithm is more easily parallelized. What exactly do you mean by that? Could you compare your results to those of using a parallel PC?\n\n8. The pseudo-code described in Algorithm 4 appears to not exclude edges like $(u, v)$ where both nodes $u$ and $v$ belong to the same subset $S_i$. However, based on the description in Appendix C, such edges should be excluded. Maybe you could add an extra if statement.\n\n9. In Section F.1, the data is generated based on $(X\\_1, \\ldots, X\\_p)^\\top = \\left( (X\\_1, \\ldots, X\\_p) W\\right)^\\top + \\epsilon$. What is the initial distribution of $(X\\_1, \\ldots, X\\_p)$ on the right-hand side?\n\n10. Appendix G mentions that *\"We hypothesize this is related to violation of causal sufficiency of these subsets – subsets that contain more confounders (unobserved common causes) outside may result in sub-optimal convergence in the GES learner\"*. Shouldn't we expect to have fewer confounding issues as we increase the size of each subset?\n\n11. The following observations in Figure 3-5 need further explanation:\n\n    * In Figure 3 (DAGMA), why does SHD increase as the number of samples increases?\n    * In Figure 3 (RFCI), how is the SHD worse for the no-partition method than yours? Shouldn't the no-partition case provide the best results? This is also similar to that seen in Figure 4 (RFCI).\n    * In Figure 5 (and sometimes in other figures), the results are noisy, and sometimes, there is no clear pattern, even if the quality of the superstructure is higher. This may be due to the randomness in the generated graph structures. How many random seeds did you try? It might be beneficial to fix a set of graphs and only change the superstructure to account for other sources of randomness. \n\n\n12. In almost all the plots in Figures 3 to 5, the results of RFCI are worse than DAGMA. If RFCI is the only method that satisfies assumption 1, why are its results worse? \n\n**Format and Clarity:**\n\n1. Why is the proposed partition called \"causal”? Why does your title suggest causal discovery? This is probably a matter of personal taste, but I find the title slightly misleading. I couldn't find any claims or methodologies in this manuscript about *interventional distributions* (and thus causal). The proposed method can only learn the Markov equivalence class of the underlying DAG and, therefore, cannot estimate all the cause-effect pairs. This is indeed expected from observational data (unless further assumptions are made on the link functions or exogenous noise). Having a small remark might address any potential misunderstanding here.\n\n2. In the Background section, please cite the relevant work when introducing new terms like m-separation, PAGs, MAGs, etc, to distinguish between what you define and what is standard. \n\n3. I noticed that the paper consistently places footnotes before periods. They should generally go after the punctuation. \n\n4. The symbol $\\sim$ is used in Lemma 1 but is only defined later in Section 5.1. Please define it earlier. Similarly, it would be better to define edge-covering partitions in Definition 3.5 (Although the name is suggestive, I would rather see a more formal definition to avoid misunderstanding).\n\n5. What is the definition of $m_1$ and $m_2$  on page 7, under the default parameters paragraph?\n\n6. Please try to make Figures 3-5 slightly larger. It's hard to read all the details on paper.\n\n7. For section 6.3, do you use the variant discussed in Appendix C? Please mention that explicitly in the main paper.\n\n8. There are sentences that I find hard to read/understand. There might be grammatical issues. I mention them here:\n\n   * \"As the sample size increases, we see the convergence of No Partition with the MEC of $G^\\star$, and the convergence of our causal partition with No Partition.\" -- The first paragraph below Figure 3.\n\n   * \"a 10,000 node network comprised of one hundred, 100 node communities with Barabasi-Albert scale-free topology.\" -- Figure 6 caption.\n\n   * \"We observe that for our partition methods we (1) do not increase the size of the largest subset significantly, this aligns with notes in Appendix E (2) benefit from a significant boost in accuracy.\" -- Appendix G.\n\n9. There is a missing period at the end of the last sentence before Section 7.", "broader_impact_concerns": "I don't think there are ethical implications for this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2XDkPAsfGL", "reviewer": "Reviewer_8zeN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n* The paper is well-organized and easy to follow.\n* The proposed causal partition framework is algorithm-agnostic and practical. It can be integrated with any kind of causal discovery (CD) algorithm and potentially be scaled up to large-scale analysis in other science fields. \n* Under well-defined assumptions, it has consistency guarantees using the Maximal Ancestral Graph (MAG) under infinite data limit. It also doesn't require additional learning steps regarding aggregating local results from partitions to the global structure. \n* The authors conduct a comprehensive evaluation from different perspectives (number of samples, network size, superstructure density, CD algorithms, partition algorithms...) and present the effectiveness of the framework. Compared to the PEF and no partition baselines, it exhibits significant speedup and maintains reasonable accuracy.\n\nWeakness\n* The proposed algorithm requires the causal discovery algorithm to tolerate hidden confounders for partitions. \n* The reliance on the perfect superstructure is strict. The extra time complexity and efficiency of acquiring a good initial superstructure also need to be considered when combining the framework here.\n* The sample efficiency issues need to be taken care of. The computational benefits at the cost of reduced accuracy observed in the E.coli experiment are less pronounced than in previous experiments. \n\nQuestions\n* The causal discovery algorithm's runtime is often affected by the sparsity of the true graph, how would this framework behave under different scales of the sparsity of the true graph?\n* Figure 5 shows the framework's stability under the different PC-generated superstructures. How would the distinct initial superstructure (generated in different ways) affect the result in terms of accuracy and efficiency (including the time of generating an initial superstructure)?\n* Are all partitions showing consistent recovering quality, or do some partitions exhibit extremely good or bad?\n* The number of partitions seems like an important hyperparameter, could the authors elaborate more on how to choose it and the effect of it?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel approach to scaling causal discovery for high-dimensional problems through graph partitioning. The authors introduce the concept, \"causal partition\", which leverages a superstructure (known or learned hypothesis space) to partition variables into disjoint partitions and then expand to overlapping subsets for divide-and-conquer causal discovery. They theoretically prove that under certain assumptions, learning with such causal partition recovers the Completed Partially Directed Acyclic Graph (CPDAG), corresponding to the true causal graph. They also develop an efficient algorithm to construct causal partitions from any initial disjoint partition, making the method adaptable to different graph topologies. Empirical validation on both synthetic networks (up to 10,000 nodes) and biologically-tuned E. coli networks, demonstrating practical scalability while maintaining reasonable accuracy.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* It would be nice to include an analysis of the effect of different scales of sparsity on the framework's outcome.", "broader_impact_concerns": "This framework is practical in improving the inference efficiency of causal discovery applications for scientific discovery. The authors should include more about the benefits and limitations of applying this method in such scenarios and the consequences/outcomes of wrong inferences in the broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tI4N00bwPQ", "reviewer": "Reviewer_FLui", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\n    - Theoretical guarantees for causal discovery algorithms are always difficult to provide: their presence increase the quality of the manuscript consistently.\n    - Divide-and-conquer algorithms are known to lead to fast parallel implementations, especially in the context of causal discovery, which is usually computationally expensive by design.\n\n- Weaknesses\n    - The use of a superstructure that is assumed to contain a superset of the true edges hinders the real world applicability of the proposed method. This is supported by the (limited) evidence collected by the authors in the \"imperfect superstructure\" experiment.\n    - In general, the experimental results are quite hard to justify in the context of causal discovery: while it is true that the \"no partition\" option is significantly slower, the SHD is generally an order of magnitude better than the partition-based alternatives. It would be more interesting to include metrics about the \"causal properties\" of the structures, like the Structural Intervention Distance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- Definition of a novel causal partition of causal graphs.\n- Proof that under certain assumptions causal discovery with a causal partition is consistent.\n- Extensive experiments synthetic data in high-dimensional setting (up to 10^4 vertices).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Notation\n    - Authors tends to provide extensive definitions of sets, which makes the notation longer and increase the overall complexity. It would be better to define symbols for the most recurrent sets instead of listing the elements or the indices every time.\n\n- Experiments\n    - I would prefer to have more evidence in the case of an \"imperfect superstructure\", that is the usual case for most of practical applications.", "broader_impact_concerns": "No concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers raised valid points about the limitations of the method, but they do not invalidate the core contribution of the paper, only perhaps bring nuance (that can be reflected in the text of the paper) to the scope of the contribution.
Decision: Accept (poster)