Differentiable Structure Learning with Partial Orders

Authors: taiyu  ban
lyuzhou  chen
xiangyu  wang
xin  wang
derui  lyu
huanhuan  chen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-06 12:38:31

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.

Main paper: 
 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, 2000] . Traditionally, it has been approached as a combinatorial optimization problem dominated by independence tests and score-and-search methods [Heinze-Deml et al., 2018] . Zheng et al. [2018] reformed it as a continuous optimization problem through a novel characterization of the acyclicity constraint in a differentiable form. Subsequently, numerous studies have proposed various learner architectures [Yu et al., 2019; Zhu et al., 2019; Zheng et al., 2020] , acyclicity characterizations [Yu et 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 as known gene activation sequences in genetics [Olson, 2006] , standard treatment sequences in healthcare management [Denton et al., 2007] , and sequential seasonal weather patterns in meteorology [Bruffaerts et al., 2018] . Such prior information can be generally formalized as a set O = {(x, y) | x, y ∈ X} of partial orders, where the binary relation (x, y) represents that variable x precedes y in the ordering, denoted as x ≺ 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 2 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.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 continuous 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 et al. [2023a] use a 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 implemented 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 a feasible way to apply partial orders in differentiable structure learning. However, for a sequential ordering with m variables, there are( m 2 )paths to be forbidden in the equivalent constraint. This complexity makes it impractical to develop constraints on path prohibitions individually, 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. Concretely, 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 to 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 constraints 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 applicable to all continuous methods in the differentiable structure learning context. • We address the misalignment between the hypothesis space of differentiable structure learning and partial order constraints by converting them into an equivalent form of path prohibition constraints. By formalizing the continuous characterization of this equivalent constraint, we show its limited practicality in dealing with long sequential orderings. • To efficiently integrate long sequential orderings, we introduce a 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. 
notations and preliminaries: 
 Notations In the following illustrations, we denote W i,: , W :,j , and W i,j to represent the ith row, jth column, and (i, j)th element of a matrix W , respectively. If a matrix symbol includes a subscript, like W s , we represent its elements as W s,i,j . For operations resulting in a matrix, such as W 1 + W 2 , we denote elements of the resulting matrix as (W 1 + W 2 ) i,j . For simplicity, the symbol (i, j) is used contextually: it can refer to a partial order X i ≺ X j or to a directed edge (X i , X j ) 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 = {X 1 , X 2 , . . . , X d }, and the edge set E(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 a function of its parent variables in G and an independent noise component:EQUATIONwhere Pa G j = {X i | X i ∈ X, (X i , X j ) ∈ E} denotes the set of parent variables of X j in G, and z j represents noise that is independent across different j. Denoting the structure of G as a weighted adjacent matrix W ∈ R d×d , where W i,j ̸ = 0 equals that (X i , X j ) ∈ E(G), we have:X j = f j (W :,j , X, z j ) (2)Given a set of samples D ∈ R m×d generated from this model with either linear or nonlinear functions in {f j }, we next describe the process of learning the structure of G in a differentiable manner.Differentiable structure learning The objective of structure learning is to deduce the DAG structure represented by the weighted adjacency matrix W ∈ R d×d from the data D generated by a specific set of functions f . We define all parameters characterizing W and f as θ and the graph as G(W (θ)), and we formalize the optimization problem of structure learning as follows:min θ F(D, f θ (D)) subject to G(W (θ)) ∈ DAG (3)where F is the score function, such as the least squares and Bühlmann, 2014] . For clarity, we emphasize the target W and rewrite it as F (W ). Similarly, the symbol G(W (θ)) denoting the graph is simplified as G(W ). The acyclicity degree of the graph can be characterized by a series of continuous functions for a non-negative matrix B:F(D, f θ (D)) = 1 2m ∑ m i=1 ∥D -f θ (D)∥ 2 F [Lohh(B) = Trace ( d ∑ i=1 c i B i ) , c i > 0 (4)For this acyclicity characterization, Zheng et al. [2018] [Wei et al., 2020] ). The directed graph of a non-negative adjacency matrix B is a DAG if and only if h(B) = 0 for any h defined by (4).(B) = -log det(sI -B) + d log s. For W ∈ R d×d , 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(W • W ). Proposition 1. (Theorem 1 inAccording to this result, the constraint G(W ) ∈ DAG can be implemented by the continuous equality h(W ) = 0. This transformation converts the structure learning problem into a continuous optimization problem with an equality constraint, formulated as:min W ∈R d×d F(W ) subject to h(W ) = 0(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 order-based score-and-search method is a critical research direction in this context. It is founded on the principle that structure learning is no longer NP-hard when the total ordering of variables is 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 et 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.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 a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
differentiable structure learning with partial orders: 
 This section introduces the integration of partial order constraints into the continuous DAG optimization framework. First, we convert the constraints from the ordering space into an equivalent form in the DAG space. Next, we discuss the limitations of direct characterizations of these equivalent constraints. Finally, we present an efficient approach to integrate partial order constraints and illustrate its theoretical correctness and completeness.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 is a binary relation ≺ on S which is a subset of S × S. For all elements x, y, and z in S, the following properties are satisfied:Reflexivity: x ≺ x for every x in S; Antisymmetry: If x ≺ y and y ≺ x, then x = y; Transitivity: If x ≺ y and y ≺ z, then x ≺ z.For the structure, if x ≺ y, then y cannot be the ancestor of x; that is, no directed path exists from y to x 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 2 (Transitive closure). For a set S and a binary relation R ⊆ S ×S, the transitive closure of R, denoted by R + , is defined asR + = ∪ ∞ n=1 R n . R n is defined recursively by: R 1 = R, R n+1 = R • R n , R • T = {(x, z) ∈ S × S | ∃y ∈ S such that (x, y) ∈ S and (y, z) ∈ T }.Remark 1. The transitive closure O + of a set of partial orders O encompasses all orders either directly contained in or inferable through transitivity from O. Now, we consider the following result from graph theory, which is essential for transforming order constraints into structural constraints.Proposition 2. 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 j is not an ancestor of X i in G.With this statement, the structure learning problem with partial orders O can be implemented by its equivalent constraint set of path prohibitions, formalized as:min W ∈R d×d F(W ) subject to h(W ) = 0, X j ⇝ X i / ∈ G(W ) for all (i, j) ∈ O + (6)whereX j ⇝ X i / ∈ G(W ) indicates that no directed path exists from X j to X i in G(W ).Subsequently, we introduce this constraint's continuous characterization and discuss its limitations.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 a permutation π of all the variables, with π(i) denoting the index of the variable in the ith position. X π(i) precedes X π(j) if and only if i < j.For total ordering, the order relationship between any pair of variables is contained in the transitive closure π + . This property allows for a simple implementation of the constraint of π by edge prohibition, as illustrated below: Proposition 3. A graph G is a DAG and satisfies total ordering π if and only if edge (u, v) does not exist in G for all (v, u) ∈ π + .This edge absence constraint on G(W ) can be directly implemented by setting the corresponding parameters in W to zero, resulting in the following formulation:min W F(W ) subject to W π(i),π(j) = 0 for all i ≥ j (7)In this case, structure learning becomes an 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. 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 i ⇝ X j exists in G(W ) if and only if ( ∑ d l=1 (W • W ) l ) i,j = 0.With this statement, we can formalize the optimization problem in Equation ( 6) as follows: ) 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 computational 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).EQUATIONThis observation underpins the need to develop a more efficient method to ensure that the structure learning process remains computationally feasible for long sequential orderings.This section introduces an efficient method to characterize partial orders, distinct from directly representing the equivalent path prohibitions. We first introduce some critical concepts. 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)}, its transitive closure is O + = O ∪ {(1, 4), (2, 4)}, and its transitive reduction isO -= O \ {(1, 3)}. Definition 5. Let G = (V, E) be a graph. A source is a vertex in V with no incoming edges, i.e., {v ∈ V : deg -(v) = 0}. A sink is a vertex with no outgoing edges, i.e., {v ∈ V : deg + (v) = 0}. Definition 6 (Maximal Path). Let G = (V, E) be a graph with a node set V and edge set E. A path p = (v 1 , . . . , v k ) with (v i , v i+1 ) ∈ E is considered a maximal path if v 1 is a source, v k isa sink, and the path is not a proper subsequence of any other path from v 1 to v k . Definition 7. The transitive closure of a path p = (v 1 , . . . , v k ), denoted as p + , is the set of all ordered pairs (v i , v j ) for 1 ≤ i < j ≤ k. 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, j), as both node reachability in 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, j) | (i, j) ∈ 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 as follows (see Appendix D for detailed implementations):min W F(W ) subject to h ′ (W, O) = 0 (9a) h ′ (W, O) = ∑ o∈P(O -) h(A(W, o)) (9b) A(W, o) = W + τ W o -W • W o (9c) W o,i,j = [(i, j) ∈ o] (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 1 if condition P holds and 0 otherwise. τ > 0 is a hyperparameter used for adjusting the weight in gradient calculation.Remark 5. Recall that h(W ) ≥ 0 by Equation (4). Then we have thath ′ (W, O) = 0 is equivalent to h(A(W, o)) = 0 for o ∈ 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) = 0. Specifically, we use a series of partial order-augmented acyclicity constraints h(A(W, o)) = 0 for o 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 acyclicity 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 1 , p 2 , • • • , p m )} if and only if graph G ′ is a DAG where E(G ′ ) = E(G) ∪ o.This lemma states the equivalence of h(A(W, o)) = 0 to adherence to the sequential ordering o. Now consider the following statement. Theorem 1 shows the correctness and completeness of the equality h ′ (W, 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 1. Split the partial order constraint O into sequential orderings.Step 2. Ensure that these sequential orderings are maximal paths in O -. IfStep 1 is removed4 , and we directly add all the edges in O -to G(W ) for augmented acyclicity, h ′ will degenerate intoh(A(W, O -)). This introduces extra orders outside of O, as indicated in the following example.Example 3. Assume that h ′ (W, O) ≡ h(A(W, O -)). Consider a partial order set O = {(1, 2), (3, 4)} and a DAG G(W ) with edges E(G(W )) = {(2, 3), (4, 1)}. Obviously, G(W ) satis- fies O. Consider the graph constructed by adding edges in O -(where O -= O) to G(W ), i.e., the graph of the matrix A(W, O -). Its edge set is O ∪ E(G(W )) = {(1, 2), (2, 3), (3, 4), (4, 1)} and contains a cycle (1, 2, 3, 4, 1). This makes h ′ (W, O) ≡ h(A(W, O)) ̸ = 0 by Proposition 1.In this case, a legal DAG that satisfies O is forbidden by the constraint h ′ (W, O) = 0, indicating that extra constraints beyond the prior are introduced. In other words, Step 1 guarantees the necessity of the constraint equality for partial order O. For Step 2, it guarantees the sufficient adherence to O. If this step is removed, some order constraints of O can be lost. See the following case.Example 4. Consider a partial order constraint setO = {(1, 2), (2, 3), (4, 2)}. Suppose that it is di- vided into two sequential orderings o 1 = (1, 2, 3) and o 2 = (4, 2), where o 2 is not the maximal path of O -. Then consider graph G(W ) with edges {(1, 2), (3, 4)}. We have that E(G(A(W, o 1 ))) = {(1, 2), (2, 3), (3, 4)} and E(G(A(W, o 2 ))) = {(1, 2), (3, 4), (4, 2)}. Both graphs are DAGs satis- fying h(A) = 0 by Proposition 1. Then we have h ′ (W, O) ≡ h(A(W, o 1 )) + h(A(W, o 2 )) = 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 ′ (W, O) = 0. This indicates that some orders in ) factors as discussed in Remark 2. Note that the computational complexity of h ′ (W, O) can increase with multiple sequential orderings, which is evaluated in the following section.O + are not specified by h ′ (W, O) = 0 ifQuestion: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: The full set of assumptions is provided and the proof of all theoretical results under these assumptions are 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experiments: 
 We evaluate our module for applying prior partial order (PPO) on linear NOTEARS [Zheng et al., 2018] , NOTEARS-MLP [Zheng et al., 2020] , and DAGMA [Bello et al., 2022] . It is named as 'PPOalg-l-p', where alg is the backbone algorithm, and l,p are settings on partial orders. Representative results are reported here, and the complete results are available in 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 et al., 2005] . For computational resources, linear NOTEARS and DAGMA are executed on a 32-core AMD Ryzen 9 7950X CPU at 4.5GHz, while NOTEARS-MLP uses an NVIDIA GeForce RTX 3090 GPU, both with a 32GB memory limit. We conduct five simulations for each synthetic structure and one simulation for the data and partial order constraints for each structure.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 T X + z, X ∈ R d using noise models {Gaussian (gauss), Exponential (exp)}. Observational samples D ∈ R n×d are then generated with the sample size n = 4d. For nonlinear cases, uniformly random weights are assigned to weighted adjacency matrices W 1 , W 2 , W 3 . Based on these matrices, samples are generated using X = tanh(XW 1 ) + cos(XW 2 ) + sin(XW 3 ) + z with z ∼ N(0, 1). The sample size is set to n = 20d. The parameter τ in Equation ( 9c) is set to 1.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 to derive a total ordering π. We then randomly select l chains, each denoting a sub-ordering randomly generated from π. Here, l is the number of chains and m is the size of each chain. We first investigate the case of a single chain of ordering and then the case of multiple chains of orderings. For single-chained ordering, l = 1 and m is in {0.5d, 0.75d, d} (where d is the number of nodes). For multi-chained ordering, l is in {1, 2, 3, 5, 10} and m is fixed at 0.5d.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 are presented in Figure 2 .Output quality. Our method demonstrates notable superiority over algorithms without prior information in terms of output quality in most cases, with the advantage becoming more pronounced as the number of nodes in the ordering chain increases. This confirms the effectiveness of our approach 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 structure 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-MLP 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.The results for SHD, F1-score, and run time using linear NOTEARS and NOTEARS-MLP with multi-chained orderings are presented in Figure 3 . The output quality demonstrates similar trends to 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, run time increases and then decreases as the number of chains grows. This pattern results from the increasing complexity of gradient calculations for the constraint term h ′ , 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 can be covered by a longer chain, which leads to fewer maximal paths in its transitive reduction, resulting in better time efficiency. The dataset provided by Sachs et 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 experimental resources, we selected the first s data samples for testing, where s ∈ {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 τ in Equation (9c) is set to 3.The structural evaluation metrics reported in Table 1 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. Remarkably, 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 of the proposed partial order constraint-based differentiable structure learning approach in conserving experimental resources in scientific research contexts.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 conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: All the critical algorithms of implementation of the proposed method is provided, and all the critical parameter settings are provided in Appendix.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors 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 be possible for other researchers to have some path to reproducing or verifying the results. • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
discussion: 
 Limitations and future directions Despite the theoretical correctness and completeness of the proposed method for integrating partial orders in differentiable structure learning, there are some practical limitations.First, the augmented acyclicity constraint h ′ (W, O) = 0 cannot be strictly satisfied during the optimization 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 inherent 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 efficiency can be impacted by partial orders with complex structures. This is evident from the experimental results involving multi-chained 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 a sharp increase in the number of constraint terms in the augmented acyclicity constraint. Fortunately, real-world ordering priors typically do not exhibit such complex structures and can usually be captured by a few chains. To enhance time efficiency in such cases, a more refined characterization method could be 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 or developing more efficient characterizations.This paper enhances the field of differentiable structure learning by enabling this framework to apply priors of partial order constraints. We systematically analyze the related challenges of applying flexible order constraints and propose a novel and effective strategy to address them by augmenting the acyclicity constraint. We present a theoretical proof confirming the correctness 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-known real-world dataset further emphasize its potential in uncovering more accurate causal mechanisms with reduced experimental resources.The proposed method allows researchers across various scientific fields to specify ordering priors, enhancing causal discovery with state-of-the-art 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 a 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-economic events are used as priors, the resulting causal model may be misleading, affecting policy decisions based on such a model.A.1 Combinatorial optimization of structure learning Traditional combinatorial optimization of structure learning includes constraint-based, score-based, and hybrid methods. Constraint-based methods utilize conditional independence (CI) tests to construct 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 a set of other variables [Spirtes et al., 2000] . Constraintbased approaches typically result in a partially directed acyclic graph (PDAG), where some edges remain undirected due to equivalent DAG configurations.Score-based methods employ a 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 score-based methods assumes a total ordering of the variables to expedite finding the optimal solution within this constraint, followed by a search among different order hypotheses to locate the most fitting order. Teyssier and Koller [2005] demonstrated that with a fixed ordering, the optimal solution could be computed in polynomial time, avoiding the need for DAG consistency checks. Although searching the order space is computationally intensive, these methods have outperformed traditional DAG-based searches. Subsequent studies have expanded on this framework [Xiang and Kim, 2013; Raskutti and Uhler, 2018; Squires et al., 2020; Wang et al., 2021; Solus et al., 2021; Chen et al., 2019] .Hybrid methods integrate score-based and constraint-based 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 et al., 2006] and H 2 PC [Gasse et al., 2014] .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 (continuous 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 performance compared to state-of-the-art 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, developing more powerful neural network architectures, and enhancing optimization approaches. Yu et al. [2019] formalized the structure learning task using a graphical neural network (GNN) and proposed a 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 continuous data (modeled by SEMs). Zhu et al. [2019] introduced a reinforcement learning approach for structure learning. Yu et al. [2019] used a different polynomial function to characterize acyclicity, achieving better computational efficiency. Bello et al. [2022] proposed DAGMA, which employs a 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 et al. [2023a] further introduced 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 comprehensive. Therefore, 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.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 × d nodes in the DBN, where each variable has one "copy" in each time slice. The influence patterns among the variables vary according to different assumptions, with a common premise being the order constraints of the time slices [Pamfil et al., 2020; Sun et al., 2023; Yang et al., 2022] . Specifically, a variable in a 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 a time-series ordering S, the entire set of variables is partitioned 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 a later stage.In the time-series ordering, the partial order between any two variables in different stages is known. For a time-series ordering, it can be integrated into the structure learning by parameter freezing.Theorem 2. A graph G(W ) is a DAG and satisfies time-series ordering S if and only if h(W ) = 0 and W i,j = 0 for all (j, i) ∈ S + .Proof. The aim is to prove the following equivalence:h(W ) = 0 and W i,j = 0 for all (j, i) ∈ S + ⇐⇒ G(W ) ∈ DAG and X i ⇝ X j / ∈ G(W ) for all (j, i) ∈ S + .1. If G(W ) is a DAG, then by Proposition 1 in the main text, h(W ) = 0. 2. If X i ⇝ X j / ∈ G(W ) for all (j, i) ∈ S + , this implies that there is no directed edge from i to j for any (j, i) ∈ S + . Therefore, W i,j = 0 for all (j, i) ∈ S + . Thus, if G(W ) is a DAG and X i ⇝ X j / ∈ G(W ) for all (j, i) ∈ S + , then h(W ) = 0 and W i,j = 0 for all (j, i) ∈ S + .1. If h(W ) = 0, then by Proposition 1 in the main text, G(W ) is a DAG. 2. We need to show that W i,j = 0 for all (j, i) ∈ S + implies X i ⇝ X j / ∈ G(W ) for all (j, i) ∈ S + .We prove this by contradiction. Assume that there exists a pair(v, u) ∈ S + such that X u ⇝ X v ∈ G(W ).This means there is a directed path from u to v in G(W ).Let the path be (i 0 , i 1 , • • • , i q-1 , i q ) where i 0 = u and i q = v. Since v is in an earlier stage than u, v precedes u in the partial order S + . Therefore, there must exist at least one pair (i k , i k+1 ) in the path such that i k+1 is in an earlier stage than i k . This implies (i k+1 , i k ) ∈ S + , and hence W i k ,i k+1 ̸ = 0.However, this contradicts our assumption that W i,j = 0 for all (j, i) ∈ S + . Therefore, our assumption is false, and it must be that X i ⇝ X j / ∈ G(W ) for all (j, i) ∈ S + .Thus, if h(W ) = 0 and W i,j = 0 for all (j, i) ∈ S + , then G(W ) is a DAG andX i ⇝ X j / ∈ G(W ) for all (j, i) ∈ S + .This result leads to a parameter freezing strategy for applying the time-series ordering into differentiable structure learning: min W ∈R d×d F(W ) subject to h(W ) = 0 and W i,j = 0 for all (j, i) ∈ S + (10)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:∪ o∈P(O -) o + = O + Proof. We have o + ⊆ O + by that o ⊆ O -⊆ O. Therefore ∪ o∈P(O -) o + ⊆ O + . Then we prove O + ⊆ ∪ o∈P(O -) o + by contradiction. Suppose that ∃(i, j) ∈ O + such that (i, j) / ∈ ∪ o∈P(O -) o + .We have that (i, j) ∈ (O -) + by that (O -) + = O + . This indicates that a path from i to j exists in O -. Moreover, we have that this path does not belong to any maximal path of O -by that (i, j) / ∈ ∪ o∈P(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 be a maximal path). Now we derive the result of Theorem 1 by these results. Consider the result of Lemma 1:G ′ ∈ DAG for E(G ′ ) = E(G) ∪ o ⇐⇒ G ∈ DAG and X j ⇝ X i / ∈ G for (i, j) ∈ o +The left-hand condition equals h(A(W, o)) = 0. Combining this with Equation ( 11), we have:h ′ (W, O) = 0 ⇐⇒ G ∈ DAG and X j ⇝ X i / ∈ G for (i, j) ∈ ∪ o∈P(O -) o +With the result ∪ o∈P(O -) o + = O + from Lemma 3, we have:h ′ (W, O) = 0 ⇐⇒ G ∈ DAG and X j ⇝ X i / ∈ G for (i, j) ∈ O +The path absence condition on the right-hand side is equivalent to adherence to O. Hence, we complete the proof of Theorem 1.Proposition 1. (Theorem 1 in [Wei et al., 2020] ). The directed graph of a non-negative adjacency matrix B is a DAG if and only if h(B) = 0 for any h defined by (4).h(B) = Trace( d ∑ i=1 c i B i ), c i > 0This function can be understood by interpreting the diagonal elements of the matrix powers B i , which represent the weighted i-length directed paths from a 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 ∈ N + , evidenced by Trace(B i ) = 0. Consequently, Trace(B i ) = 0 must hold for all i ∈ N + if B describes a DAG. The converse is supported by Lemma 3, which confirms that the absence of cycles ranging from 1-length to d-length, as characterized by Equation ( 4), sufficiently ensures the acyclicity of the graph.Proof. We prove this lemma by contradiction. Suppose that the cycle with the minimum length l > d as (i 1 , i 2 , • • • , i l , i 1 ). Since there are d nodes, there exist at least two indexes in the cycle i q , i p that refers to the same node, i.e., i q = i p . Suppose that that q < p, then the new cycle(i 1 , • • • , i q-1 , i p+1 , • • • , i 1by cutting the paths from i q to i p has a lower length. This conflicts with that the original cycle has the minimum length.(u, v) does not exist in G for all (v, u) ∈ π + .Proof. Firstly, we formalize this statement according to Proposition 4 as follows:(u, v) / ∈ G for (v, u) ∈ π + ⇐⇒ G(W ) ∈ DAG and X u ⇝ X v / ∈ G for (v, u) ∈ π + The necessity (⇐=) is straightforward by that X u ⇝ X v / ∈ G =⇒ (u, v) / ∈ G.For sufficiency (=⇒), we employ a proof by contradiction. Assume that there exists a path (u 1 , u 2 , . . . , u k ) in G that violates π, such that (u k , u 1 ) ∈ π + . For u i and u i+1 , either (u i , u i+1 ) ∈ π + or (u i+1 , u i ) ∈ π + given that the order of any pairwise nodes in contained in π + . Combined with the transitivity of orders, there must be at least one edge (u i , u i+1 ) ∈ E(G) where (u i+1 , u i ) ∈ π + . This contradicts the condition that (u, v) / ∈ G for all (v, u) ∈ π + . To demonstrate the absence of cycles (DAG constraint), consider setting u k = u 1 , which similarly leads to a contradiction under these conditions.Proposition 2. 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 j is not an ancestor of X i in G.Proof. (=⇒) If there exists a topological sort that satisfies O, then for any (i, j) ∈ O + , X j is not an ancestor of X i in G.Suppose there exists a topological sort T of G that satisfies O. For any (i, j) ∈ O + , i must appear before j in the topological sort T because O + represents a transitive closure of the order constraints. If X j were an ancestor of X i in G, there would be a path from X j to X i . In a topological sort, for any edge (u, v), u must appear before v. Therefore, if X j were an ancestor of X i , X j would appear before X i in the topological sort. However, this would contradict the fact that i appears before j in the topological sort T (as i is related to j by O + ). Thus, X j cannot be an ancestor of X i in G.(⇐=) If for any order (i, j) in O + , X j is not an ancestor of X i in G, then there exists a topological sort of G that satisfies O.Assume for any (i, j) ∈ O + , X j is not an ancestor of X i in G. This implies there is no directed path from X j to X i for any (i, j) ∈ 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) ∈ O, i appears before j in the ordering. Since O + does not create any cycles (because X j is not an ancestor of X i ), the ordering respects the partial order O. The resulting topological sort T satisfies the constraints of O by construction.Proposition 4. No directed path X i ⇝ X j exists in G(W ) if and only if ( ∑ d l=1 (W • W ) l ) i,j = 0.Proof. ∑ d l=1 (W • W ) l 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 1 to d from X i to X j , fulfilling the necessary condition for X i ⇝ X j ̸ ∈ G(W ). This condition is also deemed sufficient due to Lemma 4.Lemma 4. If a directed path X i ⇝ X j exists in a graph with d nodes, then a directed path X i ⇝ X j of length less than d must also exist.The proof of Lemma 4 is similar to that of lemma 3.This section presents the psudocodes of the implementations of the proposed method. W ′ ← Replace the (i, j)th element of W with τ for each edge (i, j) ∈ o ▷ τ > 0 is a hyper-parameter that controls the strength of the order constraints.7:result ← result + h(W ′ ) 8: end forreturn result Algorithm 3 Find All Maximal Paths in a DAG Require: A directed acyclic graph G = (V, E) Ensure: A set of all maximal paths in G 1: function FINDMAXIMALPATHS(G) 2:Initialize an empty list all_paths3:Identify all nodes in G with no incoming edges as start_nodes 4:for each node u in start_nodes do for each v such that there is an edge from node to v do for each pair (k, l) ∈ O do 5:if i ̸ = k and j ̸ = l then 6: if (i, k) ∈ R and (k, j) ∈ R then 7:Remove (i, j) from T 8:end ifend if 10:end for 11: end for 12: return T F(W ). These edges, termed "virtual" edges, may not exist in the actual graph but are included in the "acy-graph" used to enforce acyclicity constraints. The following analysis highlights the theoretical impact of different values of τ .Small τ : When τ is too small, it fails to properly reflect the presence of virtual edges in the acygraph, leading to 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 acyclicity constraint and compromising the learning process.Large τ : On the other hand, if τ is too large, it can disrupt numerical stability by overshadowing small weights that signify absent edges. For example, consider a forbidden cycle p = W 1,2 W 2,3 W 3,1 , where W 1,2 = τ is set to a large value, while W 2,3 = r -(indicating edge absence). This configuration results in ∇ W3,1 p = τ × r -, making the influence of W 1,2 on W 3,1 large enough to enforce the absence of W 3,1 , even though the cycle should be considered broken due to the absence of W 2,3 . This misinterpretation can lead to the erroneous removal of edges, potentially producing an empty graph.We conducted experiments with varying values of τ and observed the real acyclicity loss h, augmented acyclicity loss h ′ , data approximation loss F, and output metrics such as 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 γ = 0.1 support this theoretical analysis and are presented in Table 3 .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 5 6 7 8 , expand on the analysis, offering a more comprehensive understanding of the experimental outcomes. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Sufficient information on the computer resources is provided in the experiment 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 (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as 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 or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: This paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.The terms with powers higher than d are expressible in finite terms with powers not exceeding d by the Cayley-Hamilton theorem. Therefore, Trace(e B ) -d is also an instance of Equation (4).Note thatStep 2 would also be omitted in the absence of Step 1. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_summary: This paper introduces an approach to integrate partial order constraints into differentiable structure learning for causal discovery. The key contributions are:
* Formulating an equivalent constraint set of path prohibitions to implement partial order constraints in the graph space.
* Proposing an efficient method to integrate partial orders by augmenting the acyclicity constraint.
* Proving the theoretical correctness and completeness of the proposed augmented acyclicity constraint.
* Demonstrating the effectiveness of the method through experiments on both synthetic and real-world datasets.

The 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.
strength_weakness: strength_weakness: * Several statements are known or follow easily from existing results. 
* As noted in the limitations section, the method's efficiency can degrade with complex partial order structures involving multiple chains.
* The paper doesn't extensively discuss how sensitive the method is to incorrect or conflicting partial order priors, which is possible in applications.
* While the paper compares to baselines without priors, it doesn't compare to other methods that might incorporate different types of prior knowledge.
* 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.
questions: 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.

* 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.

* 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.

Minor things:
* L21: reform -> reformed
* L25: Ng et al., 2020, do not propose an aciclicity characterization.
* 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: Limitations are addressed in Appendix F.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. Typo: Line 204 $\mathcal{O}^-)$ should be corrected to $\mathcal{O}^-$.
questions: 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?
2. 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.
3. 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?
4. In the experiments, do you test $p$ is small, such as $p = 10$?
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: While I overall did enjoy reading the paper, I do have a number of questions and concerns:

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.
questions: questions: 1. Can you clarify which theoretical statements are novel by specifying if Theorems 1, 2, and 3, and Lemma 1 were already known?

2. Theoretical clarifications:
   + 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.
   + 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.**

3. 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?

4. 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?

5. 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**?

I 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: Not all my comments below are weaknesses and some of them are questions.

1. 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.

2. 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?

3. 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.

4. The proposed method introduces a new hyperparameter $\gamma$. How to determine $\gamma$ in practice as there is no ground truth to do validation?

5. 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?
questions: questions: Please see my comments above.
limitations: limitations: The authors adequately addressed the limitations

Comments: title: Acknowledgement of Author Rebuttal
Thank you!
comment: Thanks for the detailed response. I am happy to keep my original positive score of the paper.
I thank the authors for their response. I will increase my score to 6 for now.
Thanks for your patient review and invaluable comments. We will refine related parts in alignment with your suggestion.
I sincerely thank the authors for clarifying both my theoretical and empirical concerns. I now see that Theorem 4 indeed holds in its fullest generality and I would suggest the authors to replace lines 567-569 with the step-by-step explanation given in their answer as it is much clearer how Theorem 4 follows from Lemma 2 and 3. Additionally, the empirical comparison between Equation 8b and 9b given to Reviewer FFcG clearly shows the improvement in computational efficiency while maintaining performance. Finally, as also requested by Reviewer 99Ub, the authors have more clearly separated their novel result from previous results. Hence, I will increase my score to a full accept and congratulate the authors on the nice marriage of theory and practice.
Thank you for addressing all of my concerns. At this point, I don’t have any additional concerns. I raise my score.