Differentiable Structure Learning with Partial Orders
Authors: Taiyu Ban
Lyuzhou Chen
Xiangyu Wang
Xin Wang
Derui Lyu
Huanhuan Chen
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal discovery
Continuous optimization
Differentiable Structure Learning
Partial Orders
Primary area: causal_inference
TL;DR: This paper extends the continuous optimization of structure learning able to integrate structural partial orders, an important prior information in real-world causal research.

Abstract: Differentiable structure learning is a novel line of causal discovery research that transforms the combinatorial optimization of structural models into a continuous optimization problem. However, the field has lacked feasible methods to integrate partial order constraints, a critical prior information typically used in real-world scenarios, into the differentiable structure learning framework. The main difficulty lies in adapting these constraints, typically suited for the space of total orderings, to the continuous optimization context of structure learning in the graph space. To bridge this gap, this paper formalizes a set of equivalent constraints that map partial orders onto graph spaces and introduces a plug-and-play module for their efficient application. This module preserves the equivalent effect of partial order constraints in the graph space, backed by theoretical validations of correctness and completeness. It significantly enhances the quality of recovered structures while maintaining good efficiency, which learns better structures using 90\% fewer samples than the data-based method on a real-world dataset. This result, together with a comprehensive evaluation on synthetic cases, demonstrates our method's ability to effectively improve differentiable structure learning with partial orders.

Differentiable Structure Learning with Partial Orders
Taiyu Ban
Lyuzhou Chen
Xiangyu Wang"
Xin Wang
Derui Lyu Huanhuan Chen"
University of Science and Technology of China (banty, clz31415, wz520, drlv) @mail wstc. edu, cn {sa312, hchen } @ustc. edu.
Abstract
Differentiable structure learning is novel line causal discovery research that transforms the combinatorial optimization of structural models into continuous optimization problem. However, the field has lacked feasible methods to integrate partial order constraints, critical prior information typically used in real-world scenarios, into the differentiable structure learning framework. The main difficulty lies in adapting these constraints, typically suited for the space of total orderings, to the continuous optimization context of structure learning in the graph space. To bridge this gap, this paper formalizes set of equivalent constraints that map partial orders onto graph spaces and introduces a plug-and-play module for their efficient application. This module preserves the equivalent effect of partial order constraints in the graph space, backed by thcoretical validations of correctness and completeness. It significantly enhances the quality of recovered structures while maintaining good efficiency, which learns better structures using 90% fewer samples than the data-based method on real-world dataset. This result, together with comprehensive evaluation on synthetic cases, demonstrates our method's s ability effectively improve differentiable structure learning with partial orders.
Introduction
Learning directed acyclic graph (DAG) structures from observational data is fundamental for causal discovery in scientific research [Opgen-Rhein and Strimmer, 2007; Pearl and others, 2000J. Tra- ditionally, it has been approached combinatorial optimization problem dominated by indepen- dence tests and score-and-search methods (Heinze-Deml el al., 2018). Zheng el al. [2018) reformed it continuous optimization problem through novel characterization of the acyclicity constraint in a differentiable form. Subsequently, numerous studies have proposed various learner architec- tures [Yu al., 2019; Zhu et al., 2019; Zheng et al., 2020], acyclicity characterizations [Yu al., 2019; Ng et al., 2022; Bello et al., 2022], and optimization techniques (Wei et al., 2020; Deng et al., 2023a.b] to advance differentiable structure learning.
In practical scenarios of causal discovery, researchers often possess prior knowledge of ordering, such known gene activation sequences in genetics [Olson, 2006), standard treatment sequences in healthcare management [Denton el al., 2007], and sequential seasonal weather patterns in me- teorology [Bruffaerts al., 2018]. Such prior information can be generally formalized O = {x, y) I, E X} of partial orders, where the binary relation (z, y) represents that variable precedes y in the ordering, denoted as y. For traditional score-and-search structure learning methods, the constraints of partial orders can reduce the space of total orderings in which the search algorithms² are usually performed [Teyssier and Koller, 2005]. Thus, the prior partial order informs the search process to find more genuine structures, which is essential for practical causal discovery.
* Coorreponniig authors.
'Such algorithms are known as order-based search in the literature, see Appendix A for details.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

However, the application of prior partial orders in the context of differentiable structure learning has not been explored. The main challenge arises from the inapplicability of the scenario, as the contin- nous optimization of structures is conducted in the graph space, while partial orders are constraints in the ordering space, leading to a misalignment of the hypothesis space. In related studies, Deng er al. [2023a] use search strategy to solve the constrained optimization problem in the ordering space, which is not a purely continuous method. Some research applies differentiable structure learning to dynamic Bayesian network (DBN) structure learning [Pamfil et al., 2020; Sun et al., 2023; Yang et al., 2022], which assumes a strict time-series ordering. This strict order prior can be simply imple- mented in the graph space by freezing the parameters of certain edges (see discussions in Appendix B), which significantly differs from the general partial orders discussed in this paper.
Despite of the misalignment of hypothesis spaces, the partial order constraint in the ordering space has an equivalent form in the graph space captured by path prohibitions [Grimmett and Stirzaker, 2015]. This leads to feasible way to apply partial orders in differentiable structure learning. How- ever, for sequential ordering with m variables, there are (2) paths be forbidden the equivalent constraint. This complexity makes it impractical to develop constraints path prohibitions individ- ually, leading to substantial computational overhead for long sequential orderings.
To address this issue, we propose an efficient approach that augments the acyclicity constraint to naturally forbid all paths in the equivalent constraint of partial orders O. Coneretely, we infer the transitive reduction of O and divide it into maximal paths to capture all possible sequential orderings. These paths are then individually added the adjacency matrix of the acyclicity term, forming an augmented acyclicity constraint. We prove that adherence to this new constraint is equivalent to adherence to partial order constraints. Furthermore, this method efficiently handles long sequential orderings, requiring only one factor to describe a sequential ordering regardless of its length. It is a plug-and-play module that can be easily adapted to various algorithms. Evaluations on both synthetic and real-world data verify its effectiveness. Contributions are listed:
To the best of our knowledge, this is the first work to discuss the integration of prior con- straints of partial orders into the continuous optimization of structure learning. We propose a plug-and-play module enabling the integration of this prior, which is theoretically appli- cable to all continuous methods in the differentiable structure learning context.
We address the misalignment between the hypothesis space of differentiable structure learn- ing and partial order constraints by converting them into an equivalent form of path prohi- bition constraints. By formalizing the continuous characterization of this equivalent con- straint, we show its limited practicality in dealing with long sequential orderings.
To efficiently integrate long sequential orderings, we introduce novel approach to apply path prohibitions by augmenting the acyclicity constraint with partial orders. We prove the equivalence of this augmented acyclicity constraint to the adherence to partial orders and show its efficiency in dealing with long sequential orderings.
2 Notations and Preliminaries
Notations In the following illustrations, we denote Wi., W.j- and Wi, represent the ith row, jth column, and (i.j jhth element of a matrix W. respectively. If a matrix symbol includes subscript, like W., we represent its elements as W.,.j. For operations resulting in a matrix, such as W1 + W2. we denote elements of the resulting matrix as (W1 + W2),s. For simplicity, the symbol (i, j) is used contextually: can refer to a partial order X; x X, or to a directed edge (X, in the graph. Related work and proof of statements can be found in Appendix A and Appendix C, respectively.
Structural equation model Let G denote a directed acyclic graph (DAG) with d nodes, where the vertex set V corresponds to a set of random variables X (X1, X2,..., Xa), and the edge set F(G)) V V defines the causal relationships among the variables. The structural equation model (SEM) specifies that the value of each variable is determined by function of its parent variables in G and an independent noise component:
X, = fy(Paf.
where pa. = (X, X, E XX,, X,) E F denotes the set of parent variables of X, in G, and zy represents noise that is independent across different j. Denoting the structure of G as weighted
2

---

adjacent matrix W E Raxd, where Wa, # 0 equals that (X,, E E(G), we have: X, 22)
X, = Given a set of samples D E Rxd generated from this model with either linear or nonlinear func- tions in {fy}: J. we next describe the process of learning the structure of G in differentiable manner.
(W f
(2)
Differentiable structure learning The objective of structure learning is to deduce the DAG struc- ture represented by the weighted adjacency matrix W E TRdxa from the data D generated by a specific set of functions f. We define all parameters characterizing W and f 0 and the graph as (()) and we formalize the optimization problem of structure learning as follows:
min ((D, subject to G(W DAG
where F is the score function, such as the least squares [Loh and Bühlmann, 2014]. For clarity, emphasize the target W and rewrite F(W). Simi- larly, the symbol (0) denoting the graph is simplified as G(W). The acyclicity degree of the graph can be characterized by series of continuous functions for non-negative matrix B:
2m E. IID Ja (D)
b(B) Trace Σ
&B
C. C
(4)
For this acyclicity characterization, Zheng al. [2018] use h(B) = Trace(e d. derived from an infinite power series² of B. Yu el al. [2019] suggest a polynomial form BBB) = Trace( + /B)d-
f), and Bello et al. [2022] employ a log-determinant function h(B) = log det(s1 - B3) + d log s.
For W E Rdxd it is common to use B = W W to ensure the non-negativity of B. Hence, the following mentioned h(W) actually refers to h o W))
Proposition (Theorem in (Wei al., 2020]). The directed graph of a non-negative adjacency matrix B is a DAG if and only if (B) = 0fror any h defined by (4).
According to this result, the constraint G(W) DAG can be implemented by the continuous equal- ity h(W)= = O. This transformation converts the structure learning problem into a continuous opti- mization problem with an equality constraint, formulated as:
min F(W) subject to h(W) = 0 WER
(5)
Zheng et al. [2018] apply the augmented Lagrangian method to solve this problem. a technique widely adopted in subsequent studies. Note that our proposed plug-and-play module does not alter the optimization process; therefore, this aspect is out of scope and not discussed in this paper.
Role of orders in structure learning Variable ordering plays a crucial role in the combinatorial optimization of structure learning. The direction in this context. It is founded on the principle that structure learning is no longer Na-hard when the total ordering of variables known [Teyssier and Koller, 2005]. These methods search within the hypothesis space of total orderings to identify the optimal solution within this constraint [Xiang and Kim, 2013; Raskutti and Uhler, 2018: Squires et al., 2020; Wang el al., 2021; Solus et al., 2021; Chen et al., 2019; Li and Beek, 2018; Chen et al., 2016). They benefit from prior partial orders, which help reduce the space of possible total orderings. However, differentiable structure learning solves Equation (5) in the DAG space, making it inapplicable to directly use partial orders. Therefore, we employ an alternative constraint equivalent to partial orders in the following section.
score-and ande-aand-eeach method is a critical research
3 Differentiable Structure Learning with Partial Orders
This section introduces the integration of partial order constraints into the continuous DAG opti- mization framework. First, we convert the constraints from the ordering space into an equivalent form in the DAG space. Next, discuss the limitations of direct characterizations of these equiv- alent constraints. Finally, we present an efficient approach to integrate partial order constraints and illustrate its theoretical correctness and completeness.
'The terms with powers higher than d are expressible in finite terms with powers not exceeding d by the Cayley-Hamitton Hamilton theorem. Therefore, Trace(e - d is also instance of Equation (4).
3

---

3.1 Capture partial orders with path prohibition constraints
To begin with, we formally define critical concepts related to partial orders.
Definition 1 (Partial Order). For a set S of variables. a partial order a binary relation < on S which is subset of S x S. For all elements z, y, and in S, the following properties satisfied: Reflexivity: x < x for every x in S; Antisymmetry: If < y and y < I. then I = y; Transitivity: If and 2, then x - z.
For the structure, x < y. then cannot be the ancestor of x; that is, no directed path exists from to in the graph. Note that while the partial order relation is transitive, the absence of paths is not. This requires further consideration of the transitive property of orders.
Definition (Transitive closure). For a set S and a binary relation R S the transitive closure of R. denoted by R+, is defined as R+ -Un=1 R R" is defined recursively by: R. R, R"-1 R. RD,
{(x, z) E S x Ry S such that (2,y) E S and (y, z) E T).
Remark 1. The transitive closure O+ of set of partial orders O encompasses all orders either directly contained in or inferable through transifivity from O.
Now, we consider the following result from graph theory, which essential for transforming order constraints into structural constraints.
Proposition 2. There exists at least topological sort of DAG G that satisfies the partial order set O if and only if. for any order (i.j) in O+, Xj is not an ancestor of X, in G.
With this statement, the structure learning problem with partial orders can be implemented by its equivalent constraint set of path prohibitions, formalized as:
min WER
F(W)
subject h(W) 0, X, X; & G(W) for all (i,5) E E
(6)
where Xj ~ X, & G(W) indicates that no directed path exists from X, to X, in G(W). Subse- quently, we introduce this constraint's continuous characterization and discuss its limitations.
3.2 Continuous characterization of path prohibitions
This section introduces the continuous characterization of the path prohibition constraint in Equation (6) and the practical difficulties in optimizing it. To clarify the unique challenges when dealing with flexible partial orders, we begin with the case of total orderings.
Definition 3 (Total Ordering). A total ordering is permutation of all the variables, with (() denoting the index of the variable in the ith position. X precedes Xmis) if and only if j.
For total ordering, the order relationship between any pair of variables is contained in the transi- tive closure न. This property allows for simple implementation of the constraint of π by edge prohibition, as illustrated below:
Proposition 3. A graph is a DAG and satisfies total ordering n if and only if edge (u, v) does not exist in G for all (v. u) E ext
This edge absence constraint on G(W) can be directly implemented by setting the corresponding parameters W to zero, resulting in the following formulation:
min F(W) subject to W Wn()) = for j W
In this case, structure learning becomes unconstrained optimization problem, as adherence to total orderings naturally satisfies the DAG constraint. This problem can be solved more efficiently than the original problem with the constraint equality h(W) = 0.
Now we consider the flexible partial order constraints. Let represent set of partial orders that do not inherently contain cycles within their transitive closure O+. Merely forbidding edges that violate O+ is insufficient for compliance, as it is possible to walk from variable to a preceding variable in O through another variable whose order with others is not contained in O, such as:

---

Example 1. For example, consider four nodes 1,2, 3, 4 with a partial order set O = (2.3))
forbid all inverse edges in O+, which are (2, (3, 2), (3, 1). Despite this, directed paths violat- ing the partial order (1 can still exist, such as the path (2, 4, 1). Such paths can be constructed by traversing nodes not in O like node in this case.
Consequently, we must consider the constraint of path prohibitions equivalent to O. According to the proof to Proposition 1, the following equality can be used for path prohibition constraints.
Proposition 4. No directed path X; Xj exists in G(W) if and only if (Eizi (W w)))
0.
With this statement, we can formalize the optimization problem in Equation (6) as follows:
min F(W) W
subject to h(W) = O, p(W,O)=
(8a)
(W. E (6.5)E+
Σ
E(won ( wy
(8b)
j
Remark 2. A significant difficulty of the optimization problem formulated in Equation (8a) is its steep decline training efficiency as the complexity of partial orders increases. The penalty term p(W, O), as defined by Equation (8b), includes a term for each order in O+, directly impacting the computational cost for gradient calculations. When dealing with a sequential ordering with m variables, it introduces (2) new terms. Each of these terms demands comparable time for gradient calculation to the acyclicity term h(W) typically used in current studies. This makes the computa- tional load impractical for long sequential orderings. Note that the total ordering constraint results in the most constraint terms in this case, while it can be efficiently addressed by Equation (7).
This observation underpins the need develop more efficient method to ensure that the structure learning process remains computationally feasible for long sequential orderings.
3.3 Augmented acyclicity-based partial order characterization
This section introduces an efficient method to characterize partial orders, distinct from directly rep- resenting the equivalent path prohibitions. We first introduce some critical concepts.
Definition 4 (Transitive Reduction). The transitive reduction O of relation O is the smallest relation such that the transitive closure of O is equal to the transitive closure of O. Formally, (0-)+ 0 and O- is minimal.
The transitive reduction is used to eliminate redundant orders to facilitate calculation efficiency. Below, we provide an example to illustrate transitive reduction alongside transitive closure.
Example 2. For a set of transitive binary relation O = ((1, 2), (2, 3). (1, 3). (3,4) 4)}, iss transitive closure is + O U {(1, 4), (2, 4)), and its transitive reduction is O = 0 ((1,)))
Definition 5. Let G = (V, E) be graph. A source is vertex in V with no incoming edges, i.e., {U E V deg (v) 0}. A sink is a vertex with no outgoing edges, i.e., {u E V deg (v) = 0}. Definition (Maximal Path). Let G (V, F.) be a graph with node set V and edge set F. A path p (UI..... ..) with (et, v1+1) E E is considered maximal path if U1 is source, Uy is sink, and the path not a proper subsequence of any other from U1 to Ug.
Definition 7. The transitive closure of path p -v1:-.., Uk), denoted as pt, is the of all ordered pairs (0i, v;) for Si<j <
Remark 3. For brevity, the following discussions regard the concepts of the directed graph, path, sequential ordering, and partial order set as an identical type of set whose element is an ordered pair (i, as both node reachability a graph and the order relationship are transitive. Especially, we do not distinguish between a partial order set O and the graph G(O) constructed by E(G(O)) {(i.)) | (I.j) E O).
Remark 4. We assume that no cycle exists in O+. That is, O is not conflicting with itself.
With these definitions, we formalize the new approach to integrating partial order constraint O into differentiable structure learning follows (see Appendix D for detailed implementations):
5

---

min F(W) subject to H'(W,), = 0 W
(9a)
N(W,O)= = Σ M(A(W,))
(9b)
OEP(O)
A(W,0) = ---W++G + W W.
(9c)
Wo.s. = [(i,5] c]
(9d)
Here, O- is the transitive reduction of O. P(O-) represents the set of all maximal paths of O (-).
[P] is the indicator function valuing if condition P holds and 0 otherwise. T > is a hyper- parameter used for adjusting the weight in gradient calculation.
Remark 5. Recall that h(W) 2 0 by Equation (4). Then we have that h' N'W, O) = 0 is equivalent to ((A(A((W))) o)) = for o E P(O-) by Equation (9b).
Equation (9) can be interpreted as augmenting the original acyclicity constraint h(W) = 0 to a stronger one h'W, O) = O. Specifically, we use series of partial guder-augmented acyclicity con- straints h(A(W,)) o)) = O for in the maximal path set of O as described in Equation (9b). For each augmented acyclicity, we add the path o to the adjacency matrix W by A(W, o) as detailed in Equation (9c). Thus, the acyclicity function h with A(W, o) as input represents a stronger acyclic- ity constraint. The additional part of this stronger acyclicity accurately captures adherence to the sequential ordering indicated by o, which can be derived from the following statement.
Lemma 1. A graph G is a DAG and satisfies a sequential ordering o = {(P), {(PI,2,.... P2. only if graph G' is a DAG where E(G")= = E(G) U..
,Pm)) ,Pm)} if and
This lemma states the equivalence of h(A(W,)) o)) = 0 to adherence to the sequential ordering o. Now consider the following statement.
Lemma 2. For the set P(O-) ) of all maximal paths of O= thee union of the transitive closures of these paths is the transitive closure of O: Uper(o-) o = 0
This lemma states that adherence to all the sequential orderings o indicated by maximal paths in O- is equivalent adherence to the complete set O of partial orders. Recall that h (W: 0) is equivalent to h(A(W, 0)) = 0 for o in P(O-), and h(A(W,) o)) = 0 is equivalent to adherence to o. is equivalent to adherence to O by Lemma 2, as described in
Hence, we derive that h (W, O) the following statement (the proof of these statements is provided in Appendix C.I).
Theorem 1. A graph G is a DAG and satisfies a set of partial orders O if and only h' O) = 0 for the function h defined by Equation (4) and h' defined by Equations (9b), (9c), and (9d).
Theorem shows the correctness and completeness of the equality h' NWW O) = 0 in capturing the partial order constraint O. More concretely, all prior information of O is fully integrated while no extra information beyond O is introduced. This is attributed to two critical steps in integrating O into the acyclicity constraint. Step Split the partial order constraint O into sequential orderings. Step 2. Ensure that these sequential orderings are maximal paths in O- If Step 1 is removed", and we directly add all the edges in O to G(W) for augmented acyclicity. h' will degenerate into h(A(W, O O). This introduces extra orders outside of O as indicated in the following example.
Example 3. Assume that h' H'(W, = h(A(W, O-)). Consider a partial order set O = ((1,2), (3, 4)} and DAG G(W) with edges E(G(W)) = ((2,3) 3), (4, 1)). Obviously G(W) satis- fies O. Consider the graph constructed by adding edges in O- (where O = O) to G(W), ), Lee the graph of the matrix A(W, O-). Its edge set is OU F(G((W)) {(1, 2), (2,3). (3,4), (), 1)) and contains a cycle (1,, 3, 4, 1). This makes h' (((,O)) = h(A(W, O)) 4 0 by Proposition 1.
In this case, a legal DAG that satisfies O forbidden by the constraint h ('(W,) = O. indicating that extra constraints beyond the prior are introduced. In other words, Step guarantees the necessity of the constraint equality for partial order O. For Step guarantees the sufficient adherence to O. If this step is removed, some order constraints of O can be lost. See the following case.
Note that Step 2 would also be omitted in the absence of Step 1.

---

Example 4, Consider partial order constraint ser 0 = (2,,(), (2, (4) Suppose that it is di-
vided into two sequential orderings 0r = (1,2,3) and 02 (4.2), where 02 not the maximal path
of O- Then consider graph G(W) with edges (1,2). (3,4)) We have that E[G(A(W, o1 01))) (1,2), (2,3), , (3, 4)} and FAG(A(WW 02))) (11,2), 2). (3, 4), 2,2)). Both graphs are DAGs satis- fying l((A) = O by Proposition I. Then we have h' (W, O) h(A(W, + h(A(W, 02)) 0.
Even if G(W) satisfies this constraint equality, the edge (3, 4) in G(W) still violates the order (4,3) O+, derived by the transitive result of (4, 2) and (2,3).
In this case, an illegal instance that violates O is not forbidden by the constraint h' h'(,, O) = 0. This indicates that some orders in O+ t are not specified by h N'WW, O) = 0 if Step 2 is omitted.
Remark 6. Now we discuss the complexity of gradient calculation for h (W, O). Equation (9b) indicates that this complexity is determined by the number [P(O-) of maximal paths in O ruther than the size |O+| of its transitive closure. For a sequential ordering with m variables, h contains only one factor of h regardless of the value of m. This addresses the impractical computational load of path prohibition constraints with (22 factors as discussed in Remark 2. Note that the computa- tional complexity of ('W, O) can increase with multiple sequential orderings, which is evaluated in the following section.
Experiments
We evaluate our module for applying prior partial order (PPO) on linear NOTEARS [Zheng et al., 2018], NOTEARS- [Zheng et al., 2020], and DAGMA [Bello et al., 2022]. It named 'PPO- alg-t-p', where alg is the backbone algorithm, and Lp are settings on partial orders. Representative results are reported here, and the complete results are available Appendix E.
Section 4.1 presents the results on synthetic datasets. Section 4.2 discusses the results obtained using a well-established biological dataset [Sachs el al., 2005]. For computational resources, linear NOTEARS and DAGMA are executed on a 32-core AMD Ryzen 7950X CPU at 4.5GHz, while NOTEARS-MI.P uses NVIDIA GeForce RTX 3090 GPU, both with 32GB memory limit. We conduct five simulations for each synthetic structure and one simulation for the data and partial order constraints for each structure.
4.1 Synthetic datasets
Random DAGs are generated using Erdös-Rényi (ER) and scale-free (SF) models with node degrees in (2,4) and numbers of nodes d in {20, 30, 50). For linear SEM, uniformly random weights are assigned to the weighted adjacency matrix A. Given A, samples are generated by X = A + 2, E Rd using noise models (Gaussian (gauss), Exponential (exp)). Observational samples D E Raxd are then generated with the sample size n = 4d. For nonlinear cases, uniformly random weights are assigned weighted adjacency matrices W1, W2, W3. Based on these matrices, samples are generated using X = tanh( XW1) + cos(XW, (W2) sin( (inn((WW XW3) 3 2 with N(0, 1). The sample size set to n- 20d. The parameter 7 in Equation (9c) is set to
To mimic real-world prior partial orders, we generate multiple sequential orderings, referred to as the chain of ordering. Specifically, we first conduct a topological sort on the DAG derive a total ordering т. We then randomly select chains, each denoting a sub-ordering randomly generated from т. Here, / is the number of chains and of a single chain of ordering and then the case of multiple chains of orderings. For single-chained ordering, 1 and is in (0.5d, O. 7,d,, d} (where d is the number of nodes). For multi-chained ordering, is in {1, 3, 5, 10] and m is fixed at 0.5d.
the size of each chain. We first investigate the case
4.1.1 Single-chained ordering
In this experiment, we examine structure learning using single-chained ordering. The results of Structural Hamming Distance (SHD), F1 score, and run time for linear NOTEARS are illustrated in Figure 1. Results for NOTEARS-MLP (nonlinear samples) and DAGMA presented in Figure 2.
Output quality. Our method demonstrates notable superiority over algorithms without prior infor- mation in terms of output quality in most cases, with the advantage becoming more pronounced
7

---

gaues
gaens
13
0.9
PRO-DACIMA-L-50 Structural Hamming Djstance (SHD)
10
0.5
0.8
0.7
CPU time (log10
280
F1 srore
80
0.6
60
0.5
215
245
0.9
0.85
100
80
1:55
0.7
NB
0.5
0.65
40
20
50
20
40
50
20
30
-0
50
20
30
40
50
20
30
40
50
20
50
40
50
(Number of Nodes)
d (Number of Nodes)
d (Number of Nodes)
Method
NOTERSS PP0-NOTTERR- H P7O-NOTTA
-PPO-NOTEARR---DO0
Figure: 1: Structural discovery terms SHD (lower is better). Fl Fc-re (higher is better) CPU time (log10 s) with NOTEARS on linear data. Rows: graph types. [ER,SF)-& J-k represents (Erdös-Rényi. scale-free) graphs with kd expected edges. Columns: noise types of SEM. Error bars represent standard errors over 5 simulations. Method: PPO-alg- 1-p denotes method with partial order settings / and m p%6d.
0.9
1.5
CPU (loEss
20.55
1.4
SHTD
80006
0.75
17:20
CPU
122
1.8
0.72
40
0.7
1.6
0.58
22
30
40
30
20
30
40
20
43
50
20
30
40
52
20
30
40
50
20
32
40
53
[Number of Nudi))
d (Namber Nodes)
Method
NOTEARS-MLP
NOT-NOTE
PPO PPO-NOTEARS-I-UO
PPO-NOTEARS-IL-0
Method
PPO-DAGMA-1-75
DACMA
PRO-DAGIMA-L-100
(a) NOTEARS MLP on nonlinear data
(b) DAGMA on linear data with exp noise
Figure 2: Structural discovery in terms of SHD (lower is better), Fl (higher is better) and CPU time (logı0 with NOTEARS-MLP and DAGMA on representative cases.
as the number of nodes in the ordering chain increases. This confirms the effectiveness of our ap- proach in enhancing structure learning quality with prior partial orders. Some degradation cases may be caused by invalid priors in the simulated ordering. Since the topological sort for a DAG is not unique, some random ordering chains may not contribute to revealing the most essential parts of orderings, especially with smaller chain sizes.
Run time. We observe that our method with a single-chained ordering is typically faster than struc- ture learning without prior. This efficiency is due to the effective management of our module for single-chained orderings. However, in some cases, such as on the SF4 graph with NOTEARS-MLA and DAGMA, the efficiency can be degraded. This indicates that the impact of partial orders on efficiency can vary with different data distributions and backbone algorithms.
4.1.2 Multi-chained ordering
The results for SHD, F1-score, and run time using linear NOTEARS and NOTEARS-MI.P with multi-chained orderings are presented in Figure 3. The output quality demonstrates similar trends to
8

---

0.3
12
24
15
130
CPU time Doosio
CPU time (Indan
100
6.5
10
30
40
(Number Nodee)
(Number Chains)
(Nambee Nodos)
[Numbar of Chaine)
NOTEARS
PPO-NOTEARS-1-5
1-50
d0 de50
NOTEAKS-MEZ
NOO-NOTTARS-- 1-50
d-20 de50
Method
PPD-NCIEARS
BAREARS
10-50
d-30 CPU Time
Method
NOTERO MOOOEERRS-O-- 10-30
d-30 CPU Time
(a) NOTEARS on linear data with gauss noise
(b) NOTEARS MLP on nonlinear data
Figure 3: Structural discovery in terms of SHD (lower is better), Fl-scor (higher is better) and CPU time 10 S) with linear NOTEARS and NOTEARS-MLP. Method: PPO-alg-I-50 represents our method where / the number of chains and the size of chains is 0.5d.
those seen with single-chained ordering, with more pronounced improvements over the baselines as the number of partial order constraint chains increases. The run time dynamics are illustrated with a curve that reflects changes corresponding to the primary influencing factor: the number of chains. Initially, time increases and then decreases the number of chains grows. This pattern results from the increasing complexity of gradient calculations for the constraint term /t, which scales with the number of maximal paths in the partial orders. At first, the increasing number of chains leads to more maximal paths in the partial order, thus delaying time efficiency. As the partial order becomes denser, more chains be covered by longer chain, which leads to fewer maximal paths in its transitive reduction, resulting in better time efficiency.
Table 1: Structural discovery in terms SHDI, FDR1, TPR and Flf on sach dataset with various sample sizes. Linear NOTEARS is used as the backbone algorithm, and PPO-1-m denotes our method using a single- chained ordering containing m nodes. The best result is highlighted with bold texts.
sach-50
sach- 100
sach-500
sach-853
Method
SHD
FDR
TPR
F1
SHD
FDR
TPR
SHD
FDR
TPR
F1
SHD
FDR
TPR
NOTEARS
25
0.76
0.41
0.30
16
0.65
0.41
0.38
15
0.60
0.35
0.38
12
0.57
0.35
0.39
PPO-1-6
20
0.70
0.35
0.32
15
0.62
0.29
0.33
13
0.50
0.35
0.41
14
0.55
0.29
0.36
PPO-1-8
16
0.59
0.41
0.41
0.42
0.41
0.48
12
0.40
0.35
0.44
10
0.30
0.41
0.52
PPO-1-11
0.27
0.57
0.00
0.41
0.58
0.13
0.41
0.56
0.41
4.2
Real-world data
The dataset provided by Sachs al. [2005] consists of continuous measurements of protein and phospholipid expression levels in human immune system cells. It is frequently used as a benchmark in graphical models due to its associated consensus network, which includes 11 nodes and 17 edges, based on experimental annotations recognized by the biological community.
We use experimental data from one of the cells with 853 samples. To mimic varying levels of exper- imental resources, we selected the first data samples for testing, where s E (50, 100, 500, 853). A single-chained prior ordering is given involving different numbers of variables in {6, 8, 11). Linear NOTEARS serves as the backbone algorithm. The parameter r in Equation (9c) is set to 3.
The structural evaluation metrics reported in Table I include SHD, False Discovery Rate (FDR), True Positive Rate (TPR), and F1 score. The findings reveal that NOTEARS with partial orders discovers more accurate structures than NOTEARS without prior information in most cases. Re- markably, even with the smallest sample size (50), NOTEARS with partial order constraint (11 nodes) significantly outperforms the baseline using the largest sample size (853). This underscores the efficacy the proposed partial order constraint-based differentiable structure learning approach in conserving experimental resources in scientific research contexts.

---

Discussion
Limitations and future directions Despite the theoretical correctness and completeness of the proposed method for integrating partial orders differentiable structure learning, there are some practical limitations.
First, the augmented acyclicity constraint h' (W. O) = 0 cannot be strictly satisfied during the op- timization process of the augmented Lagrangian method, as proven by Wei et al. [2020]. This may result in some order constraints from the prior not being satisfied in the output. This issue is inher- ent to the optimization aspect of differentiable structure learning and may be addressed with more refined optimization techniques in the future.
Additionally, although the proposed method efficiently handles long sequential orderings, its effi- ciency can be impacted by partial orders with complex structures. This is evident from the experi- mental results involving multi-chainee orderings. We randomly selected multiple ordering chains, each comprising half of the nodes, forming a complex order structure with considerable maximal paths. This leads to sharp increase in the number of constraint terms in the augmented acyclicity constraint. Fortunately, real-world ordering priors typically do exhibit such complex structures and can usually be captured by few chains. To enhance time efficiency in such cases, more re- fined characterization method could explored to reduce computational overhead in the future. We may focus on improving the gradient calculation of the proposed augmented acyclicity constraint in the context of multiple sequential orderings. This can be explored by merging the common parts of the gradient calculation process developing more efficient characterizations.
Conclusion This paper enhances the field of differentiable structure learning by enabling this framework apply priors of partial order constraints. We systematically analyze the related chal- lenges of applying flexible order constraints and propose novel and effective strategy to address them by augmenting the acyclicity constraint. We present theoretical proof confirming the cor- rectness and completeness of our strategy, Empirical results highlight the superiority of our method in improving structure learning with partial order constraints. Results on a well-know real- world dataset further emphasize its potential in uncovering more accurate causal mechanisms with reduced experimental resources.
Broader Impact
The proposed method allows researchers across various scientific fields to specify ordering priors, enhancing causal discovery with state-of-the--ar differentiable structure learning algorithms from experimental or observational data. As demonstrated with the real-world Sachs dataset [Sachs et al., 2005], differentiable structure learning using a proper ordering prior with only 10% of the samples required by methods without prior yields significantly better structures. This reduction in data requirements for causal discovery can save experimental resources across many domains.
However, researchers must exercise caution when providing ordering priors. The proposed method strictly adheres to these priors, and numerous incorrect ordering priors can severely impact the results. For instance, in social sciences, if incorrect assumptions about the order of socio- eecio-cconomic events are used priors, the resulting causal model may be misleading, affecting policy decisions based on such a model.
Acknowledgements
This research was supported in part by the National Key R&D Program of China (No. 1021200111700), in part by the National Nature Science Foundation of China (No. 62137002, 62176245, 62406302), part by the Natural Science Foundation of Anhui province (No. 2408085QF195), in part by the Key Research and Development Program of Anhui Province (No. 202104a05020011 part by the Key Science and Technology Special Project of Anhui Province (No. 202 202003007))0))
10

---

References
Kevin Bello, Bryon Aragam, and Pradeep Ravikumar. Dagma: Learning dags via m-matrices and a log-determinant acyclicity characterization. Advances in Neural Information Processing Systems, 35:8226 8239, 2022.
Nicolas Bruffaerts, Tom De Smedt, Andy Delcloo, Koen Simons, Lucie Hoebeke, Caroline Ver- stracten, An Van Nieuwenhuyse, Ann Packeu, and Marijke Hendrickx. Comparative long-term trend analysis of daily weather conditions with daily pollen concentrations in brussels, belgium. International Journal of Biometeorology, 62:483-491, 2018.
Eunice Yuh-Jie Chen, Yujia Shen, Arthur Choi, and Adnan Darwiche. Learning Bayesian networks with ancestral constraints. Advances Neural Information Processing Systems, 29, 2016.
Wenyu Chen, Mathias Drton, and Y Samuel Wang. On causal discovery with an equal-variane assumption. Biometrika, 106(4):973-95)) 980, 2019.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 30755): 2002.
Gregory F Cooper and Edward Herskovits. A bayesian method for constructing bayesian belief networks from databases. In Uncertainty Proceedings 1991, pages 86 64.9.. Elsevier, 1991.
Chang Deng, Kevin Bello, Bryon Aragam, and Pradeep Kumar Ravikumar. Optimizing notears objectives via topological swaps. In International Conference Machine Learning, pages 7563- 7595. PMLR, 2023.
Chang Deng, Kevin Bello, Pradeep Ravikumar, and Bryon Aragam. Global optimality in bivariate gradient-based dag learning. Advances in Neural Information Processing Systems, 36:17929- 17968, 2023.
Brian Denton, James Viapiano, and Andrea Vogl. Optimization of surgery sequencing and schedul- ing decisions under uncertainty. Health Care Management Science, 10:13-24, 2007.
Maxime Gasse, Alex Aussem, and Haytham Elghazel. A hybrid algorithm for bayesian network structure learning with application multi-label learning. Expert Systems with Applications, 41(15):6755-6777, 2014.
Geoffrey Grimmett and David Stirzaker. Mathematics for computer science. MIT OpenCourse- Ware, Massachusetts Institute of Technology, 2015. Available at: https://oow. wwtp:/eww.iittte.e. mit.edu/ccurses/ 6-042j-matteematic-foroooo www---ooputessiennceeeeeee - _aaiioo__22s11____ 042js15_ssession18 session18..ps p.pdf.
Christina Heinze-Demt Deml, Marloes H Maathuis, and Nicolai Meinshausen. Causal structure learning.
Annual Review of Statistics and Its Application, 5:371-391. 2018.
Andrew Li and Peter Beek. Bayesian network structure learning with side constraints. In Interna- tional Conference on Probabilistic Graphical Models, pages 225-236. PMLR, 2018.
Po-Ling Loh and Peter Bühlmann. nigh-diimnssioall learning of linear causal networks via inverse covariance estimation. The Journal of Machine Learning Research, 15(1):3065-3 -105,, 2014.
Ignavier Ng, AmirEmad Ghassami, and Kun Zhang. On the role of sparsity and dag constraints for learning linear dags. Advances in Neural Information Processing Systems, 33:17943-17954 2020.
Ignavier Ng. Sébastien Lachapelle, Nan Rosemary Ke, Simon Lacoste-Julien and Kun Zhang. On the convergence of continuous constrained optimization for structure learning. In International Conference on Artificial Intelligence and Statistics, pages 8176-8198. PMLR, 2022.
Eric N Olson. Gene regulatory networks in the evolution and development of the heart. Science, 313(5795);19222-197, 2006.
Rainer Rhein and Korbinian Strimmer. From correlation to causation networks: a simple approximate learning algorithm and its application high-dimensional plant gene expression data. systems biology, 1:1-10, 2007.

---

Roxana Pamfil, Nisara Sriwattanaworachai, Shaan Desai, Philip Pilgerstorfer, Konstantinos Geor- gatzis, Paul Beaumont, and Bryon Aragam. Dynotears: Structure learning from time- series data. In International Conference on Artificial Intelligence and Statistics, pages 1595-1605. PMLR, 2020.
Judea Pearl et al. Models, reasoning and inference. Cambridge, UK: CambridgeUmibeerinyPPesss, 19(2):3, 2000.
Garvesh Raskutti and Caroline Uhler. Learning directed acyelic graph models based sparsest permutations. Stat, 7(1):e183, 2018.
Karen Sachs, Omar Perez, Dana Pe'er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308(5721):523-555 529,, 2005.
Liam Solus, Yuhao Wang, and Caroline Uhler. Consistency guarantees for greedy permutation-based causal inference algorithms. Biometrika, 108(4):795-8)) 814, 2021.
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, prediction, and search. MIT press, 2000.
Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation-basee causal structure learning with unknown intervention targets. In Conference on Uncertainty in Artificial Intelligence, pages 1039-1048. PMLR, 2020.
Xiangyu Sun, Oliver Schulte, Guiliang Liu, and Pascal Poupart. Nts-notears: Learning nonpara- metric dbns with prior knowledge. In International Conference on Artificial Intelligence and Statistics, pages 1942-1964. PMLR, 2023.
Mare Teyssier and Daphne Koller. Ordering-basse search: a simple and effective algorithm for learning bayesian networks. In Proceedings of the Twenty-First Conference Uncertainty in Artificial Intelligence, pages 584-590, 2005.
loannis Tsamardinos, Laura E Brown, and Constantin F Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Machine learning, 65:31-78, 2006.
Xiaoqiang Wang, Yali Du, Shengyu Zhu, Liangjun Ke, Zhitang Chen, Jianye Hao, and Jun Wang- Ordering-based causal discovery with reinforcement learning, arXiv preprint arXiv:2105.0663/ 2021.
Dennis Wei, Tian Gao, and Yue Yu. Dags with no fears: A closer look at continuous optimization for learning bayesian networks. Advances in Neural Information Processing Systems, 33:3895-3906, 2020.
Jing Xiang and Seyoung Kim. A lasso for learning a sparse Bayesian network structure for contin- uous variables. Advances in neural information processing systems, 26, 2013.
Xing Yang, Chen Zhang, and Baihua Zheng. Segment-wise varying dynamic bayesian network with graph regularization. ACM Transactions on Knowledge Discovery from Data, 16(6):1-23, 2022.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. DAG-GNN: DAG structure learning with graph neural networks. In International Conference on Machine Learning, pages 7154-7163. PMLR, 2019.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Continuous optimization for structure learning. Advances Neural Information Processing Systems, 31, 2018.
Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, and Eric Xing. Learning sparse non- parametric dags. In International Conference on Artificial Intelligence and Statistics, pages 3414- 3425. PMLR, 2020.
Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal discovery with reinforcement learning. In International Conference on Learning Representations, 2019.
12

---

Appendix A Related Work
A.1
Combinatorial optimization of structure learning
Traditional combinatorial optimization of structure learning includes constraint- based, score-based, and hybrid methods. Constraint-base methods utilize conditional independence (CI) tests to con- struct the graph. The most notable example is the PC algorithm (named after its developers, Peter and Clark), which begins with a complete graph and progressively removes edges between nodes that are conditionally independent given set of other variables [Spirtes et al., 2000]. Constraint- based approaches typically result in a partially directed acyclic graph (PDAG), where some edges remain undirected due to equivalent DAG configurations.
Score-based methods employ scoring function to assess the fit of a DAG model to the observed data, aiming to identify the graph with the best score. Commonly used scoring functions, such as BIC, BDeu, and MDL, are decomposable, which facilitates local optimization for each variable. Notable algorithms in this category include the Greedy Equivalent Search (GES) [Chickering, 2002] and the K2 algorithm [Cooper and Herskovits, 1991].
A significant subset of cosee methods assumes a total ordering of the variables to expedite finding the optimal solution within this constraint, followed by a search among different order hy- potheses to locate the most fitting order. Teyssier and Koller [2005] demonstrated that with fixed ordering, the optimal solution could be computed polynomial time, avoiding the need for DAG consistency checks. Although searching the order space is computationally intensive, these meth- ods have outperformed traditional DAG-based searches. Subsequent studies have expanded on this framework [Xiang and Kim, 2013; Raskutti and Uhler, 2018; Squires al., 2020; Wang et al., 2021; Solus et al., 2021; Chen et al., 2019].
Hybrid methods integrate based and constraint- bbase approaches. They streamline the search for potential parent nodes for each variable by applying CI tests to narrow down the set of candidates. Examples of hybrid methods include Max-Min Hill Climbing (MMHC) [Tsamardinos er al., 2006] and PC [Gasse et al., 2014].
A.2 Differentiable structure learning
Zheng et al. [2018] introduced NOTEARS, which proposes a continuous characterization of the DAG constraint. This transforms the structure learning within the structural equation model (con- tinuous scoring function) into a differentiable constrained optimization problem. The authors used an augmented Lagrangian method to solve this problem in a linear SEM, observing superior perfor- mance compared to state-of -ort----rttttttt- structure learning solvers. They further extended this approach with an MLP learner to address nonlinear SEMs [Zheng et al., 2020]. Subsequent studies have advanced the field of differentiable structure learning by improving acyclicity characterization, de- veloping more powerful neural network architectures, and enhancing optimization approaches.
Yu al. [2019] formalized the structure learning task using a graphical neural network (GNN) and proposed GNN-based structure learning approach named DAG-GNN. A major advantage of DAG-GNN is its ability to handle both discrete data (modeled by Bayesian networks) and continu- ous data (modeled by SEMs). Zhu el al. [2019] introduced reinforcement learning approach for structure learning. Yu el al. [2019] used different polynomial function to characterize acyclicity, achieving better computational efficiency. Bello et al. [2022] proposed DAGMA, which employs log-determinant function, showing a stronger constraint on acyclicity. Ng et al. [2020] introduced a likelihood-based scoring function, demonstrating superiority over the regression-based scoring used in NOTEARS. Wei et al. [2020] developed a local search post-processing algorithm informed by the KKT conditions of the constrained optimization problem. Deng al. [2023a] further intro- duced a local search differentiable structure learning algorithm based on topological swap, similar to order-based search in combinatorial structure learning.
Distinct from these studies, this paper aims to enhance the field of differentiable structure learning by integrating more types of prior constraints. Current studies typically address straightforward prior information such as constraints of edges (Wei et al., 2020] and total ordering [Deng et al., 2023a]. However, real-world priors are often more ambiguous and less comprchensive. Therefore,
13

---

we consider partial orders, which are general enough to represent real-world priors on ordering relationships that may be contained in experimental settings or existing domain knowledge.
Appendix B Discussions of Ordering Prior in DBN
This section explores the connection between dynamic Bayesian Networks (DBNs) and the ordering prior discussed in this paper, and how this prior can be implemented through parameter freezing. DBNs assume that the observational data are time-series data containing m time slices. Given d variables. there are m X d nodes in the DBN, where each variable has one "copy" each time slice. The influence patterns among the variables vary according to different assumptions, with common premise being the order constraints of the time slices [Pamfil el al., 2020; Sun al., 2023; Yang et al., 2022]. Specifically, a variable in later time slice cannot affect one in an earlier time slice. This order constraint can be generally described by the following ordering type.
Definition 8 (Time-series ordering). In time-series ordering S, the entire set of variables is parti- tioned into distinct stages. Variables within the same stage do not have a defined ordering relative to each other, while variables in an earlier stage precede those in later stage.
In the time-series ordering, the partial order between any variables in different stages is known. For time-series ordering, it can be integrated into the structure learning by parameter freezing.
Theorem 2. graph G(W) is a DAG and satisfies time-series ordering S and only if h(W) and i = 0 for all (j.i) i) E St.
Proof. The aim is to prove the following equivalence:
h(W)- = 0 and Way = 0 for all (i,) E S+ + G(W) E DAG and X₃ ~ X2 $ G(W) for all (i.t) St.
Necessity (=):
1. If G(W) is a DAG, then by Proposition I in the main text, h(W) = 0. 2. If; ~ X, $ G(W) for all (i,) E St, this implies that there is no directed edge from to j for any (j.d) E St. Therefore, W 0 for all (j.i) St.
Thus, if G(W) is DAG and X₃ mm X, & G(W) for all (f,1) e St, then h(W) 0 and Wi, for all (j,i) E S
Sufficiency (=)):
1. If h(W) 0, then by Proposition 1 in the main text, G(W) is a DAG. 2. We need to show that Wa = 0 for all (j,i) S+ implies X; ~ Xj & G(W) for all (j,i) E St.
We prove this by contradiction. Assume that there exists a pair (v, E S+ such that X,, X. G(W). This means there is directed path from u to v in G(W).
Let the path be (fo. i.. 1g-1, ig) where in and ig precedes u in the partial order St. Therefore, there must exist at least one pair (ix, 4 in the path such that 1 is in earlier stage than it. This implies (fx+1, ik) S+ and hence W Weydees 0.
Since is in earlier stage than
However, this contradicts our assumption that Wi, 0 for all (j,t) E St. Therefore, our assump- tion is false, and it must be that X, X, & G(W) for all (j. E S+.
Thus, if (W) = 0 and Wi5 = 0 for all (j.t) E S+, then G(W) is DAG and X₁ ~ X, $ G(W) for all (j,1) S-
This result leads parameter freezing strategy for applying the time-series ordering into differen- tiable structure learning:
min F(W) subject to h(W) = 0 and Wi 0 for all (j, E S WeRoxd
(10)
14

---

Appendix C Proof of Main Results
C.1 Proof of Theorem
This section proves the equivalence of the constraint equality h (WW, O) as designed in Equation (9) to the adherence to the partial order constraint O.
Theorem 1. A graph G is DAG and satisfies for the function h defined by Equation (4) and h' defined by Equations (9b), (9c), and (9d).
of partial orders O if and only if .0)
Recall the construction of h': The function
1 ((WWO) = Σ h(A(W,o)
DEP(O-)
where P(O represents the set of maximal paths in O- o) returns a adjacent matrix that represents a graph by adding the path to the graph G(W),, denoted as E(G(A)) = (( Given that h(W) 2 by Equation (4), we have:
h' W'W O) = =0 MA(W.)) for o E P(O-)
(11)
The proof of Theorem completed by two statements. We consider the first one:
Lemma 1. A graph G is a DAG and satisfies a sequential orlering o = {(p), P2, .Pm)} if and only if graph G' is DAG where E(G')= = E(G) U..
Proof. Recall the equivalent constraints of the order constraint in Proposition 4, and we have the following objective prove:
G' E DAG for E(G") F(G) Uo - DAG and X5 ~ X; & G for (i.j) E
(12)
(=) We prove the necessity by contradiction. Suppose that the right side holds and G' is not a DAG. Consider a cycle (2, Ck. C1) in G' under the following
cases.
1) No edge in the cycle is contained in o. Then all these edges in the cycle belong to G by the condition E(G")= = E(G) o. This conflicts with the fact that G is DAG.
2) If some edges are contained in o and they form consecutive path (Cr1, Cr ( Cg In this case, the rest part of the cycle (Cqu Cor Cr,) is contained in the graph G. This forms directed path from Cq. to Cr, for (Cr, Cqi E ot, which conflicts with the condition of the right-hand side of Equality (12) X2 A X, & G for (i,j) é ot.
3) Some edges are contained in and do not form single consecutive path. Then them as a set of disjoint paths in sequence:
represent
.. To = {(Crr: Cr Gr ".. (Gq)) (Cru: Crat1, (.p), ... (Cr, Cry+1, , }}
where 1 s q, T:+1 I k for E (1,2, .1). Consider the rest parts of the cycle in G: = {(Cg) +1.-1... .r..,,,,,,))))))) Gr2), (Cqu+ 1g2+1.'" Cpa)) ........... (Cqu: Ck2 C1,
.r,) }}
Consider Cg. and Cret for arbitrary Since they are included in and is sequence, we have:
Either Cr4z)) ) or (Crua: Cy.) is contained in o
(13)
Recall that all the paths in TG belong to G. then the path (Cg, Cuttls Cras)) belongs to G. Combined with the right-hand condition in (12), we have (Cys Cri1) & ot. Then we have (CuesCoer) ) E o by (13). This conclusion holds for all i E (1,2, (note that r141 = rt). Then we have:
{Cog Crg), (Caz Cry). (Cm, c, at
(14)
Recall that paths in r. are contained in o, and we also have:
{(rr Cn)), (Crz: Cop)) ... (crt), Cyp Co+
(15)
Combining (14) and (15), we derive that cycle (cr, Cq. Gras" " CCy Cry) is contained in ot, which conflicts the premise that o is acyelic.
Since E(G) C E(G") and G is DAG, we have that G is DAG. Since the path o is contained in G", we have X; X, E G for all (i, ot. Then we have that no path X, ~ X, exists in G' as it will introduce a cycle. The proof is completed.
15

---

Now we consider the second statement:
Lemma 2. For the set P(O-) of all maximal paths of O the union of the transitive closures of these paths is the transitive closure of O: UOEP(O-) o+ 0+
Proof. We have ot So+ by that O CO Therefore UOEP(O-) _ S Then we prove O+ UOEPiO--) ot by contradiction. Suppose that 3(),j) E E such that (i,j) & UnEP(o-> o+_ We have that (i,j) (O-)+ by that (0-)+ O+ This indicates that path from to j exists in OF. Moreover, we have that this path does not belong to any maximal path of O by that (i,5) É UsEP(O-) o². This introduces contradiction since any path in a graph at least belongs to one of its maximal path (we can extend any path to maximal path).
Now we derive the result of Theorem 1 by these results. Consider the result of Lemma 1:
G' DAG for E(G") = B(G) Uo = G E DAG and Xj ~ X, $ G for (i,j) E of The left- ceft-hand condition equals h(A(W,o) = 0. Combining this with Equation (11), we have:
N'(, =0 + GE DAG and Xj X & G for (i,j) UoEp(o yo
With the result UoEP(O- yot = 0 from Lemma 3, we have:
W(W = = GE DAG and X, ~ X, E G for (1,5) E 0+ The path absence condition on the right-hand side is equivalent to adherence to O. Hence, we complete the proof of Theorem 1.
C.2 Proof of the rest statements
Proposition (Theorem in [Wei al., 2020]). The directed graph of a non-negative adjacency matrix B is a DAG if and only if hBB = 0 for any defined by (4).
Proof. Recall the definition of h(B):
d h(B) Trace( Σ BBB c >0
This function can be understood by interpreting the diagonal elements the matrix powers Bi, which represent the weighted č-length directed paths from variable to itself, essentially, a cycle. A matrix B represents a DAG if and only if there are no i-length cycles for any i E N+, evidenced by Trace (+)) = O. Consequently, Trace B*) 0 must hold for all i N+ if B describes DAG. The converse is supported by Lemma 3, which confirms that the absence of cycles ranging from I-length to d-length, characterized by Equation (4), sufficiently ensures the acyclicity of the graph.
Lemma 3. Any cyclic graph with d variables must contain cycle(s) with less than d length.
Proof. We prove this lemma by contradiction. Suppose that the cycle with the minimum length I >> d as (f,, i2, it, i.). Since there are d nodes, there exist at least two indexes in the cycle &p that refers to the same node, i.e., i = ip- Suppose that that q < p. then the new cycle (i1,".- .dg-1, i.. i by cutting the paths from ig to ip has a lower length. This confficts with that the original cycle has the minimum length.
Proposition 3. A graph G a DAG and satisfies total ordering π if and only if edge (u, v) does exist in G for all (v, u) E t
Proof. Firstly, we formalize this statement according to Proposition follows:
(u, v) & G for (v, u) E Ex+ + G(W) E DAG and X,, ~y X. G for (u, E ETT
The necessity (=) is straightforward by that X,, ~ X, & = (u,v) v)
G. For sufficiency
(=), employ proof by contradiction. Assume that there exists path (u, ug..... 2x) in G
16

---

that violates т,, such that (ug, u1) E x*. For u, and 1441, either (u,, U++1) E x or (u,+1, u:) E x given that the order of any pairwise nodes in contained in ग², Combined with the transitivity of or- ders, there must be at least one edge (u,, us+1) 1) E FT()) where (#++1, ;&) É xτ. This contradicts the condition that (u, v) & G for all (v,u) x-. To demonstrate the absence of cycles (DAG constraint), consider setting us u1, which similarly leads to contradiction under these condi- tions.
Proposition There exists at least one topological sort of DAG G that satisfies the partial order set O if and only if. for any order (i.j) in O+, X, is not an ancestor of X₃ in G.
Proof. (=) there exists a topological sort that satisfies O, then for any (i,5) O+ Xj is not an ancestor of X; in G.
Suppose there exists topological sort T of G that satisfies O For any (i,j) E O+ i must appear before j in the topological sort 7 because O represents a transitive closure of the order constraints. If X, were an ancestor of X; in G. there would be path from X; to X; In a topological sort, for any edge (u, v), u must appear before u. Therefore, if X5 were an ancestor of X, X, would appear before X, in the topological sort. However, this would contradict the fact that appears before j in the topological sort I" (as is related to j by O+). Thus, Xy cannot be an ancestor of X; in G.
(-) If for any order (i.j) in O+, Xy is not ancestor of X; in G, then there exists topological sort of G that satisfies O.
Assume for any (i.j) E O+ X, is not an ancestor of X, in G. This implies there is no directed path from Xj to X, for any (i.j) E O+). Construct a topological sort of G using a standard topological sorting algorithm (such as Kahn's Algorithm or Depth-First Search). During the construction, ensure that for any (i,j) E O, appears before j in the ordering. Since O+ does not create any cycles (because X, is not an ancestor of X,). the ordering respects the partial order O. The resulting topological sort satisfies the constraints of O by construction.
Proposition 4. No directed path X₁ ~4 X, exists in G(W) and only if (Ei o (WoW)) = O.
Proof. E/E (W o w'' is an instance of the acyclicity function defined in Equation (4). By the proof of Proposition 1, setting the matrix entry (i,j) to zero effectively blocks all paths of lengths ranging from I to d from X; to Xj, fulfilling the necessary condition for X; me X; & G(W). This condition also deemed sufficient due Lemma 4.
Lemma 4. If a directed path X; X2 exists in graph with d nodes, then directed path X; ~m X3 of length less than d must also exist.
The proof of Lemma 4 is similar that of lemma 3.
Appendix D
Implementation of the Proposed Method
This section presents the psudocodes of the implementations of the proposed method.
Algorithm Partial Order Constraint- based Differentiable Structure Learning
Require: Observational data E [gaad, A of partial orders O.
Ensure: DAG G.
W +- -Sovee minw F(W, D) subject h'(W, O) 0 by a backbone algorithm h/ is defined by Algorithm 2.
2: Construct G by adding edges (i. where [W, y y >> 0 the threshold value, which is set to 0.3 in experiments.
3: return G
17

---

Algorithm Augmented Acyclicity Characterization Function I RRdxd R
Require: A weighted matrix W E IRdxd, A set of partial orders O; An acyclicity characterization
function __dxd +
1: O < Derive the transitive reduction of O by Algorithm 4
2: G f Construct graph by adding edges (1,j) where (i.j) E O
3: result <
4: P <- Find all maximal paths in G by Algorithm 3
5: for each path in P do
6: W' + Replace the (i, element of W with r for each edge (i,j) E hyper-parameter that controls the strength of the order constraints.
DT> 0
7: result <- result + h(W")
8: end forreturn result
Algorithm 3 Find All Maximal Paths in DAG
Require: A directed acyclic graph G' = (V, E)
Ensure: A set of maximal paths in G
1: function TIINMAXXIAAPPATISS
2: Initialize an empty list all paths
3: Identify all nodes in G with no incoming edges start _onees
4: for each node u in start_noded nodes
5: Call DFS(u, ()
6: end for
7: return all all_paths
8: end function
9: function DFS(node, path)
10: Append node to palh
Initialize oetensionssfoore
False
12:
for each v such that there is an edge from node to do
Set extensions. farrnssffuuddd found True Call DFS(e, path)
14:
end for if not extensions fanissionsfoouddd then
16:
Add path all paths end if
D Path is maximal
18:
19:
Remove node from poth
Backtrack
20:
end function
Algorithm Derive Transitive Reduction a Relation
Require: set of ordered pairs O representing a relation.
Ensure:
Transitive reduction of O.
1: Compute R, the transitive closure O
2: Initialize T <- O
3: for each pair (i.j) E E do
4: for each pair (k:, E do
5: if i + and j # then if (i, k) E R and (k.j) E R then Remove (i,j) from T
6:
7:
8:
end if
9:
end
end for
11:
end for
return T'
18

---

Appendix E Complete Experimental Results
This section presents the complete experimental results and detailed experimental settings. The hyper-parameters of algorithms include: the threshold y 0.3 for the existence of an edge. the weight A 0.03 for LI regularization term, the weight X2 0.01 for L2 regularization term, the weight r in the proposed augmented acyclicity term, the maximum p value Pmux 10 for augment Lagrangian method. The NOTEARS-ML. uses an MLP with an input dimension d. hidden layer of size d 10, and output layer of size d, where d is the number of variables. The evaluation settings are detailed in the caption of each figure.
The evaluation metries used in the study include the following: Structural Hamming Distance (SHD), which counts the number of edges that differ between the recovered structure and the ground truth; True Positive Rate (TPR), defined as TP/TPP FN), where TP is the number of correctly recovered edges and FN is the count of missing or reversed edges; False Discovery Rate (FDR), calculated FP/(FP TP, where FP represents the number of extra edges; and the Fi-score, computed as 2- P/ + R), with R = TPR and P
FDR.
The runtime of the algorithm refers to the time taken generate the final result, specifically the time required for the acyclicity term h(-)) to reach a sufficiently small value (set to 10-8 in the experiments).
We first report two supplementary results regarding 1) the comparison of the pure path absence- based implementation partial order constraints shown in Equation (8) and 2) the selection of hyper-parameter 7 in Equation (9c). Following this, we report the supplementary results to those in the main texts.
Table 2: Comparison of path absence- and augmented acyclicity- partial ordering constraints for structure learning in terms of run time t (s) and output quality F1-score.
Prior
Metric
d=20
d=30
d=40
d=50
Na
1/F1
18.3 / 0.47
35.1 /0.51
4..54
71.6 /.6/0..49
0.1d
(s)
19.7 / 107.3
41.1 / 170.9
117.5 6523.0
0.42 / 0.39
0.56
0.48 0.52
0.5d
(s)
26.2/ 328.3
21.3/ 221.1
41.9/27188
106.7 / 4124.5
Fl
0.50 /555
0
0.59
0.52 0.52
(()
4.2/ 140.0
5..5
12.1/83.0
41.9 1475.3
Fl
0.71/0.71
0.75
0.72
0.70 0.70
E.1 Comparison of Path Absence- and Augmented Acyclicity-based Partial Order Constraints
We implemented Equation (8), which applies straightforward path absence constraints to enforce partial order, and compared its performance with our augmented acyclicity- based method. The results, averaged over repetitions, in terms of runtime and F1-score using NOTEARS are shown in Table The experimental settings include: ER-4 structure, linear data with Gaussian noise, sample size of 40, and a single-chained partial order with nodes 1d, 0.5d, d). Results are presented as Ours/Equation 8, with Prior Na representing the baseline (NOTEARS without prior constraints).
The results demonstrate that the method in Equation (8) achieves comparable output quality to our main approach, showing that effectively represents partial order constraints. However, as expected, Equation (8) exhibits significantly slower runtime. Interestingly. the most significant slowdown occurs when fewer variables are included in the ordering than the total variable set. This may be due to the method's 's disjoint integration with the acyclicity term, possibly causing the partial order term take longer to reconcile with the acyclicity constraint when the prior information insufficient.
F.2 Analysis of Selection of Virtual Edge Weight
The hyper-parameter > serves as the uniform weight for edges in the set P(O-), which are added solely to the augmented acyclicity term h'(W, O) and not to the data approximation term
19

---

Table 3: Variance of different properties in partial order-based structure learning with varying values.
7
4.E-01
1.E-04
2.E-01
2.E-06
4.E-07
1.E-09
4.E-09
1.E-0
5.E-11
6.E-09
3.E-09
7.E-05
1.E-12
0.E+00
A'
6.E.09
2.F.05
6.F.04
2.F.08
2.E.08
3.F.08
6.F.09
S.E.09
4.F.09
2.F.10
8.-008
4.E.00
1.F.02
5.F.02
F
9.6
5.E-03
4.E+03
12.9
12.7
16.9
11.7
11.7
11.5
11.7
8.E402
2.E+04
3,E+04
3.E+04
DAG?
V
V
v
Bidge
53
31
55
61
62
69
71
70
66
67
33
0.36
0.69
F(W). These edges, termed "virtual" edges, may not exist in the actual graph but are included in the "acy-graph" used to enforce acyelicity constraints. The following analysis highlights the theoretical impact of different values of
Small 7: When is too small, it fails to properly reflect the presence of virtual edges in the acy- graph, leading inadequate enforcement of prior information. This can result in reversed paths not being properly excluded, weakening the acyclicity constraint and potentially allowing cycles to form. Essentially, a very small removes the effect of virtual edges in P(O-), ). diminishing the strength of the acyelicity constraint and compromising the learning process.
Large On the other hand, if is large, it can disrupt numerical stability by overshad- owing small weights that signify absent edges. For example, consider a forbidden cycle p = W,,2W2,3W', 33.1. where W122 sence). This configuration results in V Ww.. = X r", making the influence of W1,2 on 33,1 large enough to enforce the absence of W3.1. even though the cycle should be considered broken due to the absence of W2.3. This misinterpretation can lead to the erroneous removal of edges, potentially producing an empty graph.
is set large value, while W2,3 r- (indicating edge ab-
We conducted experiments with varying values of r and observed the real acyclicity loss h, aug- mented acyclicity loss h', data approximation loss F, and output metrics such DAG condition, edge count, and F1 score. Results for an ER-4 graph with Gaussian noise model, node count d = 20, sample size 40, and edge threshold 7 0.1 support this theoretical analysis and presented in Table 3.
E.3 Supplementary Results
This section presents supplementary results to the main text, providing additional insights across complete datasets, various data settings, and methods used. The figures included, Figures 4-8, ex- pand on the analysis, offering more comprehensive understanding of the experimental outcomes.
20

---

csp
1.5
20
0.9
15
Structurel Hamming Distance (SHD)
10
0.8
0.5
0.7
1.5
100
F1 score
0.7
time (log
PM9
80
10
0.95
2.5
0.9
-04
100
0.75
80
1:15
60
0.5
0
20
30
40
50 20
30
40
50
30
40
50 20
30
40
50
20
40
50
30
(Number of Nodes)
(Number Nodes)
d. (Number of Nodes)
psro
2sp
exp
0.2
0.15
0.8
0.1
0.7
0.05
0.6
Aggee Discageeng Rate
0.7
225
True Positive
15
0.
0.
0.9
Method
3.04
0.02
+ NOTEARS- SEM
PPO-NOTEARS-1-50
0.2
0.55
PPO-NOTEARS-1-25
0.15
0.6
PRO-NOTEARS-III 1-100
0.55
0.5
20
30
50
20
40
50
30
40
20
30
30
(Number of Nodes)
d (Number of Nodes)
Figure 4: Results of single-chained ordering for NOTEARS with linear SEM. Structural discovery in terms of SHD (lower is better), F1-score (higher better), FDR (lower better). TPR (higher is better) and CPU time (logıo s). Rows: graph types. (ER,SF)-K represents /Erdäs-Rényi, scale-free) graphs with kd expected edges. Columns: noise types of SEM. Error bars represent standard errors over simulations. Method: PPO- NOTEARS- 1-p represents our method with the ordering of a single chain with size m = p%o.
21

---

$2655
osp
6/455
ssp
23150
0.8
15
Struchural Homming Distance (SID)
0.85
0.8
0.75
0.8
CPU (log 8
1.5
PH5
PNB
8
0.6
10
235
0.9
545
0.85
-02
1.4
0.78
80
0.76
60
1:5
0.72
08
40
0.4
0.68
0.2
40
50
(Number of Nodes)
d (Number of Nodes)
d (Number of Nodes)
28650
oup
giMss
esp
0.35
0.9
0.1
0.05
0.7
20.25
True Poeltive Rate
0.7
dae Discogass
PS
0.6
0.1
0.5
Method
0.06
0.9
0.04
DAGMA- SSM
0.02
6.8
PPO-DAGMA-1-50
PPO-DAGMA-1-75
0.35
PPO-DAGMA-I-IO
135
0.6
0.05
0.55
20
30
50.20
20
40
50
20
30
40
50.20
50
d (Number of Nodes)
d (Number of Nodes]
Figure 5: Results of single-chained ordering for DAGMA. Structural discovery in terms of SHD (lower is better), Fi-score (higher is better), FDR (lower is better), TPR (higher is better) and CPU time (logıo s). Rows: graph types. [ER,SF)- represents [Erdös-Rényi, scale-free) graphs with kdd expected edges. Columns: noise types of SEM. Error bars represent standard errors over simulations. Method: PPO-DAGMA-I I-p represents our method with the ordering of a single chain with size m = p%d.
22

---

rsp
2010
exp
eq
20
15
420
Structural Hamming Diet ante (SHD)
10
0.8
0.7
120
0.8
CPU time (loSie
100
281
0.7
783
-0
0.6
40
P1
0.98
16
0.94
0.9
0.58
0.75
5055
0.7
7:55
60
0.55
40
50
(Number of Nodes)
d (Number of Nodes)
(Number of Chains)
esp
puns
d-20 + d-50
d-30 CPU
0.9
0.15
0.8
C35
0.7
0.05
Palee Disugeery Rate
0.3
True Positive Rate
0.7
0.6
2XI
05
0.5
0.1
0.4
Method
NOTEARS-I Siner-SEM
30006
+ PPO-NOTEARS-I-50
PPO-NOTEARS-2555
0.02
+ PPO-NOTEARS-3-50
0.8
0.2
PPO-NOTEARS.5.50
PPO-NOTTEARS-I0-50
0.15
0.6
1.5
8.05
0.5
30
40
30 (Number Nodes)
40
(Number of Nodes)
Figure 6: Results multi-chainer orderings for NOTEARS with linear SEM. Structural discovery in terms of SHD (lower is better), F1-score (higher is better), FDR (lower better), TPR (higher is better) and CPU time (log s). Rows: graph types. (ER,SF)-K represents Rérdäs-Rényi, scale-free) graphs with kd expected edges. Columns: noise types of SEM. Error bars represent standard errors over simulations. Method: PPO- NOTEARS-I-50 represents our method using the ordering where the chain number I and the chain size
w 0.5d.
23

---

0.95
0.2
0.04
2.2
0.00
09
15
0.9
0.8
0.1
0.86
0.85
0.84
Sirwtirra Harniing Ditaace (SHD)
00
0.12
0.82
1.4
0.1
0.8
60
783
0.7
Disooeers
0.6
20
0.5
CPU timee
40
0.85
0.1
Thue
0.88
0.08
-60
1.3
0.89
288
0.06
225
0.7
2.55
235
22
0.75
0.7
0.8
120
80
0.7
MS
0.6
60
1.8
0.4
20
0.01
3.0
20
30
40
50
20
50
40
50
20
30
40
50
20
30
40
50
20
50
40
50
(Numzbr of Nodes)
d (Number Nodes)
(Namber of Nodee)
d (Nuumbrr Nodes)
4 (Nuumber of Nudes)
Method
NOTEARS-MLP
1-P7O-NOTEARS-1-500 P-PPO-NOTEARS--- 4-P7O-NOTEARRS-I-000
Figure 7: Results of single-chained Ordering for NOTEARS-MLP Structural discovery in terms of SHDD (lower better). Fl-score (higher is better), FDR (lower is better). TPR (higher is better) and CPU time (log10 s). Rows: graph types. (ER,SF)-K -k represents
Rénds- scale-free) graphs with kd expected edges. Error bars represent standard errors over 5 simulations. Method: SPO-NOTEARS--E 1-p represents our method with the ordering of a single chain with size m = =dhd.
6.64
0.95
25
6,92
0.9
0.15
0.9
20
2301
0.55
15
0.84
10
0.82
1
Steuctural Hammingg Dhelanoe
80
0.8
60
0.8
Pale Discover Bete
0.08
True Postiive Rote
0.7
0.06
40
0.6
0.04
26
13
0.5
80
0.12
0.8
80
0.8
525
0.06
0.08
0.7
20
0.75
0.04
0.02
0.6
10
155
0.3
120
0.8
100
0.06
80
0.7
0.06
0.5
125
60
0.6
0.04
20
15
20
30
40
50
20
30
40
50
20
30
40
30
20
30
40
50
7
(Numbor Nodrs)
d (Number Nodrs)
(Number of Nodes)
d (Namber of Nodes)
(Numher of Chains)
Method
+ NOTEARS-MLP + PPO-NOTEARS- 1-50 Fi PRO-NOTRARS-2-50
+ d-20 + d-50
PRO-NOTEARS.3.50 + PPO-NOTEARS.5.50
PRO-NOTEARS-10050
+ d:30 CPU
Figure 8: Results of multi-chained orderings for NOTEARS-MI.P. Structural discovery in terms of SHD (lower is better), Fi-score (higher is better), FDR (lower is better), TPR (higher is better) and CPU time (logıg s). Rows: graph types. (ER,SF)-k -k represents (Erdös-Réne Rényi, scale-free) graphs with kd expected edges. Error bars represent standard errors over 5 simulations. Method: SPO-NOTEARS-L-50 represents our method using the ordering where the chain number is / and the chain size is m = 0.5d.
24

---

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: The main claims made in the abstract and introduction demonstrated both theoretically and practically.
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 can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper lists the limitations of the proposed method in the Appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create 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 au- thors 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. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren'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?
25

---

Answer: [Yes]
Justification: The full set of assumptions is provided and the proof of all theoretical results under these assumptions provided in Appendix.
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 or referenced in the statement of any theo- rems.
The proofs can either appear in 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 comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided not)?
Answer: [Yes]
Justification: All the critical algorithms of implementation of the proposed method is pro- vided, and all the critical parameter settings are provided in Appendix.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily a new algorithm, the paper should make it clear how to 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 way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to 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.
26

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: All the codes of implementations and evaluations are provided in the supple- mentary file.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines (https://nips.cc/pbblic/ quides/CooeSubbiissiooooo/l
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: httpppuiiccuuuudeeeooeuuuuiiiias
for more details. The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, 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
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?
Question:
Answer: [Yes]
Justification:
All the detailed hyperparameters are provided the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: Multiple simulations are made and the error bars are reported in the result.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
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 with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably 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 figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Sufficient information on the computer resources is provided in the experi- ment section, including CPU, GPU and memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g.. preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
No ethics issues are with this paper.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS 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 (c.g., there is 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:
A relevant discussion is provided in Appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not 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 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 mitiga- tion 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 deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
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 re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
All the datasets and algorithms used in this paper are correctly cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswitheode.comm wwwpswitthode.coomaaataeee has cu- rated licenses for some datasets. Their licensing guide can help determine the license of dataset.
29

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/modell as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS 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.
30


Reviews:
[{"review_id": "SUog5DL9E1", "reviewer": "Reviewer_99Ub", "summary": "This paper introduces an approach to integrate partial order constraints into differentiable structure learning for causal discovery. The key contributions are:\n* Formulating an equivalent constraint set of path prohibitions to implement partial order constraints in the graph space.\n* Proposing an efficient method to integrate partial orders by augmenting the acyclicity constraint.\n* Proving the theoretical correctness and completeness of the proposed augmented acyclicity constraint.\n* Demonstrating the effectiveness of the method through experiments on both synthetic and real-world datasets.\n\nThe authors show that their method can significantly improve the quality of recovered causal structures while maintaining computational efficiency, especially for long sequential orderings. They also demonstrate that using partial order constraints can reduce the required sample size for accurate causal discovery on real-world data.", "questions": "My overall take of this paper is that it could be a nice contribution as it appears to effectively handle partial ordering constraints for differentiable structure learning methods. However, some rewriting might be deemed necessary.\n\n* The definition of the SEM is confusing, in eq.(1) you might want to define $z$ as well, and I also find eq.(2) confusing, the definition of W_kj is not a real number but then you are taking an inner product in the function for D_ij. First, why is it necessary to write the sample version? Second, it is clearer if you state what kind of models work for the results in the sequel.\n\n* Several results are known or are trivial. Theorem 1 is already proved in Wei et al. (2020); Lemma 1 and Theorem 2 are straightforward results; Theorem 3 follows also directly from prior results in Wei et al. (2020). My point here being that theorems in a paper are typically representative of novel results and that correspond to the main contributions. In this case, I failed to see this. Theorem 4 should perhaps be Theorem 1 and the only theorem in the paper.\n\nMinor things:\n* L21: reform -> reformed\n* L25: Ng et al., 2020, do not propose an aciclicity characterization.\n* You can also consider citing Deng et al. 2023 (\"Global Optimality in Bivariate Gradient-based DAG Learning\") as they formally show, albeit in the bivariate case, how the continuous framework can succeed in recovering the underlying DAG.", "limitations": "Limitations are addressed in Appendix F.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper addresses an important gap in differentiable structure learning by enabling the integration of partial order constraints.\n* The augmented acyclicity approach handles long sequential orderings more efficiently, addressing a key limitation of a naive implementation.\n* The experiments cover both synthetic and real-world datasets, demonstrating the method's effectiveness across various scenarios.\n* Results on the Sachs dataset show significant improvements in structure recovery with reduced sample sizes, highlighting the method's impact for real-world applications.\n* The proposed method is designed as a plug-and-play module that can be integrated with various differentiable structure learning algorithms.", "weaknesses": "* Several statements are known or follow easily from existing results. \n* As noted in the limitations section, the method's efficiency can degrade with complex partial order structures involving multiple chains.\n* The paper doesn't extensively discuss how sensitive the method is to incorrect or conflicting partial order priors, which is possible in applications.\n* While the paper compares to baselines without priors, it doesn't compare to other methods that might incorporate different types of prior knowledge.\n* The paper doesn't provide an in-depth analysis of how sensitive the results are to the choice of hyperparameters, particularly τ in the augmented acyclicity term.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and valuable feedback. We begin by addressing your critical point regarding the analysis of the hyper-parameter $\\tau$ as highlighted in Weakness 5. Following this, we will address your other questions and concerns. Here are our responses:\n\n**Weakness 5: Analysis of the Influence of Hyper-Parameter $\\tau$**\n\nWe agree that an in-depth analysis of the hyper-parameter $\\tau$ is essential. $\\tau > 0$ serves as the uniform weight for the edges in $\\mathcal{P}(\\mathcal{O}^-)$, which are added solely to the augmented acyclicity term $ h'(W,\\mathcal{O}) $ and not to the data approximation term $ \\mathcal{F}(W) $.  Here's our analysis of the sensitivity of results to $\\tau$:\n\n- Keep in mind that $\\tau$ represents the weight of *virtual* edges, which may not be present in the actual graph but are included in the graph used for enforcing the acyclicity constraint, referred to as the **acy-graph**.\n\n- **Small $\\tau$**: When $\\tau$ is too small, it fails to indicate the presence of virtual edges in the acy-graph effectively. This can make the absence of reversed paths not adequately enforced, losing prior information and even breaking acyclicity. In essence, a small $\\tau$ can be seen as removing all edges in $\\mathcal{P}(\\mathcal{O}^-)$ from the acy-graph instead of adding these edges, thus weakening the acyclicity constraint and **leading to cycles**.\n\n- **Large $\\tau$**: Conversely, a large $\\tau$ can disrupt numerical stability by ignoring small weights that signify edge absences. For instance, we consider an edge to be absent if with a weight below a threshold $r$, and we have a forbidden length-3 cycle $ p = W_{1,2}W_{2,3}W_{3,1} $, setting $W_{1,2} = \\tau$ to a large value while $W_{2,3} = r^-$ (indicating absence), can result in the influence of $W_{1,2}$ on $W_{3,1}$ being incorrectly propagated through backpropagation. Specifically, $\\nabla_{W_{3,1}} p = \\tau \\times r^-$ becomes large enough to enforce the absence of $W_{3,1}$, even though this cycle is already absent due to the absence of $W_{2,3}$. This misinterpretation can lead to the erroneous removal of edges, potentially **resulting in an empty graph**.\n\n- We conducted experiments with varying $\\tau$ values and observed the real acyclicity loss $ h $, augmented acyclicity loss $ h' $, data approximation loss $ \\mathcal{F} $, and output's DAG condition, edge count, and F1 score. Results for an ER-4 graph with Gaussian noise model, node count $ d = 20 $, sample size $ n = 40 $, and edge threshold $ \\gamma = 0.1 $ are reported here and align with our discussion.\n\n  | $\\tau$        | 0.0  | 0.1  | 0.2  | 0.3      | 0.4      | 0.5      | 1.0      | 2.0      | 3.0      | 4.0      | 5.0  | 6.0  | 7.0   | 8.0  |\n  | ------------- | ---- | ---- | ---- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | ---- | ---- | ----- | ---- |\n  | $h$           | 0.4  | 1e-4 | 0.2  | 2e-6     | 4e-7     | 1e-9     | 4e-9     | 1e-10    | 5e-11    | 6e-9     | 3e-9 | 7e-5 | 1e-12 | 0.0  |\n  | $h^\\prime$    | 6e-9 | 2e-5 | 6e-4 | 2e-8     | 2e-8     | 3e-8     | 6e-9     | 5e-9     | 4e-9     | 2e-10    | 8e-8 | 3.9  | 1e-2  | 5e-2 |\n  | $\\mathcal{F}$ | 9.6  | 5e+3 | 4e+3 | **12.9** | **12.7** | **16.9** | **11.7** | **11.7** | **11.5** | **11.7** | 8e+2 | 2e+4 | 3e+4  | 3e+4 |\n  | $\\text{DAG?}$ | ❌    | ❌    | ❌    | ✓        | ✓        | ✓        | ✓        | ✓        | ✓        | ✓        | ✓    | ✓    | ✓     | ✓    |\n  | @Edge         | 53   | 31   | 55   | 61       | 62       | 69       | 71       | 70       | 66       | 67       | 33   | 1    | 0     | 0    |\n  | F1            | 0.27 | 0.27 | 0.36 | 0.61     | 0.65     | 0.56     | 0.68     | 0.69     | 0.70     | 0.69     | 0.23 | 0.0  | 0.0   | 0.0  |\n\n**Questions**\n\n- Thank you for pointing out the missing note regarding noise $z$ in the SEM and the confusion caused by the sample version definition. We have removed the sample version SEM definition and clarified the applicable models within the context, covering both linear and nonlinear models.\n\n- Thank you for pointing out the novelty issues with our statement presentation. We have clearly cited sources for statements not originally proposed. Theorems 1, 2, and 3 have been reclassified as propositions, with Theorem 4 now presented as the sole Theorem 1.\n\n- The typo on L21 has been corrected, and the citation for Ng et al., 2020 has been moved to the correct position.\n\n- Thank you for your suggestion. We find the work by Deng et al. (2023) highly relevant for demonstrating the theoretical promise of the continuous framework in DAG learning and have added it to the introduction section.\n\n**Addressing Other Weaknesses**\n\n- **Weakness 1**: Addressed above.\n- **Weakness 2**: Acknowledged in the limitations section.\n- **Weakness 3**: As noted in the Broader Impact section (line 656), the method is sensitive to prior errors due to its hard constraint on partial orders. However, based on our empirical experience with edge constraints, using a soft constraint alternative also has limitations in addressing prior errors and may reduce the benefits derived from prior information.\n- **Weakness 4**: Analyzing different types of priors is theoretically complex because they influence structure learning in varied ways. Most existing methods treat priors as secondary and struggle to handle complex priors beyond edge constraints. However, edges are typically the aim of discovery from data rather than being available as rich, pre-existing priors. Therefore, we believe a detailed analysis of different priors is beyond the scope of this paper.\n\nThank you again for your insightful feedback. Please let us know if you have further concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i4UPI7pNY5", "reviewer": "Reviewer_jpLj", "summary": "The paper provides a solution for imposing partial ordering information into differentiable DAG learning, which is a very important problem. It also proposes an efficient implementation based on rigorous theoretical justification. With this prior information, even with fewer samples, better structural recovery can be achieved in experiments.", "questions": "1. Lines 164-166: \"Merely forbidding edges...not contained in $\\mathcal{O}$\" I'm not sure I understand this point. Could you provide some examples to illustrate this argument?\n2. In Eq (6), $(i,j)\\in \\mathcal{O}^+$ indicates $i\\prec j$, meaning there is no directed edge from $j$ to $i$. However, in Equation (8b), $(i,j)\\in \\mathcal{O}^+$ implies there is no directed edge from $i$ to $j$. Do I understand this correctly? If so, please make notation is consistent throughout the paper.\n3. What Equation (9c) means here? $W - W\\circ W_o$ can be regarded as remove edge in path $o$, then we add $\\tau W_o$ back?\n4. In the experiments, do you test $p$ is small, such as $p = 10$?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "1. This paper imposes partial ordering into the differentiable DAG learning problem. It is a very interesting problem to the community.\n2. The paper is theoretically well-supported.\n3. This paper addresses computational issues when imposing partial ordering into differentiable DAG learning. The experiments indicate that better structural recovery can be achieved with the information of partial order.", "weaknesses": "1. I found there are some points in the paper that are hard to understand. A mild suggestion is to add examples to illustrate these concepts, which would make the paper more readable. For instance, toy examples to explain what $\\mathcal{O}^+$ and $\\mathcal{O}^-$ are. Especially in section 3.3, where there are many definitions, theorems, and lemmas, examples would help readers grasp the points and have a better understanding of the paper.\n2. Typo: Line 204 $\\mathcal{O}^-)$ should be corrected to $\\mathcal{O}^-$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and valuable questions. Here are our responses:\n\n**1. Explanation on the Difficulty of Integrating Partial Order Constraints**\n\nThe statement \"Merely forbidding edges that violate $ \\mathcal{O}^+ $ is insufficient for compliance, as it is possible to *walk* from a variable to a preceding variable in $\\mathcal{O}$ through another variable whose order with others is not contained in $\\mathcal{O}$.\" highlights why simply constraining edge absence $(x_i,x_j)$ for all $(j,i)\\in \\mathcal{O}^+$ is **not enough** to fully satisfy partial order constraints.\n\nFor example, consider four nodes $1,2,3,4$ with a partial order set $\\mathcal{O}=\\{(1,2),(2,3)\\}$. We forbid all inverse edges in $\\mathcal{O}^+$, which are $\\{(2,1),(3,2),(3,1)\\}$. Despite this, directed paths violating the partial order $(1,2)$ can still exist, such as the path $(2,4,1)$. Such paths can be constructed by traversing nodes not in $\\mathcal{O}$, like node $4$ in this case. This demonstrates why integrating a total order is straightforward, while integrating partial orders is challenging due to variables whose order relations with others are unknown.\n\n**2. Typo Revision**\n\nThank you for your comment. The typo in Eq. 8b has been noted. For a partial order $(x_i,x_j) \\in \\mathcal{O}^+$, there should not be any directed path from $x_j$ to $x_i$. We will thoroughly review all mathematical presentations to ensure correctness.\n\n**3. Explanation on Eq. 9c**\n\nYou are correct about the operation in Eq. 9c. This operation aims to assign uniform weight $\\tau$ to all virtual edges added to the augmented acyclicity term, indicating their existence. This serves two functions: **1) Avoid accidental edge removal:** The weight of an edge in $W$ can be negative, risking erroneous edge removal in the augmented acyclicity constraint and losing prior information. **2) Maintain stability:** The influence of the acyclicity term on edge recovery can be sensitive to weights, so we use uniform virtual weights to ease hyper-parameter selection. More details and analysis are provided in our reply to **Weakness 5 to Reviewer 99Ub**.\n\n**4. Supplementary Experiment with Small $p$**\n\nWe conducted a supplementary experiment with $p=10$, indicating a small number of variables in the partial order sequence. Considering the random generation of partial orders from the topological ordering of a DAG, the partial order sequence may not address critical order relationships that contribute to better structure recovery when the variable number is small. For instance, if two nodes $x,y$ do not have an ancestor-descendant relation, then either $x \\prec y$ or $y \\prec x$ is correct, making the specification of such partial orders less impactful.\n\nWe performed ten repetitions of the random generation of single-chained partial orders with $p=10$ (containing $0.1d$ variables in the sequence). The output quality results are reported individually for each repetition. Settings here are an ER-4 graph with a Gaussian noise model and the sample size $n=40$. Prior Na denotes the baseline without prior (NOTEARS). Cases where integrating the prior partial order yields better results than the baseline are highlighted in bold. Please note that all results presented are from a single repetition rather than an average of multiple repetitions.\n\n| Prior | Repeat | d=20 (SHD / F1)   | d=30 (SHD / F1)   | d=40 (SHD / F1)    | d=50 (SHD / F1)    |\n| ----- | ------ | ----------------- | ----------------- | ------------------ | ------------------ |\n| Na    | 1      | 68 / 0.43         | 98 / 0.48         | 122 / 0.52         | 165 / 0.46         |\n| $p=10$  | 1      | **64** / **0.46** | **93** / **0.53** | 136 / 0.47         | **160** / **0.49** |\n|       | 2      | 68 / **0.45**     | **93** / **0.52** | 125 / 0.51         | 175 / 0.45         |\n|       | 3      | **64** / **0.46** | **85** / **0.56** | **113** / **0.56** | 169 / 0.44         |\n|       | 4      | **66** / **0.46** | **94** / **0.52** | 137 / 0.45         | 170 / 0.46         |\n|       | 5      | 70 / 0.41         | **85** / **0.58** | 122 / **0.53**     | **162** / **0.49** |\n|       | 6      | **66** / **0.47** | 100 / **0.51**    | **121** / **0.53** | **152** / **0.53** |\n|       | 7      | **67** / 0.40     | **87** / **0.56** | 131 / 0.48         | 183 / 0.44         |\n|       | 8      | **63** / **0.48** | **78** / **0.60** | 126 / 0.51         | **160** / **0.51** |\n|       | 9      | 73 / 0.36         | **95** / **0.52** | 132 / 0.48         | **158** / **0.49** |\n|       | 10     | 70 / 0.40         | **94** / **0.50** | **119** / **0.54** | 165 / 0.46         |\n\n**Addressing Weaknesses**\n\nThank you for the suggestion to improve the paper's clarity. We will add more examples to help readers understand the core concepts of the paper. Additionally, we will thoroughly check and correct all typos.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "icGbeoJc6v", "reviewer": "Reviewer_SXfo", "summary": "This paper contributes interesting new theoretical results for the field of differentiable graph structure learning and showcases how to practically exploit those results for improved structure learning. Differentiable structure learning converts the combinatorial optimisation problem of finding the correct graph structure of a problem into an optimisation problem by parametrising an adjacency matrix according to the structural equation model (SEM). Existing methods focused on enforcing DAG structures on these parametrised matrices such that DAG graphs can be learned. This paper instead focuses on a new type of constraints, trying to enforce that the learned graphs adhere to a given set of orders on the underlying variables. It is first proven (Theorem 3) that adherence to a set of orders $\\mathcal{O}$ is equivalent to a constraint comprised of $|\\mathcal{O}^+|$ terms, which is deemed computationally infeasible. Then the paper continues to prove its main result, showing that adherence to the set of orders $\\mathcal{O}$ is also equivalent to a constraint over maximal paths in the transitive *reduction* $\\mathcal{O}^-$ of $\\mathcal{O}$. Finally, this theoretical result is implemented such that it can take any existing SEM-based structure learning algorithm and augment it with given orders. The increase in performance is shown on a number of synthetic and more realistic structure learning benchmarks when comparing with and without the exploitation of given orders.", "questions": "1. Can you clarify which theoretical statements are novel by specifying if Theorems 1, 2, and 3, and Lemma 1 were already known?\n\n2. Theoretical clarifications:\n   + I believe the proof of Lemma 2, specifically the necessity part, is not fully complete. The second case (line 543), where some edges of the cycle are contained in $o$, implicitly seems to assume that there are at least 2 disjoint paths in the cycle with edges in $o$, i.e. $|r_o| = l \\geq 2$ because it is written that $q_i  < r_{i + 1}$. If $l = 1$, then $r_2$ does not exist and this inequality does not make sense. Hence, the case where $l = 1$ seems missing, although I think that a shorter version of a similar argument could apply.\n   + I do not see how the argument in lines 567-569 follows from Lemma 3 together with Equation 16. Concretely, Lemma 3 **only** seems to say that simultaneous adherence to $o^+$ for all $o \\in \\mathcal{P}(\\mathcal{O}^-)$ is equivalent to adherence to $\\mathcal{O}^+$, **not** that adherence to $o$ for all $o \\in \\mathcal{P}(\\mathcal{O}^-)$ is equivalent to adherence to $\\mathcal{O}$. This confusion might be due to the ambiguity of notation as described in Remark 3, but it is important to validate Theorem 4. From Remark 3, it seems that you do not consider a sequential ordering, such as $o$, to be a partial ordering as it is not transitive (line 199). However, then $o$ and $o^+$ are not the same, implying that adherence to $o^+$ is stronger than adhering to $o$. Similarly, it is unclear whether $\\mathcal{O}^+ = \\mathcal{O}$. **This confusion can have strong implications on the impact of the paper and is my primary concern. If the reasoning in lines 567-569 is invalid, the proposed objective in Equation 9b only enforces a weaker version of ordering adherence than the one enforced by Equation 8b.**\n\n3. Experimental clarification: What is the precise meaning of \"run time\" here? Is it the time required to learn the provided solutions? If so, what is the stopping condition for the algorithm?\n\n4. Can you elaborate on the computational trade-off between using Equation 8b compared to Equation 9b? Do you believe there are cases where this trade-off is negligable or even in favour of Equation 8b?\n\n5. Example 1 is not clear to me as it discusses the effect of removing **step 1** from the overall algorithm. However, it seems to be that **step 2** does not make sense without  **step 1**. So to be precise, why does $h'$ degenerate into $h(\\mathcal{A}(W, \\mathcal{O}^-)$ when removing **step 1**?\n\nI want to stress that I am very open to significantly increase my overall score (and my scores of soundness and contribution) to a full accept if the authors can address my questions. In particular, the seeming uncertainty around the validity of Theorem 4 is my main reason for borderline rejection because of its potential impact. If Theorem 4 does end up being weaker than stated, I believe an empirical comparison between Equation 8b (which surely enforces strict partial order adherence) and Equation 9b is warranted.", "limitations": "The limitations are very well described in the appendix. I would only have like for it to be (partly) present somewhere in the main body of the paper, especially how any optimisation-based paradigm can not fully guarantee constraint satisfaction.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The structure of the paper is very clear and hence reads well. As someone who is not deeply familiar with the details of differentiable structure learning, the incremental and logical build-up of the preliminaries is also appreciated. In general, the authors put significant effort into making the paper self-contained, improving readability further. \n\n2. The paper is very formal in its notation and methodology, without going overboard on mathematical notation or jargon. Again, this allows for someone not intimately familiar with the topic to more easily follow the proofs and reasoning of the paper.\n\n3. The idea of the paper is certainly interesting and novel, especially considering the reference that incorporating orders can significantly reduce the search space of possible structures and the hardness of structure learning [1]. The overall idea of trying to incorporate prior knowledge of any form also ties in well with the rising popularity of neurosymbolic methods [2, 3].\n\n4. The authors clearly also put in a lot of effort to ensure a reader can follow the theoretical arguments on a high level throughout the text without getting lost in mathematical intricacies during reading. The many intermediate comments and examples are very helpful to keep the story focused, which is never easy when the road to a general result requires multiple intermediate results.\n\n5. The empirical evidence is very convincing. I thank the authors for including aggregates and variability metrics over multiple runs, which is sadly not a given anymore.\n\n[1] Teyssier, M., & Koller, D. (2005, July). Ordering-based search: a simple and effective algorithm for learning Bayesian networks. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (pp. 584-590).\n\n[2] Garcez, A. D. A., & Lamb, L. C. (2023). Neurosymbolic AI: The 3 rd wave. Artificial Intelligence Review, 56(11), 12387-12406.\n\n[3] Marra, G., Dumančić, S., Manhaeve, R., & De Raedt, L. (2024). From statistical relational to neurosymbolic artificial intelligence: A survey. Artificial Intelligence, 104062.", "weaknesses": "While I overall did enjoy reading the paper, I do have a number of questions and concerns:\n\n1. The paper does not clearly distinguish its own theoretical contributions from previously known results. While I appreciate all lemmata and theorems are proven either in the main body or in the appendix, I would like to see clear statements of which results were already known, as some seem to relate to the provided references. In particular, I suspect Theorems 1, 2, and 3 were already proven before, though I am unsure about 3. Same for lemma 1. If some or all of these results are indeed novel, then explicitly stating they are can only further increase the impact of the paper.\n\n2. Theorem 2 is a nice result showing how knowing a total ordering can indeed considerably reduce the complexity of a DAG structure learning task. However, it is not used in the rest of the paper. If Theorem 2 is not a new result, I would remove it to improve the flow of the paper and give more space for further clarifications.\n\n3. I am not sure if I can agree with Remarks 2 and 6, where it is stated that the result of Theorem 3 does not lead to a computationally feasible solution while that of Theorem 4 does. It seems that using Equation 8b introduces a number of terms that is quadratic in the number of variables, as it is bounded by the number of possible pairs over those variables. While I can see that using Equation 9b is certainly more efficient for a single sequential ordering, the picture is less clear when $\\mathcal{O}$ consists of many (sequential) orderings. In general, the trade-off between orderings in $\\mathcal{O}^+$ or maximal paths in $\\mathcal{O}^-$ does not seem clear, especially since no bounds on $|\\mathcal{P}(\\mathcal{O}^-)|$ are given.\n\n4. While I generally agree with the provided proofs of all statements, there are a couple of places where I do have concerns about the validity of the results (see precise questions below). Importantly, I am unsure whether the exact statement of the main Theorem 4 holds, leading me to maintain a lower score for now until my questions are clarified.\n\n5. The experimental section certainly considers enough datasets and data-generating configurations, but it does seem to miss one important comparison. I would have liked to see an experimental confirmation of the trade-off between using Equation 8b compared to Equation 9b, for both run time and general performance. Especially since the complexity of 8b is used as a motivation to discard it in favour of 9b. Moreover, some of the metrics could be better explained, even if only in the appendix. For example, I am not familiar with the details of the structural Hamming distance (SHD) or False Discovery Rate (FDR) and the notion of run time is also ambiguous.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and invaluable questions. We begin with addressing your major question on the proof part in the paper (point 2 in the Question section). Then, we will respond to your other questions point-by-point.\n\n**Regarding Eq. 8 and the comparison results:** We have implemented the method in Eq. 8 and derive the comparison results. Due to text length limitations, please refer to **Point 1 of our reply to Reviewer FFcG** for these details.\n\nHere are our responses and revisions:\n\n**2. Theoretical Clarifications:**\n\n2.1 **Proof of Lemma 2:**\n   Thanks for your clarification on the rigor of the proof of Lemma 2. We have added the proof of the missing case when $|r_o| = l = 1$ here and also to the paper.\n\n\n   - If some edges are contained in $o$ and they form a consecutive path $(c_{r_1},c_{r_1+1},\\cdots,c_{q_1})$. In this case, the rest part of the cycle $(c_{q_1},c_{q_1+1},\\cdots,c_{r_1})$ is contained in the graph $G$. This forms a directed path from $c_{q_1}$ to $c_{r_1}$ for $(c_{r_1},c_{q_1})\\in o^+$, which conflicts with the condition of the right-hand side of Equality (12) $X_j\\leadsto X_i \\notin G \\text{ for }(i,j)\\in o^+$. (Note that there is a typo in the original paper as $X_i\\leadsto X_j \\notin G \\text{ for }(i,j)\\in o^+$, which is fixed.)\n\n2.2 **Sequential Ordering and Transitive Closure:**\n   \nIt seems that you concern about whether a graph satisfying $o$ equals satisfying its transitive closure $o^+$.\n\n   - $G$ satisfies partial order set $\\mathcal{O}$ if and only if any path $X_j \\leadsto X_i\\notin G$ for all $(i,j)\\in \\mathcal{O}^+$ (Lemma 1, line 141). For a graph $G$ satisfying $\\mathcal{O}$, we consider its transitive closure $\\mathcal{O}^+$. Given that $(\\mathcal{O}^+)^+$ is still $\\mathcal{O}^+$, $G$ also satisfies $\\mathcal{O}^+$.\n\n   - Besides, we derive Theorem 4 from Eq. 12 proved in Lemma 2 (line 538):\n\n     $G^\\prime \\in \\text{DAG for } E(G^\\prime) = E(G) \\cup o \\iff G \\in \\text{DAG and } X_j\\leadsto X_i \\notin G \\text{ for }(i,j)\\in o^+$\n\n     Note that the left-hand condition equals $h(\\mathcal{A}(W,o))=0$. Combining with Eq. 11 (line 533), we derive:\n\n      $h^\\prime (W,\\mathcal{O})=0 \\iff G\\in \\text{ DAG and } X_j \\leadsto X_i \\notin G \\text{ for } (i,j)\\in \\cup_{o\\in \\mathcal{P}(\\mathcal{O}^-)} o^+$\n\n     With the result $\\cup_{o\\in \\mathcal{P}(\\mathcal{O}^-)} o^+ = \\mathcal{O}^+$ from Lemma 3, we have:\n\n     $h^\\prime (W,\\mathcal{O})=0 \\iff G\\in \\text{DAG} \\text{ and } X_j\\leadsto X_i\\notin G \\text{ for }(i,j)\\in \\mathcal{O}^+$\n\n     The path absence condition on the right-hand side is equivalent to adherence to $\\mathcal{O}$. \n\n   - As for Remark 3 (line 199), it is to help readers understand our identical representation for paths and partial orders, which does not influence the transitive nature of them. We will clarify this in the paper.\n\nPlease let us know if you have further questions.\n\n**1. Clarify the Novelty of Theorems:**\n\n   Thanks for pointing out the novelty of Theorems. Theorem 1 is previously proven by Wei et al. [1]. We re-illustrate this Theorem from a pure graphical perspective to help understand the connection between orderings and path existences. Theorem 3 can be derived by the proof of Theorem 1. Your concern reminds us to prioritize the novelty; therefore, we will change the display of Theorems 1, 2, and 3 to Proposition 1, Proposition 2, and Corollary 3, and also explicitly clarify the reference to the previous work. Proposition 2 is a trivial result in graph theory, illustrated in the paper to help readers understand the typical complexity from integrating partial orders compared to total ordering, which will also be clarified in the paper. Lemma 1 functions an important result to bridge the ordering space and graph space, which is also a trival result in the Graph Theory and will be clarified in the paper.\n\n   [1] Wei, D., Gao, T., & Yu, Y. (2020). DAGs with No Fears: A closer look at continuous optimization for learning Bayesian networks. Advances in Neural Information Processing Systems, 33, 3895-3906.\n\n**3. Experimental Clarifications:**\n\nYes, the run time is the time consumed for the algorithm to learn the provided solutions. The stopping condition is that the acyclicity loss $h$ reaches a threshold small enough to justify the acyclicity of the graph, which is set to $1 \\times 10^{-8}$ in the experiment.\n\n**4. Trade-off Between Equations 8b and 9b:**\n\nThanks for your interesting question. When all partial orders are graphically separate, meaning no sequential orderings longer than 1 exist in the partial order set, the two formulations have close numbers of terms (Eq. 9b has one fewer than Eq. 8b). In this case, the computational difference can be negligible. However, we still do not have an idea to construct a case where Eq. 8b is preferred. Please let us know if you have further considerations.\n\n**5. Example 1 Clarification:**\n\nThanks for your question. You are correct that step 2 does not exist without step 1, which will be clarified in the paper.\n\n- The detailed process of our operation is to split the graphical structure of the transitive reduction $\\mathcal{O}^-$ (as adherence to $\\mathcal{O}^-$ equals adherence to $\\mathcal{O}$) of the partial order set into paths (sequential orderings), and then add them individually to the acyclicity term to form the augmented acyclicity. \n\n- If we do not split the graphical structure of the partial order set into paths, the operation will directly add all the edges in $\\mathcal{O}^-$ to the acyclicity term. This operation corresponds to the formulation $h(\\mathcal{A}(W,\\mathcal{O}^-))$, where the function $\\mathcal{A}$ adds the edges in $\\mathcal{O}^-$ to $W$.\n\n\nThank you again for your insightful feedback, which has greatly helped in refining our paper. Please let us know if further clarifications are needed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iFpZrPrN40", "reviewer": "Reviewer_FFcG", "summary": "This paper studies the problem of learning DAGs from observational data with incorporating prior knowledge represented as partial order constraints by extending from existing continuous DAG learning methods such as NOTEARS and DAGMA. The paper first presents a method that shuts down the corresponding cells of the adjacency matrix of the DAG according to the permutations of the partial orders and then proposes an augmented acyclicity-based method with improved efficiency. The paper conducts experiments on simulated datasets and a real-world dataset. In addition, the paper also provides comprehensive theoretical motivations and analysis to the research problem and the proposed method.", "questions": "Please see my comments above.", "limitations": "The authors adequately addressed the limitations", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem studied in the paper is novel and has significance in practice. To my knowledge, it is a new (sub-)problem of DAG discovery from observational data, which has not been studied before.\n\n2.  The proposed method is well motivated both conceptually and theoretically. The notations and definitions are rigorously defined.\n\n3. The experiments are comprehensive and support the claims of the paper.", "weaknesses": "Not all my comments below are weaknesses and some of them are questions.\n\n1. In Eq 8a, a (relatively) straightforward method is introduced, which is argued to be less efficient, motivating the development of the augmented acyclicity-based method. Is the straightforward method implementable? If so, it would be better to compare it with augmented acyclicity-based method in terms of the performance and efficiency.\n\n2. I find it hard to fully understand Eq 9c and 9d. What's the definition of $\\mathcal{A}(W, o)$ and why does it have the formulation in 9c? What's $W_{o,i,j}$? Does it mean $W$ is a three dimensional tensor?\n\n3. To learn $W$, one needs the algorithm to be differentiable in terms of $W$. For the method in Eq 8a, one might need to backpropagate gradients through permutations. If so, how can we do this without continuous relaxation? For the augmented acyclicity-based method, it seems that one needs to conduct a few algorithms (Algorithm 2, 3, 4). Are the operations in these algorithms differentiable in terms of $W$? More discussions are needed.\n\n4. The proposed method introduces a new hyperparameter $\\gamma$. How to determine $\\gamma$ in practice as there is no ground truth to do validation?\n\n5. In the experiments of real-word data, Linear NOTEARS is used as the baseline. How do we know the (non)linearity in the real data?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and insightful questions.  Here are our responses:\n\n1. **Comparison with Eq. 8a:** \n\n   We have implemented Eq. 8 and compared it with our augmented acyclicity-based method. The results (average of 3 repetitions) using NOTEARS are reported here. Settings are: ER-4, linear data with gauss noise, sample size is 40, single-chained partial order with nodes $[0.1d,0.5d,d]$. **Results are reported as Ours/Eq. 8. Prior Na denotes the baseline (NOTEARS without prior).**\n\n\n| Prior  | Metric | d=20           | d=30           | d=40           | d=50             |\n| ------ | ------ | -------------- | -------------- | -------------- | ---------------- |\n| Na     | *t*/F1 | *18.3*/.47     | *35.1*/.51     | *44.7*/.54     | *71.6*/.49       |\n| $0.1d$ | t (s)  | **19.7**/107.3 | **41.1**/170.9 | **65.8**/316.5 | **117.5**/6523.0 |\n|        | F1     | .42/.39        | .49/.52        | .56/.54        | .48/.52          |\n| $0.5d$ | t (s)  | **26.2**/328.3 | **21.3**/221.1 | **41.9**/271.8 | **106.7**/4124.5 |\n|        | F1     | .50/.53        | .60/.62        | .59/.57        | .52/.52          |\n| $d$    | t (s)  | **4.2**/140.0  | **7.2**/56.5   | **12.1**/83.0  | **41.9**/1475.3  |\n|        | F1     | .71/.71        | .75/.75        | .72/.72        | .70/.70          |\n\n\n   - The results show that the method in Eq. 8 produces comparable output quality with our main approach, indicating that it can correctly represent the partial order constraint.\n   - As expected, Eq. 8 has significantly slower run time. Interestingly, the worst efficiency occurs with fewer variables than the total variables in the ordering, possibly due to its disjoint manner with the acyclicity term. This might (not very clear) cause the partial order term to take more time to balance with the acyclicity term when the prior is not sufficient.\n\n2. **Explanation on $\\mathcal{A}(W,o):$**\n\n   $\\mathcal{A}(W, o)$ sets the edges in the path $o$ to a uniform weight to indicate their existence.\n\n   - $W_{o,i,j}$ is the $(i,j)$th element of $W_o$ (as illustrated in Notations), a mask matrix where edges in $o$ are 1 and others are 0.\n   - For $\\mathcal{A}(W, o)$ in Eq. 9c, we remove the original weights in $W$ for the edges in $o$ by $W - W \\circ W_o$, and then add the edges in $o$ with a uniform weight $\\tau$ by $W - W \\circ W_o + \\tau W_o$. This operation 1) avoids the sum of $\\tau>0$ to negative weights that can lead to *accidental removal* of edges, and 2) ensures numerical stability by uniforming the weights.\n\n3. **Differentiability of Algorithms:**\n\n   Thanks for your insightful question. Indeed, transforming a discrete constraint to a continuous one typically requires some continuous relaxation. The differentiable nature of our constraint terms is illustrated as follows.\n\n   - In Eq. 8a, the prior information of partial orders is transformed into the sum of multiple path absence terms for each pair in the transitive closure $\\mathcal{O}^+$ of partial orders. Each path absence term is naturally continuous because the structural negative constraint aims to set corresponding structural parameters to strictly 0 without requiring additional relaxation. For example, to forbid an edge $(x_i, x_j)$, we add a penalty $\\lambda|W_{i,j}|$ to push it towards 0, similar for path absence. Conversely, for edge existence, a threshold is typically used to confirm its presence, with a possible penalty being $\\lambda \\text{ReLU}(\\text{thr}-|W_{i,j}|)$.\n\n   - For the augmented acyclicity method, Algorithms 3 and 4 preprocess $\\mathcal{O}$ to derive $W_o$, and Algorithm 2 calculates the augmented acyclicity term with respect to the continuous function presented in Eqs. 9b and 9c, thus ensuring the differentiability.\n\n4. **Selection on Hyper-Parameter**\n\n   We assume you are referring to $\\tau$ in Eq. 9c, a new hyperparameter introduced by our method. All other hyperparameters remain the same as in NOTEARS. Here is how to select $\\tau$ without ground truth:\n\n   - Start with a relatively small value and incrementally increase it, observing the **number of recovered edges** by the algorithm. Choose $\\tau$ values that maintain a stable number of recovered edges.\n   - Due to text limitations, please refer to our reply to **Weakness 5 to Reviewer 99Ub** for an in-depth analysis. The optimization process is sensitive to $\\tau$; too small a $\\tau$ can lead to a weaker acyclicity constraint and result in cycles, while too large a $\\tau$ can erroneously enforce the absence of edges. Fortunately, the stable range of $\\tau$ is relatively wide, as indicated in the experiment results and related discussions in the reply to Reviewer 99Ub.\n\n5. **Nonlinear Results on Sach**\n\n   - Indeed, we do not know the (non)linearity of data in practice. Hence, we add an experiment using NOTEARS-MLP to fit possible nonlinear functions in the Sach-853 dataset. The MLP layers are $11, 11 \\times 10, 1$, with L1-reg weight of 0.1 and L2-reg weight of 0.03. Results:\n\n   |             | SHD  | F1   | TPR  |\n   | ----------- | ---- | ---- | ---- |\n   | NOTEARS-MLP | 39   | 0.21 | 0.35 |\n   | PPO-1-6     | 40   | 0.29 | 0.53 |\n   | PPO-1-8     | 26   | 0.29 | 0.35 |\n   | PPO-1-11    | 17   | 0.44 | 0.41 |\n\n   - The nonlinear baseline without prior performs much worse than the linear method, likely due to noise or unobserved influences in real-world data. However, integrating more partial orders improves SHD and F1 scores, leading to a structure closer to the ground truth. This indicates the effectiveness of using partial orders to improve nonlinear models.\n\nThank you again for your insightful feedback, which has been invaluable in refining our paper. Please let us know if any further clarifications or additional information are needed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper describes a method of incorporating partial order constraints into differential DAG learning. The authors devise a mechanism to incorporate these constraints into the acyclic constraints, highlight why partial ordering constraints pose significant difficulty, and develop a technique to impose the constraints in a more efficient manner.  After author discussion, reviewers were uniformly positive, viewing the method as novel and with practical significance.  Reviewers also offered several constructive suggestions to improve the presentation.
Decision: Accept (poster)