An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer
Authors: Lifu Liu
Shiyuan He
Jianhua Guo
Venue: ICML 2025 oral (2025)
Keywords: Directed acyclic graphs
Markov equivalence class
Causality
Undirected connected component
Primary area: general_machine_learning->causality

Abstract: Efficiently counting Markov equivalent directed acyclic graphs (DAGs) is crucial in graphical causal analysis. Wienöbst et al. (2023) introduced a polynomial-time algorithm, known as the Clique-Picking algorithm, to count the number of Markov equivalent DAGs for a given completed partially directed acyclic graph (CPDAG). This algorithm iteratively selects a root clique, determines fixed orientations with outgoing edges from the clique, and generates the unresolved undirected connected components (UCCGs). In this work, we propose a more efficient approach to UCCG generation by utilizing previously computed results for different root cliques. Our method introduces the concept of super cliques within rooted clique trees, enabling their efficient transfer between trees with different root cliques. The proposed algorithm effectively reduces the computational complexity of the Clique-Picking method, particularly when the number of cliques is substantially smaller than the number of vertices and edges.

An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer
Lifu Liu Shiyuan He
*2 Jianhua Guo
Abstract
d-separation properties of the identified DAG correspond to the conditional independencies observed in the data (Pearl, 2009; Verma & Pearl, 1992; Spirtes et al., 2001). However, observational data alone is often insufficient to uniquely determine the true DAG. Instead, can identify a set of DAGs that encode the same conditional independencies, collectively known as Markov equivalence class (MEC). This limitation has driven extensive research into learning MECs from both observational and interventional data (Perl- man, 2001; Geiger & Heckerman, 2002: Chickering, 2002; Castelo & Perlman, 2004; Maathuis et al., 2009).
Efficiently counting Markov equivalent directed acyclic graphs (DAGs) crucial in graphical causal analysis. Wienöbst et al. (2023) intro- duced a polynomial-time algorithm, known the Clique-Picking algorithm, to count the number of Markov equivalent DAGs for given completed partially directed acyclic graph (CPDAG). This algorithm iteratively selects a root clique, deter- mines fixed orientations with outgoing edges from the clique, and generates the unresolved undi- rected connected components (UCCGs). In this work, we propose more efficient approach to UCCG generation by utilizing previously com- puted results for different root cliques. Our method introduces the concept of super cliques within rooted clique trees, enabling their efficient transfer between trees with different root cliques. The proposed algorithm effectively reduces the computational complexity of the Clique-Picking method, particularly when the number of cliques is substantially smaller than the number of ver- tices and edges.
A MEC can be uniquely represented by an essential graph (Andersson et al., 1997), also known the completed par- tially directed acyclic graph (CPDAG). They use both di- rected and undirected edges to represent causal relationships that are consistent across all DAGs in the equivalence class, with directed edges indicating fixed causal directions and undirected edges reflecting ambiguous dependencies unre- solved by conditional independence constraints. The size of a MEC, defined as the number of DAGs within the class, plays critical role in the design of causal intervention ex- periments (He & Geng, 2008) and average causal effect estimation (Maathuis et al., 2009).
Exhaustive search for all Markov equivalent DAGs is only computationally feasible for small graphs (Madigan et al., 1996; Gillispie & Perlman, 2002). Generally, the size of MEC grows superexponeenially in the number of its ver- tices. He et al. (2015) addressed the counting challenge by introducing five special MECs with explicit size formu- las, and exploiting recursive partitioning into the respective subclasses for efficient counting. A modified approach by Ghassami et al. (2019) leverages the clique tree representa- tion to decompose the essential graph into smaller compo- nents. More recently, dynamic programming enhancements (Ganian et al., 2022) and iterative methods over possible in- terventional essential graphs (AhmadiTeshnizii al., 2020) have been proposed.
1. Introduction
Directed acyelic graphs (DAGs) are widely used to represent multivariate causal structures across diverse fields, includ- ing epidemiology, biology, and economics (Pearl, 1988; Pingault et al., 2018). In DAG, nodes represent variables, and directed edges denote causal relationships (Koller & Friedman, 2009; Spirtes et al., 2001). Under the Markov condition and faithfulness assumption, the causal structure can be inferred from statistical data to identify a DAG. The
'Equal contribution 'School of Mathematics and Statistics, Northeast Normal University, Changchun, China "School of Mathematics and Statistics, Beijing Technology and Business University, Beijing, China. Correspondence to: Jianhua Guo <jhguo@ chnauo@btbu.cdu.cn..
Notably, Wienöhst et al. (2023) introduces the Clique- Picking (CP) algorithm, which is a polynomial-time al- gorithm for determining the size of a MEC. This method partitions the MEC into subclasses by fixing a clique as root and avoids overcounting using minimal separators
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
derived from the clique tree representation. However, for given chordal graph G (V, F),, the algorithm needs to recursively select a clique as root, introduce outgoing edges from the root, and determine smaller undirected connected components (UCCG) from the resulting graph. Suppose there are m maximal cliques in G, this intensive process [E])). Moreover, this process has
subgraph of G on set C' S V by G[C], which only keeps the vertices in C and the egdes connecting them. A directed acyclic graph (DAG) is directed graph without any di- rected cycle, A topological ordering of a DAG is linear ordering of its vertices such that for every directed edge Vi + Vj. vertex U; appears before vertex Vj in the ordering. The skeleton of graph G is the undirected graph formed by ignoring the edge directions in G, while retaining its vertices and edges. An induced subgraph of the form t1 - U2 U3 is u-structure.
has a cost of ((m[[V] + to be repeated during the recursive function calls, until the reduced UCCG only contains a single maximal clique.
Fortunately, an improvement is feasible because there are considerable structure overlaps when different cliques are selected as the roots. We propose a novel approach for this purpose. Our contributions are summarized as follows.
A Markov equivalence class (MEC) is the set of all DAGs that encode the same conditional independence relations among the variables. Verma & Pearl (1990) state that two DAGs are markov equivalent if and only if they share the same skeleton and u-structures. Furthermore, Andersson et al. (1997) show that MEC can be uniquely represented by completed partially directed acyclic graph (CPDAG), denoted as G", which is the union of all DAGs in the equiva- lence class. An undirected graph is chordal if every cycle of length greater than three has a chord, i.c., an edge connecting two nonconsecutive vertices in the cycle. Each undirected connected component of CPDAG a connected chordal graph, referred to UCCG. In particular, each UCCG is itself CPDAG representing MEC.
1. We introduce higher level structures called super clique and super residual for clique tree in Section 5. For a chordal graph G with some clique selected as the root, we show the UCCGs can be easily identified from the super residuals.
2. When two different cliques (K₁, Kb)) are selected the root, show structure changes can be easily identified for the corresponding super cliques and super residuals. Hence, when the UCCGs are known for K; as the root, we can efficiently identify UCCGs for the case when the other K2 is the root. This leads to the super clique transfer operation in Section
Let Size(G") denote the size of the Markov equivalence class represented by a CPDAG G". The value of Size(G") equals the product of the number of Markov equivalent DAGS for each UCCG of G" (Andersson et al., 1997):
3. The above techniques lead to the Super Cliques Trans- fer Algorithm in Section 4. Overall, our procedure of UCCG identification for all root cliques has reduced cost of Omm²).
Size(G") = II
Size
4. To provide solid theoretical foundation for our algo- rithm, we characterize super cliques and super resid- uals from two distinct perspectives: the clique-rooted tree perspective in the main text and the clique se- quence perspective in the Appendix. The former offers an intuitive understanding, while the latter provides more fundamental framework that facilitates theoreti- cal proofs.
UCCG G in G-
However, the above equation is not directly applicable in general to compute Size(G"). This is because the value of Size(G) can grow superexponentially with respect to its vertex number [V.. It is essential to develop an efficient approach for the computation of (iz)
2.2. Clique Rooted Trees
The rest of the paper is as follows. Section 2 reviews the con- cepts for Markov equivalent DAGs and clique rooted trees. Section 3 reviews the Clique-Picking algorithm of Wienöbst et al. (2023) at a high level. Our proposed algorithm and its detailed operations will be presented in Sections 4-6. Section 7 presents the experimental results.
In graph, clique is a set of pairwise adjacent vertices. For a UCCG G, we denote the set of all its maximal cliques as Ka = [KI.... Km For example, the chordal graph G in Figure I(a) contains seven cliques: K₁ = {a, b, c). K₂ = {b, c, d]. K3 = (b. e). K4 = (e, f]. K₁ = (b. g, g. Kg g. i} and K- (b, j.. The maximal cliques in a chordal graph G can be ordered to satisfy the running intersection property (RIP, Blair & Peyton, 1993).
2. Preliminaries
Definition 2.1. (Running intersection property) A clique sequence, K1, K2...., Km, has the running intersection property (RIP) if for each clique Kp (with p = 2,... m), there exists a clique K, for some t E (l.....p p 1}, such that
2.1. Markov equivalent DAGs
A graph G = (V, E) is a tuple consisting of a vertex set V fu),.... } and an edge set E. An edge e - 0y is undirected if (v,, 15), (1,, v1) E E and directed U + By if ()), E E and (1y, 0i) & F. We denote the induced
K₂ 7 (K1 U K2 ......U ....U.K-I)) C Kr.
(1)
2

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
K1
0.
b, c
b
b. c
b
K3
K2
K5
h
e
8. 1
b,
b I
K4
K6
K7
f
i
(a)
(b)
(c)
Figure 1. The UCCG G Figure 1(a) has several maximal cliques: Ki {a, b, c, K2 db. Ks = (b, e). K₁
fe, f}.
Ks = 9.). Ks = {b, it and K7 = (b, j.. Figure l(b) is the GKi with K₁ = faa et. The rooted clique tree T is shown
Figure I(c).
From any sequence of cliques satisfying RIP, we construct a rooted tree on KG by making each clique K2 adjacent to a "parent" clique K, in (1). This tree has the first clique K1 in the sequence as its root, and is denoted as TK1,, For the example in Figure I(a), K1, K2, K3, KA, K5, Ke, K7 is RIP sequence. The corresponding rooted tree 7K1 is shown in Figure ((c).
Algorithm Function CP-Count(.)
Input: A UCCG
Output: Size(G)
I: Generate rooted clique tree of G;
2: Generate Co (,)) for each K, E KG. which is selected as the root for clique tree T Evaluate Size(J) for all UCCG inside Co(Kp) by recursively calling (ount)
Given a UCCG G, a clique tree T with some root clique K1 can be generated via the MCS algorithm (Blair & Peyton, 1993). For each clique Kp. its separator Sp is as Sp K2 n (K1 U... U K5-1) Kp n K,, and its residual Rp is defined as Rp Kp Spp. For the root clique, simply set S₁ = ( and R₁ = K2. For the rooted clique tree TKk the collection of all separators is denoted as Sep(Ki). and all residuals as Res(K))
4: Compute Size(G) in (2).
denote by (c(T(()) the undirected connected components of (*(k) (V) K].
Furthermore, let GK denote the union of π -(r))ooientaaiinns of G over all permutation π. That is, G = U,, (K),), We also denote (K) as the undirected connected components of GK [V)) K]. For the graph in Figure 1(a), suppose K₃ = {a, b, e} is picked as the prefix of the ordering, then the corresponding graphs GK is shown in Figure 1(b). We can see, by picking K₃ as the root, we introduce outgoing edges from K₃ in GK: compared with the original undirected G in Figure (a)). For GKK,, we have the undirected connected components (a()) = [Gle], G[d], GIJ), G Eig h, i.j]}-
3. The Clique-Picking Algorithm
We now review the Clique-Picking algorithm proposed by Wienöbst et al. (2023) and highlight, at the end of this section, the specific part where our super clique approach can provide improvements. Wienöbst et al. (2023) exploited the fact that each DAG within MEC can be represented by topological vertex orderings, and a maximal clique can be selected as the prefix of an ordering. In this way, the Markov equivalent DAGs can be divided into small groups for more efficient computation.
Wienöbst et al. (2023) show that the size of the Markov equivalence class represented by GK can be calculated by:
Size (G*) = |K]!
II (Jze
Wienöbst et al. (2023) introduced several concepts to for- malize the idea. Suppose K be a clique in G and selected as the root. Let π (K) be a permuted ordering of the vertices in K, and consider all topological orderings of G that start with T (). The T (() -orientaaaiio of G, denoted (*))), is the union of all DAGs within the MEC represented by G that have topological orderings beginning with л (K). Then,
JECo(K)
It is tempting to select each K in Ka. compute Gize(G and sum all these values to get Size(G) for UCCG G. However, this will count some DAGs multiple times, as a DAG can be represented by multiple topological orderings with different cliques as the root. To resolve this issue,
3

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
Algorithm 2 Super Cliques Transfer Algorithm
Algorithm 3 SC-Create-Op
Input: A UCCG G and a rooted clique tree T of Ka (.
Input: A UCCG G. rooted clique tree T of Koc
Output: Ca(K)), (K2)),
Output: L Co C Sep(K)), and Res(K1)
1: L CC((K)) Sepp)K Res( + SC-Create-Op
I: Initialize Cc: + {):
(G, 11) via Algorithm 3:
2: Sep Bep(K1) < the set of separators SI. SI....,Sm. Sm:
2: for io
vn do
3: Res( Res(Ki)
the set of residuals Ri..... Rm:
3: Ke <- The parent clique of K; in T
4: Based on Sep K1), get the set of super cliques of T and
4: Initialize Sep(K.) + Sep(K,) and Res(K.)
denote as T,
Res(K:);
5: for SK in ( do
5: Update S; + 0 and St + K&n K2 in Sep(Ki));
p=
6: Update R2 + K; and Rs + K, \. (K; n Ko) in Res(
6: Obtain SR (1) for SK (2) p=
p+ based on Res(Ki);
7: Run Algorithm 4 to get (K.), L +- SC-Trans-Op(Co
7: Co(Ki) + (Ki) U (.]
L (Tep,S) Resp(K)))ss(K))) (i)): 8: Get 7K. by reversing the edge "K₃- - K2" in Tike to
8: end for
"K: + K,";
9: end for
the computation cost of Step 2 of Algorithm 1. The main idea is to group the cliques in rooted clique tree into higher level structure, called super cliques. We connect the super cliques with the UCCG, and develop an efficient super clique transfer algorithm to obtain the UCCGs when different cliques are selected as the root.
Wienöbst et al. (2023) further introduced the correct iterative formula
Size(G) = Σ FKK, TK)).
II (KC)(Kp)
SJze(J), (2)
The proposed approach, referred to the Super Cliques Transfer (SC-Trans) Algorithm, is outlined in Algorithm 2. It takes as input a UCCG G and corresponding rooted clique tree 7ki, and outputs all sets Ca (Cc(K)),, (K))....,Co (Km). Step 1 identifies all separators S1)(K)), all residuals Res( (es(Ki), all super cliques T2(1) and Co(Ki) for TK., It utilizes the super clique create operation (SC-Create- Op) in Algorithm 3, which will be introduced in details in Section 5. Steps 2-9 sequentially generate the other ( ... .......,,G(hee (K,) These steps depend on the techni- cal details to be presented in Section 6. In each iteration of i E (2...., ,m). the parent clique K, of K, in TK1 is found. Steps 4-7 then efficiently identify structure changes from T TKk In particular, Algorithm in Step 7 is the super clique transfer operation (SC-Trans-Op) in Section 6. Step 8 then updates T to become rooted tree for K,,
where <0-) is a corrected multiplicative factor to avoid over- counting. The formal definition of the above Φ(-) is provided in Section 4.3 of Wienöbst et al. (2023), where the authors discuss in detail.
At high level, the recursive strategy of Wienöbst et al. (2023) is summarized in Algorithm 1. We present their pro- cedure as function, called CP-Count(-). that takes a UCCG G as input and return the number of Markov equivalent DAGs, Le. Size(G). In particular, Step of Algorithm generates all Co (p),, when different K₂ are selected as the root. Wienöbst et al. (2023) proposed an adapted Max- imum Label Search algorithm for this task. The cost of generating single Ca(K)) is ((V + +EE), and the overall cost for Step 2 of Algorithm is O(m- ([V)+ + [El)), where m is number of maximal cliques in the chordal graph G.
We have the following results for Algorithm 2, the proof of which can be found in Appendix E. Proof of Theorem 4. I and Proof of Theorem 4.2.
is important to note Step of Algorithm can be further improved to achieve greater efficiency. This is because there are considerable structure overlap for (K) with differ- ent K E KG selected as the root. For example, easily see that, when K3 is selected the root, we have (os)) {G[a, d]. G[f), Gig, h, i, j.j]}. It is clear that the undirected connected components G[J] and Glg, h i, appear in both (K1) and Co (K3). To address this redun- dancy, we will introduce our super clique transfer algorithm in the next section. With the proposed algorithm, once we get (K,),,) ). we can more efficiently compute and derive all the other Co (Kp) with p- = ,,. The reduced cost is Om?) ) for Step 2 of Algorithm
Theorem 4.1. Let G be a UCCG, and TKk be a rooted clique tree with cliques ordered as K according to the MCS algorithm. Algorithm 2 will correctly relurn Ca(Ki), Ca(K))....,,
can
Theorem 4.2. Algorithm 2 runs in time O(m²), where m is the number of cliques of UCCG G.
5. Super Cliques and Undirected Connected Components
m.
In this section, we discuss the details of Algorithm 3. It is a novel approach to compute Co(K) based on the concept of super cliques for T The new concepts are built upon the basic rooted clique tree structures introduced in Section 2.2.
4. The Super Cliques Transfer Algorithm
Our main contribution is a novel algorithm that reduces
4

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
Algorithm 4 SC-Trans-Op
panel of Figure 2, there are four super cliques: SK2)
Input: Co(K)), ( T Sep(K.), Res(Ki).
{K2), SKS = {K3}. SK = {Ka} and SK { [Ks; Ko, K7} within TK: Note the superscript "(1)" in these notations emphasizes that they are super cliques (or super residuals) within the clique tree T rooted at Kj-
Output: (a(K,) and 1,
1: Initialize (o( < O. 1 - 0. SK( + {Ke).
SRR) (Ki) + {Re}
2: for SK( in ( do
pt 3: i then
Regarding the super cliques in TKs, we can observe a few properties. Firstly, for each SK pt the subgraph T [SK[1] is connected and constitutes a subtree of T This is because the clique tree 7 generated from UCCG G satisfies the called induced-subtree property (Blair & Peyton, 1993). The property states that, for every vertex v E V of G, the set of all cliques containing induces a connected subtree of T. Consequently, the subgraph T [SK is connected because all the cliques within SKp+ share the common node set Sp-
4: for all child clique K₂ of K; in T do
5: Induce " and SR from SK and SR
gt
6: Ca(K.) (a( U (G[SR(1):
( L u (Sk g+ }: end for else if Kp is a child clique of K; in TKi and S. is proper
7:
8:
9:
subset of Sp then
10:
SK() < Sk (
u USK SR + SR USR[1:
11:
else
12:
S + SR SK pt -K g=:
13:
Co(Ki) Co(Ki) u [c]s
Secondly, we observe that Ca(K) (1) can be easily obtained from the set of super residuals. Consider again the clique tree in the left panel of Figure 2 in Figure 1(c), we can see G(SRL (1) = Gld], GISR = Gle). G[SR[]] GIf), (1) and G 6.7 Glg. h, i,j] are the undirected connected components in Ca(K)). In fact, this observation holds in general. For any super residual SR (2) the induced subgraph
14:
7,00 < 1,09 u (SK()) pt }:
15: end
16: end for
17: L + 1 U (s
18: Co(K.) - Co(K.) u (c]
Definition 5.1. (Clique header, clique tail) Let T be a rooted clique tree with RIP clique order K1, K2,-.., .. Km-
G[SR[1] pil is exactly element of the set (K))) More- over, (a(K)) is just the collection of all such subgraphs induced by every super residual.
i. For any p = .,..., m, Kp is a clique header within T if for any ancestral clique K, of K, with q X 1, the corresponding Sg is not proper subset of Sp.
Theorem 5.3. Let T1 be rooted clique tree of a chordal graph G with MCS clique order K1,
Km. Then
ii For p 2...., m, suppose Kp is a clique header within TKi a descendant clique Kg of Kp is clique tail that follows Ko if Sp Sq.
Ca(K,) - - [G(SS(]]
SR
is a super residual within T pf
For given TK:, Algorithm 3 is designed to return the set [()) of all super cliques, all separators and residuals, and (K,).. Algorithm 3 is valid due to Theorem 5.3. It seems natural that, for i = 2...., m. we can apply the same procedure to each TK, for getting the corresponding Co (K.). However, such procedure is unnecessary. Recall we have discussed that, for any pair of cliques K, and K; with A + i, there are many shared undirected connected components between Co (K,) and CK,)) We can reuse the computation results for one rooted clique tree to speed up the computation for the other. In the next section, we will present an efficient strategy serving this purpose.
Note the root K1 is neither a clique header nor a clique tail, as we require p > 1 in the above definitions. For the example in Figure I(c), K2, K3. K4 and K5 are clique headers within T Kg and K7 are the clique tails that follows Ks. Using the concepts of clique header and clique tail, we can define the super clique and super residual within TKK.
Definition 5.2. (Super clique, super residual) Within clique tree TKk, suppose Kp is clique header and K Kpp.-. .p....... Kp. are all its clique tails.
i. The clique set (K()) pt
(K(1)
plpp....pp. (Kp, K } } is called a super clique.
ii The set of the residuals corresponding to the cliques within SK(!) is called super residual, and denoted as p+
6. The Super Cliques Transfer Operation
We now present our efficient super clique transfer operation to generate all the other Co(K)), ... (Km),, given Ca(K)), The overall iterative strategy is described in Algorithm 2, which generates Co(K,) based on Co(K,), where K2 is a parent clique of K; in TKk
SR P- SR(() (1)
plp....... == {Rg R Rr. }.
A clique header Kp will form a super clique itself if it does not have any clique tail. For the clique tree in the left
5

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
To efficiently obtain C,(K,) from Co (K,), we need to con- struct an appropriate clique tree TK: with minimal structure changes from Tkr, We exploit the computed results from TK: and our super clique transfer operation to reduce the computation cost. Now, without loss of generality, we dis- cuss in details the particular situation where we transit from TKi to TK; where K; is child clique of Ki in TKi, The procedure for the other cases similar.
Table 1. The separators and residuals for the cliques K₃ and K;
within the two rooted clique trees 7 7 and 1 T:K;
K
K;
sepurator
residual
separutor
residual
T T
0
K1
K1 n K.
K, K, n K.)
Ki n K;
Ki KK
(K
K.)
K.
cliques remain unchanged, which is stated in the follow- ing proposition.
Recall TKi corresponds to clique sequence K1,..., Km that satisfies the RIP. As stated in Lemma 6.1 below, there al- ways exists permuted sequence K=(1). ...., Ka(m), which starts with K; and also satisfies the RIP.
Proposition 6.3. Assume K₃ is a clique such that K₁ n (Kr U...U U 1 C. K1. Let Ko(I)...,KK Ka(m)) be the permutation obtained by applying Lemma 6.1 with (1) = i. Then for any p in [m]] \ {1.i} and p' satisfying p = app). we have Sp = Sots') and R.p Ro(p')
Lemma 6.1. (Proposition 2.4 of Leimer (1993)) Let Ki...., Km be an RIP sequence of the clique set. For any i = 2,...,m, m, there exists a permutation satisfying that (1) i and (2) = 1, and meanwhile Ko()).--;; K Ko(m)
The proof of above two propositions are claimed in Ap- pendix E. Proof of Propositions 6.2 & 6.3. The edge K1 - K, in TK: will be redirected as K; + Ki in TK: This implies K1 becomes a child clique of K; in TKK As the root K; is the only ancestral clique of K; in TK; K, must be a clique header within T by Definition 5.1. The child cliques of K; in TKi will all become clique headers in 7K, Additionally, some cliques that were headers in T:K will become clique tails of K₁ in IK; Specifically, if Kp (p * i) is child clique of K₁ in TKs, tthn K2 is a clique header within TK,, but it can possibly become clique tail within Tk. We need to check whether Ki n K; is a proper subset of Sp. If this is true, K₂ will become a clique tail of K₁ in TK: otherwise, K₂ remain a clique header in TKK
is still an RIP sequence.
In fact, the permuted sequence has a simple structure change. The proof of Leimer (1993) actually states the permuted indices as: 1) (1) = i and o (2) = 1: 2) for p = , 1, we have (p + 1) = p; and 3) for p = + 1,..., m, we have (p) = p. The permuted RIP sequence has minimal change of the clique order. Based on the permuted sequence, the new clique tree TKK rooted at K; can be obtained. We continue to examine the structure changes from T to TK. in more details.
6.1. Basic Structure Changes in the Clique Trees
To understand the structure changes for TK, we first state a property regarding the permuted sequence.
For Figure 2, let us consider the structure changes from 7 in the left panel to I in the right panel. We can see that Ke and K7 both become clique headers within Tss Furthermore, K₁ also becomes clique header in 7's, Since K₁ n K₃ is not a proper subset of $3. K3 remains a clique header in TKs On the other hand, K₁ n K₁ is a proper subset of S2, so K₂ becomes a clique tail that follows Kj within T The clique K₁, which is not adjacent to K1, remains as a clique header within TKs.
Proposition 6.2. Assume K₃ is a clique such that KGn(K,U ...U ...U.,.i)) C K1. Let Ko(I)...,, Kotm) be the permuted clique obtained by applying Lemma 6.1 with (1) = i. For any p E [m]] \ i1 and any q E [ml) if Kp n (K1 U U..U kp-1) C Kg then for p' and of with p = (pp) and q= =dd'), it holds that
Kaby n (Ko(1) U...U Ko( C (Koto)-
6.2. High-level Structure Changes in the Clique Trees
Note in the above p $ {1,i}. Proposition 6.2 has the fol- lowing implication for any K, and its child clique K2 in
We can further characterize higher level structure changes from 7 to TK; in terms of super cliques and super resid- uals. In fact, all super cliques in 7 can be identified from those of T There are three cases to consider:
TK: Suppose the p-th clique Kp in T corresponds to p'tth clique Katny) in TK, and suppose K, corresponds to Ko(g)) We have Ko(p) is a child clique of Ko(g)) in TKK
The above discussion implies that, from T to this T only one edge changes. That is, K₁ > K; in TK1 becomes K: K1 in T.K The other edges in KKK remain un- changed. Due to this edge direction change, we can see that their separators and residuals also change. The changes are summarized in Table
1. Consider the super clique SK( with clique header K, in TK. Suppose K, has h child clique(s) in TK:: Kp....., Kpn. Then, the super clique SKI2 of TKi get split into h super clique(s) in TK: SK() "K...,,((()). These super cliques have Kpi...., Kpn as their clique headers, respectively. In the special case that K; has no child clique in TK,
Additionally, the separators and residuals for the other
6

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
K1
K
0. b N
K3
K2
b
Ks
K3
C
K5
g
Ngg.
K
à. g
K7
i
KB
g
K7
f
Figure 2. The structure changes from T to T The blue eycle means that the cliques within it will form super clique. We omit the blue cycle when a clique itself is super clique(root excluded).
we can simply ignore SKQ when generating super cliques for .
Once the super residuals in TKK are identified, the undi- rected components in (K,) can be immediately deter- mined based on Theorem 5.3.
2. Consider all child cliques of K2 in TKi but with K; excluded. Among these child cliques, select those that become clique tails of K₃ in TK; and denote these selected cliques as K Kpp...., pp.. Then, their corresponding super cliques (K(1) .......S! in TK, p ................................ P/ together with K1, will form new super clique in TK::
We now illustrate the structure changes from T to T for the example Figure 2. Corresponding to Cases 1-3, have the following:
1.
Ks has two child cliques in TK:; Kg and Kg. Then the super clique SK (1)
5/6,7 in T' get split in two super cliques in T. SK(0) and SK Correspondingly. we can generate the undirected connected components G[i] and G(h] in (Ks)).
SK [K1) ( pl
U...
U..
(3)
pl."
Note, if there does not exits any clique tail of K1 in TK; then (3) simply becomes SK = {Ki}. For the child cliques of of K₃ in 7 that are not selected for (3), their corresponding super cliques remain un- changed and continue to constitute super cliques in T
Additionally, consider the child cliques of K₁ in T In T K2 becomes a child tail of K₁. Then SK in 7'K together with K1, will form the new super cliques SK of TKs. Due to the change of resid- ual of K1, we can see G(SR( undirected connected component in Co where SR (5) {Kr \ (Kr n Ks)) USR (1)
Gla, cla,c,d d] is an
3. Aside from the Case and Case discussed above, all other super cliques in T remain unchanged and continue to form super cliques in 7 TK.
Except for SK( 5/6,7 and SK all the other super cliques: SKY and SKS remain exactly the same in TK's and the same apply SR and SR Hence we have Gie] and Giff] in Ca(Ki) still belong to CG(Ks).
All super residuals in k: can be identified from those in T in the same spirit as the three cases above. Recall by Proposition 6.3 the only difference between Res(K,) and (e) lies in the pair (R1, R.), and the changes are summarized in Table
Corresponding to Case above, the super residual (R(") of T get split into h super residual(s) in TKK +
6.3. The Iterative Algorithm
In the above, we focus on the case where K; is one child clique of K₁ in T and we identify all super cliques and super residuals of T'K from those of Tkk The results can be easily generalized. For any clique K; in KG with < i S m, suppose its parent clique of K; in TKk as K,, we can efficiently obtain super cliques and super residuals of TrK from those of TK. This leads to the super clique transfer operation (SC-Trans-OPp OO) in Algorithm 4, which derives the set of super cliques of TKK from that of TKk
SR ...... (R()) +. As for Case in the above, the super residual SR(1) corresponding to K2 in T will be
$ = [Ki) \ (K1 n K.) U SR (1) P
U... ....UST S Ph
(4)
Except for SR! and the super residual in (4), all the other super residuals of TK: remain exactly the same in TK,
7

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
0.34
0.08
JCP CP
-CP CP
1200
670
Average run time (second)
250
Average run (second)
160
50
40
10
512
1024
2048
4096
512
1024
2048
4096
The number of vertices
The number of vertices
(a)
(b)
1024 2048
1024 2048
66
80
Runtine difference (second)
Ranlime difference (seccond)
46
24
24
10
0.04
0.06
0.12
0.24
0.46
0.04
0.06
0.12
0.24
0.46
The graph density
The graph density
(d)
Figure 3. Figures (a) and (b) present the avorage running times of the original "CP" method and our improved "ICP" method across different numbers graph vertices. runtime differences, Tep Tiep and TCP.2 Ticp,2 are illustrated Figures (c) and (d), respectively, for varying graph densities. All axes use logarithmic scale.
and generates Co(K) from Co(K) (2)). In Algorithm 4, Lines 3-8, Lines 9-10 & 17, and Lines 11-15 correspond to Cases 1-3 in Section 6.2, respectively.
Table Average running time (in seconds)
0.34
0.08
V
Ticr
Tcp
Ticr
Tcp
Now, let us return to Algorithm Lines 4-6 and Line are due to the basic structure changes in Section 6. When transitioning from Kr to K. the of separators (Sep(K.) and the set of residuals (Res(K)) K2)) be readily determined, Proposition 6.3. Line 8 is due to Proposition 6.2 and the subsequent discussion there. Line employs Algorithm 4.
Algorithm 2, its
512
1.022
2.081
0.842
1.494
1024
8.048
15.579
5.586
9.974
2048
68.048
125.181
40.545
74.940
4096
707.484
1169.811
387.491
660.435
discussed for Table and
7. Experiment
In the following theorem, we prove the correctness of Algo- rithm
We now evaluate our proposed SC-Trans algorithm. It is integrated into the Clique-Picking (CP) algorithm re- placing its Step 2 in Algorithm 1. The improved version is denoted as ICP. We compare the practical performance of our improved ICP and the state-of oftte-of-the-an CP algorithm in a series of experiments. Both methods are implemented using Julia. All experiments are run on laptop with AMD
Theorem 6.4. For any i ....., m, let K₁ denote the par- clique of K2 in T ((t) be the set of super cliques of TKk Then given Co(Ki), L(), TRs Sep(Ki), and Res( K2), Algorithm will return Co (K)) and the set I,(0) of super cliques of K..
8

---

Recall that our proposed algorithm enhances Step 2 of Al- gorithm 1. When focusing solely on the computational cost of this step. the advantage of our method becomes even more evident. Let T denote the average running time of Step 2 of CP algorithm, and let TicP,2 denote the average running time of ICP for the same step. Table 3 presents both the difference and the ratio between these average running times. Figure 3(d) shows the average runtime difference of An Improved Clique-Picking Algorithm via Super Cliques Transfer
Table Comparison between ICP and CP (the runtime difference Tcr
Tier and Tep T are measured in seconds)
1024
2048
0
TCp
TIcP
TCp.2
T
Tep.2/TicP.2
Tcp
Tiep
Top
Ticp,2
Tep.2/TicP.2
0.04
0.0381
2.17
2.33
5.34
0.0189
20.45
17.99
12.27
0.06
0.0243
2.84
3.30
7.56
0.0126
27.87
24.19
17.16
0.12
0.0108
5.01
4.73
18.43
0.0054
45.58
37.41
39.70
0.24
0.0044
7.02
7.35
47.59
0.0022
60.40
76.63
95.35
0.46
0.0015
8.42
9.20
153.55
0.0007
80.97
81.45
264.54
Ryzen9 2.7GHz and 16G RAM. All the implementations use only one thread of execution and the running time is measured for exact counting.
Step 2 of CP and ICP. The results highlight substantial im- provements achieved by our method terms of efficiency.
We use the minimal triangulation method to generate chordal graphs (Dethlefsen Højsgaard, 2005). The repli- cates generated by first generating undirected graph of [V] vertices and p- ( edges, and then, the triangulation is made until the resulting graph is chordal. Graph density r is measured by | For each [V], the parameter p is adjusted to make the aver- age number of edges of resulting chordal graphs equals to r. (..).
8. Conclusion
In this work, we propose an enhancement the Clique- Picking algorithm (Wienöbst et al., 2023) by avoiding the intensive and repeated generation of (K,)) for each clique K₁ of a chordal graph G. Our improvement introduces a higher-level structure, termed a super clique, within the clique tree. We demonstrate that an efficient transfer of super cliques is possible between two clique trees with dif- ferent choices of K₃ as the root. The proposed algorithm significantly reduces the computational cost of Step 2 in Algorithm
with |Emaxl= = IV[(V] 1)/2.
Varying numbers of graph vertices. We first tested the performance of ICP and CP in various vertices of chordal graphs. We performed experiments with [V] = 512, 1024, 2048, 4096. In each experiment we chose r as ei- ther r = 0.34 or r = 0.08 and generated ten chordal graphs for each number of graph vertices. Let Tep denote the aver- age running time of CP algorithm, and let TIeP denote the average running time of our ICP algorithm. The experimen- tal results are shown in Table 2, Figure 3(a) and (b). Our ICP clearly consistently performs better and solve within less amount of time.
Acknowledgements
This work was supported part by the National Natural Science Foundation of China under Grant No. 12431009; the National Key R&D Program of China under Grant No. 2020YFA0714102.
Impact Statement
Varying graph densities. We then tested ICP and CP over various specification of graph density r. We performed ex- periments with 0.04, 0.06, 0.12, 0.24, 0.46. In each periment we chose [V] either [V| 1024 or [V| 2048 and generated ten chordal graphs for each graph density. As shown in Table and Figure 3(c), the difference in running time between the two algorithms becomes more pronounced with the increase of r. This trend is attributed to the fact that denser graphs generally correspond to a lower value of 0 m [[V] + [E), which enhances the performance advantage of our proposed method.
This paper presents work whose goal is to advance the field of machine learning and causal analysis. Our work facili- tates more efficient causal discovery and decision-making processes, particularly in scenarios where high-dimensional data are involved. This advancement contributes to im- proving the feasibility of real-world applications such as automated causal inference in healthcare, policy-making, and artificial intelligence systems.
References
AhmadiTeshnizi, A., Salchkaleybar, S., and Kiyavash, N. Lazyiter: a fast algorithm for counting markov equiva- lent dags and designing experiments. In International Conference on Machine Learning, pp. 125-133. PMLR, 2020.
Andersson, S. A., Madigan, D., and Perlman, M. D. A characterization of markov equivalence classes for acyclic

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
digraphs. The Annals Statistics, 25(2):505-541 1997.
Maathuis, M. H., Kalisch, M., and Bühlmann, P. Estimating high-dimensional intervention effects from observational data. The Annals of Statistics, 37(6A):3133 3164, 2009,
Blair, J. R. and Peyton, B. An introduction chordal graphs and clique trees. In Graph theory and sparse matrix compulation, pp. 1-29. Springer, 1993.
Madigan, D., Andersson, S. A., Perlman, M. D., and Volin- sky, C. T. Bayesian model averaging and model selection for markov equivalence classes of acyclic digraphs. Com- munications in Statistics-Thean and Methods, 25(11):
Castelo, R. and Perlman, M. D. Learning essential graph markov models from data. In Advances in Bayesian Networks, pp. 255-269. Springer, 2004.
2493 2519, 1996.
Chickering, D. M. Learning equivalence classes bayesian- network structures. The Journal of Machine Learning Research, 2:445-498, 2002.
Pearl, Probabilistic Reasoning Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988. ISBN 1558604790.
Dethlefsen, C. and Højsgaard, S. A common platform for graphical models in R: The gRbase package. Journal of Statistical Software, ((11))1-12, 2005.
Pearl, J. Causality: Models, Reasoning and Inference. Cam- bridge University Press, USA, 2nd edition, 2009, ISBN 052189560X.
Ganian, R., Hamm, T., and Talvitie, T. An efficient algo- rithm for counting markov equivalent dags. Artificial Intelligence, 304: 103648, 2022.
Perlman, M. D. Graphical model search via essential graphs.
Contemporary Mathematics, 287:255-266, 2001.
Pingault. J.-B., O' O'reilly, P. F., Schoeler, T., Ploubidis, G. B., Rijsdijk, F., and Dudbridge, F. Using genetic data to strengthen causal inference in observational research. Na- ture Reviews Genetics, 19(9):566-55) 580. 2018.
Geiger, D. and Heckerman, D. Parameter priors for directed acyclic graphical models and the characterization of sev- eral probability distributions. The Annals of Statistics, 30 111412--440,, 2002.
Spirtes, P., Glymour, C., and Scheines, R. Causation, Pre- diction, and Search. The MIT Press, 01 2001. ISBN 9780262284158.
Ghassami, A., Salchkaleybar, S., Kiyavash, N., and Zhang, K. Counting and sampling from markov equivalent dags using clique trees. In Proceedings of the AAAI confer- ence on artificial intelligence, volume 33, pp. 3664-3671, 2019.
Verma, T. and Pearl, J. Equivalence and synthesis of causal models. In Proceedings of the Sixth Conference on Un- certainty in Artificial Intelligence, pp. 220-227, 1990.
Gillispic, S. B. and Perlman, M. D. The size distribution for markov equivalence classes of acyclic digraph models. Artificial Intelligence, 141(1-2):137-155 2002.
Verma, T. and Pearl, J. An algorithm for deciding if set of observed independencies has causal explanation. In Uncertainty in Artificial Intelligence, pp. 323-330. Elsevier, 1992.
Guo, J. and Wang, X. Graph Decomposition: Theory, Algo- rithms and Applications (Unpublished Manuscript in Chi- nese). Changehun: Northeast Normal University, 2010.
Wienöbst, M., Bannach, M. and Liskiewicz, M. Polynomial-time algorithms for counting and sampling markov equivalent dags with applications. Journal of Machine Learning Research, 24(21))11-5,222
He, Y. and Geng, Z. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, (84))252332247, 2008
He, Y., Jia, J., and Yu, B. Counting and exploring sizes of markov equivalence classes of directed acyelic graphs. Journal of Machine Learning Research, 16(79):2589- 2609, 2015.
Koller, D. and Friedman, N. Probabilistic Graphical Mod- els: Principles and Techniques Adaptive Computation and Machine Learning. The MIT Press, 2009, ISBN 0262013193.
Leimer, H.-G. Optimal decomposition by clique separators. Discrete Mathematics, 113(133)999122) 1993.
10

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
In this appendix, Section A contains a list of the main symbols and their meaning in the paper. There are several definitions and theorems necessary for the main theoretical derivations. These preliminary results are presented in Sections B-D. In Section E, we present the detailed proofs for the theorems and propositions in the main paper. Finally,Section F includes detailed example illustrating how the proposed algorithm proceed step by step.
A. Notation List
Table 4. Table of Frequently Used Notations
Notation
Meaning
T
Rooted clique tree
Clique tree with rooted K
T T(K)
A permuted ordering of the vertices in K
The union of all DAGs within the MEC represented by G that have topological order- ings beginning with (K)
(T(K)
Gk
Ug U*G
G|C]
Induced subgraph
The induced subgraph of G on a vertex set C The set of undirected connected components of GK \ K]
(K)
(ep(K)
The set of separators for 7 The set residuals for T
Res(K) K)
SK (i)
Super clique
The clique set contains clique header Kp and the clique tails of Kp within T The set super cliques within TK;
L
SR (1)
Super residual
The set of the residuals for T corresponding to the cliques within SK
B. D-Numbering
We now discuss D-numbering (Leimer, 1993; Guo & Wang, 2010), which offers effective approach for analyzing clique sequence.
Definition B.1. (D-numbering) For a UCCG G, an order of its vertices called a D-numbering if there exists an RIP clique sequence Ki,..., Km with corresponding residuals Ri...., Rm such that
a ( (n, n 1...., n |R 13 ................................ .(......((R.)) {| .......... 2,
where n = [/ is the number of vertices in = E).
Note the above definition only specifies a set-to-set relation. Each R2 is mapped to set of numbers; however, the specific ordering of vertices within each R2 is not defined. Therefore, generating a D-numbering from an RIP sequence does not yield a unique result, as multiple D-numberings can correspond to the same RIP sequence. For example, consider an RIP sequence for the graph in Figure I(a): K₁ {a, c). K₂ {b,ce c, d], K₃ = (b. e}. K₃ {e, f). Ks = (b, g. g. Kg (b,g, and K₁ (b, h. From this RIP sequence, we can determine the mapping for the residuals:
= ba = (10, 9, 8), (d) (e) = (6), a = -) (() ()))))))(()())))))))))))))))) (()) = (1).
Correspondingly, one of the D-numberings for the vertices can be defined as:
(bb) = 10, a(a) 9, (c)) 8, a(d) = 7, a(e) = 6, a() 5, a(j) - - 4,0(g) = 2, a())) =
Another D-numbering is (aaa) 10, a(c) ab)) ad) = 4.())) =3,((1) 2,
which only changes the vertex order in residual R1.
We that D-numbering is also perfect elimination ordering, meaning it represents DAG of G.
Theorem B.2, (Leimer, 1993). Any D-numbering must be a perfect elimination ordering.

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
It is well known that any perfect elimination ordering can represent a DAG in Markov equivalent class (Wienöbst al., 2023). Therefore, for any D-numbering (which is a perfect elimination ordering by Theorem B.2), there exists corresponding DAG in the MEC. On the other hand, a DAG in the MEC can be represented by one more D-numbering(s). This statement correspond to Lemma B.3 below, respectively.
Lemma B.3. Every DAG in the Markov equivalence class represented by G can be represented by at least one D-numbering.
Proof. Every DAG in a Markov equivalence class represented by G can be represented by the ordering generated by MCS algorithm. The ordering of UCCG obtained from the MCS algorithm is also a D-numbering (Blair & Peyton, 1993).
C. D-numbering, Clique Sequence and Root-Selected Essential Graph
Recall from Section 3 that, for a chordal graph G with some selected maximal clique K1, the root-selected essential graph GKK, is critical to the construction of the Clique-Picking algorithm of Wienöbst et al. (2023). We now discuss in more details how to relate D-numbering and clique sequence to this GK,,
In fact. with the concept of D D-numbering, we can construct GKv in the following way. First, for a chordal graph G, we find all RIP clique sequences beginning with K₁- Then, for each clique sequence, enumerate all its D-numberings and construct the corresponding DAGs. The union of these DAGs is exactly GKi, This approach of constructing GKv help us to identify the edges' direction and undirected connected component (UCCG) of GKi from a different perspective. In this section, we address the edge direction determination. The UCCG identification for GKI is left for the next section.
We start by considering specific RIP sequence S (KI....; Km). Suppose x and y are two adjacent vertices in G. We consider two cases below:
1. If x and y are in two different residuals R. and Rg. respectively with < q. In this case, for any D-numbering a of
S. we have axx) > aly). Recall a D-numbering is perfect elimination ordering. This implies that we always have
x: -> y in the DAGs represented by all D-numberings of S.
2. If x and y are in an identical residuals Rp, then relative order between (xx) and ayy) can be arbitrary. The means the edge direction between and y can be arbitrary among the DAGs represented by the D-numberings of S.
Consider all the D-numberings of the RIP clique sequence S, and denote GS as the union of DAGs represented by these D-numberings. Then, we can conclude: (1) the endpoints of any directed edge in GS are in different residuals and (2) the endpoints of any undirected edge in G are in the same residual.
Instead of a single RIP sequence, let us now consider all RIP sequences that start with Kj. For two adjacent vertices x, y/ in G, it is possible that
(I) there exists an RIP sequence S = (K1, K2,..... Km), such that æ and y are in two different residuals Rp and Rg- respectively with < q. Then, we have x + y as an edge in G$:;
(2) there exists a permuted RIP sequence S₂ = (Ka( Ka(z)..... Ko(m)) such that x and y are in two different residuals Ro(y') and Ro(g'), respectively but with p/ o' Then, have <- y as an edge in GO. When both (1) and (2) in the above happen, the edge direction between and y is undirected in GK1 UsGS, which is a union with respect to all RIP sequence S that starts with K1.
In summary, the above discussion indicates we can construct GK by enumerating all clique sequences starting with K1, enumerating all their D-numberings and construct the corresponding DAGs. Then, GKK, is simply the union of these DAGs, More importantly, if the relative order of two maximal cliques (K, p and K₂) can vary across different RIP sequences, the direction of the edge between two vertices in their residuals may potentially be undirected in GKK
D. Super Cliques and Super Residuals from the Perspective of RIP Sequences
Now, we examine super clique, super residual and undirected connected component (UCCG) from the perspective of RIP clique sequence alone, without relying on the clique rooted trees. This provides more theoretical tools for establishing Theorem 5.3.
Recall from Section C, to construct some root-selected essential graph GK3, we have to consider all RIP sequence starting with K₁. Fortunately, this exhaustive process is not necessary. Instead, the key question is: how can we characterize K using a single RIP sequence that starts with K₃?
12

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
As discussed in Section C, if the relative order of two maximal cliques (Kp and K₂) can vary across different RIP sequences, the direction of the edge between their residuals may potentially remain undetermined. The following lemma implies that this uncertainty can be identified using single clique sequence. Specifically, if their separators satisfy Sp Ç Sq. then the relative order of Kp and Kg is interchangeable, and the edge between their residuals may remain undetermined.
Lemma D.I. Let K1; K2,...,K Km be an RIP sequence of the clique set Kg in UCCG G. If Sp is proper subset of Sq for any P. 9 = 2,..., with p < 9, then there exists a permutation such that o (11) = 1 and > t(p = a(8), (()) in the RIP sequence Ko(1), Ko())..., Ka(m)-
....
Proof. We can assume without loss of generality q 9= m. The proof is by induction on m.. The case m = 2 is trivial. Let Ki...., Km be an RIP sequence for some m 2 3. There is p such that Sp & Sm.
Case 1: p= m 1.
Then we define amm - 1) = m, ((m) m 1, and (kk) k, Vk < m Sm \ Sm-1 is not in Kiy..., Km 2. so there is clique K, such that Km n (K) U-.. U K,. Meanwhile, Km- n (Ki U... ..... U Km-2 2 U km)) must be subset of Km. Hence Ko()), Ko()).... .... Ko(m) is an RIP sequence in this case.
Case 2: p < m m--1 1.
Without loss of generality, assume that Sp is a proper subset of Sm-1. Using the induction hypothesis there is a permutation such that Ko(1), K Ko(2)..... Ko(m-1) an RIP sequence. Then we get
K Koa))...KK.rr-u1
1o(r-1); Km (
where a(r) = m-1, For Vw > f, S. SS, is not in the (Ko Meanwhile we have Sp = Km and Sm = (a(t) n (Ko(1) U... U Ko(t-1) U Km). Hence the separators of the full sequences are also identical this case.
For any two cliques Kp and Kg in the sequences Ky,..., Km. suppose their relative order can be reversed to get (a())-K(2))- Ka(2)..... K Ko(m), where p < q but o (p) > o (q). This reflects the ambiguity in the direction of edges between RS and Rg. In fact, this uncertainty further indicates the residuals Rg and Ry can be potentially merged form an undirected connected components in Ca(Ki).
For example, consider again the graph in Figure I(a). The graph has the RIP sequence K1, K2, K3, Ka, Ks. Ko. KG. Because S5 ; Ss, the graph also has the RIP sequence K1, K2, Ks, K4, Ks, Ks, K7, which is obtained by permuting Ks, and Kg. This indicates the uncertainty in the direction of the edge - i in GK1 which serves as a clue that R&, and Rg may form a UCCG in k1.
However, checking interchangeability between two cliques is not sufficient determine if can merge their residuals. An additional requirement for merging their residuals is that Sp does not separate R2 and Rg in G. Still consider our example in Figure 1. S3 is a proper subset of Sg. But there is no need to merge Rd and R3 as S2 separates R2 and R3. This leads to the following definitions. They correspond to the clique header and clique tail in the main text, but the definition here is deseribed in terms of clique sequence.
Definition D.2. K2, K2...., Km is an RIP sequence of KC in UCCG G. For any = 2,..., m. we say Kp is a sequence clique header within this sequence if for any = 2, P..,P (1) S, is not proper subset of Sp or (2) Sp separates Ry and Rgin G.
Definition D.3. Let Kp,1 1 < S m, be a sequence clique header within given K1, K2,... Km- For any g = p, p.... m. we say that Kg is a sequence clique tail following K, if (1) S, is a proper subset of S, and (2) Sp does not separate R, and Rs in G.
In fact, when a clique tree is given, the above definitions are equivalent to those presented in the main text from the perspective of the clique tree structure. Similarly, super cliques and super residuals can be defined from the viewpoint of a clique sequence.
Definition D.4. (Sequence super clique, sequence super residual) Within an RIP sequence, suppose Kp a sequence clique header and Kp....., Ky, are all its sequence clique tails.
The clique set (Kp, Kp....., Kp.} } called a sequence super clique.
13

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
ii. The set of the residuals {Rps Ppt....,, . is called sequence super residual.
Theorem D.5. For a given RIP sequence K1,'' .. Km, Ca (K1) consists of the subgraphs of G induced by the sequence super residuals within K1:'.,, Km-
Proof. For a sequence clique header p- assume there are u separators, of which Sp is a proper subset. We denote them as Spi...., Sp.,. where 1 < P1 < not separate Rp and Rg in G. This is the opposite for any q = Pr+1..... Pu. For any q = Pl..... Pu. from Lemma D.I, we know that there exists an RIP sequence Ko(1), K Ko(2).... (m)) such that (11) = and & > l(p= (8), q (t)). When q= = P1, for a node x in R2 n and any y in Rg. assume æ ~ y in G. The edge x - y must be directed as x + y in the DAG represented by the D-numbering generated from K1, K2,.... Km. At this point x and y are in Ro(e). Therefore, the edge x y can be either - y or y + z in the DAG represented by the D-numbering generated from Ko(1): (o()) (o.))..... Ka(m). As result, the edge x y will remain undirected in GKi,
Pv. I m. For convenience, assume that for any q ....... Pr. where r < u, Sp does
Now we know that CK [Rp; R is an undirected graph. Similarly, if exists an t = ......,u u and y E Rp, n NSp, such that in G for any 2 E Rp., the edge y 2 will remain undirected in GKK, For any q = Pr+l...., Pa. we know that Sp separates R and Rg in G. so such v should lie in 2....,,. r. Recursively, (Rp, Rp:...., Rp. is an undirected graph. In [Rp,
Definition D.2, we confirm that Kp cannot be a sequence clique tail following another clique. There are only K Ku....,. Kp. such that Kp and Kp, can be sequentially replaced for any v = 1,.... u. Furthermore, Kpp.... Kp. are sequence clique tails following Kp as defined in D.3. According to the above description, only Rpi...., Ro, and Rp together induce an undirected graph.
E. Technical Proofs for the Main Paper
Proof of Theorem 5.3. First, assume that there exists a clique Kg, where q < p. such that K2 is not an ancestral clique of the sequence clique header y,- For such a K,. we have Sg & Sp. and Sp does not separate R and Rg in G. Without loss of generality, assume that there exist nodes x E Rp and y E Rg such that x ~ y in G. Then, the union of Sy and fz. y} will form a clique in Kg. This must be a child clique of Kp according to the MCS algorithm. From the clique-intersection property, we know that y must appear in every clique along the unique path from Kp to Kg. However, y is not in Kp. leading to a contradiction.
The same argument applies for the second case. There cannot exist a non-descendant elique K2 of K2 such that Sp & S. and Sp does not separate Rd and Rg in G.
Proof of Propositions 6.2 & 6.3. Denote Kin.... the Hp-1 remains unchanged after the permutation. For p 2, 2 1, we have K2 1) In K1 .K...... Km- denote the parent clique of Kp as Kg. Thus, Kp n Hp-1 lies within Kg. Lemma 6.1 implies that Ho = Hp U K,, which means Sa(pt1)=
Kp-1 D.....KK---1- as Hp. For forp=i+1,.... m. the proposition holds naturally, as
K Ko(p+1) 1) n (am)) = (Ko(pt)) n Hp-1) ((())(((())))) n K,).
The first item is equal to Kp n Hp-1, which is contained within Kg. The second item is a subset of K2 U H;-1, which in turn is contained within K,. It follows naturally that So(++1) remains contained within K, when KG n K; = 0. When Kp n K2 & 0. we also have Kp n K2 * 0, indicating that K₁ must be the parent of Kp. i.c., t == 1. In this case, Sa(p+1) is still contained within Kg.
Proof of Theorem 6.4. First, K, cannot be a clique header within K. Thus, for SK() of T.K it will break down into several super cliques with respect to TK: Any child clique of K, must be a clique header within 7Kk From Propositions 6.1 &&&&O 6.3, the separator Sp remains the same in Sep(K, (K,) and Sep(K,) for any p E [m]] \ t). For any child clique of K;, denote it temporarily as Kg. All descendant cliques of Kg in SK!! will be clique tails that follows clique header K₂ within T
Second, K, must be a clique header within TKk The child clique of K, must be a clique header within TKk However, the child clique of K, may also be a clique tail that follows clique header K, within TK, For any child clique of K,, denote it temporarily as Kp. From Definition 5.1, if S, in Sep K,) is a proper subset of S, in Sep( then K, will be a clique tail that follows clique header K, within TK. Otherwise, Kp remains a clique header within TKK
14

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
Thus, aside from the two points mentioned above, the clique header within T'K remains the same within TK, The separator Sp is identical in both Sep(K;) and Sep( K2) for any p E [m]] (i, Therefore, the set of clique tails that follows clique header within 7 is the same as that within TK:
Proposition 6.3 tells us that for any P E [m]] \.  W: {i,t}. Rp is the same in both Res(K, and Res( K2). Additionally, it is clear that Rg = K2 A (K₃ n K2) in Re)( The super cliques described in SC-Trans-Opp (llanss 3-8) do not involve K₃- Similarly, any super clique described in Trans() 11-14) also does not involve K,. However, for the super cliques described in Trann 9-10), K2 is involved. Thus, SR (8) of TK: is the union of R2 = K2 \ (K; n K₂) in Res(K, and the super residuals of the super cliques with respect to T proposed in (C-Trans-Op(->line 10).
Proof of Theorem 4.1. We begin by showing that any clique header within 7 and the following clique tails are obtained from Sep(K) ). The conditions for a clique header and a clique tail are opposites. For the sequence p = 2...., m, we proceed with the following procedure: there an ancestral clique Kg of K2 such that S. S Sp (with S. and Sy being in Sep(K) (1)), )), then K₂ will be a clique tail following Kg- Otherwise, K₂ will be a clique header within T'i, For any super clique SK(1. 2 S P S m, of TKs, the clique Kp will be identified in the p-th step, and all other cliques in SK p i.e., the clique tails following Kp, denoted as Kp, Pp:.... Kp, will be identified in the P1. . P,-th steps.
For any i = 2.....,... m. in TKK, K, + K;, and by reversing K, + K; to K; + K,, the resulting tree is TK, where K, is the parent of K; in T There are m separators Si...., Sm in Sep(K,), Let S. = K, n K, and S = 0. Now Si...., Sm will form Sep(K)). Similarly, there are m residuals Ri.... . Rm in Res R,)) Let R. K, (K₃ n K,) and R3 = K, Now R1, ......, , R., R... will form Res(K,). Next proof is by induction on i. Using the induction hypothesis we have computed the set of super cliques and super residuals with respect to T < t). Thus will derive the set of super cliques and super residuals with respect to TK, from these with respect to TKk by Theorems 6.4.
Proof of Theorem 4.2. To compute Co (K1), we need to implement the procedure in order 2, .,..., proof of Theorem 4.1. For each clique Kp. there are most p 1 ancestral cliques. So we obtain the following bound:
... m. as proposed in the
m
i i--18 1) Σ
2 (m² -m)-
For = -....., m. we can easily get Scp(K,) and Res(K), (i) from Sep (K,) and Ros(K)), where K2 is the parent clique of K; in TKi, Function SC-Trans-Op(.) describes the difference between the set of super cliques with respect to T.K and T'K, SC-Trans-Opt 0aoe00(OOe)sss 3-8) requires identifying all child cliques of K; in TKK while SC-Trans-Op( (lines 9-10) requires identifying all child cliques of K, in TKk The sum of the number of child cliques of K, and K; is bounded in m In the worst case, for any K,, = 2, ................................ m, the computation of (ax))) is bounded by m. Therefore, the total computation for Co (K2).... Co (m)) ) is bounded by m(m 1). In conclusion, SC-Trans algorithm has time complexity of ((m)). O
15

---

An Improved Clique-Picking Algorithm via Super Cliques Transfer
F. Working Example
Input: pki
SC-Creme-Opp
SeptEj), RestKi)
Le colke)
Read Cg(Kg)
SC-Trans-Op Op
1., Calia)
Upddato OP
1-2
Ky-48g 1f
Giet Sep(K5), Kes(Kig), 2
Sept8y), Kost&g)
CotKg), 7%:
SC
100, Colka)
Update
1-3
K1 in
Get Stpt&g), Ros(Kg),
Sept(ig), Reat&ig)
1,99, 7hss Septiig), RostK(a)
SC-Trans-Op
219 ColKa)
Update
Ag -hk in
Get SeptK Res(K.),
Read LP), CalKi)
SC-Trans-Op
pm Co(Rs)
8, -K,
Get Sep(Kg), Res(Kg),
OP
SuptAig), RestK's)
Read (.9), ColKs) ph,
SC-Trans Op
1 Colka)
Update OP
Kg K in
Sep(Fig). Res(Kg),
Sep(Kg), Res(Kg)
Rend EP9, CalKia,, 7
SC-Trans-Op
Calks)
Update OP
-
Sep(Ky), Res(&iy),
SeptK;), Res(Kr))
Get The Parent Cligue
By Capring These of lts Paront Clique
Algurihmm
Oupprr
Figure working example of our SC-Trans algorithm (Input: UCCG G in Figure ((a) and rooted clique tree Kh in Figure 1(b). Output: Co(K)))) The detail of Update OP is presented in Algorithm 2 Lines 5-6 & 8.
16


Reviews:
[{"review_id": "RDVNl0Z8wJ", "reviewer": "Reviewer_WqwP", "summary": "Paper addresses the computational complexity of finding the size of the so-called Markov equivalence class (MEC) encoding conditional dependencies. Conditional dependence properties are captured by d-separation property of the DAGs and the method counts DAGs in the MEC class (representing the same/equivalent causla relationships). Generally, size of MEC grows exponentially in number of vertices and efficient methods are needed.\n\nThe paper improves on the recent Clique Picking (CP) method of Wienobst et al. (2023) presented in Algorithm 1. in the paper. Authors propose novel click structures called Superclicks (Definition 5.2) and propose a novel Super Clique Transfer procedure to improve computational cost of generating undirected connected components $C_G(K)$ of the tree with selected root clique $K$, the step 2. of the Algorithm 1. Using Super Cliques (SCs) enable an efficient reuse of the structures across different rooted trees avoiding repetitive construction. As a result, after definitions and theoretical framework derivations (Theorem 4.1, 4.2) and further detailed in Sections 5&6, the complexity of step 2 of Algorithm 1 is reduced from $O(m(|V|+|E|))$ to $O(m^2)$.\n\nThis constitutes the main contribution of the paper, supported by numerical experiments on random choprdal graphs in Section 7. This is claimed to enhance a feasibility of real-world applications such as casual inference in healthcare and AI.\n\n## update after rebuttal: Thanks to authors for updates, new experiments and clarifications regarding proofs. I found their arguments and experimental results convincing and raise my score to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your feedback. We are excited that you have found our approach useful and novel. Please find below our response to your concerns.\n\n> **Claims And Evidence:** *\"...further visual helpers may improve appeal of the paper to wider community...\"*  \n\nThank you for the helpful suggestion. We will include a table summarizing all key notations and concepts, along with a detailed example illustrating how the algorithm works. These additions, to be placed in the appendix, will enhance the clarity and accessibility of our method for a broader audience.\n\n> **Theoretical Claims:** *\"...but some details are missing, e.g., 'easy to see' under Proposition 6.3, etc.\"*\n\nThank you for pointing this out. We will provide more detailed explanation texts  to improve clarity and rigor.  In particular, for *'easy to see' under Proposition 6.3*, we will add an explanation: \"The edge $K_1\\rightarrow K_i$ in $T^{K_1}$ will be redirected as $K_i\\rightarrow K_1$ in $T^{K_i}$. This implies $K_1$ becomes a child clique of $K_i$ in $T^{K_i}$. As the root $K_i$ is the only ancestral clique of $K_1$ in $T^{K_i}$,  $K_1$ must be a clique header within $T^{K_i}$ by Definition 5.1.\"\n\n\n> **Weakness 1** *\"...it is unclear where the proof can be found... Overall I find arguments convincing but theoretical argument would benefit from more detailed proofs...\"*\n\nThank you for your  feedback. We would like to clarify that the technical proofs are included in the **Appendix of the main paper**, *not* in the Supplementary Material. Please refer to **Appendix D. Technical Proofs for the Main Paper** at the end of the main manuscript. To help readers locate the proofs more easily, we will explicitly highlight their locations in the final version of our manuscript:\n1. The  proof of Theorems 4.1 can be found in Appendix D.*Proof of Theorem 4.1.* (Line 699); \n2. The  proof of Theorems 4.2 can be found in Appendix D.*Proof of Theorem 4.2.* (Line 713); \n3. The  proof of Propositions 6.2 \\& 6.3 can be found in Appendix D.*Proof of Propositions 6.2 \\& 6.3.* (Line 668).\n\nLastly, we will clarify that  Lemma 6.1 was established in Leimer (1993), Page 105, Proposition 2.4. (iii).\n\n> **Weakness 2** *\"Clarity of presentation of the evidence in Section 7 is recommended for a remake.\" \"...It is suggested to use  relative measure over changing $r$ or vertices...\"*\n\nThanks for your comments. We have conducted additional experiments and will revise Section 7 to better demonstrate the advantage of the proposed method. \n\nWe would like to clarify that the proposed algorithm (ICP) and the previous algorithm (CP) were tested over various specifications of **graph edge density** $r=|E|/|E_{\\max}|$ with $|E_{\\max}|=|V|(|V|-1)/2$.\n\nWe performed experiments for $|V|=1024$ and $2048$, and the results are summarized in the tables below. As the edge density $r$ increases, the difference in running time (in seconds) between the two algorithms becomes more pronounced. This trend is attributed to the fact that denser graphs generally correspond to a lower value of $\\theta=m/(|V|+|E|)$, which enhances the performance advantage of our proposed method.\n\n**Table1: Comparison between ICP and CP**\n|||||||\n|:-:|:-:|:-:|:-:|:-:|:-:|\n||| $\\vert V\\vert=1024$ ||||\n|$r$|0.06|0.09|0.15|0.27|0.43|\n|$\\mathrm{CP}-\\mathrm{ICP}$ (seconds) |3.75|4.40|5.72|7.10|8.73|\n||| $\\vert V\\vert=2048$ ||||\n|$r$|0.04|0.06|0.10|0.22|0.49| \n|$\\mathrm{CP}-\\mathrm{ICP}$ (seconds) |19.45 |34.47|41.54|59.24|62.24|\n\nRecall that our algorithm enhances Step 2 of Algorithm 1. When focusing solely on the computational cost of this step, the advantage of our method becomes even more evident. Let $T_{\\mathrm{CP},2}$ be the average running time of Step 2 as implemented in Wienöbst et al. (2023), and let $T_{\\mathrm{ICP},2}$ be the average running time of our improved approach for the same step. The table below presents both the difference and the ratio between these average running times. The results highlight substantial improvements achieved by our method in terms of efficiency.\n\n**Table2: Comparison between Step 2 of ICP and CP**\n|||||||\n|:-:|:-:|:-:|:-:|:-:|:-:|\n||| $\\vert V\\vert=1024$ ||||\n|$r$|0.06|0.09|0.15|0.27|0.43|\n| $T_{\\mathrm{CP},2}-T_{\\mathrm{ICP},2}$ (seconds) | 3.31 | 4.65 |5.66 |8.04| 9.28 |\n|$T_{\\mathrm{CP},2} / T_{\\mathrm{ICP},2}$ |7.88|19.02|26.80|65.91|159.57|\n||| $\\vert V\\vert=2048$ ||||\n|$r$|0.04|0.06|0.10|0.22|0.49|\n|$T_{\\mathrm{CP},2}-T_{\\mathrm{ICP},2}$ (seconds) |17.99| 24.19|37.41 |72.44 |81.45 |\n|$T_{\\mathrm{CP},2} / T_{\\mathrm{ICP},2}$ |10.05|16.42|29.71|92.31|318.54|\n\nThe full new results will be included as new figures and tables in the revision. We believe these additional experiments will significantly enhance the evidence to support the advantages of the proposed method.\n\n> **Other Comments Or Suggestions:**\n\nThank you for pointing this out. We will carefully proofread the paper and correct these typos in our final submission.", "claims_and_evidence": "Overall, problem to solve is well motivated and laid out. Arguments are clear and readable, yet exposition is quite technical. Figure 1. helps a lot, but further visual helpers may improve appeal of the paper to wider community. Experimental evidence is rather frugal but conceptually sufficient I believe. Clarity of presentation of the evidence in Section 7, is on the other hand, recommended for a remake. See comments and Weaknesses 1 and 2 in respective sections.", "methods_and_evaluation_criteria": "Paper argument is mainly theoretical so the selected experiments on random graphs are rather verification and supportive evidence. In this sense they are sufficient. For details see respective sections below.", "theoretical_claims": "As for Theoretical evidence, Theorems 4.1, 4.2, Lemma 6.1, Propositions 6.2 and 6.3. are clearly stated but it is unclear where the proof can be found. Supplementary Material contains only Jupyter Notebook implementation of the SC+Trans algorithm. \n\nThe sketch of the arguments is to be found in related sections for Lemma and Propositions, but some details are missing, e.g., 'easy to see' under Proposition 6.3, etc.\n\n$\\textbf{Weakness 1}$: Overall I find arguments convincing but theoretical argument would benefit from more detailed proofs in Supplementary Material. This would make the paper more complete and self-contained rendering it more useful to wider research community, I believe.", "experimental_designs_or_analyses": "Section 7 presents experiments (Figure 3, Tale 2) on rangom graphs with increasing number of vertices for two ratios of dependencies in them. Namely $r=0.08$ vs. $r=0.34$, where $r=m/|V|+|E|$ suitably chopsen to demonstrate strong side of the proposed SC-Trans algortihm whose efficiency should excel in settings, where number of DAGs $m$ is strongly smaller than number of vertices and edges.\n\nWhile text in Section 7. claims the Table 2 and Fig.3 demonstrates this well, it is in fact quite hard to see from the experiments how the compute time scales with $r$.\n\n$\\textbf{Weakness 2}$: While I agree with experiments supporting the claim, it is just quite hard to read it aout from absolute numbers presented. It is suggested to use relative measure, e.g., a (run time diference ICP-CP) over changing $r$ or vertices, or other means to present the evidence of the main claim of the paper more clearly.", "relation_to_broader_scientific_literature": "Introduction contains relevant mentions of the literature of the field with applications in epidemiology, biology ad economics with references mentioned.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths: novelty, contribution, addressing a timely problem, theoretical arguments are well written (yet still lacking some rigour that is suggested to be added, see W1)\n\nOther Minor Weaknesses: Applications and possible problems to be solved by proposed method", "other_comments_or_suggestions": "-typos, L076 (\"product\" instead of multiplication), L186 (\"be be\")", "questions_for_authors": "See above", "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": "", "extra_scores": {}}, {"review_id": "ZkNsdxMinp", "reviewer": "Reviewer_y8Y8", "summary": "This submission presents an improvement of the recent polynomial time algorithm for counting moral acyclic orientations of chordal graphs, a problem which lies at the core of counting Markov equivalent DAGs. The main idea of that algorithm compared to older iterative root-picking algorithms lay in picking root-cliques. However, the prior algorithm recomputed equivalent information multiple times when choosing a different sequence of root-cliques. The present submission can identify and avoid this behavior by using what the submission refers to as super clique structure. Overall this improves the efficiency of the general approach at the point where the next lookup assuming the specific choice of the root clique. Beside proving the improved asymptotic complexity bound, the submission includes small test indicating the increased efficiency also empirically.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly thank you for the positive feedback and valuable recognition of our work's core ideas and contributions.", "claims_and_evidence": "No concerns.", "methods_and_evaluation_criteria": "The methods make sense for the claims being made.", "theoretical_claims": "I read only what is not in the appendix.", "experimental_designs_or_analyses": "I did not as the experiments are not the main contribution and the mild claims made about them seem unproblematic.", "relation_to_broader_scientific_literature": "The submission continues a line of research improving the runtime of algorithms for counting MAOs. This is also clearly described in the introduction of the submission.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "The topic and contribution are relevant to the audience at ICML. The presentation is also satisfactory. In terms of content, I find the key ideas behind the improvement elegant and natural. I recommend acceptance of this submission.", "other_comments_or_suggestions": "None.", "questions_for_authors": "None.", "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": "", "extra_scores": {}}, {"review_id": "3Rmkec08yb", "reviewer": "Reviewer_ev8s", "summary": "This paper proposes an improvement to the clique-picking algorithm introduced by Wienöbst et al. (2023) for counting Markov Equivalent Directed Acyclic Graphs (DAGs). The authors introduce super cliques and super residuals to reduce computational complexity when identifying undirected connected components (UCCGs) in a Completed Partially Directed Acyclic Graph (CPDAG). The proposed Super Cliques Transfer Algorithm optimizes the recursive clique-selection process, leading to a computational cost reduction from $O(m(|V|+|E|)$ to $O(m^2)$ where $m$ is the number of maximal cliques. Experiments on randomly generated chordal graphs demonstrate that the improved algorithm (ICP) outperforms the original Clique-Picking (CP) algorithm in runtime.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable comments and remarks. We will address your questions and suggestions below.\n\n> **Other Comments Or Suggestions:**\n*\"More discussion on the quantitive comparison between the computational complexity of proposed algorithm with the existing work will be appreciated.\"*\n\nThanks for the comments. We have conducted additional experiments and will expand the related discussion as follows.\n\nIn particular, we have  tested the proposed algorithm (ICP) and the previous algorithm (CP) over various specification of **graph edge density $r$**, which is measured by $|E|/|E_{\\max}|$ with \n$|E_{\\max}| = |V|(|V|-1)/2$. We performed experiments for $|V| = 1024$ and $2048$, and the results are summarized in the tables below. As the edge density $r$ increases, the difference in running time (measured in seconds) between the two algorithms becomes more pronounced. This trend is attributed to the fact that denser graphs generally correspond to a lower value of $\\theta = m / (|V| + |E|)$, which enhances the performance advantage of our proposed method.\n\n**Table1: Comparison between ICP and CP**\n|||||||\n|:-:|:-:|:-:|:-:|:-:|:-:|\n||| \\|$V$\\|=1024 ||||\n|$r$|0.06|0.09|0.15|0.27|0.43|\n|$\\mathrm{CP}-\\mathrm{ICP}$ (seconds) |3.75|4.40|5.72|7.10|8.73|\n||| \\|$V$\\|=2048 ||||\n|$r$|0.04|0.06|0.10|0.22|0.49| \n|$\\mathrm{CP}-\\mathrm{ICP}$ (seconds) |19.45 |34.47|41.54|59.24|62.24|\n\nRecall that our proposed algorithm enhances Step 2 of Algorithm 1. When focusing solely on the computational cost of this step, the advantage of our method becomes even more evident. Let $T_{\\mathrm{CP},2}$ denote the average running time of Step 2 as implemented in Wienöbst et al. (2023), and let $T_{\\mathrm{ICP},2}$ denote the average running time of our improved approach for the same step. The table below presents both the difference and the ratio between these average running times. The results highlight substantial improvements achieved by our method in terms of efficiency.\n\n**Table2: Comparison between Step 2 of ICP and CP**\n|||||||\n|:-:|:-:|:-:|:-:|:-:|:-:|\n||| $\\vert V\\vert=1024$ ||||\n|$r$|0.06|0.09|0.15|0.27|0.43|\n| $T_{\\mathrm{CP},2}-T_{\\mathrm{ICP},2}$ (seconds) | 3.31 | 4.65 |5.66 |8.04| 9.28 |\n|$T_{\\mathrm{CP},2} / T_{\\mathrm{ICP},2}$ |7.88|19.02|26.80|65.91|159.57|\n||| $ \\vert V\\vert=2048$ ||||\n|$r$|0.04|0.06|0.10|0.22|0.49|\n|$T_{\\mathrm{CP},2}-T_{\\mathrm{ICP},2}$ (seconds) |17.99| 24.19|37.41 |72.44 |81.45 |\n|$T_{\\mathrm{CP},2} / T_{\\mathrm{ICP},2}$ |10.05|16.42|29.71|92.31|318.54|\n\nThe full results will be included as new figures and tables in the final version of the manuscript. We believe these additional experiments significantly enhance the evidence to support the advantages of the proposed method.\n\n> **Other Comments Or Suggestions:**\n*\"Is this a strict improvement? When is there a significant gap? Is there any special class of DAGs where the proposed algorithm is much better?\"*\n\nIn this work, we propose SC-Trans algorithm to improve Step 2 of Algorithm 1, which is the Clique-Picking (CP) algorithm by Wienöbst et al.(2023).  The computational complexity of our proposed algorithm is $\\mathcal{O}(m^2)$, compared to $\\mathcal{O}(m(|V| + |E|))$ for the corresponding step in the CP algorithm. This constitutes a strict and significant improvement when $m (> 1)$ is a moderate value and the graph size, i.e., $|V| + |E|$, is large. The improvement is especially pronounced for large graph where the ratio $m/(|V| + |E|)$ is small. This is supported by the numerical evidence as in our response to your previous comment (please refer to the tables above).\n\n> **Other Comments Or Suggestions:**\n*\"It would be more illustrative to plot the experiment results in log-log plot.\"*\n\nThanks for the suggestions. We will adjust the plot to better demonstrate the advantages of the proposed algorithm in the final version of the manuscript.\n\n> **Questions For Authors:**\n*\"How do we compare the proposed algorithm to other counting algorithms\"*\n\nThank you for the question. The Clique-Picking (CP) algorithm proposed by Wienöbst et al. (2023) is the first known algorithm with polynomial complexity for this task and currently represents the state of the art. In their work, the CP algorithm has been shown to significantly outperform previous counting algorithms. Our proposed approach builds upon and improves the Clique-Picking algorithm, and therefore also outperforms existing alternatives.", "claims_and_evidence": "- The proposed Super Cliques Transfer Algorithm reduces the computational complexity of counting MEC sizes from $O(m(|V|+|E|)$ to $O(m^2)$ is supported by the theoretical analysis in Theorems 4.1 and 4.2. \n- The claim of the improved algorithm speeds up MEC size counting is supported by the experimental results in Table 2 and Figure 3.", "methods_and_evaluation_criteria": "The paper follows a solid algorithmic and theoretical approach. The evaluation is conducted via simulation experiments.", "theoretical_claims": "The paper presents several new theoretical constructs, including super cliques and super residuals, and proves their validity. Theorems 4.1 and 4.2 ensure the correctness and complexity of the Super Cliques Transfer Algorithm. While not carefully checked, the proofs appear well-structured and logically sound.", "experimental_designs_or_analyses": "The experiments are conducted to demonstrate the improvement in computational complexity. They all make sense to me.", "relation_to_broader_scientific_literature": "Bayesian network is widely used for scientific exploratory analysis, which is typically only identifiable up to so-called Markov equivalence class (MEC). To count the number of possible elements inside a given MEC is crucial for many downstream task and experimental degisn.", "essential_references_not_discussed": "Not sure. But the literature seems to be well cited in the discussion in paragraph 3-4 in the introduction.", "other_strengths_and_weaknesses": "**Strength**:\n- Reducing redundancy in clique-picking through transfer operations is well-motivated.\n- The running examples provided in Figure 1 are very helpful for illustrating the mathematical concepts and understanding the algorithms.\n\n**Weakness**:\n- See suggestions and questions", "other_comments_or_suggestions": "- More discussion on the quantitive comparison between the computational complexity of proposed algorithm with the existing work will be appreciated. Currently, the only comparison is $O(m^2)$ v.s. $O(m(|V|+|E|)$. Is this a strict improvement? When is there a significant gap? Is there any special class of DAGs where the proposed algorithm is much better?\n- It would be more illustrative to plot the experiment results in log-log plot.", "questions_for_authors": "- How do we compare the proposed algorithm to other counting algorithms listed in the literature review -- thrid paramgraphs in the introduction -- in terms of both theoretical analysis and experimental comparison?", "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": "", "extra_scores": {}}, {"review_id": "O4oyrIoz04", "reviewer": "Reviewer_W4jQ", "summary": "The paper proposed a more efficient way to improve the existing work by Wienobst et al on counting the number of DAGs in an MEC. The authors argue that the previous approach suffers in the case where there are multiple maximal cliques in a MEC. The proposed improvement is to make use of structure overlaps between these maximal cliques. To facilitate the construction of the method, the paper introduces two key notions named super clique and super residual. The key contribution in this paper is to come up with an efficient transfer operation of super cliques from one maximal clique-directed tree to another to avoid counting redundant structures.\n\n## update after rebuttal\n\nI have not changed my score because I support this paper to be accepted.  I think the paper has made a non-trivial contribution to improving the efficiency of the clique-picking algorithm by Wienobst et al. The efficiency is significant for scalable causal discovery.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading and valuable feedback. We address  the comments  in details below.\n\n>**Weaknesses:***\"...the paper can be improved by providing a working example in the appendix...\"*\n\nThanks for the suggestion. We plan to include a table summarizing all key notations and concepts, along with a detailed example illustrating how the algorithm works. These additions, to be placed in the appendix, will enhance the clarity and accessibility of our method for a broader audience.\n\n>*\"The most obvious weakness is the efficiency gain over the previous work .... try more extreme cases to show different behaviors of the algorithm.\"*\n\nThank you for this insightful comment. We agree that evaluating performance on larger and denser graphs is important for highlighting the efficiency gains. The state-of-the-art Clique-Picking (CP), proposed by Wienöbst et al. (2023) and presented as Algorithm 1 in our paper, is already quite efficient. Our work focuses on improving Step 2 of Algorithm 1 through our proposed algorithm ( ICP).\n\nFor Step 2, the computational complexity of  ICP and CP is $\\mathcal{O}(m^2)$ and $\\mathcal{O}(m(|V| + |E|))$, respectively. This represents a strict and substantial improvement when $m(>1)$ is of moderate size and $|V|+|E|$ is large. \n\nTo provide additional evidence, we conducted experiments across various levels of graph edge density $r=|E|/|E_{\\max}|$, where $|E_{\\max}|=|V|(|V|-1)/2$. We performed experiments for $|V|=1024$ and $2048$, and the results are reported in the tables below. As the edge density $r$ increases, the difference in running time between the two algorithms becomes more pronounced. This trend is attributed to the fact that denser graphs generally correspond to a lower value of $\\theta=m/(|V|+|E|)$, which enhances the performance advantage of our proposed method.\n\n**Table1: Comparison between ICP and CP**\n|||||||\n|:-:|:-:|:-:|:-:|:-:|:-:|\n||| $\\vert V\\vert =1024$ ||||\n|$r$|0.06|0.09|0.15|0.27|0.43|\n|$\\mathrm{CP}-\\mathrm{ICP}$ (seconds)|3.752|4.40|5.71|7.10|8.73|\n|||$ \\vert V\\vert=2048$||||\n|$r$|0.04|0.06|0.10|0.22|0.49| \n|$\\mathrm{CP}-\\mathrm{ICP}$ (seconds) |19.45 |34.47|41.54|59.24|62.24|\n\nWhen isolating the comparison for Step 2 of Algorithm 1, the advantage of our algorithm becomes even prominent.  Denote $T_{\\mathrm{CP},2}$ as the average running time of Step 2  executed as in Wienöbst et al. (2023), denote $T_{\\mathrm{ICP},2}$ as the average running time of our approach for Step 2. The table below presents both their difference and ratio. The results highlight substantial improvements achieved by our method in terms of efficiency.\n\n**Table2: Comparison between Step 2 of ICP and CP**\n|||||||\n|:-:|:-:|:-:|:-:|:-:|:-:|\n||| $ \\vert V\\vert=1024$ ||||\n|$r$|0.06|0.09|0.15|0.27|0.43|\n| $T_{\\mathrm{CP},2}-T_{\\mathrm{ICP},2}$ (seconds) | 3.31 | 4.65 |5.66 |8.04| 9.28 |\n|$T_{\\mathrm{CP},2} / T_{\\mathrm{ICP},2}$ |7.88|19.02|26.80|65.91|159.57|\n||| $ \\vert V\\vert=2048$ ||||\n|$r$|0.04|0.06|0.10|0.22|0.49|\n|$T_{\\mathrm{CP},2}-T_{\\mathrm{ICP},2}$ (seconds) |17.99| 24.19|37.41 |72.44 |81.45 |\n|$T_{\\mathrm{CP},2} / T_{\\mathrm{ICP},2}$ |10.05|16.42|29.71|92.31|318.54|\n\nThe full results will be included as new figures and tables. We believe these additional experiments significantly enhance the evidence to support the advantages of the proposed method.\n\n> **Other Comments Or Suggestions:**\n\nThank you for these detailed suggestions. We will carefully revise the manuscript to address each of these points in the final version.\n\n> **Questions For Authors:**\n\n> **Q1**\n\nThank you for the question. The orientation of the UCCG  $G$ cannot form new  $v$-structures or directed cycles. When  $K_1$ is selected the root, the edge between vertices $b$ and $e$ will be oriented as $b \\rightarrow e$. Suppose $f \\rightarrow e$, this would lead to  $v$-structure: $b\\rightarrow e\\leftarrow f$. Therefore, to avoid this, it must be  $e\\rightarrow f$ in $G^{K_1}$, and $G[e]$ and $G[f]$ remain two separate undirected connected components.\n>**Q2**\n\nYou are right. We deeply apologize for this typo. $\\mathcal{C}_G(K_3)$ should contain $G[a,c,d]$, *not* $G[b,c,d]$. We will carefully proofread the paper and correct the typos in the final version.\n\n>**Q3**\n\nWe assume your question refers to Theorem 5.3. The answer is no—replacing \"super residuals\" with individual residuals would lead to incorrect identification of undirected connected component, and hence incorrect counts of Markov Equivalent DAGs via Equation (2).\n\nTake the example in Figure 1: the subgraph $G[g,h,i,j]$ forms an undirected connected component in $G^{K_1}$. This component arises from merging the residuals $R_5$={ $g,j$ }, $R_6$={ $i$ } and $R_7$={ $h$ } into a single super residual. However, these residuals on their own—$R_5,R_6,R_7$—do not, by definition, form undirected connected components. Therefore, super residuals are essential for correctly identifying related structures and correctly counting Markov Equivalent DAGs.", "claims_and_evidence": "Mostly yes with some minor issues I raised in the questions.", "methods_and_evaluation_criteria": "Mostly yes. I think the experiment should try to push for very large and dense graphs in order to show the merits.", "theoretical_claims": "Yes. I have checked the proofs in section D. I don't find any issue.", "experimental_designs_or_analyses": "I have checked the experiment presented in the paper. I don't see any issue.", "relation_to_broader_scientific_literature": "This work further improves on the previous polynomial-time counting algorithm by Wienobst et al. (2023). It is built on the previous approach with an improvement to avoid counting the number of DAGs in the overlapping members of the undirected connected components. The algorithm remains polynomial-time with respect to the number of maximal cliques.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "I think this work will have the most positive impact on large and dense graphs. This aligns with the original motivation why one even needs to have a polynomial-time counting algorithm. The non-trivial part of this paper is to come up with the notion of super cliques and residuals and innovatively incorporate them in an efficient transfer operation. I personally spent quite a lot of time to understand the idea and tried to come up with an alternative method, but I failed. \n\nFor weaknesses, there are a few typos, but it's very minor. I think the presentation of the paper can be improved by providing a working example in the appendix since there are various different graph concepts and it's hard to remember all the notations until I have read it many times back and forth. The most obvious weakness is the efficiency gain over the previous work. It does not save more than half of the time even for the size of 4096. When r is increased, the patterns in the left and right figures in Figure 3 are almost the same. It would be better to try more extreme cases to show different behaviors of the algorithm.", "other_comments_or_suggestions": "- \"Notably, Wien¨obst et al. (2023) introduce the Clique- Picking (CP) algorithm, which is a polynomial-time algorithm for counting MECs.” I think it will be better to just say determining the size of an MEC or counting the number of DAGs in an MEC instead of saying counting MECs. \n- The big O notations are inconsistent e.g. line 193,194 vs line 56\n- It would be better to add an example in the paper to walk people through the algorithm to show how the algorithm works in one clean way.\n- I suggest the authors to put Algorithm 2 instead of \"SC-Trans algorithm” in Theorem 4.1 and Theorem 4.2 so that the authors don’t need to explicitly say: \"For our SC-Trans algorithm in Algorithm 2, we have the following results.”\n- The \"Case 1, Case 2, Case 3” in section 6.2 can be wrapped by a number list.\n- Line 427: \"Algorithm1\" -> \"Algorithm 1\"", "questions_for_authors": "1. In line 147, why G[e] and G[f] are two separate undirected connected components but not G[e,f] in C_{G}(K_{1})?\n\n2. In line 201, how can C_{G}(K_{3}) contain G[b,c,d] given that K_{3} = {b,e} and C_{G}(K_{3}) is defined as the undirected connected components of G^{K}[V \\ K], which is a subgraph that excludes K by definition? Do you mean G[a,c,d]?\n\n3. Can I replace \"super residuals” in Theorem 4.5 with just residuals except for the residuals from the root?", "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": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: All reviewers are unanimous in their opinion of this paper. This paper addresses an important algorithmic aspect of counting Markov equivalent (ME) DAGs efficiently by improving an existing algorithm. This ability to count ME DAGs is very useful for Bayesian approaches for experimental design. This paper makes a non trivial algorithmic contribution in this space with theoretical results backing it. 

Recommendation: Accept
Decision: Accept (oral)