DSCS: Fast CPDAG-Based Verification of Collapsible Submodels in High-Dimensional Bayesian Networks
Authors: Wentao Wu
Shiyuan He
Jianhua Guo
Venue: NeurIPS 2025 poster ()
Keywords: directed acyclic graph
Bayesian network
Markov equivalence class
estimation-collapsibility
completed partially directed acyclic graph
Primary area: probabilistic_methods

Abstract: Bayesian networks (BNs), represented by directed acyclic graphs (DAGs), provide a principled framework for modeling complex dependencies among random variables. As data dimensionality increases into the tens of thousands, fitting and marginalizing a full BN becomes computationally prohibitive—particularly when inference is only needed for a small subset of variables. Estimation-collapsibility addresses this challenge by ensuring that directly fitting a submodel, obtained by ignoring non-essential variables, still yields exact inference on target variables. However, current DAG-based criterion for checking estimation-collapsibility is computationally intensive, involving exhaustive vertex searches and iterative removals. Additionally, practical applications typically identify the underlying DAG only up to its Markov equivalence class, represented by a completed partially directed acyclic graph (CPDAG). To bridge this gap, we introduce sequential $c$-simplicial sets—a novel graphical characterization of estimation-collapsibility applicable directly to CPDAGs. We further propose DSCS, a computationally efficient algorithm for verifying estimation-collapsibility within CPDAG framework that scales effectively to high-dimensional BNs. Extensive numerical experiments demonstrate the practicality, scalability, and efficiency of our proposed approach.

DSCS: Fast CPDAG-Based Verification of Collapsible Submodels in High-Dimensional Bayesian Networks
Wentao Wu', Shiyuan He², Jianhua Guo
Northeast Normal University, BBejjing Technology and Business University
Abstract
Bayesian networks (BNs), represented by directed acyelic graphs (DAGss) pro- vide a principled framework for modeling complex dependencies among random variables. As data dimensionality increases into the tens of thousands, fitting and marginalizing full BN becomes computationally vrohibiivee-patiiullal inference is only needed for small subset of variables. addresses this challenge by ensuring that directly fitting a submodel, obtained by ignoring non-esso -ossenntttall variables, still yields exact inference on target variables. However, current DAG-based criterion for checking estimation-collapiibbe computationally intensive, involving exhaustive vertex searches and iterative re- movals. Additionally, practical applications typically identify the underlying DAG only up to its Markov equivalence class, represented by completed partially directed acyclic graph (CPDAG), To bridge this gap, we introduce sequential o-simplicial sets-a novel graphical characterization of estimation-collapsibiltt directly applicable to CPDAGs. We further propose DSCS, a computationally effi- cient algorithm for verifying citimation-oollasibbiii within CPDAG framework that scales effectively to high-dimensional BNs. Extensive numerical experiments demonstrate the practicality, scalability, and efficiency of our proposed approach.
when cetimation-collassilblie
is
1 Introduction
Bayesian networks (BNs), represented by directed acyclic graphs (DAGs), offer a powerful and transparent framework to model complex dependency structures among random variables. By representing each variable as a vertex and each direct influence as a directed edge, BNs allow practitioners read off causal correlational relationships from their DAGs and to leverage powerful algorithms (such as paassage-asssigg to compute marginals and posteriors efficiently. As result, BNs have become indispensable tools across numerous domains, including econometrics [[]. engineering (2H4), bioinformatics 6). causal inference [7)), and machine learning [10H12). Recently hybrid architectures that integrate DAG structure with deep neural networks have further extended BNs expressive power while preserving their causal semantics [e.g. 13.15
Despite these strengths, the explosive increase of data dimensionality has highlighted critical bottleneck: constructing and marginalizing full BN becomes infeasible when thousands- or even tens of thousands-of variables are involved, yet in many applications one cares about inference on only a small subset of variables. For instance, the Cancer Network Galaxy (TCNG) database hosts 768 networks encompassing over 20,000 genes and more than 16 million interactions. Typically, researchers only focus on disease-related or hub genes (genes with many interactions), which usually constitute a significantly smaller subset of the entire network. To draw inference and probability query for the target variables, it is both computationally expensive and wasteful to fit the full model and then marginalize obtain a target submodel.
Corresponding author: jhguo@ hthu.edu.cn
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

when GO is DAG
Our work
Algorithm complexity
sequential c* removable set [28]
CPDAG G*
O(VI))
Algorithm complexity
DSCS (O([V) + [E)))
sequential c- simplicial set
when G is UG
Algorithm complexity
simplicial set [23,25]
O + (=1)
Figure I: Criteria for verifying cetimatiinncollaasiiiii along with their worst-case computational complexities. Our proposed CPDAG-baset criterion, sequential e-simplicial sets, generalizes and Our algorithm, DSCS,
unifies previous criteria for DAGs [28] and undirected graphs (UGs) 23 25 achieves worst-case complexity of O(VVI + E=))
In such scenarios, we would like to "collapse" away irrelevant graph vertices (variables) and directly obtain an exact estimate of the submodel. This desideratum is captured by the notion of estimation- collapsibility, which ensures submodel's s direct estimation and inference aligns perfectly with that from the full-model, yielding drastic savings in data collection, computation, and robustness to unobserved variables [16-20] However, neglecting proper validation of the submodel's collapsibility risks misleading contradictory conclusions, exemplified by phenomena such as the Yule-Simpson paradox 21 222. Hence, identifying the precise conditions under which collapsibility holds is pivotal for trustworthy statistical inference with submodels.
Most existing works addressing collapsibility focused on undirected graphical models [e.g.. 23/26),
while the literature for Bayesian networks (or DAG models) remains notably limited [27 28 Despite its theoretical and practical significance,
in Bayesian networks remains as substantial challenges that are far from fully resolved. In particular, existing DAG-based criterion, sequential c-removability 28 can be computationally intensive verify. requires multiple laborious rounds of vertex examination, repeatedly identifying and removing c-removable vertices until none remain. The complexity can escalate up to O(IVi*), making the algorithm impractical for high-dimensional Bayesian network with a large cardinality [V] for its vertex set V.
Moreover, existing works [27 28 assume the DAG structure is known, which rarely true in practical scenarios. Typically, the underlying DAG must be inferred from observational data using causal discovery methods 31 & 36) Lacking strong assumptions like linearity
33 or
additive noise [7], causal discovery process usually yields a Markov equivalence class, which is succinctly represented by completed partially directed acyclic graph (CPDAG) (29 38
44.. Consequently, a pressing open problem emerges.
How can we efficiently verify estimation collaassiityy directly on the CPDAG for a high-dimensional Bayesian network?
To address this challenge, the current work presents the following novel contributions:
In Section 3.1
we introduce a novel concept, sequential c-simplicial sets, and find it as a necessary-and--ufficee criterion for estimation-collaassiiltt based CPDAG.
As shown in Figure [ our framework recovers and unifies prior collapsibility results for DAGs and undirected graphs (UGs). When CPDAG G" only has directed edges, sequential c-simplicial set reduces to sequential c-removable set of [28). When G only contains undirected edges, sequential c-simplicial criterion is equivalent to the simplicial
criterion for undirected graphs 23 25
we develop the Detecting Sequential C-simplicial Sets (DSCS) algorithm, for rapid verification of estimation colattiinnollllsiiilii..... It achieves complexity order ([V++ [F*1), where [V] and | denote the number of vertices and edges in CPDAG G", respectivell.
In Section 3.2

---

Extensive experiments have been conducted in Section practical effectivvness and computational efficiency.
4 to demonstrate our method's
Lastly, we emphasize that while our method addresses typical scenarios where the underlying DAG is unknown, the DSCS Algorithm also offers significant advantages when the DAG is explicitly available. Indeed, verifying estimation petpaaiioonoollsibiliiy.i is substantially simpler with our CPDAG- -aasee criterion. Given a known DAG G. converting it into its CPDAG representation G and applying our DSCS Algorithm enables efficient verification at significantly reduced computational cost.
Preliminaries and Related Works
We begin by providing a review of graphical model concepts in Section 2.1 More terminologies and
notations can found in Appendix A The notion of estimation-collapsibiity for Bayesian networks
is formally defined in Section 2.2 In Section 2.3 we review the existing criteria for checking
collappiiit.lllllilliitttt..... as summarized in the right panel of Figure
2.1 Graphical terminologies
A graph G = EV is defined by set V of nodes (or vertices), and set E' consisting of directed and (or) undirected edges. We use pAg(A), (A), ueg(A), (A), deg and mbç(A) to denote the union of the parents, children, neighbors, ancestors, descendants, and the Markov boundary of each vertex in a set A S V in G. respectively, and with the set A excluded after taking the set union. Note that, among these, neg (A) defined with respect undirected edges, while the other five notions are defined in terms of directed edges. Formal definitions can be found in Appendix [A] If A needs to be included, we simply capitalize the first letter of the corresponding symbol, e.g.. (A) (Ag U.A.
UGs, DAGs, CPDAGs. g consists solely of undirected edges, is referred to as an undirected graph (UG), denoted as G = E). When & is composed entirely of directed edges and contains no directed cycles, it is referred to directed acyclic graph (DAG), denoted Ō = (V, F). A DAG encodes set of conditional independence relations based on the notion of d-separation II. Two DAGS are Markov equivalent if they encode the same set of conditional independence relations. A Markov equivalence class of a DAG G can be uniquely represented by a completed partially directed acyclic graph (CPDAG) (4). denoted by G = (V, E*). The undirected components of G are undirected and connected chordal graphs (UCCGs) 46 also known as chain components of G"
7 46).
We use M(G)) ) to denote the set of all Markov equivalent DAGs represented by the CPDAG
G*.
2.2 Bayesian network and estimatiin-collapsiibiie
For a DAG T = (V, E). suppose Xv is random vector indexed by the graph vertices. For A(C V). let XA be the sub-veetor indexed by the subset A. A joint distribution P over Xy is compatible with G if it holds that P (xv)= II P(x., (r))(()) for any xV- This means that P factorizes according
to the parents of each vertex in G. The family of distributions compatible with G is denoted as P(G) and the pair B P(G)) is termed Bayesian network (BN) DAG model.
For a BN, cssiiaaton-colllappiiittt can formally defined via the commutativity of model fitting and marginalization [47] Let R(S V) be the subset of nodes of interests, and let M & V R represent the non-irrelevant variables we want to marginalize out. Denote P(æR) as the estimate of P(*R) obtained by marginalizing the maximum likelihood estimate (MLE) P(r) under the full DAG model (G. P(G)). Meanwhile, let (G P(GR)) be the induced model, where the graph G is obtained by removing the vertex set M and all edges incident to any vertex in M. We let Pa (Fx) be the MLE of the joint probability under the induced model (GR. P(GR)) Estimation- collapsibility means that the MLE obtained from the original DAG model, after marginalization, equals the MLE from the induced DAG model.
Definition 1. (see 27 Definition 1] Suppose =GG, (G)) Bayesian network, P(G) is estimation-coollassible over single vertex v (or onto V {8) for any zV it holds that
3

---

204
SAN
AIS
FTM
Yodk
20C
APA
ALN
(a)
(b)
(c)
Figure 2: A DAG from [49] depicting the assumed causal relations between 12 prodromal symptoms
of schizophrenia. Fig. a) shows the causal DAG, and Fig. b2 displays the corresponding CPDAG.
Fig. e) presents the largest chain componeni in the CPDAG. The nodes represent: AFF= Affective
Flattening, AIS= Active Isolation, ALN = Alienation, APA= Apathy, CDR= Cognitive Derailment, DET= Delusional Thinking. EGC= Egocentrism, FTW= Living in Fantasy World, HOS= Hostility,
PER= Perceptual Aberrations. SAN= Social Anxiety, SUS= Suspiciousness.
P(ov(o)) = Porm, (ZV Estimation-collapsibitty over a set M (or onto R 2 V holds if P(xR) PG (xR).
When this estimation-collapsibilii property holds, only need to work with the induced sub-model (GR, P(GR)) to directly obtain the estimate P(IR). The obvious benefit is substantial saving of data collection and computational efforts while maintaining exact estimate and inference for nigh-dimensional Bayesian network.
2.3 Existing criteria for checking estimatiin-collapsiiilli
2.3.1 Criterion for DAG. Kim & Kim discussed estimate-collapsiillity for directed acyelic graph (DAG) models of contingency tables 48 Xie & Geng (28 further investigated for discrete and continuous variable DAG models, and introduced the important concepts below.
Definition 2. [see 28 Definition 3] A veriex v is c-removable from DAG G if any two vertices in Mba(v) (v) U Umba(v) are adjacent, except when both vertices belong to pag(v). A set M is sequentially c-removable if all vertices in M can be ordered such that they can be c-removed by that ordering.
Furthermore, relying on the mild assumption of model non-triviality [see 28 Definition 4]-a condition satisfied by most DAG models, including those for contingency tables and Gaussian distributions [28] and implicitly used by [27]- they established the equivalence between sequential for DAG models.
c-removability and essimation-collapsibiin
Proposition 1. (see 28 Theorem 2] Suppose that B (G)())) is non-trivial DAG model, then M is sequentially c-removable from G if and only if) is estimate-collapsibbe over M.
The above theorem enables us to check estimation-colle collpiiiiiolllsibiliity via examining the sequential c- removability. The next example illustrates this procedure.
a). a). Suppose model estimate collapsible over M {AFF, APA, SAN}. Checking sequential c-removability requires multiple roundy of iterations. In the first round, we find that neither AFF nor SAN is c-removable from G, but APA is c-removable. After removing APA, the second round is repeated by examining if any node {AFF, SAN} is c-removable from GVAAAPA-- Upon checking, we find that no vertex in {AFF, SAN) is further c-removable. The procedure stops by concluding that the model is not estimate collapsible over M.
Example 1. Consider the DAG in Figure
interested in finding whether the
The above procedure quickly becomes infeasible as the graph size grows. Given subset M with cardinality [M], it requires O([M) iterations of meticulous vertex search. In each round, one must

---

scan the remaining vertices in M to identify the c-removable ones and then remove them. In the worst case case-when the graph dense and |M is on the same order as | the first iteration alone costs O((V1),, the next O((VV 1)9), and so on, leading to a total complexity on the order of O(IV)').
2.3.2 Criterion for UG. As our criterion also recover those for undirected graph (UG), we conclude this section by briefly reviewing some important results.
Definition 3. [see 50) In an undirected graph (UG) G = E), for a vertex v E V, if the neighborhood neg(v) (v) induces a complete subgraph in G. then v is called simplicial vertex in G. For a subset M C V, if the neighborhood nea(M) induces a complete subgraph in G. then M is called a simplicial (vertex) set in G.
For multinomial and Gaussian undirected graphical models, the collapsibility over M is equivalent to the condition that each connected component of M is simplicial set [23 25 The complexity of checking this simplicial property is O(VI+ + [E))
3 Fast CPDAG-Based Verification of EesiiattionColllasibbe
We now address the main query of the current work: how can we efficiently check estimation- collapsibility for high-dimensional Bayesian Networks using CPDAGs? In Section 3.1 we will establish an equivalent characterization of estimation-collapsiiiii from the perspective of CPDAGs. In Section 3.2 we develop an efficient and scalable algorithm to check the estimation-collassiiitty
3.1 Sequential c-simplicial set
For Bayesian network (BN), checking estimation-collapsiiiti of the underlying DAG via the corresponding CPDAG G* is possible, as this property is consistent across all DAGs within the equivalence class M(G*). In fact, for two Markov-equivalenn DAGs G1 and G2 in M(G"), they encode the same set of conditional independence relations, ensuring that the families of distributions they encode are identical, i.e., P(C,) = P(G2). Similarly, for Markov-equivatee corresponding families of distributions are also identical. Therefore, when estimation-colle collapsibility holds for the underlying DAG, the property is preserved across all its Markov equivalent DAGs.
subgraphs, the
Building on this consistency, we re-state estimation-collapiibiin tive of CPDAG. The definition below formalizes this extension based the family of distributions compatible with a CPDAG. For a CPDAG G = (V, E*), a joint distribution P over Xy is said to be compatible with G* if it is compatible with DAG & in M(G*). The set of all such distributions is denoted as P(G").
(see Definition] T from the perspec-
Definition& 4. For CPDAG G EV) and some M C V, P(G*) is estimationn-olllpstbbl over the set M for every DAG G E M(G)), P[ is estimation-collapsiie over the set M.
is evident that, to examine the estimation-collapsibitn for the underlying DAG model, we only need check the estimation-collapsiii collapsibblity from CPDAG. Analogous sequential c-removability in DAGs, we introduce the concept of a sequential c-simplicial (vertex) set for CPDAGs, which proves to be key for addressing the problem.
Definition 5. Given CPDAG G = (V, for vertex V, if cha- (v) = 0 and neg- (v) is complete, then v is called a c-simplicial vertex in G Similarly, for M C Vf every vertex in M can be identified as e-simplicial vertex during successive removals according some vertex order, then M is called a sequential c-simplicial (vertex) set G*.
Remark 1. The set chg- (v) consists of nodes pointed to by directed edges from node i.e. chg- (v) = {w E V {v) > w in G*), }. while neg- (v) refers to the set of nodes adjacent to v via undirected edges, ie., ncg- (v) {w E V {u}
in G*).
Example 2. Consider the CPDAG in Figure [b. Since cha (APA) = @ and its neigh- bor set neg- (APA) = {AFF, ALN, SAN) is complete, the node APA is c-simplicial ver- tex in G*. Similarly, HOS is also a e-simplicial vertex in G The subset of nodes M a {AIS, SUS, FTW, DET, HOS, EGC} forms sequential c-simplicial vertex set in G", M can be identified as a o-simplicial vertex during successive removals according to the vertex order DET, HOS, EGC, FTW, SUS, AIS.
5

---

The concept of a c-simplicial vertex in a CPDAG generalizes the notion of a leaf node (i.e., node with an empty set of children) in DAGs and simplicial vertex (i.e., a node whose set of neighbors is complete) [50] in undirected graphs. In particular, when G is DAG, v is a c-simplicial verter if and only if u is a leaf node. This is because when G* DAG, it naturally holds that neg-(1) = 0. making the completeness of its neighbor trivially satisfied, and the only condition required is che- (v) = 0. Meanwhile, when G is an undirected graph, e being a e-simplicial vertex in the CPDAG is equivalent to being simplicial vertex in the undirected graph G", In this case, ch (v) = 0 always holds, and the sole requirement is that neg. (v) forms a complete subgraph. The "c" in e-simplicial stands for compound, the e-simplicial property (CPDAG) combines the features of a simplicial set (undirected graph) and a leaf set (DAG).
The notion of sequential e-simplicial set likewise generalizes sequential c-removable set for DAG. When G" is a DAG and M is a sequential e-simplicial set, it directly follows from the previous discussion that M is also sequentially c-removable.
Furthermore, we can find the concept of sequential c-simplicial set generalizes that of simplicial set for undirected graph. When G contains only undirected edges (i.e. G* is a chordal graph), recall a c-simplicial vertex reduces
simplicial vertex. This means that, for a sequential e-simplicial M, its vertices can be ordered such that each vertex is a simplicial vertex at the time of its removal. Consequently, in a chordal graph G, we also term a sequential c-simplicial set M as a sequential simplicial set. Lemma] I indicates that sequential simplicity (or sequential c-simplicity) is equivalent to simplicity for chordal graph.
Lemma 1. For a chordal graph G = (V, E), given a connected subset M C V, M forms a sequential simplicial set in G if and only if M is a simplicial set in G.
Remark 2. In a chordal graph G, if M is disconnected, its connected components can be analyzed independently. Then, M is sequential simplicial set in G if and only if each connected component of M is a simplicial set in G.
Remark 3. Lemma 7 connects the classical concept of simplicial set [50) and our concept of sequential simplicial set for a chordal graph. The correctness of Lemmal ! follows directly from Proposition B. in Appendix [ For general undirected graphs, the relationship between the two concepts is also discussed in detail in Appendix ( Table C. in Appendix consolidates the key concepts of simplicial, c-removable, and c-simplicial vertices and sets across UGs, DAGs, and CPDAGs to facilitate comparison and reference.
Example 3. Consider Figure 2 2(c), which we denote as G Tmaa' Clearly, Gimas is a chordal graph. Now, consider the subset M {ATS, CDR, SAN]. M is a simplicial set in G because neG; mus (M) = {AFF, APA, ALN} is complete. Additionally, M forms a sequential simplicial vertex set in G Gimax. according to the vertex order CDR, AIS, SAN.
M can be identified as simplicial vertex during successive removals
The preceding discussion underscores the profound connection between estimation-collapsiiiii and our notion of sequential c-simplicity in two classical situations. When the CPDAG is a DAG, if M is sequential e-simplicial (hence sequential c-removable), then P(G is estimate-collapssblle over the set M under the non-trivial model assumption (28) Definition 4]. Meanwhile, when the CPDAG is a undirected chordal graph, if M is sequential c-simplicial (hence each componnent is simplicial), then the estimate-coll collaatte-clllasiblliiiy also holds in multinomial and Gaussian undirected graphical models 23 (25) These relations are summarized in Figure I and lead us to the question: beyond these two special cases, can we establish a connection between estimation estimation-collapiibbiii collapsibiiiit and sequential c-simplicity for a CPDAG in general? Theorem [ below provides an affirmative answer.
Theorem 1. Given CPDAG G (V, E"), let M(G") denote the set of all Markov equivalent DAGs represented by the CPDAG G*. For M V. the following four statements are equivalent:
(1) M is a sequential c-simplicial set in G*;
(2) there exists a DAG G M(G") such that cha(M) = =0;
for all DAGs G E MMG)), M is sequentially c-removable from G:
(4) under the non-trivial model assumption. P(G)) is estimate collaptecollapsible over the set M.
Theorem T establishes the connection between estimation-collapsiiii sets. It clearly shows that our notion of a e-simplicial set naturally extends to the broader framework of CPDAG models, including DAGs and undirected chordal graphs special cases. Specifically,
and sequential c-simplicial

---

under the non- con-trivial model assumption 228 Definition 41, it can be employed to verify estimation- collapsibility for nigh-dimessiona Bayesian network. The proof of Theorem is in Appendix D
3.2
DSCS: fast CPDAG-based verification of estimation-collassiiittt
Although Theorem D establishes CPDAG-based criterion for checking estimation-collassiiliii directly determining a subset M is sequential e-simplicial remains challenging. This is because multiple iterations are still needed to search for the e-simplicial vertices, which is a daunting task. Fortunately, for a CPDAG, we can find an equivalent characterization of sequential e-simplicity, which does not involve vertex order and eliminates the requirement of multiple algorithm iterations.
Remark 4. To highlight the essential concepts and intuitions, the following discussion focuses on the case where M connected. For disconnected M, the conclusion can be easily generalized as each connected component can be considered separately. In the Appendix, the theoretical derivations are developed for the general case where M has several connected components.
First, we establish necessary condition for M to be sequential e-simplicial set.
Lemma 2. Suppose G = EV) is CPDAG. For any M S V. M is sequential e-simplicial set in G*, then it holds that cha- (M) 0.
If cha- (M) * 0. then by Lemma 2 it follows directly that M is not sequential c-simplicial set in G*, thereby avoiding further effort for verification. However, the condition cha- (M) = @ alone does is not sufficient ensure that M is a sequential c-simplicial set. Consider the CPDAG in Figure for example, and let M = {AFF, SAN). Although chg (M) = 0. neither AFF nor SAN is a c-simplicial vertex in G It follows that M is not a sequential e-simplicial set in G*.
In addition to requiring che- (M) 0, additional conditions must imposed for sequential c- simplicity to hold. We start by examining a special case where M is contained within single chain component, and provide an equivalent characterization of its sequential c-simplicial property.
CPDAG with its chain components denoted by T {TI. T2....... ]. For connected subset M VV there exists i E [K] such that M C Tú then the following two statements are equivalent:
Lemma 3. Suppose GH (V,
(1) M is sequential c-simplicial set in G*;
(2) cha- (M) 0 and M is a simplicial set in meaning that nec; forms a complete subgraph.
Remark 5. For disconnected M, it is sufficient to impose the constraints separately on each of its connected components. In this case, statement (2) in Lemma 3 can be easily reformulated as follows:
(2') cha- (M) = 9, and each connected component of M is simplicial set in the subgraph G
We continue to consider the general case where a connected M is contained within multiple chain components of G Let T [TI, .2,..., .K be the set of chain components of G", and define as a mapping from T to {1, 2,... K} such that if there is a directed edge from Tę to Tj. then a(T)) < aTT)). This mapping Without loss of generality, assume a(T) < (T(2) < ... < (((TK). For M to be a sequential c-simplicial set in G*, in addition to requiring cha (M) = 0. it suffices that each M; & A n T; is a sequential simplicial set in G for all E [K]. By Lemma I this is equivalent to requiring each connected M, in G", forms a simplicial set. This is because we can always remove the sets in the reverse order MR, MM-1,".. ... M1. The specific conclusion is given by Theorem 2
called a topological ordering of the chain components in G*
Theorem Given CPDAG G (V,E*) with its chain component set T (TI, (TI,,T,..... T2. .T.....TKk..... T.K. for connected M CV, let M, & M n Ts for each i E [K]. The following two statements are equivalent: (1) M is a sequential c-simplicial set in G*;
(2) chg (M) 0. and M, in G being a simplicial set for all i [K].
Remark 6. For disconnected M, statement (2) in Theorem 2 naturally extends to:
(2') cha- (M) 0, and each connected component of M, in G being a simplicial set for all i [K].
7

---

Algorithm 1: DSCS Algorithm
Input :A CPDAG G" (V, F*), M MCV.
Output: :If M is a sequential c-simplicial set in G", the algorithm returns TRUE; otherwise, the algorithm returns FALSE.
if chcc (M) # 1 then
return FALSE;
Search for the set of chain components of G and denote them {Ti, T2, ". ,
for i 1--11 1 to K do in parallel
M. C * 0 then
Search for the connected components of M n and denote them as
M2.... M2, for j <- to 1, do in parallel
.M
if neG: (M,) is not complete then
return FALSE;
return TRUE.
The significance of Theorem is that it provides order-free way to check sequential c-simplicity. Recall from Section 3.1 that sequential c-simplicity for CPDAG implies estimation-collapite for the underlying DAG model. Therefore, Theorem 2 provides convenient avenue determine the estimation-collapsiiitty The proof of Theorem can be found in Appendix D
Building Thcorem 2 we introduce the Detecting Sequential C-simplicial Set (DSCS) algorithm in Algorithm ! The algorithm proceeds in two steps. the first step (Lines 1-2). we check whether che. (M) is empty; if not,
immediately conclude that M is not sequential c-simplicial set in G" If chg. (M) is empty, we proceed to the second step (Lines 3-19). For each chain component and each connected component Mi, of M within Ti, examine whether its neighboring nodes of Mi form a complete subgraph. Note that these checks are independent across chain components in parallel. The next example illustrates the execution of the algorithm.
Example 4. Let us re-examine Example 7 and recall we are interested in checking estimate- collapsibiläty with M {AFF, APA, SAN). Our DSCS algorithm works with the CPDAG in Figure 2 b). The CPDAG has chain components T = {AFF, OPFFAAD APA, ALN, SAN, PER, CDR, ATS), TO (UU), T3 (FTW), 74 (FGG)) TB (HOS), and T6 (DET). DSCS starts by checking if cha-((M) = which is clearly true. Next, it checks whether each connected component of M n in for 1, 6 is simplicial set. From Figure F it is evident that M C Tı so only the connected components of M in G*,, need to be checked for being simplicial. Since M is connected in G and neg:, (M) = {ALN, AIS, CDR} is not complete, we conclude the underlying DAG model is not estimate over M.
The complexity of DSCS Algorithm is O + (E7)), where [V| and |E* denote the number of vertices and edges in G", respectively. While operations such as identifying the children subset ch (M), detecting connected components in M, and analyzing their neighborhoods have relatively low complexity, the chain component decomposition
G*, requiring O(VV [E*)), constitutes the primary bottleneck. Following reviewer feedback. we use the maximum cardinality search (MCS) algorithm 511 - which identifies all maximal cliques in a chordal graph and finds a perfect elimination ordering in linear time perform parallel verification of whether each neighborhood forms a clique across all chain components. This done by checking whether the neighborhood subset of the maximal clique associated with the node (within that neighborhood) that appears earliest in the elimination ordering. Consequently, the complexity of Line 8 in the DSCS algorithm is [), where |maael is the number of vertices the largest chain component Tmax. and [E* is the number of edges in this component. Thus, the overall complexity of the DSCS algorithm is O(VV [=")).
O(1 Tmaz| + +1*

---

p-o (00.1
pno (RDSCS)
proasDOR)
p.0.110CR))
p-o.atsjocrt
10000
n=500
1000
n=1500
100
1000
100
10
Average running time
10-
0.1
0.1
0.08
0.05
0.1
90
100
150
200
300
350
400
450
100
300
500
700
800
900
300
600
750
1050 1200 1950
Figure 3: The average running time of DSCS (solid curves) versus DCR (dash-dotted curves) for different values of n = [V]. and JM. The y-axis (average running time in seconds) is in logarithmic scale, and the x-axis represents JM The three panels correspond different values of n.
Simulation
Through numerical experiments, examine the performance of the proposed DSCS Algorithm in Algorithm [ Our algorithm is compared to the approach of directly detecting sequential removability M, as proposed by (28). The latter approach abbreviated as DCR. The experiments were implemented with R and run on a computer with 2.20GHz CPU and 256 GB memory.
In the experiments, Erdös-Rényi graphs and the corresponding CPDAGs were obtained from the generated DAGs. We use n [V| to denote the number of graph vertices and p to represent the edge creation probability. In each simulation replicate, we randomly generate a DAG with E {500, 1000, 1500, 2000, 4000, 6000, 8000, 10000) 0.01,0.005) 0.005). and the vertex subset M was randomly selected from the graph with cardinality [M). DCR (or DSCS) then applied to the genrated DAGs (or corresponding CPDAGs) to check if the models are sstimate-collassbbe over M. For each combination n, p. and [M I the simulation was run 30 times. The average rumning time (in seconds) and the standard error were then calculated. Note that the proposed DSCS Algorithm can be run for each chain component of a CPDAG in parallel. In this experiment, only serial execution is implemented. Due the extremely long computational time of the DCR Algorithm for large graphs, we only compared the average running time of DSCS with DCR for n (500, 1000. 1500]. When n (2000, 4000, 6000, 8000, 10000), the running times for DSCS are reported in Appendix Moreover, to further highlight the advantages of the DSCS algorithm, we selected three real-world Bayesian networks from the R-package bnlearn WIN95PTS (76 nodes, 112 edges), LINK (724 nodes, 1 1125 edges), and MUNIN (1041 nodes, 1397 edges). A detailed description of the three Bayesian networks can found at hhttp:: : // //wwww bnlearn. com/ lbrrpoostoory randomly sampled a vertex subset .M of size [M| J, then applied DCR (on the DAGs) and DSCS (on the corresponding CPDAGs) to test collapsibility over M. The running times are also reported in Appendix B
randomly generated using the R- R-package pcalg 54
and p E 10.1, 0.05, 0.01,
For each network, we
For E (500, 1000, 1500), the average running times of the two algorithms are shown in Figure For different values of p, the corresponding curves are distinguished by color and point shape. Detailed results, including average running times and standard errors, are also provided in Table E. in Appendix E In Figure across various graph sizes E (500, 1000, 1500] and different values of p and |M], DSCS consistently outperforms DCR terms of runtime. For fixed n. the average running time of the DCR Algorithm increases rapidly with p and [M], while the DSCS Algorithm

---

exhibits much slower growth, demonstrating clear computational advantages. As n, p. and [M increase, the advantage of the DSCS Algorithm becomes more pronounced. For example, when = 500, = 0.1, and IM] 450, the proposed DSCS is more than 530 times faster than DCR. When n 1500, p = 0.1, and | 1350, DSCS achieves a speedup of more than 4000 times.
Conclusion
In this work, we have tackled fundamental bottleneck in high-dimensional Bayesian network inference: how to efficiently verify a submodel's estimation cooiaptioonolllasibblltyy and reliably collapse away irrelevant variables. Departing from the traditional DAG framework [ 281, show that one can directly work on a CPDAG learned from observational data. We introduce the concept of sequential e-simplicity and find criterion generalizes and unifies previous characterizations in both DAG models [28] and undirected chordal graph models [23 [25] Remarkably, based on CPDAG, we are able develop an order- free characterization (i.e. independent of the vertex permutation) and design an efficient Detecting Sequential C-simplicial Set (DSCS) algorithm. Beyond its theoretical value and computational efficiency, DSCS has profound practical consequences: it enables researchers to focus data-collection and computational effort on small subsets of interest to accelerate scientific discovery. We believe that incorporating collapsibility checks into researchers' preprocessing toolkit will significantly aid scalable probabilistic modeling, paving the way for robust and efficient inference ever-expanding data regimes.
necessary and sufficient criterion to check estimation-collapsiiite This
limitation of this work is that we require the CPDAG be accurately and fully learned from observational data. One could further relax the requirement of a fully accurate CPDAG by developing incremental local CPDAG-learning strategies that suffice for collapsibility checks. Another direction is to extend DSCS to accommodate interventional data or dynamic Bayesian networks, broadening its applicability to sequential and adaptive decision-mant makiin..
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers and area chair for their insightful comments, which helped strengthen this paper. This work was partially supported by the Key Program of the National Natural Science Foundation China (Grant No. 1e111124999 and the National Key Research and Development Program of China (Grant No. N0.2220YFAOTT 11000, Grant No. 20000T000044000 The first two authors contribute equally. Shiyuan He was partially supported by the National Natural Science Foundation of China (Grant Numbers 2271.78).
References
[1] Norman Fenton and Martin Neil. Risk Assessment and Decision Analysis with Bayesian Networks. CRC Press, 2018.
[2] Baoping Cai, Yonghong Liu, Jinqiu Hu, Zengkai Liu, Shengnan Wu, and Renjie Ji. Bayesian Networks in Fault Diagnosis: Practice and Application. World Scientific, 2018
[3] Baoping Cai, Yonghong Liu, Zengkai Liu, Yuanjiang Chang, and Lei Jiang. Bayesian Networks for Reliability Engineering. Springer, 2020.
[4] Olivier Pourret, Patrick Na, Bruce Marcot, et al. Bayesian Networks: A Practical Guide to Applications. John Wiley & Sons, 2008
[5] Steffen L Lauritzen. Some modern applications of graphical models. In Peter J Green, Nils Lid Hjort, and Sylvia Richardson, editors, Highly Structured Stochastic Systems, Oxford Statistical Science Series, pages 13-32. Oxford University Press, 2003.
[6] Marloes Maathuis, Mathias Drton, Steffen Lauritzen, and Martin Wainwright. Handbook of Graphical Models. CRC Press, 2018.
[7] Steffen L Lauritzen and Thomas S Richardson. Chain graph models and their causal interpre- tations. Journal of the Royal Statistical Society: Series B (Methodological), 64(3):321-344 2002.
10

---

[8] Judea Pearl. Causal inference in statistics: An overview. Statistics Surveys, 3:96-146, 2009.
[9] Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search. MIT Press, 2001.
[10] Zongming Ma, Xianchao Xie, and Zhi Geng. Structural learning of chain graphs via decompo- sition. Journal of Machine Learning Research, 9(Dec):2847-288) -8800, 2008.
[11] Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Elsevier, 2014.
[12] Xianchao Xie, Zhi Geng, and Qiang Zhao. Decomposition of structural learning about directed acyelic graphs. Artificial Intelligence, 170(4-5):422 -29, 2006.
[13] Sourabh Balgi, Adel Daoud, Jose M Pena, Geoffrey T Wodtke, and Jesse Zhou. Deep learning with DAGs. Sociological Methods & Research, page 0049124125131929) 2024.
[14] Adrián Javaloy, Pablo Sánchez-Martin, and Isabel Valera. Causal normalizing flows: from theory to practice. Advances in Neural Information Processing Systems, 36:58833-58864 2023.
[15] Veronika Thost and Jie Chen. Directed acyclic graph neural networks. In International Conference on Learning Representations, 2021.
[16] Peter Bühlmann and Sara van de Geer. Statistics for High--Dimensioal Data: Methods, Theory and Applications. Springer Science & Business Media, 2011.
[17] Robert G Cowell, Philip Dawid, Steffen L Lauritzen, and David Spiegelhalter. Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks. Springer Science Business Media, 2007.
[18] Arthur Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1):1-22, 1977.
[19] David Heckerman. A tutorial on learning with Bayesian networks. In Michael I. Jordan, editor, Learning in Graphical Models, pages 301-354. Springer, 1998.
[20] Pradeep Ravikumar, Martin J Wainwright, and John D Lafferty. High-dimensional Ising model selection using él El-regularized logistic regression. The Annals of Statistics, 38(1):1277-1319 2010.
[21] E.H. Simpson. The interpretation of interaction in contingency tables. Journal of the Royal Statistical Society: Series B (Methodological), 13(2):238- 2411, 1951.
[22] G.U. Yule. Notes on the theory of association of attributes in statistics. Biometrika, 2(2): 121-134, 1903.
[23] Søren Asmussen and David Edwards. Collapsibility and response variables in contingency tables. Biometrika, 70(3):567-577 1983.
[24] David Madigan and Krzysztof Mosurski. An extension of the results of asmussen and edwards on collapsibility in contingency tables. Biometrika, 77(2):315-35 -199 1990.
[25] Morten Frydenberg. Marginalization and collapsibility in graphical interaction models. The Annals of Statissiiss pages 790-805, 1990.
[26] Vanessa Didelez and David Edwards. Collapsibility of graphical CG-regression models. Sean- dinavian journal of statistics, 31(5):535-551, 2004.
[27] Song-ho Kim and Seong-Ho Kim. A note on collapsibility in DAG models of contingency tables. Scandinavian Journal of Statistics, 33(3):575-590, 2006.
[28] Xianchao Xie and Zhi Geng. Collapsibility for directed acyclic graphs. Scandinavian Journal of Statistics, 36(2): 185-203, 2009. 2009.

---

[29] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 30N05):507-554, 2002.
[30] Diego Colombo, Marloes H Maathuis, et al. Order-independent constraint based causal structure learning. Journal of Machine Learning Research, 15(1):3741-378) 2014.
[31] Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. Advances Neural Information Processing Systems, 21, 2008
[32] Jonas Peters and Peter Bühlmann. Identifiability of Gaussian structural equation models with equal error variances. Biometrika, 101(1):219-22) 2014.
[33] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. linear non-Gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
[34] Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, (1)662277, 1991.
[35] Peter Spirtes, Clark Glymour, Richard Scheines, Stuart Kauffman, Valerio Aimale, and Frank Wimberly. Constructing Bayesian network models of gene expression networks from microarray data. 2000.
[36] Kun Zhang and Aapo Hyvärinen. On the identifiability of the post-nonlineat causal model. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 647-655, 2009.
[37] Jonas Peters, Joris M Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15(1):2009-2053, 2014.
[38] Tom Claassen and Tom Heskes. A logical characterization of constraint- based causal discovery. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, pages 135-144, 2011.
[39] Tom Claassen, Joris M Mooij, and Tom Heskes. Learning sparse causal models is not NP-hard. In Proceedings of the Twenty-Ninhh Conference on Uncertainty in Artificial Intelligence, pages 172-181, 2013.
[40] David Heckerman, Dan Geiger, and David M Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Machine Learning. 20(3):197-243, 1995.
[41] Thomas Verma and Judea Pearl. Equivalence and synthesis causal models. Proceedings of the Sixth Annual Conference Uncertainty in Artificial Intelligence, pages 255-270, 1990.
[42] Thomas Verma and Judea Pearl. An algorithm for deciding if a set of observed independencies has causal explanation. In Uncertainty in Artificial Intelligence, pages 323-330. Elsevier, 1992.
[43] Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. DAGS with no tears: Continuous optimization for structure learning. Advances in Neural Information Processing Systems, 31, 2018
[44] Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal discovery with reinforcement learning. arXiv preprint arXiv: 1906.0990. 2019.
[45] Christopher Meek. Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh Conference Uncertainty in Artificial Intelligence, pages 403-410, 1995.
[46] Steen A. Andersson, David Madigan, and Michael D. Perlman. A characterization of Markov equivalence classes for acyclic digraphs. The Annals of Statistics, 25(2):505-541, 1997.
[47] Joe Whittaker. Graphical Models in Applied Multivariate Statistics. Wiley Publishing, 2009.
12

---

[48] Steffen L Lauritzen. Graphical Models, volume 17. Clarendon Press, 1996.
[49] D. van Kampen. The SSQ model of schizophrenic prodromal unfolding revised: An analysis of its causal chains based on the language of directed graphs. European Psychiatry, 29(7):
437-448, 2014.
[50] Gabriel Andrew Dirac. On rigid circuit graphs. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, pages 71-76. Springer, 1961.
[51] Fănică Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of chordal graph. SIAM Journal on Computing. 1(2): 180-187, 1972.
[52] Donald J Rose, R Endre Tarjan, and George S Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on computing. 5(2):266-283, 1976.
[53] Robert Tarjan and Mihalis Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs. and selectively reduce acyelic hypergraphs. SIAM Journal on computing, 13(3))566-5777 1984.
[54] Markus Kalisch, Martin Mächler, Diego Colombo, Marloes H Maathuis, and Peter Bühlmann. Causal inference using graphical models with the R package pealg. Journal of Statistical Software, 47:1-26, 2012.
[55] Judea Pearl, Dan Geiger, and Thomas Verma. Conditional independence and its representations. Kybernetika, 25(7):33 44, 1989.
13

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide the supplemental material for codes in a zip file to ensure easy reproduction of all reported results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
ctaaps.cc/publcc//uee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Section for the detailed description simulating outcome and experi- mental details. In addition, provide the supplemental material for codes in zip file to ensure easy reproduction all reported results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: In Table E. and Table E.2
report the mean running time along with the standard error of the mean (SEM) computed over multiple independent runs. This provides statistically sound measure of the variability in timing results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Section we provide detailed description of the type of compute workers, memory, and execution time required for the simulation experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
All experiments are conducted on publicly available datasets.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In the second and third paragraphs of Section and Section we outline various potential applications of our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
All experiments are conducted on publicly available datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: In Section 4 provide references for the datasets and the simulation setups of the lata-gengg process.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
datasets.papersstt
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification: In Section we provide references for the datasets and the simulation setups of the data-generating process. addition, we provide the supplemental material for datasets and codes in zip file to ensure easy reproduction of all reported results.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We don't use a crowdsourcing service.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurips: hatt::///earrrpsscc//oooerrreee/ cc///oofeeeeeecs//22/////.. for what should or should not be described.
20

---

A Graph terminology
A graph g (V, E) is defined by a set V of nodes (or vertices), and set E consisting of both directed and undirected edges, There is at most one edge between any pair of nodes u and v. We use (u, v) u + v to denote a directed edge from u to u, and u v to represent an undirected edge connecting u and v. The nodes and are adjacent if there is an edge connecting them, which is denoted by u & v. Otherwise, u, V are nonadjacent and denoted by u º2 v. A path connecting and u in G. denoted by luv. is sequence of distinct vertices (co u. C1...... Cm-1 Cm = v)
1. The path fue is a directed path, denoted by luv. from and an undirected path if Cj Ci+1 for all i == 0, 1, ...... m - 1. Additionally, the path L. is a partially directed path from u to v if there are no edges of the form C: f G++11 for all 0, I,.... m A cycle is path from a vertex to itself. An undirected path from to along with the edge v u. forms an undirected cycle. A directed path from и to v, along with the edge v - u, forms a directed cycle. A partially directed cycle is formed by partially directed path from directed paths (cycles) and undirected paths (cycles) are partially directed paths (cycles).
such that G - C++1 for i 0, ....., m to v if C3 + G++1 for all .....
1,.......... 1..... m
v, together with the edge v + or u. We note that both
When u + U. u is referred to as the parent node of v. and is called the child node of u. If a neighbor node of u. For some u E V. let pag(u) denote the set of parent nodes of u, chg (u) the set of child nodes of u, and neg( the set of neighbor nodes of u. Specifically, these sets are defined as follows:
pag(u) = {w E V \ {u}: : w - in 9),
cha(u (u) = (w E V {u} = w in 9), neg - [w E V \ {u} u w in 9).
If ch = 0, then u is called leaf node in G. For subset A S V, the sets of its parents and children in G are, respectively, defined as
(Ay(A)
U pag(u) \ A, Cha(A) 2 uEA
U cha \ A. uEA
If (A) = 0, then A is called a leaf set in G. We define the Markoy boundary of u and A as mb3( (u) cha (u) pag(u) U ppg(chh {u) and mby(A) = U mbg(u) \ A.
uEA
For simplicity, we also define
Pag(u) (u) pag (u) U {u],
PAg(A) (Ag(A) U.A
Cha (u) ch U [u);
Cha (A) = cha(A) U A;
Neg (u) neg(u) U [m).
(A) nes U A;
Mbg (u) = mbg U fu].
(bg(A) = mbg(A)
If there exists directed path from u to in G, is referred as ancestor of and is called descendant of u. The set of ancestors of u in & is denoted as ang (u), and the set of descendants u in G is denoted as deg (u). Specifically, these sets defined as follows:
ang (u) = {ww w V \ [u} 3ww S }) deg(u) = {u E V (u]: 3 co..
{{
For subset A C V, the sets of its ancestors and descendants in G are defined as follows:
aA) A U ang(u) \ A, deg(A) A U dec(u) \A.
aEA
DEA
We also define
Ang(u) = ang (u) U fu],
Ang(A) = ang (A) (A) J A;
Deg(u) (u) des (u) U (u), Deg (A) = de A) U A.
If G consists solely of undirected edges, it is referred to as an undirected graph (UG). In contrast, if g composed entirely of directed edges and contains no directed cycles, it is referred to directed acyclic graph (DAG). Let G = (V, E) denote DAG, where V is the set of vertices and É is the set of directed edges in G. A path luv between u and e in G is said to be blocked by a set C of vertices if and only if one of the following holds:
21

---

(i) lae contains a chain x + + y or fork x + 2 such that the middle vertex 2 is in S (i.e.,
2 E S);
(+i) Lao contains a collider x - <- y such that the middle vertex e is not in S and no descendant of is in S (i.e., (e n 0).
If all paths between u and e are blocked by S in G, then u and u are d-separated by S in G, denoted as u IL v [G]. For disjoint subsets A, B, 5 _ V, if every path between any vertex a E A and any vertex b E B is blocked by S in G. then A and B are d-separated by S in G, denoted as A TL B|S [G]. The collection of all d-separation relations induced by G is denoted as
I(ā) = (A, : A B|STō] with pairwise disjoint subset B.
For two directed acyclic graphs (DAGs) G = (V, Ei) and G2 = (V, iTZ they said to be Markov equivalent, denoted as G1 ~ Gg. For three distinet vertices u, v, and w, if - +- and is not adjacent to in G, the triple (u, w, is referred as e-structure collided on w. The skeleton of G is an undirected graph resulted from turning every directed edge in G into an undirected edge. Pearl et al. (55) showed that two DAGs are equivalent if and only they share the same skeleton and the same u-structures. The Markov equivalence class of G, or simply an equivalence class, denoted by M(G), contains all DAGs that are equivalent to G. This equivalence class can be uniquely represented by a partially directed graph known as completely partially directed acyclic graph(CPDAG) [5].. Let G* = E*) denote a CPDAG, where V is the vertex set and E the set of directed and undirected edges of G We use M(G") ) to denote the set of all Markov equivalent DAGs represented by the CPDAG G It can be shown that the skeleton of a CPDAG G identical to the skeleton of every DAG in M(G"), ), and an edge is directed in CPDAG if and only if it is directed in every DAG in MMG") (55) As demonstrated by Andersson et al. [46]. G* is a chain graph composed of both directed and undirected edges, and contains neither directed cycles nor partially directed cycles with directed edges. Additionally, the undirected components of a CPDAG G* are undirected and connected chordal graphs. A chordal graph (also known as a triangulated graph) is undirected graph in which every cycle of length greater than three contains chord-thh that is, an edge connecting two non-consecutive vertices in the cycle. Equivalently, a graph is chordal if and only if it contains no induced cycles of length greater than three.
B Estimatton--ollapsibiii for UG models
For undirected graph models, estimation-collapsbiity has been characterized via simplicial set [50]. Asmussen & Edwards (23] and Frydenberg (25 established the equivalence between collapsibility over M and the condition that each connected component of M is a simplicial set, in the context of multinomial and Gaussian undirected graphical models. Below, we provide brief introduction to the core concept of simplicial (vertex) sets in UG [50). By drawing an analogy with the concept of sequentially c-removable sets in DAGs, we introduce the concept of sequential simplicial (vertex) sets in UG and explore its relationship with the concepts of simplicial (vertex) sets.
Definition B.1. (Dirac (50)) In an undirected graph (UG) G = (V, F.), for a vertex e E V, if the neighhorhood neg (v: forms complete subgraph in G, then is called simplicial vertex in G. For a subset M C V, if the neighborhood neg(M (M) forms a complete subgraph in G. then M is called a simplicial (vertex) set in G.
Similar to the concept of sequentially c-removable in DAG, we introduce the concept of sequen- tial simplicial (vertex) sets in an undirected graph. An illustration of the concept is provided in Example B.I
Definition B.2. In an undirected graph G = (V, for a subset M V. if all vertices in M can be ordered such that each vertex is a simplicial vertex according that ordering, meaning each vertex can be identified as simplicial vertex during successive removals, then M is called a sequential simplicial (vertex) set in G.
Example B.1. Consider the UGs in Figures B.l (a)-c), and let's denote the three graphs as G Go. and G3. respectively. For the G1, we have nec, (a) {b, c} where 6 G3 By the Definition B.1
22

---

(a)
(b)
(c)
Figure B.1; Simpliciality and sequential simpliciality.
is simplicial vertex in G1. After removing o, the resulting UG G2 has ncG, (c,d) with 23 d. As result, b is simplicial vertex in G2. Similarly, after removing node b, obtain the UG G3, where e is clearly a simplicial vertex G3. Therefore, the set {a, b, oj is a sequential simplicial set in original UG G1-
Note the classical concept of simplicial set and our proposed concept of sequential simplicial set are generally not equivalent. We illustrate this via Example B.2
(a)
(b)
Figure B.2: This example illustrates that the concepts of a simplicial set and a sequential simplicial set undirected graphs are not equivalent. Figure B.2 shows that when M {a, b). M is simplicial set but not sequential simplicial set. Figure B.2 b) shows that when M {aa, b). M is sequential simplicial set but not a simplicial set.
Example B.2. In Figure B.2 a), let M = (a,b). with neg(M) (c, and G. d which makes M simplicial set in G. However, neither a nor b is a simplicial vertex on its own, meaning that M is not sequential simplicial set. In Figure B.2 b), M {a, b), and both a and b are simplicial vertices in G, making M sequential simplicial set. However. nea(M) (c, f) where & d,
G f, and d & implying that M is not simplicial set in G.
Under additional conditions, we can establish the equivalence between simplicial sets and sequential simplicial sets for undirected graphs. In Figure B.2 a). it given that M {a, 63 is a simplicial set in G. but M is not sequential simplicial or b E is imposed, then M becomes sequential simplicial set. In the more general case, the additional condition required that (Nec(M) is chordal graph, as shown Lemma B.
However, if an additional condition such
Lemma B.1. Let G = (V, F.) is an undirected graph, for M CV, if M is simplicial set in G and (N) is a chordal graph, then is a sequential simplicial set G.
Proof. Here we consider using proof by contradiction to prove Lemma B.I Let M
{m1, M2, ... m. Suppose that for any ordering, there exists subsequence mi Mi+1." m7
where 1 < S < such that none of these vertices are simplicial vertices in the induced subgraph GR & ( .m--1)- This means that for all m, E (m,, M4+1, ,, the neighborhood neG (my) ) is not complete, i.e., there exist vertices x, y E neGA (my) such that x L y. There are three possible cases:
23

---

m
y
mj
y
mj
y
x
m
x
mi
V
M
M
M
(a)
(b)
(c)
Figure B.3: Three subgraphs of the UG. Figure B.3 a), Figure B.3
B.3 b), and Figure B.3 c) correspond
(ia), (ib), and (ii) case (2), respectively, the proof of Lemma B.1
Case (1). When 2,y M,
Since z, E neG (my) and x, y V. M, it follows that x, neg However, E y, which contradicts the fact that M is a simplicial set in G.
Case (2). When x or y is in {m, """1"""",0 ... \ {my), Without loss of generality, assume {m,, M,41, -1 .mx) {my} and y E A. Since x not
simplicial vertex in GR. there exists nega (2) such that & mj. (i) V \ M, let's consider whether and are adjacent:
(ia) If y & since y, E neg(M), this contradicts the fact that M is a simplicial set G: see Figure B.3 a).
(ib) If y G z, there exists a 4-cycle my x y - my, which contradicts the fact that GNea(M) is chordal graph; see Figure b.).
(1t) If 2 E [m, m,-1.-.. m& {m,. x) since 2 is also not simplicial vertex in GR. similar to the
case with x, we need to analyze the adjacency of z's neighbors. By applying this reasoning iteratively, we can construct maximal connected component containing my in the form my x
mi-1 my. For this maximal connected component, there must exist v E nec (m)) ( n (V M)
such that G m4-1 (otherwise, my would be simplicial vertex GR). This situation analogous to case (i). leading to contradiction; see Figure (.3
Case (3). When x, y (1m4, m,+1,-.. m {m,}), })
Since x and are also not simplicial vertices in GR and given the arbitrary choice of my. x and will encounter similar situations as in cases (1) and (2).
Given the hereditary property of chordal graphs, any subgraph of chordal graph is also a chordal graph. Therefore, for chordal graph G = (V, E), it is evident that GNea(M) is also chordal. Consequently, we have the following corollary.
Corollary B.1. Given a chordal graph G (V, E), for M C if is a simplicial set in G, then M is sequential simplicial set in G.
In Figure B. bb,, it is given that M = {a,b) b) is a sequential simplicial set. However, M is not simplicial set in G. Nonetheless, if M is sequential simplicial set and is connected, then M is simplicial set G.
Lemma B.2. Given an undirected graph G = E), M S a connected subset and M is sequential simplicial set in G, then M is simplicial set in G.
24

---

mg
1711
122
171
Mm+1
M
Figure B.4: A subgraph of the UG. It corresponds to case(2) in the proof of Lemma B.2
Proof. Here we consider using proof by contradiction to prove Lemma
B.2 Assume M is not
simplicial set in G, i.., there exist z, neg(M) such that 2 y. There possible cases:
Case (1). There exists m E M such that x, y E nea(m).
Since x and z, y E V M, m is not simplicial vertex in G for any ordering. This contradicts the assumption that M is sequential simplicial set in G.
Case (2). There exist mæ, my E M such that a E neg(m,) and y E nec(my).
Since my and my connected within M, there exists chordless path p (mo my, mi, m2, M,y, Ma+1 = my) where m. E M for i E [n]. Because is chordless, for each my (where E [n]), m4-1 and m4+1 not adjacent, meaning mi, "*..... Th are simplicial vertices. Since the vertices M can be ordered such that each vertex a simpli- cial vertex according that ordering, either my or my must be simplicial. Without loss of
generality, assume mr is simplicial vertex. Thus, G. my. Now consider the chordless path p' = (m1, m2, ... Mn, Ma+1 = my)) In this case, æ E neg(m1) and E nea(my). By similar analysis, iterating this process will lead the existence of some m' (m1, m2," mm) such that x, E neg(m'), which reduces to case (I); see Figure B.4
In both scenarios, we encounter contradictions. Therefore, the assumption that M is not a simplicial set in G must be false. Thus, if M is connected sequential simplicial set in G, then M must be simplicial set G.
By Lemma B.2
obtain sufficient condition for (Ne be chordal.
Lemma B.3. Given an undirected graph G (V, E), if M S connected subset and M is sequential simplicial set in G, then (Ne is chordal graph.
Proof. By Lemma B.2 we know that M is a simplicial set in G, which means neg(M) is a complete subgraph. Suppose (Ne is a chordal graph. For any cycle y in GNea(M) with length greater than 3, since neg is complete, I contain at most two vertices from neg neg(M). Otherwise, μ would have a chord. Without loss of generality, assume that μ contains two vertices x and from (M)) and the remaining vertices in M. Let m, be the first vertex removed from 14, then neg, (m²) is complete. Thus, yu must have at least one chord, i.e., there exists an edge connecting two neighbors of m, in μ.. This contradicts the assumption that μ a cycle of length greater than without chords. Therefore, GNeg(M) must be a chordal graph.
Based on the above series of lemmas, we can provide an equivalent characterization of sequential simplicial set in an undirected graph that does not depend on the order, stated in the following PropositiorB.I]
Proposition B.1. Given undirected graph G (V, E), for M C V, the following two stafements are equivalent:
(1) M is sequential simplicial set in G;
25

---

(2) For each connected component Cas of M, the subgraph GNec(Ess) is chordal graph, and CM is simplicial set G.
Proof. (1) (2). Since M is a sequential simplicial set in G. it is evident that M1, M2, Mr are also sequential simplicial sets in G. Therefore, for all à [K], the vertices in M, can be ordered such that each vertex is a simplicial vertex according to that ordering. Additionally, since M, is connected, by Lemma B.2.
M, is a simplicial set in G. By Lemma
B.3 (N,) is chordal graph.
(2) - (1). Given that for all E [K], GNe(M.) is chordal graph and M; is simplicial set in G, by Lemma B.I for all i E [ the vertices in M, can be ordered such that they are simplicial vertices in that order, i.e., M; is sequential simplicial set G. Furthermore, since M1, M2, Mx are mutually disconnected, they can be ordered in any sequence, and they will still form sequence of sequential simplicial sets. Therefore, M is a sequential simplicial set in G.
For chordal graphs, by hereditary property, any subgraph of a chordal graph is also a chordal graph. Proposition B.1 immediately implies Lemma for chordal graph. It states that chordal graph, for any connected subset, a sequential simplicial set is equivalent to simplicial set. Therefore, for chordal graph model, being estimation collappilll over M is equivalent each connected subset of M being sequential simplicial set.
C Summary of Key Concepts
To facilitate comparison and reference, this appendix consolidates the key concepts related to simplicial, o-removable, and c-simplicial vertices and sets across UG, DAG, and CPDAG graphical models. The detailed definitions are presented in Table C.I
Table C.I: Key Concepts in Graphical Models
Graph Type
Concept
Characterization
Simplicial vertex
vertex e is called simplicial if its neighborhood nec(e) forms complete subgraph in G.
UG
Simplicial set
A set M, neg induces a complete subgraph, then M is called simplicial set in G.
c-removable vertex
A vertex is e-removable from DAG & if any two vertices Mba(v) are adjacent, except when both belong to (v)
DAG
Sequentially c-removable set
A set M is sequentially c-removable if its vertices can be ordered such that each can be c-removed by that ordering.
c-simplicial vertex
A vertex v is e-simplicial in G* if cha (v) 0 and neg (v) is complete.
CPDAG
Sequential c-simplicial set
A set M is sequential c-simplicial in G* if its ver- tices can be successively removed as c-simplicial vertices in some order.
The concept of a c-simplicial vertex in a CPDAG generalizes the notion of a leaf node (i.c., a node with empty set of children) in DAGs and simplicial vertex (i.c., node whose set of neighbors is complete) [50] in undirected graphs. In particular, when G is a DAG, v is a c-simplicial vertex if and only if is leaf node. This is because when G* is DAG, it naturally holds that neg- (v) = 0. making the completeness of its neighbor trivially satisfied, and the only condition required is cha- (v) (6. Meanwhile, when G* is undirected graph, v being e-simplicial vertex in the CPDAG is equivalent to v being a simplicial vertex in the undirected graph G*. In this case, cha- (v) = 0 always holds, and the sole requirement is that neg- (v) forms a complete subgraph.
The notion of sequential c-simplicial set likewise generalizes sequential e-removable set for DAG. When G* is a DAG and M is a sequential c-simplicial set, it directly follows from the previous
26

---

discussion that M is also sequentially e-removable. Furthermore, we can find the concept of sequential c-simplicial set generalizes that of simplicial set for undirected graph. When G* contains only undirected edges (i.e. G* is chordal graph), recall a c-simplicial vertex reduces to simplicial vertex. This means that, for a sequential c-simplicial M, its vertices can be ordered such that each vertex is a simplicial vertex at the time of its removal. Consequently, in a chordal graph G, we also term a sequential c-simplicial set M as a sequential simplicial set. Lemma | Iindicates that sequential simplicity (or sequential c-simplicity) is equivalent to simplicity for chordal graph.
D Technical Proofs of The Main Results
Proof of Lemma
Proof. Assume that cha- (M) A 0, then 3m M such that cha (m) \ M + 0. In this case, regardless of how the vertices in M are ordered and sequentially removed as c-simplicial vertices, m can never be a c-simplicial vertex. Therefore, by Definition []] M is not sequential c-simplicial set in G", which contradicts the known result.
Proof of Lemma 3
Proof. By Lemma] 1 Statement (2') is equivalent to:
(2*) cha- (M)
0, and M is sequential simplicial set in G
We will now establish the equivalence between Statement (1) and Statement (2*).
(1)= Given that cha- (M) = clearly holds, we now need to prove that M is a sequential simplicial set in G Since M is contained within single chain component, and under the condition that cha- (M) 0, we have U ch (m) 0. Therefore, determining whether M is a sequential mEM
simplicial set in G is equivalent to determining whether M is sequential c-simplicial set in G*,
(1). Since cha- (M) = U cha (m) M = 0. and because M is contained within a single
mEM
chain component, we have U cha- (m) = 0. In this case, M is a sequential simplicial set in G mE
clearly equivalent to M a sequential c-simplicial set in G
Proof of Theorem
Proof. By Lemma] 1, Statement (2') is equivalent to:
(2*) cha- (M) = 0, where each Mj forms a sequential simplicial set in G., for all i E [K].
We will now establish the equivalence between Statement (1) and Statement (2*). (1) + (2*). chg. (M) 0 clearly holds. Next, we prove that for all i [K], M, sequential simplicial set in G
Without loss of generality, assume ((7)) < a(()) <... < a(TK). Assume there exists a largest sequential simplicial set in G Since M is sequential c-simplicial set in G", Mr is also sequential e-simplicial set in G Let G A GiiMa Then, it is evident that MK-1 is sequential c-simplicial set in G Let G GVMMX,MR-II Continuing this process, we deduce that M, is sequential e-simplicial set in Gk-j A GVV 1." ",.. By Lemma Mj must be a sequential simplicial set in G
j. where S j & K, such that the non-empty M, is
which contradicts our assumption.
(2") = (1). Without loss of generality, assume a(1) < a(T2) < ... < al (((T)) ). Given that cha- (Mk) = @ and Mr is a sequential simplicial set in Gi by Lemma 3 MM is sequential ciimpliiiill set in G Let Gj e Giy. Then, cha; (Mx-1)
sequential @ and MK-1 simplicial set in Gi.rk- By Lemma again, MK-1 is a sequential e-simplicial set in G Let
G e GVX Mx- Continuing this process, we find that Mx, Mx-1,*.. MM are sequential
27

---

e-simplicial sets. Therefore, the vertices in M can be ordered such that they are c-simplicial vertices in G", meaning M sequential c-simplicial in G
Proof of T'heorem
Proof. (1)=> (2). Assume (2) does not hold. That is, for all & E M(G)), ch) o D. Since G* is CPDAG, this implies that cha- (M) ) + 0 or there exists an undirected connected component C of M such that neg- (C) is not complete. By Theorem 2 M is not sequential c-simplicial set in G*, which contradicts (1).
(2)= (1). Let T = T2........ TK be the set chain components of G Partition M into each chain component, i.e., M = M1 U M2 U...U Mx. where M; T for each i [K]. Assume (1)
does not hold. By Theorem 2 there are two possible scenarios.
(i) cha- (M) * By the properties CPDAGs, for all G E M(G"), ch + 0, which contradicts (2).
(it) There exists j. where S S K, such that Mj is not a sequential simplicial set G Let M, = M,,1 U M, U...UU U M2J, where M2,3 (i E [4] are the connected components in G Since
M, is not sequential simplicial set in G and G is chordal graph, by Lemma T there exists i,where - i < I, such that Mj.; is not simplicial set G". That is, there exist x, y E neo,, (Mj.s
such that r E y. In every DAG & E M(G*), x and cannot both be parents of M,,s. otherwise v-structure would be formed. Therefore, cha(M,,) + 0. implying cha(MM 0, which contradicts (2).
(2) (3) (4). By 28 Lemma 1] and Theorem have (2) (3) (4) is evident.
28

---

E Additional Experimental Results
For the DSCS and DCR algorithms applied random graphs with E {500, 1000, 1500], the detailed average running times (in seconds) and the standard errors are presented in Table E.T DSCS clearly shows significant advantage over DCR, and this advantage becomes more pronounced as n and increase. Furthermore, from Table J.n Figure it can be observed that for given n and [M , the average running time of DCR increases rapidly with increasing p. whereas DSCS exhibits slower and approximately linear growth. Additionally, the standard errors of DSCS's average running times are consistently smaller than those the DCR Algorithm, indicating greater stability in DSCS's s running times across various random graphs
Due the extremely long computational time of the DCR Algorithm for large graphs, for n {2000, 4000, 6000, 8000, 10000), we only record the average running time of the DSCS Algorithm. The results are shown in Table E.2 and in Figure E. It can be seen that even for high-dimensional variables (e.g.. = 10000) and denser graphs (e.g.. determine the estimation ceoemaationcolllssibiiiiii of the underlying DAG model. For example, when 10000, p 0.1, and M = 9000, the average running time of the algorithm is just over 150 seconds. For given n and p, the average running time increases approximately linearly with JM].
0.1), the DSCS Algorithm can quickly
Based on these observations, can be concluded that the DSCS Algorithm is capable of efficiently addressing the structure dimensionality reduction problem for high-dimensional Bayesian network with complex structure. It should be noted that some of the standard errors are relatively large due to the inherent randomness in the generation of the graphs and the random selection of the set M. For certain node subsets M, after finding cha (M) * 0 during the initial check (as per Lines 1-2 in the DSCS Algorithm), the DSCS algorithm can immediately stop. leading a very fast determination of collapsibility. On the other hand, for some node subsets M with che- (M) = 0, further checks are required (as per Lines 9 in the DSCS Algorithm), resulting in longer algorithm's 's running times.
29

---

Table E.1: The comparison of our method (DSCS) and detecting sequential c-removability (DCR) on {500, 1000, 1500) in terms of average running time (in seconds) is shown below. The best result is bolded, and the values in parentheses represent the corresponding standard error of the mean.
p
P
p
[M]
DSCS
DCR
DSCS
DCR
DSCS
DCR
DSCS
DCR
50
0,037 (0.002)
6.782 (0.36R)
0.036 (0.002)
2,070 (0.108)
0,038 (0.002)
0.214 (0.017)
0.045.00.000
0.201 (0.017)
100
0.884 (0.012)
16.836 (0.591)
0.067 (0.003)
4.625 (0.219)
0,086 (0.003)
0.517 (0.023)
0.078 0.078.00003))
0.424 (0.015)
150
0.131
27.009 (0.918)
0.096
(8106)
0.127
0.673
200
0.164 (0:016)
40.370 (1.724)
(0.005)
(0.491)
(8.006)
1,205 (0/031)
0.170(00.055)
0.937 (0:023)
250
0.209 (0.018)
54,264 (2.469)
0,171 (0.006)
16.999 (0.608)
0.207 (0.011)
1,571 (0.045)
(0.00900.09)
1.231 (0:033)
300
0.260 (0.015)
75.285 (3.780)
0,200 (0.007)
21.460 (0.834)
0.246 (0.088
2.083 (0.042)
0.263 (0.008)
1.560 (0.012)
350
0.285 (0.025)
97.047 (4.818)
0.215
24. 24.446/00 (0.787)
0.277 (0.009)
2.624 (0.050)
(0.01))
1.798 (0:041)
0.320
119.086
2.015 (0.058)
450
0.318 (0:011)
170.61 (10.245)
(0.011).0)5)
47.666 (1.794)
(0.010)
3.631 (0.098)
0.414(0.010)
2.274 (0.057)
1000
0.05
0.005
[M]
D9CS
DCR
DSCS
DCR
DISC
DCR
DSCS
DCR
100
0.072 (0,003)
73,99 (4.399)
0,077 (0.006)
(3.503((1063)
0.068 (0 (0.003)
0.795 (0,040)
0.883 (0:011)
0.464 (0.021)
200
0.162 (0.022)
155.271 (8.17))
0.154 (0.009)
(2613)
0,163 (0.006)
1862 (0.089)
0.162 (0.009)
1.066 (0.001)
300
0.289 (0:015)
288, 892 (13.691)
0.331 (0.011)
124.566 (4.822)
0,247 (0,010)
3,099 (0.075)
0,253 (0.009)
1.80 (0.052)
400
0.317 (0.029)
417.435 (18.389)
0.327 (0.020)
211.005 (5.278)
0.297 (0.010)
4.915 (0.174)
0.307 (0.009)
2.499 (0.062)
500
0.413 (0.036)
536.017 (25.026)
0.307 (0.011)
264.001 (6.637)
I1.25 (0.017)
6.534 (0.175)
0.412 (0.004)
3.533 (0.005)
600
0.506 (0.042)
680.526 (24.354)
0.448 (0.013)
311,422 (10.226)
0,500 (0.015)
8:765 (0.259)
0.472 (0.011)
4.504 (0.117)
700
0.556 (0:034)
950.131 131 (34.481)
0.520 (0.010)
398.958 (12.231)
0.589 (0.010)
10.998 (0.280)
0.595 (0.015)
5.639 (0.121)
800
0,689 (0.040)
1117,812
0,618 (0.019)
$13.9972133.992)
0.633 (0.016)
13.038 (0.384)
0.675 (0.017)
6,856 (0.200)
(0.043)
2261 (110.833)
0.684 (0.022)
(23.449)
0.711 (0.018))
(0.317)
0.760 (0.019)
8,240 (0.222)
1500
0.1
0.05
0.01
0,005
[M]]
USCS
IXC
DSUS
DCR
DSCS
DXC
DSCS
DCR
(0.008)
(13.150)
(0,005)
(5.096)
0.157 (0.018)
(0.005)
568 (29
367
450
0.440 (0/03)
954.505 (48 468)
0,350 (0:012)
594.021 (25.087)
0.416
12.067 (0.295)
0,999
3:17 (0.024)
600
0,520 (0.033)
1332.058 (71.64))
0,483 (0.013)
$12.180 (52.477)
0.987 (0,000)
17.383 (0.454)
0.517 (0.011)
5.968 (0.178)
750
0.762 00.0253
903 (152,182)
0,619 (0.025)
1133.943
0.688 (0.015)
24.295 (0.741)
0.650 (0.01
8,123 (0.211)
900
1.133 (00054)
3520.613 (1800584)
0.748 (0.019)
1523,037 (62)56))
0.755 (0.022)
$2.174 (0.836)
0.786 (0.019)
10,266 (0.166)
(0.044)
4341.776 (286.208)
(0.004)
(106.079)
0.897 (0.021)
18.334
(0.024)
(0.241)
(0096))
(263.065)
(0.024)
(144.881)
49,565
(0.029)
(8.070(0.200)
2.015 (0.104)
$190.708 (452.034)
1.441 (0.050)
1.43
(1.412
30

---

Table E.2: The average running time (in seconds) of the DSCS
Algorithm for
{2000, 4000, 6000, 8000, 10000} is shown below. The values in parentheses represent the corre- sponding standard error of the mean.
2000
300
500
700
900
1100
1300
1500
1700
1900
0.1
0.224 (0.007)
0.467 (0.047)
0,711 (0.074)
0.941 (0,055)
1.254 (0.079)
1,476 (0.043)
1,578 (0.11)
2,786 (0.08))
2,6055 (0.086)
(0.008)
0.427 (0.045)
(0.038)
(0.03)
(0.044)
(0.047)
(0.073)
(0001)
0.01
0.198 (0.008)
0.333 (0.017)
0.483 (0.008)
0.627 (0.025)
0.804 (0.013)
0.907 (0.031)
1,235 (0.034)
1,342 (0.022)
1.542 (0.06))
0.005
0.193 (0.0013)
0.299 (0.012)
0.488 (0.008)
(1.588 (0A028)
0.884 (0.023)
0.968 (0.015)
1.144 (0.049)
1.335 (0.033)
1,526 (0.036)
4000
[M]]
600
1000
1400
1800
2200
2600
3000
3400
3300
0.1
2,067 (0.277)
3,649 (0.276)
(1.55())36))
9.545 (0-423)
11,170 (1,088
12.221 (0-468)
13:542 (0.558)
18.441 (0611)
18.644
0,05
2.445 (0.178)
(0L198)
8,525
10.378
13,006 (0.435)
0.785
(0.047)
3.167 (0.055)
3,722 (0.55)
5.020
5.185
(0.013)
(0.028) (0.019)
(0.028)
(0.038)
3,172
(0.046)
(0.045)
(0.033)
8000
[M]
700
1300
1900
2500
3100
3700
4300
4300
5500
0.1
(0.11)
13,099 (5.657)
18.291 (1.918)
16,860 (1
24.530 (1.61))
28101 (3856)
36.581 (1.203)
33,083 (0:916)
41.539 (0.76)
0.05
(0.599)
11,335 (0.769)
6.426.0
12,089 (1
11,453 (0,601)
(1.89)
21 (1.854((116))
26.738 (1.70)
33.046 (2.450)
0.01
12277 (0.05))
2.665 (0,095)
4.335 (0.255)
5.629 (0.191)
6.432 (0.275)
10.354
8,922
(0.35)
12:461 (0.491)
0.005
1,055 (0005))
2.188 (0.050)
3.153 (0.081)
3.847 (0.06))
4.351 (0.107)
5.235 (0009))
5,993
6.894
(.912(0.125)
1200
2000
7800
3600
4400
$200
6000
6500
7500
15.185 (L.81)
35.080 (6.570)
68.231 (2.654)
$1.077 (4.126)
64.551 (14.213)
62.069 (5.545)
89.554 (27.118))
145.404 (16.088)
179.517 (1...21)
(1.347))
(6.200(1.150)
(0.318)
30.605
38,041
0.005
3.077 (0.255)
5.765 (0.272)
4.979 (0.091)
6.070 (0.097)
9:415 (0.747)
11.517 (0.905)
13,395 (2.099)
13,895 (0.370)
15.199 (0.179)
6 10000
[M]]
2
5000
0.1
8.344 (1.851)
48.183 (24915)
47.575 (12.955)
48.310 (6-958)
790001 (21.997)
168.003 (50)873)
177.600 (59.726)
143.666/188399
157,696
(8.300)
(3.244)
61.835 (2,463)
75/421
(23,000)
(18.396)
(2.665)
(0:36))
7.108 10
12,375
14.324
21.120
29.326 (2,703)
30,7200
0.005
3.224 (0.255)
3,569 (8 (655
7.257 (L114)
11,486 03.161 (2.277(00.099)
(4,557
19.768 (0 349)
24.472 (0.270)
30.109
To further highlight the advantages the DSCS algorithm, we selected three networks from the R-package bnlearn -WNN5PTSS (76 nodes, 112 edges), LINK (724 nodes, 125 edges), and MUNIN (1041 nodes, 1397 edges). A detailed description of the three Bayesian networks can be found at hhtps:: ///www.wwa// bnlearn. com/ wwapm//brppssssoorr.... randomly sampled vertex subset M of size M. then applied DCR (on the DAGs) or DSCS (on the corresponding CPDAGs) to test estimate-collapsiiiitty over M. For every combination of network
Bayesian
For each network, we
31

---

p=0.1
p=0.05
p=0.01
p=0.005
n=2000
n=4000
Average running time
16-
12
0.5
500
960
1500
1700
1000
1400
1800
9400
700
1300
1900
2500
3100 [M]
3700
4500
4500
5500
[M]
Average running ttitee
200
n==000
240
1=10000
190
80
50-
1200
2000
2000
3600
4400
5200
6003
6500
7000
1000
2000
3000
4003
5009 [M]
5000
7000
3000
5000
[M]
Figure E.1: The average running time of the DSCS Algorithm for different and p function of MM.
and J.M. we ran 30 simulations and recorded the average running time (in seconds), as reported in the Table E.
Table E.3: Comparison of average running time (seconds) between DSCS and DCR methods on three real-world Bayesian networks (the best result bolded).
WIN95PTS: V
76,
E
112
M
5
13
21
29
37
45
53
61
69
DSCS
0.003
0.007
0.012
0.019
0.023
0.026
0.031
0.035
0.047
DCR
0.020
0.040
0.067
0.104
0.144
0.189
0.255
0.289
0.333
LINK: [V]
724,
[
1125
M
50
130
210
290
370
450
530
610
690
DSCS
0.027
0.072
0.114
0.168
0.238
0.343
0.442
0.596
0.660
DCR
0.141
0.449
0.830
1.359
2.199
3.253
4.425
6.147
7.024
MUNIN: [V]
1041,
1397
100
200
300
400
500
600
700
800
900
DSCS
0.058
0.108
0.182
0.260
0.383
0.511
0.710
0.742
0.983
DCR
0.333
0.771
1.588
2.822
4.168
6.762
9.260
11.954
15,420
Table E.3 demonstrates the decisive superiority of the proposed DSCS method over the DCR baseline in computational efficiency. Across all three real-world Bayesian networks, DSCS consistently achieves significantly lower running times for every tested size of the query set [M]. The performance
gap is particularly evident the largest network (MUNIN), where at [M| 900, DSCS completed
in under a second while DCR required over 15 seconds. These results robustly confirm that DSCS more efficient and scalable solution for determining estimation-collaasiiitty making highly suitable for application on high-dimensional Bayesian networks.
32


Reviews:
[{"review_id": "2mDATzrmAV", "reviewer": "Reviewer_Ha3g", "summary": "This paper tries to provide a unifying framework of estimation-collapsibility for CPDAG (completed partially directed acyclic graph), DAG (directed acyclic graph) and UG (undirected graph). Estimation-collapsibility refers to the ability to remove a set of variables from the graphs while preserving the structure of the rest. The authors achieve this by focusing on CPDAG, which is an Markov equivalent class of DAG, with connections to UG.\n\nFollowing prior works, they give an equivalence relation between estimation-collapsibility and $c$-simplicial, a new notion proposed in this paper, under the non-trivial CPDAG assumption. On top of this equivalence result, this paper also gives a more efficient algorithm for detecting estimation-collapasibility via $c$-simplicial that improves the time complexity from $O(|V|^4)$ to $O(|V|^2)$.", "questions": "Question.\n1. On Line 196, the authors mention $\\textbf{ne}_{G^*}(v) = \\emptyset$, I don’t see why this is true, unless you define the neighbors as the ones connected via *undirected* edges. There’s no formal definition of neighbors other than on Line 89 (which had no formal definition on the main text). To avoid confusion, I think it's best to make a note mentioning the distinction between neighbors v.s. parents and children -- that they are disjoint.\n2. Does the $c$ in $c$-simplicial stands for conditional? I think it would be helpful to point out the meaning: easier to understand what's the difference between $c$-simplicial (CPDAG) and simplicial (undirected graph).\n3. Why does the definition of $c$-simplicial (for CPDAG) seem so different from the counterpart on DAG? Intuitively, do we not expect that DAG would be reduced back to CPDAG (viewing DAG as a subset of CPDAG, or simply transforming DAG into its CPDAG)? I notice the discussion on Line 200-202: it only describes reduction from CPDAG to DAG but not the only way around. Maybe it is obvious to the authors, but I don't quite see how to convert $c$-removable to $c$-simplicial (worth writing a bit more on this). Are they incompatible?\n   For example, consider the node $v$ in DAG: $v \\rightarrow a \\leftarrow b$. $v$'s $\\mathbf{Mb}_{G}(v)$ is $a$ and $b$. They ($a$ and $b$) are adjacent and does not being to $\\textbf{pa}_G(v)$. So it should be $c$-removable (and thus estimate-collapsible according to Proposition 1). But $v$ is not $c$-simplicial in CPDAG, since it is not a leaf node.\n4. Since the definitions for CPDAG, DAG, UG and its related key concepts on $c$-simplicial, $c$-removable, simplicial are so spread out, I would suggest collecting and adding them to a table for easy comparison and reference.\n5. What do you mean by \"non-trivial\", e.g., on Line 133? Perhaps should briefly explain it or put a footnote somewhere? Is there a definition for \"chain component\" which appears first on Line 263-264? I'm not entirely sure what it means in this context.\n6. If I understand correctly, the DSCS algorithm doesn't actually provide a $O(|V|^2)$ upper bound for DAG? See the incompatibility doubt I raised in Question 3 (also see related discussion around Line 76-80).\n\nTypos:\n1. On line 245, \"establishes CPDAG-based criterion for check estimation-collapsibility\", \"check\"->\"checking\".", "limitations": "yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. The problem is well-motivated: detecting estimation-collapasibility from CPDAG is a natural generalization of the DAG setting and it is interesting to see the connection from the UG perspective.\n2. This paper is well-written, clear and mostly self-contained. I find the graphs are pretty helpful in understanding the paper.\n3. Their algorithm is quite straight-forward given the equivalence theorem between estimation-collapasibility and $c$-simplicial.\n\nWeakness:\n1. I have some questions/concerns regarding applying $c$-simplicial criteria over the vanilla DAG setting -- see Question 3.\n2. Some terminology is missing and might affect reading -- see Question 1 and 5.\n\nOverall, I think this paper is solving a well-motivated problem that could be of interests to audience of this conference. Their techniques have a lot of connections to existing works, though I do have some doubts (perhaps due to my limited understanding).", "was_revised": true, "final_justification": "The authors have addressed my concerns adequately.", "rebuttal": "Thank you for your careful reading. Your valuable feedback helps us to improve the clarity of the manuscript. We will add more detailed explanations for the important concepts in the main text. We will also thoroughly check the grammar and spelling. Regarding the issues you raised, we address the questions in detail below.\n\n&nbsp;\n\n**Question 1** \n> On Line 196, the authors mention $\\mathbf{ne}_{G^*}(v) = \\emptyset$, I don't see why this is true, unless you define the neighbors as the ones connected via undirected edges. There's no formal definition of neighbors other than on Line 89 (which had no formal definition on the main text). To avoid confusion, I think it's best to make a note mentioning the distinction between neighbors v.s. parents and children -- that they are disjoint.\n\nWe appreciate your attention to this subtle but important distinction. In our notation, \"neighbors\" indeed refer to those vertices connected via *undirected* edges, while \"parents\" and \"children\" are those via *directed* edges. We provided the definitions of \"neighbors\", \"parents\" and \"children\" in Appendix A (see the paragraph after Line 500). To improve clarity, we will include these important definitions in the main text in the final version of the manuscript.\n\n&nbsp;\n\n**Question 2**\n> Does the $c$ in $c$-simplicial stands for conditional? I think it would be helpful to point out the meaning: easier to understand what's the difference between $c$-simplicial (CPDAG) and simplicial (undirected graph).\n\nThe \"$c$\" in $c$-simplicial stands for *compound*, as the $c$-simplicial property (CPDAG) combines the features of a simplicial set (undirected graph) and a leaf set (DAG). Thank you for point this out. We will clarify this in the manuscript. \n\n&nbsp;\n\n**Question 3**\n>Why does the definition of $c$-simplicial (for CPDAG) seem so different from the counterpart on DAG? Intuitively, do we not expect that DAG would be reduced back to CPDAG (viewing DAG as a subset of CPDAG, or simply transforming DAG into its CPDAG)? I notice the discussion on Line 200-202: it only describes reduction from CPDAG to DAG but not the only way around. Maybe it is obvious to the authors, but I don't quite see how to convert $c$-removable to $c$-simplicial (worth writing a bit more on this). Are they incompatible? For example, consider the node $v$ in DAG: $v \\rightarrow a \\leftarrow b$. $v$'s $\\mathbf{Mb}_{G}(v)$ is $a$ and $b$. They ($a$ and $b$) are adjacent and does not being to $\\textbf{pa}_G(v)$. So it should be $c$-removable (and thus estimate-collapsible according to Proposition 1). But $v$ is not $c$-simplicial in CPDAG, since it is not a leaf node.\n\nThank you for your careful review. As established in Theorem 1 (Lines 223-238), $c$-removable and $c$-simplicial are compatible. \n\nThe confusion may have arisen as our notation $\\mathbf{Mb}\\_{\\vec{G}}(v)$ refers to the ***union of the vertex $v$ and its Markov boundary*** $\\mathbf{mb}\\_{\\vec{G}}(v)$ (see Lines 88-91 and the paragraph after Line 502). That is, \n$\\mathbf{Mb}\\_{\\vec{G}}(v)=\\mathbf{mb}\\_{\\vec{G}}(v) \\cup \\\\{v\\\\}$.  In your example, for the DAG $v\\rightarrow a\\leftarrow b$, $\\mathbf{Mb}\\_{\\vec{G}}(v)$ consists of $a$, $b$, **as well as $v$**, where $b$ and $v$ are not adjacent. Therefore, $v$ is *not $c$-removable*, which is consistent with $v$ not being $c$-simplicial in the CPDAG. \n\nTo enhance clarity, we will reiterate the definition of $\\mathbf{Mb}\\_{\\vec{G}}(v)$ in Definition 2 in the revision.\n\nThe intuition for the equivalence between $c$-removability for DAG and $c$-simpliciality for CPDAG is as follows. In the reference [28], $c$-removability is characterized via Markov equivalence classes: a vertex $v$ is $c$-removable from a DAG $\\vec{G}$ if and only if there exists some DAG $\\vec{G}^\\prime$ which is Markov equivalent to $\\vec{G}$ such that $\\mathbf{ch}\\_{\\vec{G}^\\prime}(v)=\\emptyset$. Inspired by this fact, in the CPDAG $G^{\\*}$, we require $\\mathbf{ch}\\_{G^{\\*}}(v)=\\emptyset$; otherwise, for every DAG $\\vec{G}\\in \\mathcal{M}(G^{\\*})$, $\\mathbf{ch}\\_{\\vec{G}}(v)=\\emptyset$ would fail. Moreover, we must constrain the neighbor set $\\mathbf{ne}\\_{G^{\\*}}(v)$ so that for all $a,b\\in \\mathbf{ne}\\_{G^{\\*}}(v)$ (i.e., $a-v-b$), there exists some DAG $\\vec{G}^\\prime\\in \\mathcal{M}(G^{\\*})$ with $\\mathbf{ch}\\_{\\vec{G}^\\prime}(v)=\\emptyset$ and with edges $a\\rightarrow v\\leftarrow b$. Since this orientation cannot create a new $v$-structure, $a$ and $b$ must be adjacent in CPDAG $G^*$. These conditions naturally lead to the definition of a $c$-simplicial vertex in a CPDAG, and hence to the concept of a sequential $c$-simplicial set. Because $c$-removability and $c$-simpliciality are compatible, our DSCS algorithm offers an efficient way to determine $c$-removability.\n\n&nbsp;\n\n**Question 4**\n> Since the definitions for CPDAG, DAG, UG and its related key concepts on $c$-simplicial, $c$-removable, simplicial are so spread out, I would suggest collecting and adding them to a table for easy comparison and reference.\n\nThank you for the helpful suggestion. We will include a table summarizing all key concepts. These additions, which will be placed in the appendix, will enhance the clarity and accessibility for a broader audience.\n\n&nbsp;\n\n**Question 5**\n> What do you mean by \"non-trivial\", e.g., on Line 133? Perhaps should briefly explain it or put a footnote somewhere? Is there a definition for \"chain component\" which appears first on Line 263-264? I'm not entirely sure what it means in this context.\n\nThank you for your suggestion.\n\nAs stated in Line 131,  ***non-triviality*** is a mild distributional constraints proposed in the work of [28].  It is pointed out in [28] and we quote here that: \"the DAG models for both contingency tables and the Gaussian distributions are non-trivial,\" and furthermore, \"non-triviality is satisfied by most DAG models and is also implicitly used in the proof of Theorem 1 in [27].\" \n\nAs for ***chain component***, this is a standard concept in the literature for CPDAG (see, e.g., Andersson et al 1997; Castelletti et al. 2024). Chain components are the *maximal undirected connected subgraphs* in a CPDAG, and are also referred to as *undirected and connected chordal graphs* (UCCGs).\n\nThese clarifications will be incorporated in the revision.\n\n**Reference**\n\nAndersson, S. A., Madigan, D. & Perlman, M. D. (1997). A characterization of Markov equivalence classes for acyclic digraphs. Ann. Statist. 25 505-5\n\nCastelletti, F., & Consonni, G. (2024). Bayesian sample size determination for causal discovery. Statistical Science, 39(2), 305-321.\n\n&nbsp;\n\n**Question 6**\n> If I understand correctly, the DSCS algorithm doesn't actually provide a $O(|V|^2)$ upper bound for DAG? See the incompatibility doubt I raised in Question 3 (also see related discussion around Line 76-80).\n\nThank you for raising this important complexity issue.  As in the response to Question 3,  $c$-removable and $c$-simplicial are compatible. Therefore, our proposed DSCS algorithm can be employed to check estimate collapsibility for DAGs. \n\nFor a given DAG, our approach involves two steps: (1) converting the DAG to a CPDAG, which is $O(|V|^3)$ (Chickering 2002), and (2) applying our DSCS algorithm, which has worst-case complexity $O(|V|^2)$. Thus, the overall procedure is $O(|V|^3)$. Nevertheless, our method improves upon the naive $O(|V|^4)$ approach and, to our knowledge, represents the most efficient algorithm available for this problem.\n\nCurrently, we are not aware of any algorithm that can check estimate collapsibility for general DAGs with $O(|V|^2)$ complexity. We will clarify this point and the open complexity question in the revised manuscript, and we believe our work lays the groundwork for future progress in this direction.\n\n**Reference**\n\n Chickering D M. Optimal structure identification with greedy search[J]. Journal of Machine Learning Research, 2002, 3(Nov): 507-554."}, {"review_id": "nvjxJaVFge", "reviewer": "Reviewer_ufyg", "summary": "This paper studies the problem of estimation collapsibility that is fitting a sub-model and ignoring non-essential variables. This is relevant in scenarios where the number of variables are much more than the relevant ones. The authors introduce sequential c-simplicial sets to characterize estimation collapsibility in CPDAG instead of DAG and introduce an algorithm for verifying estimation-collapsibility within CPDAGs.", "questions": "Please see the comments.", "limitations": "Please see the comments.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\nAs mentioned, often in practice, the exact DAG is not available and using observational data, only up to Marko equivalence class can be revealed. Hence, the result of this work which characterises the estimation collapsibility for CPDAGs becomes important.\n\nThe proposed algorithm has complexity of quadratic from in the number of vertices which makes it scalable for large networks.\n\nWeakness:\nThe paper’s presentation has room for improvement. Some important definitions are missing such as non-triviality or chain components. \nIs the chain components are unique? If not how large the set of components, i.e., what is K in line 3 of DSCS algorithm?\nSince chain components are a major part of the proposed approach without (I could not find it) proper definitions and discussion on its cardinality, it is hard to read and understand the difference between the proposed method and the previous ones. \nWhy for example, other methods do not use the chain components Idea and reduce their complexity?\n\n\nAlthough the result of this work for CPDAGs are novel but given the previous definitions and characterisation of the c-removability, it is a limited contribution. In other words, it seems that given the previous results of estimation collapsibility in DAGs, its extension to CPDAGs is not trivial but a natural generalisation.", "was_revised": true, "final_justification": "The authors rebuttal addresses some of my concerns and thus my recommendation is toward accept.", "rebuttal": "We sincerely thank the reviewer for your careful reading and thoughtful feedback. Your comments will help us further clarify and highlight the novel contributions of our work. To improve the readability of the paper, we will also elaborate on key definitions in the final manuscript. In response to your comments, we address each point in detail below.\n\n**Weakness 1**\n>The paper's presentation has room for improvement. Some important definitions are missing such as non-triviality or chain components. Is the chain components are unique? If not how large the set of components, i.e., what is K in line 3 of DSCS algorithm? Since chain components are a major part of the proposed approach without (I could not find it) proper definitions and discussion on its cardinality, it is hard to read and understand the difference between the proposed method and the previous ones. Why for example, other methods do not use the chain components Idea and reduce their complexity?\n\nThank you for the valuable feedback. We agree that precise definitions and a clear discussion of chain components and non-triviality are crucial for understanding our approach. We will ensure that all such concepts are explicitly defined in the revised manuscript.\n\nRegarding ***non-triviality***, as stated in Line 131, this assumption was originally proposed in [28] and imposes only mild distributional constraints. It is pointed out in  [28] and we quote here that: \"the DAG models for both contingency tables and the Gaussian distributions are non-trivial,\" and furthermore, \"non-triviality is satisfied by most DAG models and is also implicitly used in the proof of Theorem 1 in [27].\" \n\n***Chain component*** is a standard concept  widely used in the literature for CPDAG (see, e.g., Andersson et al 1997; Castelletti et al. 2024). Chain components are the *maximal undirected connected subgraphs* in a CPDAG, and they are also referred to as *undirected and connected chordal graphs* (UCCGs). \n\nFor any given CPDAG, its chain components are uniquely determined. Consequently, in Line 3 of the DSCS algorithm, the number $K$ of chain components is a constant for a given CPDAG structure. The value of $K$ depends on the CPDAG structure. In the extreme case where the CPDAG is a DAG, $K$ equals the number of vertices (each vertex forms its own chain component); when the CPDAG is fully undirected, $K=1$ (the entire graph is a single chain component). In practical examples, $K$ is typically small relative to the number of vertices.\n\n**Novelty and distinction**. Leveraging chain component properties for efficient verification of collapsibility is a novel contribution of our work, unique to the CPDAG setting. In DAGs, the idea of chain components does not apply, since there are no undirected edges; each node forms its own chain component only in the extreme case where the CPDAG reduces to a DAG. This structural distinction underlies both the theoretical and practical efficiency of our approach, as compared to previous methods that focus on DAGs alone [28]. \n\nWe thank the reviewer again for these suggestions and will clarify these points in the revised manuscript.\n\n**Reference**\n\nAndersson, S. A., Madigan, D. & Perlman, M. D. (1997). A characterization of Markov equivalence classes for acyclic digraphs. Ann. Statist. 25 505-5\n\nCastelletti, F., & Consonni, G. (2024). Bayesian sample size determination for causal discovery. Statistical Science, 39(2), 305-321.\n\n\n&nbsp;\n\n**Weakness 2**\n> Although the result of this work for CPDAGs are novel but given the previous definitions and characterisation of the c-removability, it is a limited contribution. In other words, it seems that given the previous results of estimation collapsibility in DAGs, its extension to CPDAGs is not trivial but a natural generalisation.\n\n**We appreciate the reviewer’s concern that our extension from DAGs to CPDAGs might appear \"natural\". In fact, as summarized in Section 1, our work overcomes several substantial and previously unaddressed challenges:**\n\n1. **Introduce the sequential c‑simplicial set for CPDAGs.** The proposed *sequential $c$-simplicial set* required a careful and unified treatment of both directed and undirected subgraphs within a CPDAG, an extension that is not only non-trivial but also far from a natural generalization of prior work on DAGs. In particular, the connection with undirected graphs involves subtle and non-obvious technical challenges, which we address for the first time in this paper. See Appendix B for the technical details.\n\n2. **Establish an order‑free characterization.** Establishing an order-free characterization of sequential $c$-simplicial (or sequential $c$-removable) sets for arbitrary node sets $M$  is remarkably challenging. To the best of our knowledge, even for DAG, no prior work has addressed this problem. A key difficulty here for CPDAG lies in  simultaneously accounting for both the complex internal structure of $M$ (which may contain a mixture of directed and undirected edges) and its intricate relationships with the surrounding graph structure. Our work makes significant headway on this problem by developing simple yet powerful equivalent characterizations (see Section 3.2). \n\n3. **Exploit CPDAG structure with a divide‑and‑conquer strategy.** The theoretical insights directly led to the novel and efficient DSCS algorithm for verifying collapsible submodels.  By exploiting the unique structural properties of CPDAGs, our method enables a divide-and-conquer approach to collapsibility verification - processing each chain component independently. This strategy achieves substantial computational savings compared to conventional approaches that rely on sequential checking.\n\n**Collectively**,  these aspects constitute significant theoretical and algorithmic contributions that go well beyond a straightforward extension of earlier results. We believe these advances meaningfully enrich both the theory and practice of estimation collapsibility in the literature. We will ensure these points are clearly highlighted in the revised manuscript."}, {"review_id": "aYyc9z9aEk", "reviewer": "Reviewer_DeqM", "summary": "This work aims to propose efficient algorithms to verify estimation-collapsibility on a completed partially directed acyclic graph, or CPDAG, for Bayesian network inference. It introduces the concept of sequential c-simplicial sets and reveals the connection between the sequential c-simplicial sets and estimation-collapsibility. Further, it proposes a so-called detecting sequential c-simplicial sets (DSCS) algorithm as the verification algorithm with computational complexity analysis to show its efficiency. Empirical results on synthetic data are further presented.", "questions": "- What is the complexity of the conversion from a DAG of a Bayesian network to a CPDAG?\n- Can the authors provide more quantitative or qualitative comparisons with other baseline methods?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "[strength]\n- The research question considered in this work is important and challenging since the estimation-collapsibility can greatly improve the inference efficiency for many probabilistic queries.\n- The introduced concept of sequential c-simplicial sets and its connection with the estimation-collapsibility is novel, which unifies the previous work.\n- This work is overall well written, with a thorough discussion on previous work and theoretical results clearly elaborated. While this work is heavy in notations, I find the running example using Figure 2 very helpful.\n\n[weakness]\n- The experimental section will benefit from including more baseline methods for comparison, since now only one baseline is considered. It will also be improved a lot if more benchmarks are included, especially the real-world ones and those with diverse graph structures, since currently only results on Bayesian networks with Erdos-Renyi graphs are presented.", "was_revised": true, "final_justification": "The authors have addressed my concerns. So I keep my positive score.", "rebuttal": "Thank you for your careful reading and valuable feedback. To make the experimental section more comprehensive and persuasive, we will add experimental results on real-world graph structures from the bnlearn—Bayesian Network Repository in the Appendix. Regarding the questions you raised, we address them in detail below.\n\n\n\n**Question 1**\n> What is the complexity of the conversion from a DAG of a Bayesian network to a CPDAG?\n\nThank you for your raising this important question. For a given DAG, the complexity of converting it to a CPDAG is $O(|V|^3)$ (see e.g., Chickering 2002). Therefore, even if the underlying DAG is known, it can still be converted to a CPDAG, and then the proposed DSCS algorithm can be applied with $O(|V|^2)$. Thus, the overall procedure has complexity $O(|V|^3)$. Our method improves upon the naive $O(|V|^4)$ approach and, to our best knowledge, represents the most efficient algorithm available for this problem. We will clarify this point  in the revised manuscript.\n\n**Reference**\n\n Chickering D M. Optimal structure identification with greedy search[J]. Journal of Machine Learning Research, 2002, 3(Nov): 507-554.\n\n &nbsp;\n\n**Question 2** and **Weaknesses**\n> The experimental section will benefit from including more baseline methods for comparison, since now only one baseline is considered. It will also be improved a lot if more benchmarks are included, especially the real-world ones and those with diverse graph structures, since currently only results on Bayesian networks with Erdos-Renyi graphs are presented.\n\nAs far as we know, the methods in [28] we compare against are the optimal approaches for addressing DAGs in the literature, and the current work is the first to investigate this problem based on CPDAGs. Therefore, we are unable to compare with additional methods. \n\nMeanwhile, we have now selected three real-world Bayesian networks from the R package *bnlearn*—WIN95PTS (76 nodes, 112 edges), LINK (724 nodes, 1125 edges), and MUNIN (1041 nodes, 1397 edges). For each network, we randomly sampled a vertex subset $M$ of size $|M|$, then applied DCR (on the DAGs) or DSCS (on the corresponding CPDAGs) to test estimate-collapsibility over $M$. For every combination of network and $|M|$, we ran 30 simulations and recorded the average running time (in seconds), as reported in the table below. Across all graphs and values of $|M|$, DSCS consistently outperforms DCR in runtime, with its advantage growing as both the network size and $|M|$ increase.\n\n**Table 1:**  *Comparison of average running time (seconds) between DSCS and DCR methods (the best result is bolded).*\n\n**WIN95PTS**: \\|$V$\\| = 76, \\|$\\vec{E}$\\| = 112\n| | | | | | | | | | |\n|:----------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| \\|$M$\\| |   5   | 13    | 21    | 29    | 37    | 45    | 53    | 61    | 69    |\n| DSCS  | **0.003** |**0.007** | **0.012** | **0.019** | **0.023** | **0.026** | **0.031** | **0.035** | **0.047** |\n| DCR   | 0.020 | 0.040 | 0.067 | 0.104 | 0.144 | 0.189 | 0.255 | 0.289 | 0.333 |\n| | | | | | | | | | |\n\n**LINK**: \\|$V$\\| = 724, \\|$\\vec{E}$\\| = 1125\n| | | | | | | | | | |\n|:----------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| \\|$M$\\| | 50 | 130 | 210 | 290 | 370 | 450 | 530 | 610 | 690 |\n| DSCS | **0.027** | **0.072** | **0.114** | **0.168** | **0.238** | **0.343** | **0.442** | **0.596** | **0.660** |\n| DCR | 0.141 | 0.449 | 0.830 | 1.359 | 2.199 | 3.253 | 4.425 | 6.147 | 7.024 |\n| | | | | | | | | | |\n\n**MUNIN**: \\|$V$\\| = 1041, \\|$\\vec{E}$\\| = 1397\n| | | | | | | | | | |\n|:----------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n|\\|$M$\\| | 100 | 200 | 300 | 400 | 500 | 600 | 700 | 800 | 900 |\n| DSCS | **0.058** | **0.108** | **0.182** | **0.260** | **0.383** | **0.511** | **0.710** | **0.742** | **0.983** |\n| DCR | 0.333 | 0.771 | 1.588 | 2.822 | 4.168 | 6.762 | 9.260 | 11.954 | 15.420 |\n| | | | | | | | | | |\n\nThese additional experiments will be included in the Appendix to further support the proposed method."}, {"review_id": "GVBRUGvb1A", "reviewer": "Reviewer_QbiJ", "summary": "The paper studies the problem of when inference and marginalization in Bayesian networks can be performed by simply looking at the subgraph induced by the variables of interest rather than having to consider all variables. The authors design a generalization of existing algorithms for DAGs and undirected graphs by considering the completed partially directed acyclic graph (CPDAG) that encodes the Markov equivalence class of the Bayesian network. The main idea is to take advantage of the fact that CPDAGs are chains of undirected connected chordal graphs (UCCGs), since the authors observe that testing the property within UCCGs is straightforward. The running time is only quadratic in the number of vertices whereas previous work on DAGs required $O(|V|^4)$ time, and the speedup is evident is also from the empirical experiments.", "questions": "You write that \"Subsequent parallel verification of neighborhood completeness across chain components has complexity of order $O(|\\tau_{\\max}|^2)$, dominated by the largest component\". If I understood correctly, the issue is that you take quadratic time to evaluate whether each neighborhood is a clique? Have you considered if this could be done in linear time in the number of edges? I suspect that this might be doable by computing a perfect elimination ordering for each chordal component in linear time, since these enable characterizing the maximal cliques of the graph (see, e.g., [1]). Then, you would probably just need to check whether the neighborhood is a subset of the maximal clique associated with the node of the neighborhood that appears in the elimination ordering the earliest.\n\n[1] Fanica Gavril:\nAlgorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM J. Comput. 1(2): 180-187 (1972)", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\nQuadratic speedup in testing estimation-collapsibility for DAGs.\n\nExperiments providing practical evidence on the speedup. \n\nConcrete examples that are associated with illustrations to assist the reader.\n\n**Weaknesses:**\n\nI think it would be desirable for the main manuscript to be self-contained; now, some terminology is defined only in the Appendix (see, e.g., Sec. 2.1, and related minor comments). Some further polishing could also be done (see minor comments for a non-comprehensive list of examples).\n\nThe experiments only consider Erdös-Rényi graphs and not any real-world instances.\n\n**Minor:**\n- Line 49: missing whitespace.\n- Line 92: $A$ is already a set, so it does not need braces around it.\n- Line 99: missing whitespace.\n- Fig. 2 caption: missing whitespace.\n- Line 121: grammatical error in \"a substantially saving of data collection and computational efforts\".\n- Lines 152, 153: maybe \"induces\" instead of \"forms\"?\n- Definition 5: I think you should emphasize that the endpoints of undirected edges of a CPDAG do not count as children. Similarly, it is unclear that children or parents aren't neighbors unless one reads the Appendix containing the definitions carefully.\n- Line 191: you have a set instead of an ordering.\n- Line 192: I think it is more common to call childless nodes sinks rather than leafs.\n- Line 265: Extra 'p'.\n- Line 529: The definition of a chord could be more precise (\"edge connecting two non-adjacent nodes\") since the nodes are, by definition, adjacent if the edge connects them. Alternatives include \"no induced cycle of length greater than 3\" or \"edge connecting two non-consequent nodes of the cycle\".", "was_revised": true, "final_justification": "The Authors have adequately addressed the other Reviewers' and my concerns, so I continue to think that this is solid work to be accepted. I consider the additional experiments that were performed for the rebuttal especially beneficial for the work, since the earlier experiments relying only on Erdös-Rényi were too limited in my opinion.", "rebuttal": "We sincerely thank the reviewer for your careful reading and valuable feedback, which will help to significantly improve the work. \n\n**Weaknesses**\n> I think it would be desirable for the main manuscript to be self-contained; now, some terminology is defined only in the Appendix (see, e.g., Sec. 2.1, and related minor comments). Some further polishing could also be done (see minor comments for a non-comprehensive list of examples).\nThe experiments only consider Erdös-Rényi graphs and not any real-world instances.\n\nThank you for your careful reading and for correcting the formatting, grammar, and spelling. We will thoroughly proofread the entire manuscript again. \n\nMost concepts have been put in the Appendix due to space limitations. To make the main manuscript self-contained, we will add more detailed explanations for some important terminologies in the final version of the manuscript.\n\nMeanwhile, we have now selected three real-world Bayesian networks from the R package *bnlearn*—WIN95PTS (76 nodes, 112 edges), LINK (724 nodes, 1125 edges), and MUNIN (1041 nodes, 1397 edges). For each network, we randomly sampled a vertex subset $M$ of size $|M|$, then applied DCR (on the DAGs) or DSCS (on the corresponding CPDAGs) to test estimate-collapsibility over $M$. For every combination of network and $|M|$, we ran 30 simulations and recorded the average running time (in seconds), as reported in the table below. Across all graphs and values of $|M|$, DSCS consistently outperforms DCR in runtime, with its advantage growing as both the network size and $|M|$ increase.\n\n**Table 1:** *Comparison of average running time (seconds) between DSCS and DCR methods (the best result is bolded).*\n\n**WIN95PTS**: \\|$V$\\| = 76, \\|$\\vec{E}$\\| = 112\n| | | | | | | | | | |\n|:----------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| \\|$M$\\| |   5   | 13    | 21    | 29    | 37    | 45    | 53    | 61    | 69    |\n| DSCS  | **0.003** |**0.007** | **0.012** | **0.019** | **0.023** | **0.026** | **0.031** | **0.035** | **0.047** |\n| DCR   | 0.020 | 0.040 | 0.067 | 0.104 | 0.144 | 0.189 | 0.255 | 0.289 | 0.333 |\n| | | | | | | | | | |\n\n**LINK**: \\|$V$\\| = 724, \\|$\\vec{E}$\\| = 1125\n| | | | | | | | | | |\n|:----------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| \\|$M$\\| | 50 | 130 | 210 | 290 | 370 | 450 | 530 | 610 | 690 |\n| DSCS | **0.027** | **0.072** | **0.114** | **0.168** | **0.238** | **0.343** | **0.442** | **0.596** | **0.660** |\n| DCR | 0.141 | 0.449 | 0.830 | 1.359 | 2.199 | 3.253 | 4.425 | 6.147 | 7.024 |\n| | | | | | | | | | |\n\n**MUNIN**: \\|$V$\\| = 1041, \\|$\\vec{E}$\\| = 1397\n| | | | | | | | | | |\n|:----------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n|\\|$M$\\| | 100 | 200 | 300 | 400 | 500 | 600 | 700 | 800 | 900 |\n| DSCS | **0.058** | **0.108** | **0.182** | **0.260** | **0.383** | **0.511** | **0.710** | **0.742** | **0.983** |\n| DCR | 0.333 | 0.771 | 1.588 | 2.822 | 4.168 | 6.762 | 9.260 | 11.954 | 15.420 |\n| | | | | | | | | | |\n\n\nThese additional experiments will be included in the Appendix to further support the proposed method.\n\n&nbsp;\n\n**Questions**\n> You write that \"Subsequent parallel verification of neighborhood completeness across chain components has complexity of order $O(|\\tau_{\\max}|^2)$, dominated by the largest component\". If I understood correctly, the issue is that you take quadratic time to evaluate whether each neighborhood is a clique? Have you considered if this could be done in linear time in the number of edges? I suspect that this might be doable by computing a perfect elimination ordering for each chordal component in linear time, since these enable characterizing the maximal cliques of the graph (see, e.g., [1]). Then, you would probably just need to check whether the neighborhood is a subset of the maximal clique associated with the node of the neighborhood that appears in the elimination ordering the earliest.\n[1] Fanica Gavril: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM J. Comput. 1(2): 180-187 (1972)\n\nThank you very much for your constructive suggestion, and your understanding is absolutely correct. We carefully reviewed the literature (see, e.g., Fanica 1972) you provided as well as subsequent works (see, e.g., Rose et al. 1976; Tarjan & Yannakakis 1984), and indeed, there exists an algorithm called the *maximum cardinality search* algorithm (MCS) (see, e.g., Rose et al. 1976; Tarjan & Yannakakis 1984), which can find a perfect elimination ordering of chordal graphs while identifying all maximal cliques in the graph, with linear complexity. Therefore, we can use the MCS algorithm to determine whether each neighborhood is a clique, as you mentioned, by checking whether the neighborhood is a subset of the maximal clique associated with the node of the neighborhood that appears in the elimination ordering the earliest. Consequently, the complexity of Line 8 in the DSCS algorithm is no longer $O(|\\tau\\_{max}|^2)$, but $O(|\\tau_{max}|+|E^{\\*}\\_{\\tau_{max}}|)$. Thus, the overall complexity of the DSCS algorithm is $O(|V|+|E^{\\*}|)$, and we will make sure to highlight this in the main text. Once again, thank you for providing such valuable and insightful suggestions.\n\n**Reference**\n\nFanica Gavril: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM J. Comput. 1(2): 180-187 (1972)\n\nRose D J, Tarjan R E, Lueker G S. Algorithmic aspects of vertex elimination on graphs[J]. SIAM Journal on computing, 1976, 5(2): 266-283.\n\nTarjan R E, Yannakakis M. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[J]. SIAM Journal on computing, 1984, 13(3): 566-579."}]

Author rebuttal:

Meta-review: The paper proposes a more efficient technique for estimation collapsibility, which is very relevant when performing inference in high dimensions for a small subset of variables. The results for completed partially directed acyclic graphs generalizes prior results for directed acyclic graphs and undirected graphs. Experimental results validate the main claims.

The reviewers unanimously agree to accept this paper. For a camera-ready version, please take into the account the comments from all reviewers regarding for instance, defining neighbors/parents/children in the main text, including other concepts such as c-simplicial/c-removable/non-triviality/chain-components, and including additional benchmark network experiments.
Decision: Accept (poster)