Differentiable Structure Learning with Ancestral Constraints
Authors: Taiyu Ban
Changxin Rong
Xiangyu Wang
Lyuzhou Chen
Xin Wang
Derui Lyu
Qinrui Zhu
Huanhuan Chen
Venue: ICML 2025 poster (2025)
Keywords: Causal discovery
Continuous DAG structure learning
Constrained optimization problem
Primary area: general_machine_learning->causality
TL;DR: This work extends the differentiable causal discovery framework able to integrate ancestral constraints.

Abstract: Differentiable structure learning of causal directed acyclic graphs (DAGs) is an emerging field in causal discovery, leveraging powerful neural learners. However, the incorporation of ancestral constraints, essential for representing abstract prior causal knowledge, remains an open research challenge. This paper addresses this gap by introducing a generalized framework for integrating ancestral constraints. Specifically, we identify two key issues: the non-equivalence of relaxed characterizations for representing path existence and order violations among paths during optimization. In response, we propose a binary-masked characterization method and an order-guided optimization strategy, tailored to address these challenges. We provide theoretical justification for the correctness of our approach, complemented by experimental evaluations on both synthetic and real-world datasets.

Differentiable Structure Learning with Ancestral Constraints
Taiyu Ban"
Changxin Rong'
Xiangyu Wang'
Lyuzhou Chen' Huanhuan Chen'
Xin Wang' Derui Lyu' Qinrui Zhu'
Abstract
In practice, it common to have prior knowledge about the presence or absence of causal relationships, which must be incorporated into structure learning to accurately recover the underlying causal mechanisms (Constantinou al., 2023; Amirkhani et al., 2016). 6). When prior knowledge is abstract and does not directly identify specific causal interaction in the data, ancestral constraints, which specify the existence or absence of either edges or indirect paths, provide a robust way to encode such abstract knowledge (Li & Beek, 2018). 8).
Differentiable structure learning of causal di- rected acyclic graphs (DAGs) is an emerging field in causal discovery, leveraging powerful neural learners. However, the incorporation of ances- tral constraints, essential for representing abstract prior causal knowledge, remains an open research challenge. This paper addresses this gap by intro- ducing generalized framework for integrating ancestral constraints. Specifically, we identify two key issues: the non-equivalence of relaxed characterizations for representing path existence and order violations among paths during optimiza- tion. In response, we propose binary-masked characterization method and an order-guided opti- mization strategy, tailored to address these chal- lenges. We provide theoretical justification for the correctness of our approach, complemented by experimental evaluations on both synthetic and real-world datasets.
For traditional structure learning methods based score- and-search, ancestral constraints can be incorporated by verifying path presence conditions in graph and eliminat- ing graphs that violate the constraints (Chen et al., 2016), or by re-scoring graphs with additional bonuses for adherence to prior knowledge (O' Donnell et al., 2006).
In contrast, differentiable structure learning of causal DAGs relies on gradient-based optimization, which demands smooth characterization that equivalently represents path presence conditions. Furthermore, the optimization pro- cess must be effectively guided toward favorable optima under continuous ancestral constraints, avoiding the risk of convergence to suboptimal points. These two distinctive requirements pose significant challenges the integration of ancestral constraints in differentiable structure learning, leaving it an open research question in the field.
1. Introduction
Structure learning of causal DAGs is fundamental task for uncovering causal relationships among variables from data (Pearl, 2000). Recent advances have reformulated this task as continuous optimization problem by representing the discrete acyclicity constraint of the graph as smooth equal- ity, a technique known as differentiable structure learning (Zheng et al., 2018). This approach facilitates the use of powerful neural learners and gradient-based optimization methods to model complex causal mechanisms (Zheng et al., 2020; Yu et al., 2019), significantly advancing the fields of causal discovery and trustworthy Al (Zhang al., 2021; Dai & Chen, 2022; Ruan et al., 2022; Wei et al., 2022).
To address this research gap, we propose generalized framework for integrating ancestral constraints into differ- entiable structure learning. First, we identify the issue of non-equivalence in continuous relaxed characterizations for representing path existence and propose binary-masked characterization that accurately and equivalently represents path existence. Next, we address the order-violating issue among individual paths specified in the constraints, which can result in incomplete adherence to the constraints and lead to suboptimal optimization. To guide the optimization process toward favorable optima, we propose an order- guided optimization strategy. It begins by enforcing partial order constraints implied by path existence, deriving DAG that satisfies all specified path orders. The resulting order- consistent DAG is then used as the initial adjacency matrix to optimize the path existence-constrainee problem.
'School of Computer Science and Technology, University of Science and Technology of China, Hefei, China. Correspon- Huanhuan Chen
dence to: Xiangyu Wang <sa3l2@ustc.eduu <hehen uutt.utttccce. edu.en>. .dd...
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We provide the necessary theorctical analysis and compre-

---

Differentiable Structure Learning with Ancestral Constraints
hensive empirical evidence on both synthetic and real-world datasets validate our approach. Additionally, related works, proofs of statements, and complete experimental results are detailed in the appendix.
where pa denotes the parent node set of xe in G, and 2,
represents independent zero-mean noise terms ( (2i)
Traditional Structure Learning. Structure learning for
an SEM FG) involves recovering the graph structure G from a dataset D E Idddd generated based on G and F. Assume the SEM is parameterized by 8, where the graph G is represented by Wo E RRddd, with (Wo)., * 0 indicating an edge (g), and the functions F' are represented by Fe. The structure learning task can be formulated as:
The main contributions are summarized as follows:
To the best of our knowledge, this is the first paper to systematically address the integration of ancestral constraints into differentiable structure learning, en- abling the use of abstract prior knowledge to guide the discovery of mnegrrined causal mechanisms.
min [D Wo) DI1 + A/10111,
9
(2)
We analyze the issue of non-equivalence in represent- ing path existence using continuous relaxed characteri- zations and propose a binary- maaked characterization that equivalently represents path existence.
subject to G(W)) E DAG.
Here, 11-11/ denotes the least-squares loss, ||- the -norm, and X > the regularization weight. For simplicity, we focus on the linear case of structure learning, where the model parameters can be directly represented by weighted adjacency matrix W E RRdxd:
We identify the order-violation issue among paths, which can lead to suboptimal optimization, and in- troduce an order-guided optimization strategy that ef- fectively guides the process toward favorable optima.
DDW - -DI12 + A/]W1,, W'Rdxd subject to G(W) E DAG.
min
(3)
2. Preliminaries
This section introduces key concepts and notations, pro- vides an overview of differentiable structure learning, and concludes with the connection between the smooth charac- terization of acyclicity and path absence.
Since the acyclicity constraint G(W) E DAG is discrete, tra- ditional methods rely on combinatorial optimization (Chick- cring, 2002) or other discrete approaches (Spirtes & Gly- mour, 1991).
Smooth Characterization of Acyelicity. To address the discrete nature of DAG structure learning, Zheng et al. in- troduced NOTEARS, which provides a smooth characteri- zation of acyclicity via the trace exponential function:
2.1. Notations
Let W E dxdd represent a weighted adjacency matrix, with the graph it defines denoted as G(W). The node set of G(W) is X {r and the edge set is (GG(W)). The existence of a directed path from x; æÿ in G(W) is repre-
h(W)= Trace (e (ewow) d = 0,
(4)
sented by x; zj. while x; & 2y denotes a path of length k. The symbol x; and its index i are used interchangeably to denote a node.
where o denotes the element wise product, and is the node number. This characterization satisfies hu(W) = 0 if and only if G(W) is a DAG. Using this, the discrete optimization problem in Equation (3) is reformulated as continuous optimization problem with equality constraint:
For matrix operations, [W| denotes the element-wise abso- lute value, W represents the k-th power of W, and W*k i.j refers to the (i,j)-th element of W Operations such as W W-a a or aW, where a is a constant, are performed element- wise as subtraction or multiplication by a, respectively.
IDDW DIL + A||W]|, WERlxd
min
s.t. h(W) = 0. (5)
Optimization and Thresholding. NOTEARS solves this problem using the augmented Lagrangian method, ensuring that h(W) remains sufficiently small to enforce the acyelic- ity constraint. The graph structure G(W) is then derived by applying a threshold to WW. This framework has become foundational in the field and is widely adopted in subsequent work (Zheng et al., 2020; Sun et al., 2023).
2.2. Differentiable Structure Learning
Causal Graphical Model. We start by defining the causal graphical model commonly used to model causal relation- ships among continuous variables.
Definition (Structural Equation Model (SEM). An SEM is a directed acyclic graph (DAG) G with a node set X = { representing random variables, and set of functions F = [f such that:
2.3. Connection between Acyclicity and Path Absence
The function h(W) representing the ayclicity degree of G(W) in Equation (4) is constructed following the idea of
3; = f. 24),
2

---

Differentiable Structure Learning with Ancestral Constraints
forbidding all paths from each node itself (cycles):
Remark 1. The above derivation provides an intuitive and accurate characterization of path absence in Equation (9), which underpins the construction of acyclicity characteri- zations central to differentiable structure learning, While path absence itself is not discussed further, it serves as a foundational concept for path existence characterization.
G(W) E DAG
Vi, (ay E G(W)).
(6)
To derive the smooth characterization of acyclicity, we first illustrate the characterization of path absence. Consider:
[
Σ 91-92...----1
Wl..g W ... IW WW qu-1a
3. Continuous Characterization of Path Existence Constraints
where |WI,, fi represents the non-negative weighted sum of all length-k k paths from z, to zj. with each path's weight being the product of the edge weights along that path. Thus:
This section begins by characterizing path existence through continuous relaxation. We then analyze its non-equivalent issue representing path existences. To address this, we introduce binary-masked continuous relaxation that pro- vides an equivalent representation. Finally, we formulate the path existence- ciistencecoosstrined task.
[witi =0 = + -1, ~ 23 E G(W)),
0
(8)
indicating the absence of length-A path between 2; and zyy- Extending this to paths of any length up to d, we derive:
3.1. Continuous Relaxation of Path Existence
M W = - vk < d, - (z. & Ij E G(W)
(9)
Characterization via Continuous Relaxation. We first recall the continuous characterization of path absence:
(.q 2zj C(W)).
(p(W)), + ((x ~+ Iz E G(W)),
The second equivalence follows from the contrapositive of the following proposition:
(12)
where p (W) = Wi
Proposition 1. If there exists directed path (I4, in a directed graph G with d nodes, then there exists at least one length-k path (ri, in G such that l S d.
Since p(W) is non-negative, its contrapositive equivalence
provides direct characterization of path existence:
Equation (9) characterizes the absence of paths. On this basis, acyclicity in Equation (6), the absence of cycles, can cquivalently be expressed as smooth equality:
(p(W))a, > 0 = I₁ - E G(W),
(13)
which states that a nonzero value in p(W) implies the exis- tence of the corresponding directed path.
Vi, (2;; m0 24 G(W))
W f =0
Proposition 2. For graph G(W) where edge existence follows Wa,; + O (II, E E(G(W)), at least one directed path from T, to F exists is and only if (p(W))), > O, where p(W) is defined Equation (12).
1=1
(10)
Trace (|W]*)= = O.
However, in the continuous optimization of structure learn- ing, edge weights Wa,; are rarely exactly zero. Instead, a threshold co > is used to determine edge existence:
From this, we derive the general form of the smooth charac- terization of acyclicity:
W co (1),, E F(G(W)).
(14)
h(W)= Trace
Ea(WW = =0, Ck >
(11)
Similarly, path existence requires threshold e > 0, lead- ing to the relaxed condition (p(W))s, 2 c. This can be equivalently reformulated using an auxiliary function, as employed the work by Wang et al. (2024):
Corollary 1. (Theorem in (Wei et al., 2020)) directed graph G(W) is DAG if and only if h(W) 0 for any h defined in Equation (11).
(P(W)) = 0, where p(W) = ReLU (c p(W)). (15)
The acyclicity function h(W) of NOTEARS in Equation (4) is a special case of h(W), containing infinite terms to forbid cycles of all lengths while being computationally efficient for gradient- based optimization. Other acyclicity functions, such as Trace((I + d B) - I) (Yu et al., 2019) and log det(sI - B) + log s (Bello et al., 2022), have also been proposed for efficient gradient calculation.
Here, ReLU(-) is the element-wise ReLU function, defined as ReLU(()) = max(0, 2r). The equality (f(W))&s equivalent to enforcing (p(W)) 2 e.
Remark 2. We refer to eo as the edge threshold and e
as the path threshold in the following discussion. Next, we analyze why the path threshold-basee characterization (p(W)) = fails to equivalently represent path existence.
3

---

Differentiable Structure Learning with Ancestral Constraints
Issue of Non-Equivalence to Path Existence. We show that Equation (15) is not equivalent to the path existence condition 2; 2 E G(W) when G(W) is constructed using edge relaxation in Equation (14).
(b(W)),, there exists at least one directed path from
24 to z.j in G(W), and (b(W))s.3 if no such path exists.
This result ensures that ((W) activates the influence of (p(W)) only if no directed path exists in G(W). This mechanism climinates redundant constraints when path ex- istence is already satisfied, thus preserving the necessity:
To begin with, we assume that elements in [W| are bounded due to regularization and data approximation:
Assumption There exists a constant a > co. where co is the edge threshold, such that W for all i,
Lemma 3. (Necessity) For any e, if there exists at least one directed path from F, 2 in G(W) for G(W) constructed by Equation (14), then (p(W)) =
Under this assumption, we establish the following result: Lemma 1. (Sufficient Condition) There exists finite thresh- old f(co. o) > en such that k., = O is sufficient to guarantee path existence Ij - T5 E G(W) under edge relaxation in Equation (14) if and only if 2 J((o..))
Next, we establish the sufficiency condition when the path threshold c is large enough, i.e., c <> f(co, o). Consider the condition (f(W) ))k3 =
This result indicates that if path threshold is not sufficiently large, the condition (p(W)) is insufficient ensure the existence of path I3 ~ Izz- Additionally, we have:
(P(W)), = 0 - (b(W)) (p(W)), =0. 0. (17)
If (b(W)) 0, Proposition ensures that zy ny 2z G(W). If (p(W)) = 0, Lemma 1 guarantees that 2; 23 E G(W). Thus, obtain:
Lemma 2. (Necessary Condition) The continuous equality (F(W)) = 0 is necessary for the path existence T2 o* Iy E G(W) under edge relaxation in Equation (14) if and only i S min(co. ())
Lemma 4. (Sufficiency) For some finite f((o, > c0, if e 2 f(eo, σ), then (f(W)) = 0 implies the existence of at least one directed fath I, to 2; in G(W) constructed with edge threshold en in Equation (14).
This result implies that when path threshold is slightly larger, (p(W)) = 0 is no longer necessary for path exis- tence, potentially introducing extraneous constraints.
Lemma 3 and Lemma 4 together establish the equivalence of (f(W)) ), in characterizing path existence when e is sufficiently large, stated in the following result:
Lemma 1 and Lemma 2 establish the critical path threshold e values for the sufficiency and necessity of the continuous relaxation p(W) = 0 in representing path existence. How- ever, no single satisfies both conditions simultancously, as [Eoo, min(eo, ef) Consequently, p(W) = in Equation (15) fails equivalently represent path existence, underscoring the need for further refinement.
Theorem 1. There exists at least one directed path from z to xy in G(W) constructed by Equation (14) if and only (p(W)) = O, where p(W) is defined by Equation (16) with e 2 f(eo, for some finite f
In summary, we introduce a binary mask 6(W) that com- putes the path sum matrix using a binary adjacency matrix representing thresholded edge presence. This mask accu- rately determines whether a directed path already exists between two nodes, thereby selectively avoiding the redun- dant influence of the equality constraint (p(W)),,) 0.
3.2. -ankry Continuous Relaxation for Equivalent Path Existence Characterization
To equivalently represent the path existence constraint, we introduce the following function:
Essentially, this operation removes the constraint on c for ensuring the necessity of path existence, making it valid for any Thus, sufficiently large can be chosen to satisfy both necessity and sufficiency, achieving equivalence.
p(W)= = p( W) a b(W), where p(W) is defined in (15),
and b(W)= = Σ (I(W) 2 (o)) =o)
(16)
Remark 3. See Section B in the Appendix for details on the motivation and alternative explorations.
Here, I[()) is an element-wise indicator function that returns 1 if the inner condition holds and otherwise, and o denotes the element-wise product.
Suppose the set of path existence con- straints is represented by A E {0, 1) jxdd where Ar,; = 1 indicates the constraint x, ~y xy G(W). The task of differentiable structure learning with A is formulated as:
Task Formulation.
To interpret the overall operation of the function p(W), it selectively activates or deactivates path existence constraints in (WW) based on whether the constraint is already satisfied, as determined by the binary mask b(W):
min DWW - DII + A||W I1 + Σ (B(W) o A),
Proposition 3. For b(W) defined in Equation (16) and G(W) constructed with edge threshold 6o in Equation (14),
(18)
subject to h(W) 0,

---

Differentiable Structure Learning with Ancestral Constraints
where y 0 is the weight of the path existence loss, and E B represents Σi,; Ba.--
in a DAG implies partial order x4 < v.y The path order violation is subsequently defined as:
In Equation (18), path existence constraints A are treated as soft constraints by incorporating (p(W))s, as a loss term rather than enforcing (f(W))..) = O strictly. This relaxation is necessary due to the inherent conflict between the path existence loss h(W) during optimization, as stated in the following result: Proposition 4. The losses (f(W)) and h(W) exhibit gradient conflict, consistently pushing the parameters of W in opposite directions during optimization:
Definition 4 (Path Order Violation). Two directed paths are in order violation if one path contains a sub-path that implies the reverse partial order of the other. In this case, the paths are said to be order-violating paths, or one path is said to violate the order of the other.
and the acyclicity loss
A recovered path I; ~- 2j from optimizing (6(W)) may be in order violation with other paths specified in the con- straint. For illustration, consider the gradient of (p(W)) ks with respect to an arbitrary edge weight W.,e:
Vu, U, WW., h(W). Vw.,. (P(W))s S O. (19)
V Viw.,, (((W)) =- EII
II
Wee (20)
When optimizing conflicting losses, the process may con- verge to a suboptimal compromise where neither loss fully minimized. To prevent violations of the acyclicity constraint, the path existence term is incorporated as a loss rather than an equality constraint. This approach ensures h(W) is fully optimized, prioritizing the fundamental DAG assumption in structure learning over prior knowledge constraints.
PEP eEpi((u,v))
where p(ur) denotes the set of directed paths of length at i-mj most & from I; to Ij that include the edge (Iru, Iw). and We represents the weight of edge in W.
Equation (20) illustrates how the path existence loss (j(W))s, influences the optimization of an arbitrary edge (T)) If a nearly complete path 2; ~4 2j exists except for the missing edge (Fu,To)) the loss strongly promotes the inclusion of (Ius Zy) in the structure. Consequently, the optimization of (p(W))s. becomes highly sensitive to initial conditions, as demonstrated in the following example:
4. Order-Guided Optimization with Path Existence Constraints
This section first analyzes the onder-violation issue in opti- mizing the path existence-based structure learning problem in Equation (18). We then introduce an order-guided opti- mization strategy to address this challenge.
Example 1. Consider two different initial weight matrices:
0
2
0.1
0
0.1 2
W1-
0.1
0.1
W.
0.1
o
0.1
(21)
4.1. Issue of Path Order Violation
0.1
0.1
0.1
0.1
With settings 60 1 and c= 9, optimizing:
When solving the path existence- based structure learning problem in Equation (18), full adherence path existence constraints may fail, leading to suboptimal solutions. This issue arises from two interrelated factors: 1) The path exis- tence loss is highly sensitive to initial guesses. potentially introducing order-violating paths. 2) In the augmented La- grangian process, the weight of the acyelicity loss increases over iterations, preventing the recovery of paths that violate the graph's 's existing order.
min(p(W))1s + O.1||W s.t. Vi, W., 0, W
using gradient descent W++1 = W V C(W) with initial conditions W1 and W₂ leads to:
0
1.0
0.0
0.0
1.0
WITH
0.0
1.0
W2T
0.0
0.0
(22)
0.0
0.0
0
0.0
0.0
0
Partial Order Relations. The (partial) order of variables refers to their position in a DAG's topological ordering:
Here, different initial guesses lead to different recovered edges in the optimal solution of the path existence loss. In structure learning, this effect can override data approx- imation, unintentionally introducing edges (or paths) that violate the order of other paths. In the above example, if the path existence constraints include x11 we Ty and m3 ~4 D2, then W where x 33 contains the edge (22,, in- troduces an order 22 < 23, violating the path 223 - Z2.
Definition 2 (Topological Order). A topological order of DAG is a permutation 7 of nodes such that for every directed edge (i, in the DAG, - (i) < π. (j), where π '(x)
denotes the position of x in n.
Definition 3 (Partial Order). The partial order relation be-
tween nodes and j. denoted as < j. implies that i pre- cedes j in the topological order, i.e., π (i) < π -i).
In the augmented Lagrangian method commonly used for structure learning, the acyclicity function h(() is incorpo- rated as a loss term with an increasing weight over iterations
By these definitions, the existence of a path F; ~ Ty E G
5

---

Differentiable Structure Learning with Ancestral Constraints
ensure full optimization zero. Consequently, when the acyclicity weight becomes large, it prevents the recovery of paths that contain order-violating paths in the current structure, as stated below:
4.2. Order-Guided Optimization
To address the order-violation issue in optimizing Equa- tion (18), propose order-guided optimization strategy. Specifically, we aim to derive weight matrix W that satis- fies all partial orders implied by the specified path existence constraints and then use this W as the initial guess for the path existence-constraing problem in Equation (18).
Proposition 5. Suppose the current graph G(W) contains a directed path from z to Ie, but there no path from Vi to vy- In this case, the loss function:
Since each path existence constraint 2; ~ 2j implies a partial order 3; K 2ij, the set of partial orders, denoted as O, coincides with the path existence set. To enforce these constraints, we should ensure that each partial order < 2j is respected by forbidding its reversed path 2j ~ 2;. However, because partial orders are transitive while path absence is not, we must derive the complete set of partial orders using transitive closure:
C(D.W) F(W; +]|I||+ (((W)) ph((W)
prevents the addition of any edge (u, v) that would establish a path from D; to Ij in an updated graph G', where G' (()) U {(u,)) v)}), as long as p is sufficiently large.
This result shows that if I2 2j conflicts with reversed path in the current graph, it will be forbidden, even if it was originally part of path existence constraints.
Definition 5 (Transitive Closure). The transitive closure of a set S = {(x; y) ). denoted by S+, contains a pair (a. b) and only if there exists a sequence a = I0, F1,..., ,.b...,,,,, Th. = such that (.,, 2++1) E S for all
For broader perspective on the order-violation issue, the acyclicity loss weight is initially small, allowing order- violating paths to emerge due to the influence of initial guesses. As the acyclicity loss strengthens, one of the con- flicting violatiiv paths is eliminated, preventing the full satisfaction of the path existence constraint.
With this, we can equivalently enforce the partial order set O using a set of path absence constraints:
Proposition 6 ((Ban et al., 2024, Proposition 2)). Given partial order set O = {r; - x2 a DAG G satisfies O if and only if. for all x; < 3 in O+, there exists no directed path from x3 to I; in G.
Algorithm 1 Differentiable Structure Learning with Path
Existence Constraints
Require: Data D, binary mask A E {0, 1]dxd of path- existence constraints, edge threshold éo Define backbone model: (L, h, Wo). with data-fit loss L. acyclicity loss h, and structure parameters Wo.
By combining this statement with the continuous charac- terization (p(W))s, = O, defined in Equation (12) for path absence, differentiable structure learning with the partial order constraint set O can be formulated as:
2: Define path existence loss:
L'= = L+ (GOW)) A)
min DDW D1E + AI|W W We
(23)
3: Define order-based acyclicity loss:
subject h(W) 0, p(W) (A+)* 0,
ho h + C o (A+)²)
where (-)T denotes matrix transposition, A is the mask of the path existence set corresponding to O, and p(W) (A+)T= = 0 ensures the absence of all reversed paths associ- ated with the indicated orders the transitive closure O+, The mask At, corresponding to O+ is computed as:
4: Solve order-based optimization (initializing from zero):
W. < (D,,,)), where (L, hor Wo)
5: Solve path sxiseence-based optimization using the order- based optimization result W. as initialization:
A+
=I
Σ
A 0 k=1
(24)
Wp + (D, Wo), where Mp(L', h, Wo)
Solving Equation (23) yields an outcome that satisfies the partial order set O implied by the path existence constraints. This outcome is then used as the initial guess for optimizing path existence-constrained structure learning problem (18).
6: Threshold learned structure:
WP + I([W,) > E0)
7: Return Final learned structure W
An overall illustration of differentiable structure learning with path existence constraints is presented in Algorithm 1.
6

---

Differentiable Structure Learning with Ancestral Constraints
Rationale Justification. During optimization, the partial order loss and acyclicity loss are gradient-consistent, mean- ing that they always push parameters in W in the same direction. This consistency enables a fuller optimization of both losses, ensuring that all partial orders implied by path existence constraints are satisfied.
1= W > 0), representing all paths. We then randomly select 9% of these paths as constraints.
Wp
Real-World Data. We use real-world protein and phos- pholipid expression data from (Sachs et al., 2005), which measures interactions in human immune system cells. This dataset is standard benchmark in graphical modeling due to its consensus network of 11 nodes and 17 edges, validated through experimental annotations.
With an initial guess that adheres to all partial orders of paths, the risk of generating order-violating paths is reduced. This is due to the acyclicity loss discouraging the recovery of paths with reversed orders relative to the initial guess. Con- sequently, the optimization of the path problem is guided toward recovering paths without violating the order of each other, leading to a stronger adherence to path existence conditions.
Methods. The backbone algorithms include NOTEARS
(Zheng et al., 2018; 2020), DAGMA (Bello et al., 2022), and GOLEM (Ng et al.. 2022). Path existence (PE)-based struc- ture learning is denoted as 'PE-alg', where alg represents the backbone algorithm used.
Furthermore, optimizing structure learning with path exis- tence constraints while respecting all their partial orders ensures that no erroneous orders are introduced. This helps refine the optima space structure learning where each optima corresponds to a topological order:
Metries. We evaluate performance using structural Ham- ming distance (SHD), true positive rate (TPR), false discov- ery rate (FDR), F1 score, and path recovery rate (satisfied constraints/ / total constraints).
Proposition 7. Each optimal solution of the equality- constrained problem (5) corresponds to the global optimum of the following convex optimization problem:
Setup. Default parameters: edge threshold 6p = 0.3, path threshold e = 10, L, weight À = 0.1, path existence weight ? = 1, path percentage = 80. Other parameters follow defaults of backbone algorithms. Experiments run on an AMD Ryzen 7950X (4.5 GHz) CPU, NVIDIA RTX 3090
DD o M) - -D112 + 111 WER
min
(25)
where Mij- = 1 if (i) < Tj) and Mij- = 0 otherwise, for a specific permutation π of {1, .d... d}.
GPU, and 32 GB RAM.
NOTEARS PE-NOTEARS-intuiee
PE-NOTEARS-eem
Hence, the optima space is refined to a more accurate one, thus improving the quality of the recovered structure.
PE-NOTEARS
exp
gauss
exp
gauss
0.75
In summary, the partial order-constrained initial guess en- forces all partial orders implied by path existence con-
Fl score B05
0.50
228
SHD
0.25
straints, thereby reducing the occurrence of order-violating paths through the acyclicity loss. The resulting solution, which adheres to all path existence constraints, avoids in- troducing erroneous orders, ultimately leading to a more accurate reconstruction of the true structure.
500
0.75
250
21
0.50
10
30
5010
50
d (Number of Nodes)
d (Number of Nodes)
exp
gauss
exp
gauss
1.0
5. Experiments
0.75
Path Recovery Rate
0.50
ERS
ER2
We present partial experimental results and analysis here, with the full results available in the appendix.
0.25
0.8
FDR
1.0
0.5
ERA
Synthetic Data. Random DAGS are generated using Erdös-Rényi (ER) and scale-free (SF) models with node de- grees in 42 and numbers of nodes d in (10,20 20, 30, 50). For observational data, uniformly random weights are assigned to the weighted adjacency matrix B. Given B, samples are generated using the structural equation model X = B"X + X E Rd, with noise models [Gaussian (gauss). Exponential (exp)}. The sample size is n = {200 10003. To generate constraints, we compute the path mask Wp from the ground truth adjacency mask W as
0.8
0.0
50
30
d (Number of Nodes)
d (Number of Nodes)
Figure 1. Comparison and ablation results of main metrics.
5.1. Comparison and Ablation Results
We compare our method (OE-NOTE with standard NOTEARS (without path existence constraints) and two ab-
7

---

Differentiable Structure Learning with Ancestral Constraints
Table I. Results of our method on the real-world Sach dataset with various sample sizes and PE constraint numbers.
Sachs-100
Sachs-200
Sachs-500
Sachs-902
Method
SHD
FDR
TPR
F1
SHD
FDR
TPR
F1
SHD
FDR
TPR
F1
SHD
FDR
TPR
F1
NOTEARS
22
0.72
0.47
0.34
17
0.63
0,47
0,41
13
0.56
0.41
0.42
13
0.58
0,41
0.41
PE-NOTEARS-25
20
0.67
0.52
0.40
15
0.60
0.47
0.43
13
0.55
0.47
0.45
12
0.52
0.47
0.47
PE-NOTEARS-50
16
0.61
0.59
0,46
13
0.55
0.53
0.48
13
0.55
0.47
0.46
12
0.55
0.47
0.46
PE-NOTEARS-75
16
0.61
0.59
0,46
13
0.55
0.53
0.48
12
0.55
0.53
0.48
11
0.52
0.53
0.50
PE-NOTEARS-IOT
100
15
0.60
0.59
0.47
14
0.57
0.53
0.47
11
0.50
0.58
0.54
12
0.55
0.53
0.48
lation variants: PE-NOTEARS- which uses the binary- masked loss but initializes with a zero matrix, and PE- WOTEEAS--intuiive which directly applies the continuous relaxed loss p from Equation (15) with a zero initial guess.
5.3. Ablations Order-Guided Optimization
We conduct ablation study different initialization strategies to assess the effectiveness and robustness of order- guided optimization. The evaluated strategies include: PE- NOTEARS using the partial order-guided outcome, PE- NOTEARS-randen with a random initial guess, and PE- NOTEARS- using the NOTEARS outcome (without prior) as the initial guess.
Results in Figure show that our method significantly out- performs the baseline and ablation variants. It achieves lower SHD and higher F1 score, indicating better overall quality. The FDR is lower, indicating less erroneous edge recovery, while the path recovery rate is higher, ensuring stronger adherence to path existence constraints. A lower FDR confirms that using á mitigates the redundancy issue in P for path existence characterization. A higher path recovery rate highlights the effectiveness of the order- order-guided initial guess resolving order-violation issues in recovered paths.
For each method, we randomly generate six initial guesses and report their individual results on the same dataset, with partial results shown in Figure 2. The partial order-guie ander-guided initialization achieves the best performance (lowest SHD, highest FI) with the highest stability (lowest variance), demonstrating its robustness and effectiveness.
5.2. Results on WorldW Data
PE-NOTEARS
NOTEARS intuitive order
NOTEARS
We evaluate our method on the real- world Sachs dataset, ap- plying different percentages p of path existence constraints, denoted PE-NOTEARS-p. Using subset of Sachs's s cell data with 902 samples, we vary the sample size denoted as Sachs-n, by selecting the first n samples.
PE-NOTEARS
PE-NOTEARS
ER2
ER4
ER2
ER4
100
0.8
Fl score
0.5
Table 1 shows that our method consistently outperforms the data-driven baseline, with greater improvements as more constraints are incorporated. Notably, using only 100 sam- ples, our method achieves a higher Fl score than the baseline trained on all 902 samples, demonstrating its potential for reducing experimental resource requirements.
2200
0.8
0.5
100
100.1
.51
510
.1
.1
510.1
5
510
Figure 3. Ablation results with varying path thresholds.
NOTEARS PE-XOTEARS-rmbot
PE-NOTEARS-
PE-NOTEARS ER4
BR2
ER4
ER2
100
5.4. Ablations with Varying e Settings
0.75
50
0.50
We conduct an ablation study on varying path thresholds c, a key hyperparameter for the path existence loss. The evaluated methods include PE-NOTEARS, PE-NOTEARS- zero, and PE-NOTEARS-intuitee along with a variant, PE-NOTEARS-intuiee which applies f as the PE loss with the order-guided initial guess for a more comprehensive ablation. Results for values ranging from 0.1 to 10 are shown in Figure 3.
SHD
0.25
0.75
as introduced earlier,
100
0.50
0.25
Algorithm
Algorithm
Figure 2. Ablation results on various initialization strategies.
Our method consistently outperforms the ablation versions across different settings. Performance initially improves
8

---

Differentiable Structure Learning with Ancestral Constraints
increases, ensuring the sufficiency of ÿ in representing path existence, and then stabilizes once p fully aligns with path existence. In contrast, other ablation variants show initial improvement but degrade as increases, particularly for p (dotted lines), which loses necessity at large e (Lemma 2). resulting in excessive extra edges. Additionally, versions without order-guided optimization (red-series lines) exhibit greater variance due the sensitivity of the path existence loss initial guesses. These results align with our analysis.
Beyond scientific applications, this work contributes the broader AT landscape by advancing NOTEARS-based causal analysis frameworks. Its ideas may benefit wide range of downstream tasks in fields such as computer vi- sion, fault diagnosis, and multi-agent systems, where causal reasoning plays an increasingly central role.
A Acknowledgements
This research was supported in part by the National Key R&D Program of China (No. 20217D011 11001117700 1700), in part by the National Nature Science Foundation of China (No. 62406302, 62137002, 62176245), in part by the Natural Sci- ence Foundation of Anhui province (No. 2408085QF195) in part by the Fundamental Research Funds for the Central Universities under Grant WK21501100335
5.5. Other Results and Analysis
The appendix provides additional evaluations on time com- plexity, path absence constraints, nonlinear data, backbone variations, and the effect of varying constraint numbers. Fur- thermore, supplementary results covering additional metrics, different graph settings, and ablation studies related to the experiments in this section are also included.
References
6. Discussion
Amirkhani, H., Rahmati, M., Lucas, J., and Hommersom, A. Exploiting experts' knowledge for structure learning of Bayesian networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(11)2215--2170 2016.
6.1. Limitations and Future Directions
The current path existence formulation lacks explicit mecha- nisms to prevent path order violation and is computationally slower than acyclicity losses. Future work may explore more efficient and reliable characterization approaches.
Andersson, S. A., Madigan, D., and Perlman, M. D. A characterization of markov equivalence classes for acyelic digraphs. The Annals of Statistics, 25(2):505-541, 1997.
6.2. Conclusion
Ban, T., Chen, L., Wang, X., Wang, X., Lyu, D., and Chen, H. Differentiable structure learning with partial orders. In The Thirty-eighth Annual Conference on Neural Infor- mation Processing Systems, 2024.
This paper extends differentiable structure learning by in- tegrating ancestral constraints, enabling the use of abstract prior knowledge to enhance fine-grained causal discovery. We identify key challenges in incorporating path existence constraints into continuous optimization and propose a binary-masked characterization with order-guided op- timization strategy to address them. Theoretical analysis supports the correctness of our approach, which is validated on both synthetic and real-world datasets.
Bello, K., Aragam, B., and Ravikumar, P. Dagma: Learn- ing dags via m- m-matrices and a log-determinant acyclicity characterization. Advances in Neural Information Pro- cessing Systems, 35:8226-8239, 2022.
Berrevoets, J., Seedat, N., Imrie, F., and Van Der Schaar, M. Differentiable and transportable structure learning. In International Conference on Machine Learning, pp. 2206-2233. PMLR, 2023.
Impact Statement
The proposed ancestral constraint-based differentiable struc- ture learning framework combines the expressive power of neural networks and GPU-accelerated optimization with the reliability of knowledge-guided constraints. This integra- tion enables efficient and accurate recovery of authentic, previously unknown causal mechanisms.
Bhattacharya, R., Nagarajan, T., Malinsky, D., and Shpitser, I. Differentiable causal discovery under unmeasured con- founding. In International Conference on Artificial Intel- ligence and Statistics, pp. 2314-2322. PMLR, 2021.
The algorithm has broad applicability in scientific discovery domains, where high-level prior knowledge about variable interactions can guide the discovery of fine-grained causal structures. Such domains include biology, medicine, and social sciences, where partial knowledge is common but direct causal relationships remain elusive.
Brouillard, P., Lachapelle, S., Lacoste, A., Lacoste- Julien, S., and Drouin, A. Differentiable causal discovery from interventional data. Advances in Neural Information Pro- cessing Systems,
8688866777177718 2020.
Chen, E. Y.J.., Shen, Y., Choi, A., and Darwiche, A. Learn- ing Bayesian networks with ancestral constraints. Ad-

---

Differentiable Structure Learning with Ancestral Constraints
vances in Neural Information Processing Systems, 29, 2016.
Heckerman, D. and Geiger, D. Learning Bayesian net- works: unification for discrete and gaussian domains. In Proceedings of the 11th Conference Uncertainty in Artificial Intelligence, pp. 274-284, 1995.
Chen, X., Sun, H., Ellington, C., Xing, E., and Song, L. Multi-task learning of order-consistent causal graphs. Ad- vances in Neural Information Processing Systems, 34: 11083-11095, 2021.
Heckerman, D., Geiger, D., and Chickering, D. M. Learning bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20(3):197-233, 1995. doi:
Chickering, D. M. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3 (Nov):507-554, 2002.
Hinton, G., Osindero, S., and Bao, K. Learning causally linked markov random fields. In International Work- shop on Artificial Intelligence and Statistics, pp. 128-135. PMLR, 2005.
Constantinou, A. C., Guo, Z., and Kitson, N. K. The impact of prior knowledge on causal structure learning. Knowl- edge and Information Systems, 65(8):3385- -434,, 2023.
Dai, E. and Chen, J. Suuph-augmented normalizing flows for anomaly detection of multiple time series. In Interna- tional Conference on Learning Representations, 2022.
Huang. J. and Zhou, Q. Partitioned hybrid learning of bayesian network structures. Machine Learning, 111: 1695 1738, 2022.
de Campos, L.. M. and Castellano, G. Bayesian network learning algorithms using structural restrictions. Interna- tional Journal of Approximate Reasoning, 45(2):233-255 2007.
Kalainathan, D., Goudet, O., Guyon, I., Lopez-Paz, D., and Sebag, M. Structural agnostic modeling: Adversarial learning of causal graphs. Journal of Machine Learning Research, 23(219):1-62 2022.
Deng. C., Bello, K., Aragam, B., and Ravikumar, P. K. Op- timizing NOTEARS objectives via topological swaps. In Proceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 7563-7595, Honolulu, Hawaii, USA, 2023a. PMLR.
Lee, H.-C., Danieletto, M., Miotto, R., Cherng, S. T., and Dudley, T. Scaling structural learning with NO-BEARS to infer causal transcriptome networks. In Pacific Sympo- sium on Biocomputing 2020, pp. 391-4022 World Scien- tific, 2019.
Li, A. and Beek, P. Bayesian network structure learning with side constraints. In International Conference on Probabilistic Graphical Models, pp. 225-236. PMLR, 2018.
Deng, C., Bello, K., Aragam, B., and Ravikumar, P. K. Optimizing notears objectives via topological swaps. In International Conference Machine Learning, pp. 7563- 7595. PMLR, 2023b.
Ma, P., Ding, R., Fu, Q., Zhang, J., Wang, S., Han, S., and Zhang, D. Scalable differentiable causal discovery in the presence of latent confounders with skeleton posterior. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2141-2152, 2024.
Deng, C., Bello, K., Ravikumar, P. K., and Aragam, B. Markov equivalence and consistency in differen- tiable structure learning. In The eiirty-eighth Annual Conference on Neural Information Processing Systems, net/ forum?
2024. URL
id=TM1 GQMM)//WWEbbb
Friedman, N., Nachman, I., and Pe'er, D. Learning Bayesian network structure from massive datasets: The "Sparse Candidate" algorithm. Proceedings of UAI 1997, pp. 206- 215, 1997.
Neapolitan, R. E. et al. Learning bayesian networks, vol- ume 38. Pearson Prentice Hall Upper Saddle River, 2004,
Ng. I. and Zhang, K. Towards federated bayesian network structure learning with continuous optimization. In Inter- national Conference on Artificial Intelligence and Statis- tics, pp. 8095-8111 PMLR, 2022.
Gao, E., Ng, I., Gong, M., Shen, L., Huang, W., Liu, T., Zhang, K., and Bondell, H. MISSDAG: Causal discovery in the presence of missing data with continuous additive noise models. Advances in Neural Information Process- ing Systems, 35:5024-5038, 2022.
Ng. L., Ghassami, A., and Zhang, K. On the role of sparsity and dag constraints for learning linear dags. Advances in Neural Information Processing Systems, 33:17943. 17954, 2020.
Hasan, U. and Gani, M. O. KCRL: A prior knowledge based causal discovery framework with reinforcement learning. In Machine Learning for Healthcare Conference, pp. 691 714. PMLR, 2022.
Ng, I., Lachapelle, S., Ke. N. R., Lacoste-Julien, S., and Zhang, K. On the convergence of continuous constrained
10

---

Differentiable Structure Learning with Ancestral Constraints
optimization for structure learning. In International Con- ference on Artificial Intelligence and Statistics, pp. 8176- 8198. PMLR, 2022.
Spirtes, P., Meek, C., and Richardson, T. Causal inference in the presence of latent variables and selection bias. In Proceedings of the Eleventh conference Uncertainty in artificial intelligence, pp. 499-506, 1995.
O' DDnnelll, R., Nicholson, A., Han, B., Korb, K., Alam, M., and Hope, L. Causal discovery with prior information. In Proceedings of the 19th Australian Joint Conference on Artificial Intelligence: Advances in Artificial Intelligence, pp. 1162-1167, 2006.
Spirtes, P., Glymour, C., and Scheines, R. Causation, pre- diction, and search. MIT press, 2001.
Sun, X.,
Schulte, O., Liu, G., and Poupart. P. NTS- NOTEARS: Learning nonparametric DBNs with prior knowledge. In International Conference on Artificial Intelligence and Statistics, pp. 1942-1964. PMLR, 2023.
Pamfil, R., Sriwattanaworachai, N., Desai, S., Pilgerstorfer, P. Georgatzis, K., Beaumont, P., and Aragam, B. DYN- Structure learning from time-series data. In International Conference Artificial Intelligence and Statistics, pp. 1595-1605. PMLR, 2020.
NOTEARS:
Teyssier, M. and Koller, D. Ordering- -based search: a simple and effective algorithm for learning Bayesian networks. In Proceedings of the Twenty- First Conference on Uncer- tainty Artificial Intelligence, pp. 584-590, 2005,
Pearl, J. Causality: Models. Reasoning, and Inference. Cambridge University Press, Cambridge, UK, 2000.
Tsamardinos, I., Brown, L. E., and Aliferis, C. F. The Max- Min Hill-Climbing Bayesian network structure learning algorithm. Machine Learning, 65:31-78, 2006.
Reisach, A., Seiler, C., and Weichwald, S. Beware of the simulated DAG! Causal discovery benchmarks may be easy to game. Advances in Neural Information Processing Systems, 34:27772 277844, 2021.
Wang. Z., Gao, X., Liu, X., Ru, X., and Zhang, Q. Incorporating structural constraints into con- tinuous optimization for causal discovery. Neuro- computing, 595:127902, 2024. ISSN 0925-2312. doi:
Richardson, T. and Spirtes, P. Ancestral graph markov models. The Annals of Statistics, 30(4):922-1030, 2002.
Rissanen, J. Modeling by shortest data description. Auto- matica, 14(5):465 4711,447111111 1978.
URL httpp://www..ceeeneddieeetttt
Ruan, J., Du, Y., Xiong, X., Xing, D., Li, X., Meng, L.., Zhang, H., Wang. J., and Xu, B. GCS: Graph-based coor- dination strategy for multi-agent reinforcement learning. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pp. 1128- 1136, 2022.
Wei, D., Gao, T., and Yu, Y. DAGs with no fears: A closer look at continuous optimization for learning Bayesian networks. Advances in Neural Information Processing Systems, 0113895-3906 2020.
Wei, Y., Wang. X., Nie, L., Li, S., Wang, D., and Chua, T.-S. Causal inference for knowledge graph based recom- mendation. IEEE Transactions Knowledge and Data Engineering, 35(11):11153-1111
Sachs, K., Perez, O., PePer' er, D., Lauffenburger, D. A., and Nolan, G. P. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308(5)))); 523 029,529,222 2005.
2022.
Yang, M., Liu, F., Chen, Z., Shen, X., Hao, J., and Wang, J. CausalVAE: Disentangled representation learning via neural structural causal models. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 9593-9602, 2021.
Schwarz, G. Estimating the dimension of model. The Annals of Statistics, 6(2):461-464 1978.
Scutari, M., Graafland, C. E., and Gutiérrez, J. M. Who learns better Bayesian network structures: Accuracy and speed of structure learning algorithms. International Journal of Approximate Reasoning, 115:235-253, 2019.
Yu, Y., Chen, J., Gao, T., and Yu, M. DAG-GNN: DAG structure learning with graph neural networks. Interna- tional Conference Machine Learning, pp. 7154-7163. PMLR, 2019.
Shahverdikondori, M., Mokhtarian, E., and Kiyavash, N.
Qwo: Speeding up permutation- causal discovery in ligams. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Zhang, Jia, B., Edmonds, M., Zhu, S.-C., and Zhu, ACRE: Abstract causal reasoning beyond covariation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10643-10653, 2021.
Spirtes, P. and Glymour, C. An algorithm for fast recovery of sparse causal graphs. Social science computer review, (1):22-72, 1991.
Zhang, J. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9:1437-1474, 2008

---

Differentiable Structure Learning with Ancestral Constraints
Zhang, Z., Ng, Gong, D., Liu, Y., Abbasnejad, E., Gong, M., Zhang, K., and Shi, J. Q. Truncated matrix power iter- ation for differentiable dag learning. Advances in Neural Information Processing Systems,
2022.
Zheng, X., Aragam, B., Ravikumar, P. K., and Xing, E. P. Dags with tears: Continuous optimization for structure learning. Advances in Neural Information Processing Systems, 31, 2018.
Zheng, X., Dan, C., Aragam, B., Ravikumar, P., and Xing, E. Learning sparse nonparametric dags. In International Conference Artificial Intelligence and Statistics, pp. 3414-3425 PMLR, 2020.
Zhu, S., Ng. I., and Chen, Z. Causal discovery with reinforcement learning. In International Conference Learning Representations, 2020. URL https:// openreview tett/fforumm:dd=11122ks55PP
12

---

Differentiable Structure Learning with Ancestral Constraints
Appendix
A. Related Work
This section reviews relevant studies related to this paper. We first provide a brief overview of traditional structure learning methods and the integration of prior structural constraints. We then discuss differentiable structure learning approaches and studies incorporating prior constraints in this field.
A.1. Traditional Structure Learning and Prior Constraint Integration
A.1.1. CAUSAL GRAPHICAL MODELS
Causal models are categorized based on graph type, including DAGs, undirected graphs, and mixed graphs.
Causal DAGs primarily encompass Bayesian networks (BNs) (Pearl, 2000) and structural equation models (SEMs) (Spirtes et al., 2001). BNs represent causal relationships through conditional probabilities, P( Pa while SEMs model causality via continuous functions, I; = f(Pa 2,), where is noise term. This paper conducts experiments with additive noise models (ANMs), a subclass of SEMs where the noise term is additive, i.e., V2 = (Pa, ()) + Zi.
Undirected causal graphs primarily involve Markov Random Fields, which capture symmetric dependencies without causal direction and are commonly used for modeling spatial or network-based relationships (Hinton al., 2005).
Mixed graphs allow the coexistence of directed, undirected, and bidirected edges. These include maximal ancestral graphs (MAGs) (Richardson & Spirtes, 2002), used to represent causal relationships in the presence of latent variables or selection bias; ancestral graphs (Zhang, 2008), which generalize both DAGs and MAGs; and partial DAGs (Andersson et al., 1997), which use undirected edges to represent ambiguous causal relationships.
A.1.2. TRADITIONAL STRUCTURE LEARNING.
Structure learning of causal DAGS aims to identify the model structure that best represents the distributions of observational data (Scutari et al., 2019). Given the DAG constraint, traditional methods typically employ discrete approaches, including constraint- basee, and hybrid methods.
Constraint- methods reconstruct the graph using conditional independence tests, followed by edge orientation within the DAG constraint. Key algorithms include the Peter and Clark (PC) algorithm (Spirtes & Glymour, 1991) and the Fast Causal Inference (FCI) algorithm (Spirtes et al., 1995).
Score-based methods evaluate DAGs using scoring functions that measure goodness-of-ff to data, followed by search for an optimal DAG. Popular scoring functions include Bayesian Information Criterion (BIC) (Schwarz, 1978), Bayesian Dirichlet Equivalent Uniform (BDeu) (Heckerman & Geiger, 1995), and Minimum Description Length (MDL) (Rissanen, 1978). Search algorithms include Greedy Equivalence Search (GES) (Chickering, 2002), Hill Climbing (HC) (Neapolitan et al., 2004), Simulated Annealing (Friedman et al., 1997), Tabu search (Li & Beek, 2018), etc.
Hybrid methods combine constraint-based and score-based techniques. Notable examples include Max-Min Hill-Climbing (MMHC) (Tsamardinos et al., 2006) and Partitioned Hybrid Greedy Search (PHGS) (Huang & Zhou, 2022).
A. 1.3. PRIOR CONSTRAINT INTEGRATION.
Structural constraints representing prior causal knowledge primarily fall into three categories:
1. Edge constraints specify the presence or absence of edges in the graph. While straightforward to integrate into structure learning, they are often difficult to obtain, as they directly reveal causal interactions, the very objective of structure learning. Relevant studies include (Amirkhani et al., 2016; de Campos & Castellano, 2007).
2. Ancestral constraints specify the existence of certain directed paths or the absence of all directed paths between variables. These constraints capture abstract causal relationships that may be realized either directly indirectly. Ancestral constraints provide a robust way to encode prior causality, aligning well with the abstract nature of knowledge. Related studies include (Li & Beek, 2018; Chen et al., 2016).
3. (Partial) order constraints define the ordering relationships among a subset (or all) of the variables. They are less
13

---

Differentiable Structure Learning with Ancestral Constraints
restrictive than edge and ancestral constraints, as they only enforce topological relationships without necessarily implying causal interactions. Given total ordering, structure learning is reduced to set of straightforward polynomial- time problems, we primarily focus on the integration of partial order constraints. Partial order constraints are commonly integrated into wrder-based search algorithms, which assume a total variable ordering and then search for the optimal ordering that yields the globally optimal DAG (Teyssier & Koller, 2005; Heckerman et al., 1995). Partial order constraints help reduce the search space by eliminating conflicting orderings (Li & Beek, 2018; Deng et al., 2023a).
The integration of structural constraints into structure learning follows two main approaches: hard and soft integration. Hard integration strictly enforces constraints by rejecting graphs that violate them. The aforementioned studies predominantly follow this approach. Soft integration balances adherence to prior constraints with goodness-of-fi to data, typically by modifying the scoring function to penalize constraint violations. CaMML (O' Donnell et al., 2006) is an open-source causal discovery tool that employs soft constraint integration. A comprehensive review prior constraint integration methods can be found in (Constantinou et al., 2023). Interestingly. both hard and soft integration methods have direct counterparts the context of differentiable structure learning, as discussed in the main text.
A.2. Differentiable Structure Learning and Prior Constraint Integration
A.2.1. DIFFERENTIABLE STRUCTURE LEARNING.
Zheng et al. first introduced differentiable structure learning, extending score- based structure learning task:
oaxo(G; D), subject to G E DAG.
(26)
For continuous causal graphical models such as SEMs, the score function a (G; D) can be formulated continuously using weighted adjacency matrix W Rd to represent the structure, leaving the DAG constraint the only discrete component. To address this, Zheng et al. proposed a smooth acyclicity characterization using the equality constraint:
h(W)= = "raceee WoW) - ===0
(27)
This formulation transforms structure learning into a continuous coustity optimization problem:
min W d |IF - X||W]|, subject to h(W)= = 0.
(28)
The augmented Lagrangian method is used to solve this problem, gradually increasing the weight of the acyclicity loss h(W) over iterations to ensure convergence to a DAG. Optimization stops when (W) falls below a predefined threshold (10-8 by default) or when the loss weight reaches a maximum (1026 by default). A threshold eg is then applied to determine the presence of edges the learned structure. This optimization framework has been widely adopted in subsequent differentiable structure learning approaches.
Existing research on differentiable structure learning can be categorized into four main directions:
1. Novel Learner Architectures 0. Zheng et al. introduced NOTEARS-MLP, extension using multilayer perceptrons for nonlinear structure learning. Yu et al. proposed DAG-GNN, a generative model leveraging graph neural networks and data reconstruction properties. Other studies have explored reinforcement learning (Zhu et al., 2020) and adversarial neural networks (Kalainathan et al., 2022) for differentiable structure learning.
Novel Acyclicity Characterizations h(W). Yu et al. proposed a polynomial based acyelicity function as an alternative the exponential formulation in NOTEARS. Wei et al. generalized polynomial-basee -basd characterizations using path (cycle) absence principles. Lee al. showed that polynomial-based constraints are equivalent constraining the spectral radius to zero and introduced spectral radius-based acyclicity formulation. Bello et al. proposed DAGMA, determinant-basel acyclicity characterization leveraging the nilpotency property of DAGs.
3. Novel Loss Formulations C(W, D). Ng et al. introduced GOLEM, a likelihood- based loss function that replaces the least squares loss NOTEARS. By incorporating soft sparsity and DAG penalties, GOLEM eliminates the need for a hard equality constraint, simplifying and accelerating DAG learning. Reisach et al. analyzed the effect of data variance on differentiable structure learning, introducing varsortability as a criterion to infer variable ordering. Their findings
14

---

Differentiable Structure Learning with Ancestral Constraints
suggest that performance improvements may stem from the increasing marginal variance of descendant nodes. Deng et al. further investigated this issue and proposed likelihood-based scoring function with quasi-MCP regularization, ensuring scale-invariant properties.
4. Applications in Causal Discovery. Some studies extend NOTEARS broader causal discovery settings. Brouillard et al. explored differentiable causal discovery in interventional and observational mixtures, a common real-world scenario. Bhattacharya et al. extended the framework settings with unobserved confounders. Gao et al. addressed structure learning with missing data. Pamfil et al. applied differentiable causal discovery to dynamic time-series data. Some extensions apply structure learning in other machine learning fields, such as multi-task learning (Chen et al., 2021), federated learning (Ng & Zhang, 2022), representation learning (Yang et al., 2021), 1) and transportable learning (Berrevoets et al., 2023).
Despite these advances, limited research has explored the integration of prior structural constraints in differentiable structure leaming, particularly beyond simple edge constraints. The next section discusses this gap.
A.2.2. PRIOR CONSTRAINT INTEGRATION IN DIFFERNNTAALEE STRUCTURE LEARNING.
For long period, studies of differentiable structure learning with prior knowledge only focus on the edge constraints. Integrating the edge absence constraint can be implemented by directly freezing the corresponding parameters to 0 (a hard constraint), or adding a loss penalizing WWk, when forbidding (I,, xT)). For the edge existence, one can use the continuous relaxed equality ReI.U(eo - [W]s,)) = 0 to force the existence of edge (I;, ). or adding the loss of ReI.U(eo - IW],)). Here are some related studies (Hasan & Gani, 2022; Sun et al., 2023; Wang et al., 2024; Ma et al., 2024).
For more complex constraints over edge constraints, a recent work by Ban et al. integrates the partial order constraints in differentiable structure learning. The authors also formulate the partial order constraints as a set of path absence constraints, as shown in Equation (23). They further propose efficient characterization typically handling long sequential orderings. We directly use the path absence-based characterization in this paper because the partial order constraints implied by path existences do not typically form long sequences. Some studies propose order-based optimization methods for structure learning, which can also integrate partial order constraints (Shahverdikondori et al., 2024; Deng et al., 2023b), despite in a different task formulation of NOTEARS. Wang et al. study incorporating various structural constraints into differentiable structure learning. However, the authors does not focus on the generalized forms of partial order or ancestral constraints, who assume the total ordering for the order constraint which is straightforward and assume the knowledge of path lengths for path existence constraints. Besides, their proposed characterization of path existence is still limited by the issue of Non-Equivalence to represent path existence, as illustrated in Section 3.1 of the main text.
In comparison, this paper addresses the generalized form of path existence constraints without knowing any information of the path. We propose an equivalent continuous characterization of the path existences with theoretical justification. We further analyze the path order violation issue typically optimizing the problem with path existence constraints, and introduce stable optimization strategy by taking the solution of path existence-implied partial order-constrained structure learning as the initial guess. In word, this work first systematically discusses and addresses differentiable structure learning with ancestral constraints, typically on the challenges related to continuous path existence constraints.
B. Motivation of Binary-Masked Characterization
This section explains the motivation behind our binary- masked characterization for representing path existence constraints. Additionally, we discuss alternative approaches that were explored but ultimately failed, providing richer insight.
B.I. Motivation
The intuitive characterization of path existence is given by (p(W)),, = 0, where:
p(W) ReLU
E Σ [wp)
(29)
We have shown that this formulation cannot equivalently represent path existence for any choice of the path threshold c. If is too small, the edge weights along path may not reach the edge threshold cg. causing the path to be considered absent. Conversely, if is too large, the constraint equality cannot be satisfied even when the path existence constraint is satisfied.
15

---

Differentiable Structure Learning with Ancestral Constraints
Despite this theoretical limitation, practical experiments indicate that when is set to appropriate intermediate value, the algorithm still performs reasonably well (see Figure 3 in the main text). However, the optimal choice of is unknown without access to the ground truth. The remaining aim is eliminating its dependence on an unpredictable and unstable
Motivated by this idea, we propose removing the redundant influence of p(W) once the path existence constraint is already satisfied. If this can be achieved, we can set é to a sufficiently large value to equivalently enforce path existence. This approach is feasible because the exact conditions for edge existence are known, allowing us to derive a binary mask indicating path presence.
A natural question arises: if existence instead of relying on p(W)? Unfortunately, this approach fails in an optimization setting. When a path is absent, the loss function b(W) cannot propagate gradients to edge weights due to the ReI.U function, which blocks gradient flow when its argument is negative.
compute path presence matrix b(W), why not directly it constrain path
In summary, using b(W) alone cannot enforce path existence when a path is missing, which can only enforce path absence when a path already present. This limitation explains why our approach integrates p(W) with the binary mask to achieve robust path existence characterization.
B.2. Alternative Explorations
We also explored a more concise path existence characterization by constructing the path existence loss in a dual manner to path absence. While theoretically appealing, this approach encountered practical challenges.
We begin by recalling the path absence loss:
(x(W)) ΣΣ II
|W = 0,
(30)
k= PEPt, (g.s)Ep
where Pi, represents the set all paths from I; to I, with length k:
Interpreting this loss from logical perspective, we consider [W]s 0 as an indicator of edge absence and | > as an indicator of edge presence. Using numerical operations represent logical expressions, where multiplication corresponds to logical and (A) and addition corresponds to logical or (V), we can rewrite the loss as:
Visn (YPEPt, (Mqge)ep 1g.x 01))
(31)
Here, the inner expression (g) (W Ig.- > 0) enforces that all edges in p must exist, ensuring the presence of a path. The outer logical or operations ensure that if at least one path from to j exists, the entire expression evaluates to true. Consequently, when this expression is false (numerically, (p(W)),, 0), path exists from ny Iz-
To enforce path existence, we considered imposing the following reversed constraint:
ReLU (e (p(W))k,) = 0.
(32)
However, this approach suffers from the non-equivalence issue discussed in the main text. Logically, this discrepancy arises because it does not accurately capture the existence condition for each edge, resulting in a mismatch between the numerical loss and the logical presence of path.
To resolve this, sought more precise condition for edge existence:
Fi.j ReLUU(e [W],)),
(33)
where Fa, = indicates the presence of edge (i.j), and F., > O indicates its absence. Notably, we define this as a complementary matrix to allow gradient propagation to edge weights when an edge is missing, which is particularly useful for enforcing path existence.
Now, consider the following logical expression:
Nf=i (Mrert, (V(g.))p (Bg.s > 0))).
(34)
16

---

Differentiable Structure Learning with Ancestral Constraints
This expression states that for all paths p from zy Jij, least edge in p absent (i.e., Eg.s 0 for some (g, 8) p).
This is precisely the path absence condition. Therefore, its logical negation corresponds to the path existence condition.
By replacing logical operations with numerical ones, we derive the following continuous formulation:
(p" (W))as II II
Σ
ReLU(eco (W...)).
(35)
k=1pEPt, (Q.4)Ep
This leads to the following theoretical result:
Theorem 2. A directed path from 2; to I exists in G(W) constructed using edge threshold eo if and only if (f"(p)))) 0, where p is defined by Equation (35).
Thus, we obtain a concise, continuous, and equivalent formulation for enforeing path existence constraints. However, despite its theoretical soundness, this formulation suffers from numerical instability in practice. The product- loss is prone to vanishing gradienis, making optimization difficult. Additionally, the magnitude of (n" (W)),. varies unpredictably: for eo 1, may becomes excessively large. while for Eo < 1/d, collapses near zero, losing its effectiveness guiding optimization. These practical issues also motivated our final binary-masker characterization, which maintains equivalence while avoiding numerical instability.
C. Proof of Statements
Proposition 1. If there exists a directed path (1), in a directed graph with d nodes, then there exists at least one length-k path (I4, in G such that S d.
Proof. Suppose, for the sake of contradiction, that the shortest directed path from v; to Ty has length k with k >> d. Label this path
p = (4, l2. ...., 4+1),, where 1 = xg and 4++1 = I... Since the path has & edges, visits k vertices. Our assumption k > d implies
k+1 1
so the path visits at least d + 2 (not necessarily distinct) vertices. But G' itself has only d vertices in total. By the pigeonhole principle, at least one vertex must repeat in the interior of the path; formally, there exist indices
1 S
1
k+1
such that 4, 4 and + 1, * k + 1. (In other words, the repeated node is not just the start or the end.)
The subpath
(1.,
4))
thus forms a directed cycle. We can "shortcut" the path by removing that cycle, obtaining a strictly shorter path from æ; to .j. This contradicts our choice of as the shortest directed path. Consequently, no shortest path can exceed length d. Therefore, if there exists path at all, there must be one of length at most d.
Corollary 1. (Theorem I in (Wei et al., 2020)) A directed graph G(W) is DAG if and only if h(() = 0 for any h defined in Equation (11).
Proof. Equation (10) shows that G is DAG equals that Ed Trace (WI+) O. Given the non-negativity of Trace([W]**) we have that this condition also equals Ed= Cs Trace ([WI+) 0 for C₁ > 0.
Proposition 2. For a graph G(W) where edge existence follows W. # 0 - (m,,,y) E E(G(W)), at least one directed path from I; to x, exists if and only if (p(W))s, O, where p(W) is defined in Equation (12).
Proof. Equation (13) already indicates this result.
17

---

Differentiable Structure Learning with Ancestral Constraints
Lemma (Sufficient Condition) There exists finite threshold [(eo σ) > eo such that (p(W)) 0 is sufficient to guarantee path existence 2; ~ Ij G(W) under edge relaxation in Equation (14) if and only if f((o.
Proof. We aim to prove the statement
(p, = = (a; ~ 23) E G(W)
if and only if 2 f(co. > co:
(36)
where feo, σ) is some finite constant strictly exceeding co.
Step 1. Construction of f(co, o). Consider situation in which G(W) does not have path from 2, zy. Then by definition of
d
(o(W))
1.3
there must exist at least edge in every candidate path (of length d) with absolute weight co- Consequently,
d W w i.
(p(W))s)
co 0-1
(37)
where p. is an arbitrary k-length directed path from 2; to 2j that contains no self-loop edges (Tm, Fm), and |pt.) denotes the number of such k-length paths. Here, least edge each p/,, must have weight < <os and we let (or some suitable parameter) capture potential reductions in absolute weights for the remaining edges.
The right-hand side of (37) is finite quantity (depending on d, a, and the number of k-paths). Hence, we can set
f(eo. sup (p(W))
|
((z ~ x2) G(W)).
Thus [EO, a) is finite and moreover
[(eo, o) <
Σ
Pis
h
eo o
k-
We must also show that f(co, co.
Step 2. Verifying (eo, r) > eo- We construct a specific W- such that G(W-) does not have a directed path from 2; to zj but (p(W)) (oss) > Eg. For instance, define
W = 60 - 6
W = 60 -- 6, W = a,
for some node xn (1 + j), where < <e0 Ito
Set all other entries W u 0. In this setup:
(p(W-))as
Σ W |+
WT, + W Wi, (co- (0+
ij
Since (1 ()+ (co c-) > co by choice of c we get
(p(W)))ss
>
Yet G(W-) has no directed path from to zy (for instance, if ø does not lead to x or if additional zeros cut off the path). Hence (p(W)))ss E (p(W), -(x; ~ 23)) E G(W)), so in particular
((Eu, 2 (p(W)))a, > eg.
Step 3. Showing the Sufficient Condition. By definition of p(W),
(p(W))s = ReL.U(e (o(W))
18

---

Differentiable Structure Learning with Ancestral Constraints
If (p(W) 0, then
(o(W))es S 0 (p(W))as 2
Suppose now c 2 f(co, o.. Then
(p(W))s 2 c 2 O(),,
implies that (p(W)),, cannot lie in the set (p((W)) (1z mz)) G(W)), because the supremum (over graphs with no 2 path) is f(e0, Hence, (p(W))ss must belong to the complementary set in which ~* 2j in G(W). Therefore, when c 2 f(c,, 0),
(p(W)) =0 (o(W)) 202 f(co. 24 mmmg xy G(W).
Thus (p(W))ks = indeed implies the path existence 24 wn Tj, establishing the "sufficiency" part under the condition <2 ((
Step Converse Argument. If < f(co, o), we can select a W from the (p(W))) -(xx ~ 2z)) E G(W) with (p(W))s For that W, have
<< (p(W))ks
= (p(W)) <0
(T(W))s = 0,
yet by construction G(W) has no directed path from x, zj. This contradicts the statement that (f(W))ss would imply 2, Tz. Hence must be at least o( for the "sufficiency" property to hold.
This completes the proof of Lemma 1.
Lemma 2. (Necessary Condition) The continuous equality (p(W));, 0 is necessary for the path existence xi Izj G(W) under edge relaxation in Equation (14) if and only if S min(Co. c
Proof. Recall that (sW)*)s, can be interpreted as the sum of products of absolute weights over all possible directed paths of length l from 2y to Zz- Suppose every directed edge in G(W) has absolute weight at least 6g. Consider specific path from Z; to z of length &. The product of its edge-weights (in absolute value) is then 2 cØ. Summing over all path lengths
1 S k < d, we get
d
d 0
if0 < 6 1
2
min( EO, e
40
ig
if ED 2 1. EDs
Hence, in either case,
d Σ [wm)t)
2 min(eo, 6)
1=1
By definition,
(p(W) ReLU(E 2 w )
1=1
If e < minn(o, ()) then
d
w1t) S min(co. <0) min(Co. (Eo, e6) = -0
e
which implies ReLU(-) of a non-positive numberis is 0. Therefore, whenever 4q w4 Dj, we necessarily get (F(W))k Conversely, i min(co, ef),, then it is possible to have
W ) > min(co. a - min(Co, A = 0.
which yields (p(W)).. > 0. Thus, in this regime (e > min(eo, ef)), the value (F(W)) need not be zero, even if x ~ Zj.
Therefore, (p(W)) a)), = forced (i.c., is necessary) by the existence of directed path x; ~ Iz if and only S min(fo, ) This completes the proof.
19

---

Differentiable Structure Learning with Ancestral Constraints
Proposition 3. For b(W) defined in Equation (16) and G(W) constructed with edge threshold eo in Equation (14),
(b(W)),) =0 if there exists at least one directed path from x: 3. in G(W), and (b(W))s.s such path exists.
Proof. Recall the definition of 6(W):
b(W) (U(W) 2 ea))* 0).
Let We = =[([ 2 6n) be the binary adjacency matrix of G(W), so that
Wi * O = (z)) E E(G(W)). and [ = We.
Then,
(b(W))s = = I((D(W"))), =0) =0 = (p(We)) 24 > 0.
By Proposition 2, we know
(p(We)) 2 >
2i m 3j E G(W).
Hence,
(b(W)).s = 0 Is m Ij E G(W).
Since b(W) takes values in {0, 1]axd, immediately have
(b(W))s.)
(1z; (2) G(W).
This completes the proof of Proposition
Lemma 3. (Necessity) For any e, if there exists at least one directed path from x; to 2y in G(W)for G(W) constructed by Equation (14), then (p(W))..) O.
Proof. From Proposition 3, we know
Ts ~r Iy G(W) = (b(W)) O.
By the definition of ((W). whenever (b(W)),, 0, follows that
(f(W) = 0.
Hence,
I,
Ij G(W)
(p(W)) 0,
which completes the proof.
Lemma 4. (Sufficiency) For some finite f(e, o) > Eo, if 2 f(eo, o), then (p(W)).s = 0 implies the existence of at least one directed path from I; to Ij in G(W) constructed with edge threshold eo in Equation (14).
Proof. By Lemma 1, there exists finite threshold f(eo, σ) > co such that for all E > f(eo, o),
(p(W)ks =
34 ~ Iy E G(W).
Next, from Proposition 3, we have
(B(W))s)
x I. E G(W).
By the definition of ((W). know
(p(W)),.
(p(W))s 0 or (b(W))s, =
Combining these facts, for c > f(co. 0) we get
(p(W)),,) = 0 = (F(W)),) = or (b(W)),, =0 = x; ~ 2j E G(W).
This completes the proof.
20

---

Differentiable Structure Learning with Ancestral Constraints
Theorem 1. There exists at least one directed path from x, x, in G(W) constructed by Equation (14) if and only if (f(W)) 0, where P(W) is defined by Equation (16) with 2 (()o, for some finite {ea, 0).
Proof. Lemma 3 and Lemma 4 together derive this result.
Proposition 4. The losses (p(W)),, and h(W) exhibit gradient conflict, consistently pushing the parameters of W in opposite directions during optimization:
Vu, v,
TW..ghWW V W... (p(W)), S.
(19)
Proof. Recall ((W) P(W) b(W), where b(W) is binary mask that does not affect the chain rule with respect to Wu,v. u Thus
Ww.... (F(W), s.g if (b(W)) = 1, (b(W)) =
V W... (D(W))
0,
When (b(W))k) 1 and (p(W)) > 0.
d
Vw.. (p(W)) 4.5 = - Vw.. (p(W)) 1.
W v.v (1WI*) b,5"
k=1
Expanding each derivative over paths that include edge (Ii Fio) yields
Ww.. (WW)*,.. sign (Wav)
Σ
II
W/es
pEP(aN) eEpl((u,v)
where plu.e) is the set all k-length directed paths from o; to that include (Iun Fe). Since II. W/e 2 0, factoring out i sign(W W., v. gives
Ww.. (f(W),.,
sign (W... n.
Σ
II W
pEp(N..) eEp)((u,r)) 1
Multiplying by sign(Wa,v). we obtain
V W... (b(W)),.)
sign(Wa..)) S O,
(38)
since the remaining sum is nonnegative.
Next, for
k(w)
W [
Ck
the gradient w.r.t. W., similarly factors out sign(W,,,. (W..)):
Vw.. h(W) sign(W
Σ
II [Wees
Ck
k=1
1=1 pep(u.)) eep)((u,t)) th
where now plu ((u,)) F
runs over k-length loops through (Fn)) Hence, we have:
Vw.. h(W) sign sign(W..o) 2 0,
(39)
under positive c (e.g., all Cs 2 0).
Combining Equations (38) and (39), we have:
Vwa, h(W). Vw... (D(W)) $ 0.
which completes the proof.
21

---

Differentiable Structure Learning with Ancestral Constraints
Proposition 5. Suppose the current graph G(W) contains directed path from æ.j De but there is path from x; to x- In this case, the loss function:
W) D) +IIII + + ph(W)
prevents the addition of any edge (u, v) that would establish path from æt æz in an updated graph G', where G' = (X, v)), as long as p is sufficiently large.
Proof. Denote by Py. any directed path from Iÿ to Fg. We first analyze
d d
V w.. h(W)
V Ww... (WW1
q=1
Because each [W|, 1gg has nonnegative partial derivatives and WWel 2 for edges present in G(W), we get
V W h(W)
i.... lw.... W
Σ
lpya
II <EPL..
[Wel II [el.
Pa.sPr. Po..
eEPo.
where Pj ranges paths 2j 2i. lpyal denotes the length of the path, Pi,u ranges paths H, T, and Pn.j ranges over paths T. Z---
Assume there is directed path 24 My in G(W), but adding the edge (iu) would create one. Then G(W) must already contain at least one path 2; mr nu and one path zo ar I.. Thus,
Vi.... ((W)
Jpsal II
Wel II eEPv.)
Weel 2 co
Ps.t:P,us Po.j
eEPL.
Denote ko
1pss| + pi.ul + |Pell-
Next, consider the overall gradient of
C(D,W) F(W;D) A + (D(W)) + ph(w).
Taking the partial w.r.t [Wu,els
V I(D,,) = F(W: D) + + (B(W))., + ViW., h(W). h(W).
Since V V.w..,h(W)> 2 c we have
V V C(D,W)
pEd
Hence,
|a|
p
2
ko
then C(D,,) 2 0, forcing the gradient update to reduce [Wa,el (i.c., disfavor adding the edge (æ x.))..
Thus, for all p above that finite threshold / the absolute weight of (Inr (.)) is pushed down to forbid its presence in G(W). This completes the proof.
Proposition (Ban et al., 2024, Proposition 2)). Given a partial order set 0 = {2; x x. ) a DAG G satisfies O if and only if, for all x; K 2y O+, there exists no directed path from x to T, G.
22

---

Differentiable Structure Learning with Ancestral Constraints
Proof. We aim to establish the equivalence:
There exists at least one topological order π of G that satisfies O Vz < 2j E 0+, -a2 xx) in G.
(-): Assume there is topological ordering π of G that satisfies O. By definition of topological ordering, if xz is an ancestor of 2 in G, then zi must appear before 2 in æ. Because respects the constraints in O, for every (1,j) 0+ have 2, placed before zy in æ. Suppose, for contradiction, that there is a directed path 2, 2, in G. Then zj is ancestor of z; and should appear before 2; in any topological ordering, contradicting the fact that z; is before zÿ in n. Hence, no such path z ~) Ij exists, proving this direction.
(=); Conversely, suppose that for every (i.j) E O+, there is no directed path zj we I2 in G. Since G is a DAG, possesses at least one topologiaal ordering (constructible via, e-g., Kahn's algorithm or a depth- first search approach). We now argue that this ordering can be adjusted, or equivalently, we can choose valid ordering outright, so that all pairs in O respected. Because the absence of path 2j 2; ensures no cycle is created by demanding 2; precede Z.j, none of the constraints in O is violated. Thus can finalize a topological ordering и of G in which, for each (i,j) E O+, appears before Ty. Hence G has topological ordering that satisfies all order constraints in O.
Combining both directions, we conclude that the existence of topological ordering G satisfying O is equivalent to having no path 2- ~4 24 G for every (i. E O+
Proposition Each optimal solution of the equality-constrained problem (5) corresponds to the global optimum of the following convex optimization problem:
min W WERexd
|ID(W M) - D1 ||[W||,
(25)
where Mr = if (j) and M.j = 0 otherwise, for a specific permutation of (1, (1, d}.
Proof. We begin with the equality-constrainee problem
min We
DDW - 21/ + A AIIII, subject to h(W) = 0.
(40)
Let W' be an optimal solution to (40). By feasibility, h(W') = 0, and by the stationarity condition (assuming a Lagrangian approach),
VS(W") l Vh(W") 0,
(41)
where f(W)- IDW DI1 A | and μ is the Lagrange multiplier associated with h(W) 0.
By definition of h(.), the condition h(W*) = 0 means that G(W) is DAG, and there is a permutation и of .d} such that
W whenever t(i) 2 T()).
Equivalently, W" is strictly upper- upper-triangulat up to reindexing of rows and columns by л. Define binary matrix M (0, jdxd by
Ma = I1, if (1) < <()).
0. otherwise.
Then W M W* because multiplying by Ma,j zeroes out all entries below or on the diagonaa"..."
Consider the convex program
D(W o M) -D1 + A |||
min x
(42)
Since W o M zeroes out the same pattern enforeed by M, the feasible set effectively restricts (W M) that strict upper-triangular shape under π. Let W' be optimal solution to (42); by standard convexity arguments, stationarity implies
o/ D(W' o M) - D 1 + X XV = O.
(43)
23

---

Differentiable Structure Learning with Ancestral Constraints
(This is taken with respect W', understanding that the chain rule also includes the elementwise product with M, but crucially (W' M) is valid for all nonzero coordinates consistent with the triangular structure.) We claim W also satisfies the stationarity for (42). Note first that
W M W"
The equality /((")) = (strict upper- apper-triangulat structure) also implics that any partial derivative of h(-)) w.r.. Wi, is zero whenever T(() < T Concretely, if we treat h(.) as a sum of path-indicator terms, no path q ~ and j ~y q can coexist
unless (j) (g) Ti)), contradicting xii) T(j). Hence:
/ = 0 for x(1) < πT T()).
Because those are precisely the coordinates in which W* could be nonzero, we get
Vh(W* o M) 0.
Returning to (41),
Vf(WW* o M) + μ (W M) =0 = Vf(WW* o M)
Thus W' satisfies the first-order condition for problem (42), i.e.
v D(W o M) D D + A \ = 0.
Since (42) is a convex optimization problem (sum of a smooth convex term and an é e-regularization), any W that satisfies the stationarity condition must be a global optimum. From (43) and the stationarity for W we see W and W both satisfy the same gradient condition. Therefore W" W"
We have shown that every global optimum W* of (40) (with h(W*) 0) coincides with the global optimum W' of the convex problem (42) defined by the matrix M associated with the same permutation æ. This completes the proof.
D. Complete Experimental Results and Analysis
This section provides a comprehensive analysis of our experimental results. First, we evaluate additional aspects not covered in the main text, including time complexity, results on nonlinear data, the integration of path absence constraints, the results of various backbone algorithms and the impact of varying constraint numbers. Then, we present supplementary results under more extensive settings for the experiments discussed in the main text.
D.1. Time Complexity
The primary computational cost in our approach arises from matrix operations. The time complexity of standard matrix multiplication for d x d matrix is O(d3). The key function in our proposed loss, p(W), involves computing p(W) = Σi= |W]k, which has time complexity of Odd*). This exceeds the computational cost of commonly used acyclicity losses, which are ((d)) However, this additional overhead can be mitigated through GPU acceleration.
To evaluate the efficiency of our method, implemented two versions: one using CPU for all computations and another utilizing GPU for computing the gradients of the newly introduced loss terms. The data approximation loss and acyclicity loss were computed on the CPU in both cases.
We denote the process of solving the partial crder-constrained problem as PO-NOTEARS and the process of using the PO-NOTEARS result as an initial guess for solving the path existence-constrained problem as PE-NOTEARS-path Note that the sum of run time of PO-NOTEARS and PE-NOTEARS-pun -atth is the total time consumed by PE-NOTEARS, the method used to integrate ancestral constraints.
Figure 4 compares the runtime of these approaches using both CPU and GPU implementations. that solving the PO- PO-constrained problem is the most computationally expensive step, whereas solving the PF-constrained problem is significantly faster, with runtime comparable to the standard NOTEARS algorithm.
The results indicate
Additionally, GPU acceleration provides a large speedup. particularly as the number of nodes increases. This demonstrates the potential for integrating our method into deep learning systems, where efficient GPU-based implementations are crucial.
24

---

Differentiable Structure Learning with Ancestral Constraints
time (log10 s)
10
20
30
50
NOTEARS-CPU
PE-NOTEARS-path--OE
PE-NOTEERSS -EEEEARRS-PpPPPP
PO-NOTEARS-CTP
PO-NOTEARS-GPU
Algorithm
Figure 4. Comparison time between GPU and CPU versions of the proposed method.
D.2. Improved Time Complexity by Accelerating Matrix Power Iteration
Zhang al. (2022) introduced an fast truncated matrix power iteration (fast TMPI) algorithm that is suitable for accelerating the calculation of matrix power iteration defined in the path existence loss, which is in complexity O log d), comparable with the complexity Odd)) of common acyclicity losses.
Below, we compare fast TMPI against the original direct matrix power operation under the following setting: ER2 graph, linear SEM with Gaussian noise, and 80% prior paths. Results of the run time (in seconds) and F1 score are reported as Direct Matrix Power / fast TMPI for PE-NOTEARS under varioud node numbers (@ (Nodee).
Node
10
20
30
Time (s)
29.8 / 26.7
106.4 99..3
90.3
269.3 188.3
973.6 153.6/500 500.8
Fl Score
0.87 0.88
0.77 / 0.77
0.68 / 0.68
0.61 0.661
We observe that PE-NOTEARS with fast TMPI achieves a significant speedup large-scale graphs while maintaining comparable performance. This confirms that fast TMPI integrates effectively into our approach, reducing time complexity from (dd*) to (d log d), making it competitive with the ((d)) complexity of NOTEARS.
NOTEARS
PE-NOTEARS-2eTO
PE-NOTEARS
200
-100
n
n=1000
n-200
1000
100
ER2
0.8
0.5
BR2
Score
FDR
200
1.0
ERR
0.8
ER4
100
0.5
0.0
10
20
30
20
30
30
20
30
10
20
10
20
30
d (Number of Nodes)
(Number of Nodes)
d (Number of Nodes)
200
1000
n=200
n=1000
n
1000
1.0
0.5
Path Recovery Rate
ERO
ERE
BR2
0.2
0.6
70.8
TPR
220.0
1.0
0.8
DRA
1.0
bR4
0.8
0.5
0.0
10
20
30
10
20
30
d (Number of Nodes)
d
(Number of Nodes)
d (Number of Nodes)
Figure 5. Comparison and ablation results nonlinear data.
25

---

Differentiable Structure Learning with Ancestral Constraints
D.3. Results on Nonlinear Data
This experiment evaluates our method on nonlinear data using NOTEARS-MLP (Zheng et al., 2020) as the backbone algorithm. The nonlinear data is generated based on the binary mask of the ground truth structure W. Uniformly random weights are assigned to the elements where Wa 1, denoted as W1, W2, W3. Given these weights, samples are generated according to the following nonlinear model:
D (DW1) + cos(DW2) + sin)) +2, 2 ~~~000
(44)
We compare the performance of the NOTEARS, PE-NOTEARS, and PE-NOTEARS- (which removes order-guided optimization and uses a zero matrix as the initial guess), using MLP to data distributions (Zheng et al., 2020). The results, reported in Figure 5, show that PE-NOTEARS consistently outperforms both NOTEARS and PE-NOTEARS- achieving lower SHD, higher Fi-score, and lower FDR.
Additionally, PE-NOTEARS demonstrates significantly higher TPR compared NOTEARS, indicating that incorporating path existence constraints effectively enhances the recovery of causal links. PE-NOTEARS-Zen achieves higher TPR than PE-NOTEARS but at the cost of recovering a large number of redundant edges, as reflected in its high SHD and FDR.
Regarding the path recovery rate, PE-NOTEARS consistently recovers the most paths from priors, confirming the effective- ness of order-guided optimization in resolving prior violations. Notably, despite PE-NOTEARS- Rero introducing many redundant edges, still fails to match PE-NOTEARS in satisfying path existence constraints. This further validates the importance of using partial order-guided initial guess to support path existence constraints.
NOTEARS
PA-NOTEARS
10
d=20
30
d=10
4=
d=30
d=20
07-11
0.8
07-11
SHD
F1 score
0.6
0
1.0
000 -1
5
0001
0000
0.0
Prior Ratio of Path Absence
Prior Ratio Path Absence
Prior Ratio of Path Absence
10
d=20
d=30
10
d=20
d d=30
d=10
d=20
d=30
0.3
Path Forbidden Rate
1.0
0.8
07=u1
0.2
0.8
0.1
0.10
00 Ill
1.0
000
0.05
000
0.9
0.00
0.8
0.5
0.5
0.5
0.5
0.5
0.5
Prior Ratio of Path Absence
Prior Ratio of Path Absence
Prior Ratio of Path Absence
Figure 6. Comparison results of the path absence-conssrriieed data-based structure learning.
D.4. Results on Path Absence Constraints
This experiment evaluates structure learning with path absence constraints. Since the characterization of path absence is straightforward, we did not include these results in the main text.
Using the characterization (p(W)),, where p(W) is defined as:
p(W)=
Σ W
(45)
This condition is equivalent to enforcing the absence directed path x; ~ Tz.
26

---

Differentiable Structure Learning with Ancestral Constraints
Given path absence mask B E {0, 10xx, where B represents the constraint -(1; v x;)) in G(W), we formulate the structure learning task as:
min WeR
DWW D112 + NIW + B (o(()) o B) s.t. h(W)= = =0
(46)
The path absence loss weight is set to 3 = 1. We denote the method solving this task as PA-NOTEARS and compare it with standard NOTEARS (without any prior constraints). The comparison results, with varying proportions of path absence constraints on ER-2 graphs, are shown in Figure 6. The results indicate that PA-NOTEARS consistently outperforms standard NOTEARS across all metrics, with greater improvements observed as the number of prior constraints increases. This improvement is expected, as path absence constraints are inherently aligned with the acyclicity loss in gradient direction, making them easy to enforce. The remaining unsatisfied constraints in the experiments are primarily due to the trade-off between data approximation and path absence loss.
Notably, path absence constraints can be viewed as an extension of the acyclicity constraint that further reduces the search space for optimal solutions. This connection aligns closely with the partial order constraints discussed in the main text, reinforcing the effectiveness of integrating path absence information into differentiable structure learning.
Discussion
Comparison with Path Existence A complete specification of path absence constraints effectively imposes precise restriction the set of potential edges in the graph. Specifically, we consider edge absence constraints as a subset of path absence constraints, since the absence of a path ~ 2y implies the absence of a direct edge + 2.. Thus, fully specifying all path absence constraints narrows the possible edge set to only those the ground truth. This makes path absence constraints strictly stronger than total ordering constraints, as a total order defines the set of potential edges (i.e., those respecting the order), while path absence constraints further eliminate incorrect edges.
In contrast, path existence constraints do not offer the same level of restriction. Even when all path existence constraints are specified, they do not uniquely determine any particular edge without additional assumptions. Moreover, path existence constraints provide no information about edge absence, the overall space of potential edges remains large. As result, we observe highly accurate outputs when many path absence constraints are available. However, such comprehensive prior knowledge is rarely accessible in practice. For d variables, specifying ((d)) path absence constraints is required to achieve this level of restriction, whereas significant improvements can be achieved with only ((d) path existence or partial order constraints. For example, total order requires just d partial orders or path existence constraints.
This comparison underscores the practical advantage of path existence constraints: while path absence provides stronger theoretical restriction, path existence is far more scalable and feasible in real-world applications.
D.5. Results with Varying Numbers of Path Existence Constraints
This experiment examines the impact of different numbers of path existence constraints on structure learning performance. We vary the prior percentage 9 and evaluate its influence several PE-constrained approaches, including PE-NOTEARS- intuitive (using p as the path existence loss), PE-NOTEARS-zen (using zero initialization), and PE-NOTEARS (ours). The results on ER-2 graphs are presented in Figure 7.
The findings indicate that PE-NOTEARS consistently outperforms other methods across different numbers of path constraints. An exception occurs in cases with 10 nodes, where PE-NOTEARS performs comparably to PE-NOTEARS. This because, with only 10 nodes, the ordering space is relatively simple, reducing the severity of order-violating issues even without order-guided initialization.
As the number of prior paths increases, the performance of PE-NOTEARS further improves. Notably, despite incorporating more prior path constraints, PE-TOSEARS is still accurate in edge recovery (as reflected in stable FDR and FPR values). In contrast, both ablation variants exhibit a substantial increase in false discoveries with more constraints.
These results further validate the effectiveness of using á as the path existence function and employing partial guder-guided optimization strategies for path constrice structure learning.
D.6. Results on Various Backbone Algorithms
This section evaluates the effectiveness of integrating path existence constraints into different backbone differentiable structure learning algorithms using our approach. The results for DAGMA and GOLEM are presented in Figures and 9,
27

---

Differentiable Structure Learning with Ancestral Constraints
NOTEARS
PE NOTEARS intuitive
NOTEARS zero
PE NOTEARS
20
1000
20
1-1000
n=
1=1000
1.00
0.5
0.75
0.0
1.0
score
SHDD
Oc-p
02=p
0.5
0.5
0.0
200
O==P
0.5
100
0.5
0.2 0.5
0.81
0.2 0.5 0.81
0 0.5 0.8
0.2
0.81
0.2 0.5
Path Existence Rate
Path Existence Rate
Path Existence Rate
20
n= 1000
n 20
n- 1000
n=
n=1000
1.00
1.0
10
O
01-p
0|=p
0.75
0.5
Path Recovery Rate
0.0
1.00
0.75
O2=p
0.50
OE=P o2-p
02=
0.25
0.50
0.00
1.00
0.4
OE=P
DE=P
0.2
0.8
0.50
0.0
0.2 0.5 0.8 0.2 0.5 0.8
0.2 0.5 0.8
0 0.5 0.8
0.2 0.5 0.81 0.2 0.5 0.8
Path Existence Rate
Path Existence Rate
Path Existence Rate
Figure 7. Comparison and ablation results with varying path existence constraint numbers.
respectively.
The findings indicate that our method significantly enhances the performance of both DAGMA and GOLEM by effectively incorporating path existence constraints. Additionally, the high path recovery rate demonstrates the effectiveness of order-guided optimization in resolving conflicts among prior constraints across different approaches.
These results confirm the broad applicability of our method, showing that it generalizes well to various differentiable structure learning frameworks for integrating path existence constraints.
D.7. Supplementary Results and Analysis from the Main Text
This section presents the complete experimental results corresponding the settings discussed in the main text. The supplementary results shown in Figures 10, 11, 12, 13, 14, and 15.
The specific experimental settings for these supplementary results are detailed in the captions of the respective figures.
28

---

Differentiable Structure Learning with Ancestral Constraints
DAGMA
PE-DAGMA
n=20
1=0000
20
n
1000
n=
1= 1000
1.0
1.0
0.5
ER2
0.8
ER2
SHD
0.5
0.0.0
220.0
1.0
0.5
0.8
FRR
ER4
0.6
0.0
10
30
5010
30
10
30
5010
30
10
30
5010
30
50
d (Number of Nodes)
d (Number of Nodes)
d (Number of Nodes)
n 20
n 1000
n=20
n=1000
n=
n=1000
1.0
0
Path Recovery Rate
1
0.8
ERC
E
BR2
0.6
FPR
5..8
1.0
1.0
0.8
02
ER4
ER4
224
99
0.0
0.8
10
5010 d (Number of Nodes)
10 5010
30
5010
50
d (Number of Nodes)
d (Number of Nodes)
Figure 8. Results of our approach with DAGMA.
GOLEM
PE-GOLEM
n
20
n --1000
n
20
n
100000
n=20
1000
1.0
2.0
ER2
ER2
Scaled SHDD
1.0
score
0.5
0.0
FDR
0.0
1.0
0.8
0.5
DRd
ERA
ER4
0.5
0.5
0.2
0.2
0.0
10
30
5010
30
50
10
30
5010
30
50
5010
d (Number of Nodes)
d
(Number of Nodes)
d (Number of Nodes)
n n=20
n
1000
n 20
n 1000
n=20
n= 1000
1.0
0.4
Path Recovery Rate
0.2
ER2
BRJ
0.8
0.8
TPR
FPR
0.0
1.0
0.8
0.5
PRA
0.5
ERI
0.5
HRA
0.2
10
30
5010
30
50
0.0
10
30
5010
30
50
0.0
5010
d (Number of Nodes)
d
(Number of Nodes)
d (Number of Nodes)
Figure 9, Results our approach with GOLEM.
29

---

Differentiable Structure Learning with Ancestral Constraints
NOTEARS
PE-NOTEARS-intuic
PE-NOTEARS-2e10
PE-NOTEARS
exp
causs
gumbel
exp
gumbel
exp
gumbel
400
0.75
BRe
200
0.50
500
500
250
ERA
0.75
FRH
1000
ER
score
0.50
SHD
200
300
ESS
0.75
SFP
355
0.50
100
0.25
400
400
PdS
0.75
200
0.50
10
30 solo
30
5010
30
50
10
30
5010
5010
30
10
30
3010
5010
30
(Number of Nodes)
d (Number of Nodes)
d (Number of Nodes)
exp
gauss
gumbel
exp
gaauss
gumbel
exp
gauss
gumbel
1.0
1.0
BR
0.50
0.5
0.8
Path Recovery Rate
1.0
0.5
ER
0.88
HDR
0.0
TPR
1.0
1.0
0.50
0.5
0.8
FAS
0.75
FFS
Fals
0.50
0.8
0.0
5010
30
10
30
5010
30
5010
30
d (Number of Nodes)
d (Number of Nodes)
d (Number of Nodes)
Figure 10. Supplementary comparison and ablations results with sample size 20.
30

---

Differentiable Structure Learning with Ancestral Constraints
NOTEARS
PE-NOTEARS-intuio
PE-NOTEARS
exp
gauss
gumbel
exp
graus
gumbel
exp
gauss
gumbel
1.0
BR2
ER2
BR2
200
0.5
0
1.0
ER4
BR4
250
score
0.5
SHD
0
2001
1.0
200
SF2
Fl
SF2
0.5
0
200
200
SPA
SF
200
FdS
100
30
5010
30
5010
30
50
0.50
10
30
5010
5010
50
%
5010
5010
30
50
d (Number of Nodes)
d (Number of Nodes)
(Number of Nodes)
exp
gauss
gumbel
exp
gauss
gumbel
exp
gauss
gumbel
1.0
1.00
0.5
FRZ
ER2
BR2
0.5
1.0
Path Recovery Rate
ERd
HR
TPR
0.5
1.0
ZP2
ZP2
0.3 1.00
0.8
1.0
hds
FSS
0.75
0.8
0.0
5010
30
5010
5010
10
5010
30
5010
30
d (Number of Nodes)
d (Number of Nodes)
d (Number of Nodes)
Pigure 11. Supplementary comparison and ablations results with sample size 1000.
31

---

Differentiable Structure Learning with Ancestral Constraints
NOTEARS
PE-NOTEARRS-ituiivv--00
SANOTEARS-intutivv-ordeee
PE-NOTEARRS-Orer
PE-NOTEARS-intuiive
SOOOTEARR-iinuiivv-orrrre 10
PE-NOTEARS--er0-0.5
PE-NOTEARS-
PE-NOTEARS-0.5
PE-NOTEARS--ero-D1
PE-NOTEARS--att--
PE-NOTEARS-10
ER2
ER4
ER2
ER4
ER2
ER4
100
0.8
07-
2Z=p
20
0.6
0.5
50
Fl score
SHD
0.4
FDR
0.2
0.8
200
0.8
OE=P
30
0.5
30
100
0.2
0.2
Algorithm
Algorithm
Algorithm
ER2
ER4
ER2
ER4
ER2
ER4
1.0
0.8
1.0
Path Recovery Rate
P
0C=p
0.5
0.8
22
0.5
0.2
TPR
FPR
0.6
1.0
0.6
0.5
0E=P
DE=P
0.8
0.2
0.4
P
Algorithm
Algorithm
Algorithm
Figure 12, Supplementary ablation results on initial random guesses with sample size n 20. The suftix 0.5 and 10 in the method reference is the value of path existence threshold
32

---

Differentiable Structure Learning with Ancestral Constraints
NOTEARS
PE:NOTEARRS-imuttvvo...
PE-NOTEARS-order
PE-NOTEARS-imtutive-llll
PE-NOTEAAS--imiiiv--odee.
PE-NOTEARS-ZerO-055
PE-NOTEARS-LaL--055
PE-NOTEARS-0.5
PE-NOTEARS-ZeTo-I1
PE-NOTEARS-datt-10
PE-NOTEARS-10
ER2
ER4
ER2
ER4
ER2
ER4
1.0
100
0.5
50
22
22
Fl score
FDR
V2200
1.0
0.5
30
100
30
30
0.5
0
0.0
Algorithm
Algorithm
Algorithm
ER2
ER4
ER2
ER4
ER2
ER4
1.0
1.0
Path Recovery Rate
0.8
02=p
0.5
02-D
0.8
0.5
TPR
FPR
0.0
1.0
1.0
O7=P
0.4
0.8
30
0.2
0.5
0.8
0.0
Algorithm
Algorithm
Algorithm
Figure 13. Supplementary ablation results initial random guesses with sample size 1000. The suffix 0.5 and 10 in the method reference is the value of path existence threshold c.
33

---

Differentiable Structure Learning with Ancestral Constraints
NOTEARS
PE-NOTEARS-intutivee
PE-NOTEARS-zero
PE-NOTEARS-imuttv--ottoe
PE-NOTEARS
ER2
ER4
ER2
ER4
ER2
ER4
100
0.8
0.8
O2
0.5
20
0.5
score
EDR
0.2
0.8
5000
00.8
D0
OE
d=
0.5
0.5
0.2
0.2
0.1 0.51
5100.1
0.51
510
0.1
0.51
5100.1
0.51
510
0.1
0.51
5100.1
1
0.51
510
3
E
ER2
ER4
ER2
ER4
ER2
ER4
1.0
Path Recovery Rate
07-p
oZ=p
0.6
0.8
TPR
FPR
1.0
OE
0
P
0.8
0.6
0.2
0.6
0.51
5100.1
0.51
510
0.51
5100.1
0.51
510
0.1
0.51
5100.1
0.51
510
3
Figure 14. Supplementary ablation results with varying path thresholds with sample size n 20. PE-NOTEARS intuitive-order refers to the method using path existence loss and the partial order-guider initial guess.
34

---

Differentiable Structure Learning with Ancestral Constraints
NOTEARS
PE-NOTEARS-imtulive
PE-NOTEARS
PE-NOTEARS-imuiivv-orrkr
PE-NOTEARS
ER2
ER4
ER2
ER4
ER2
ER4
100
1.0
OZ=P
0.5
0.8
50
Fl score
00.5
FDR
0.0
11.
22000
OH=P
0.5
03
0.5
0.1
0.51
5100.1
0.51
510
0.51
5100.1
0.51
510
0.1
0.51
5100.1
0.51
510
E
3
ER2
ER4
ER2
ER4
ER2
ER4
1.0
1.0
P Recovery Rate
02
0.5
0Z=p
d=20
0.8
00.8
00.0
1.0
0E=P
0E=P
0.8
0.2
0.9
DE
0.0
0.8
0.1 0.51 5100.1
0.51
510
0.1
0.51
5100.1
0.51
510
0.1
0.51
5100.1
0.51
510
3
Figure Supplementary ablation results with varying path thresholds with sample size n 1000. PE-NOTEARS -nnuuteeAR--ituiiiv--ooreerrrr refers
the method using p path existence loss and the partial order-guided initial guess.
35


Reviews:
[{"review_id": "E7gynNKVeh", "reviewer": "Reviewer_de6D", "summary": "The paper addresses the problem of incorporating ancestral (path) constraints into differentiable causal structure learning methods, specifically NOTEARS-style algorithms. The authors identify two key issues with existing differentiable formulations: a non-equivalence issue in previous continuous relaxations of path-existence constraints, and an order-violation issue where constraints might fail during gradient-based optimization. They propose a binary-masked characterization of the path-existence constraint that precisely captures path presence equivalently and an order-guided optimization strategy that initializes optimization using a DAG consistent with ancestral orders. The contributions consist of (i) a principled framework for differentiable causal discovery with arbitrary ancestral constraints, (ii) a new equivalently valid path constraint formulation, and (iii) an order-guided optimization strategy to satisfy constraints and achieve higher accuracy.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review. We will discuss the relevant references you mentioned in the paper. Here are our responses to your questions.\n\n# Reply to Questions\n\n1. The edge threshold $\\epsilon_0$ is a standard parameter in differentiable structure learning, set to $0.3$ following the default in NOTEARS in the paper. To address your concern, we experiment with varying $\\epsilon_0$ and report the results (**NOTEARS / PE-NOTEARS**) below. The settings are: 20 samples, 20 nodes, ER2 graphs, linear Gaussian SEM, and 80% paths.\n\n   | $\\epsilon_0$ | 0.1         | 0.3         | 0.5         | 0.7         | 1.0         |\n   | ------------ | ----------- | ----------- | ----------- | ----------- | ----------- |\n   | FDR          | 0.58 / 0.57 | 0.43 / 0.29 | 0.27 / 0.19 | 0.16 / 0.11 | 0.11 / 0.02 |\n   | TPR          | 0.75 / 0.71 | 0.68 / 0.84 | 0.60 / 0.79 | 0.50 / 0.70 | 0.25 / 0.57 |\n   | PathRecovery | 0.90 / 0.91 | 0.83 / 1.00 | 0.70 / 0.98 | 0.52 / 0.88 | 0.21 / 0.72 |\n\n   When $\\epsilon_0$ is set too small, noisy edge weights insignificant for causality frequently fall near the threshold, causing instability as the binary mask $b(W)$ repeatedly flips between 0 and 1. Conversely, when $\\epsilon_0$ is too large, the path existence loss strongly conflicts with the data fit loss by forcing edge weights to exceed their true values. Thus, data fit can override the path recovery. \n\n   In practice, selecting $\\epsilon_0$ can be guided by either the optimal path recovery rate (e.g., optimal around $\\epsilon_0=0.3,0.5$ in this case) or the distribution of edge weights from NOTEARS (above the min region where edge weights are concentrated).\n\n2. To evaluate error tolerance, we randomly introduce erroneous paths at a certain ratio (termed ErrorRatio) relative to correct ones (without creating cycles). Below, we report results comparing F1 scores and recovery rates of correct (@✅) and erroneous (@❌) paths for **NOTEARS / PE-NOTEARS**. The settings are: 20 nodes, ER2 graphs, 20 samples, linear Gaussian SEM, and 80% paths.\n\n   | ErrorRatio | 10%         | 20%         | 30%         | 40%         |\n   | ---------- | ----------- | ----------- | ----------- | ----------- |\n   | F1         | 0.62 / 0.68 | 0.62 / 0.70 | 0.62 / 0.52 | 0.62 / 0.32 |\n   | @✅         | 0.83 / 0.97 | 0.83 / 0.99 | 0.83 / 0.84 | 0.83 / 0.85 |\n   | @❌         | 0.20 / 0.50 | 0.23 / 0.61 | 0.20 / 0.40 | 0.17 / 0.38 |\n\n   When the ErrorRatio exceeds approximately 30%, PE-NOTEARS underperforms NOTEARS, exhibiting significantly reduced F1 recovery of correct paths. This result provides a practical estimate of the error tolerance of PE-NOTEARS.\n\n3. Order-guided initialization is obtained by solving the partial order-based structure learning problem in Eq. (23), providing a stable initialization that typically does not require additional selection.\n\n   If you instead refer to an arbitrary initialization that satisfies partial orders without solving Eq. (23), we tested an intuitive initialization using the matrix $\\epsilon_0 A$ (where $A$ is the path mask), denoted as PE-NOTEARS-A. We report results for **NOTEARS / PE-NOTEARS / PE-NOTEARS-A** below:\n\n   | @Node        | 20                 | 30                 | 50                 |\n   | ------------ | ------------------ | ------------------ | ------------------ |\n   | F1           | 0.62 / 0.77 / 0.67 | 0.52 / 0.68 / 0.59 | 0.45 / 0.61 / 0.55 |\n   | PathRecovery | 0.82 / 0.99 / 0.99 | 0.83 / 1.00 / 0.99 | 0.79 / 0.98 / 0.96 |\n\n   We observe that while the simpler partial order-consistent initialization (PE-NOTEARS-A) recovers most paths, it yields less optimal DAG structures compared to order-guided optimization. This is because solving Eq. (23) achieves a good optima simultaneously for partial orders and data fit, effectively mitigating conflicts with both acyclicity and data fit. In contrast, the partial-order-only initialization does not resolve conflicts with data fit, resulting in suboptimal performance.\n\n4. Actually, our order-guided optimization effectively resolves the issue of acyclicity constraints overriding path existence. To demonstrate this, we experiment with large path existence loss weights, ensuring this loss dominates the data fit loss and leaves the main trade-off between path existence and acyclicity.\n\n   In the experiment, PE-NOTEARS (with order guidance) still achieves strong adherence to prior paths and maintains good structural metrics. In contrast, methods without order guidance suffer significantly from acyclicity constraints overriding path existence, resulting in numerous unsatisfied paths due to order violations.\n\n   Please refer to the related results in the section *Evidence on Order-Violation* of our responses to reviewer MDE7.\n\n5. Following the suggestion of reviewer tD5o, we have reduced the complexity to $O(d^3 \\log d)$. Please refer to point 3 in our responses to reviewer tD5o for detailed results.", "claims_and_evidence": "The claims made by the authors are generally well supported by theoretical proofs and fair experiments. In particular, the central theoretical claim--that the masked constraint formulation exactly characterizes path existence--is substantiated by clear lemmas and theorems (Theorem 1) with complete proofs provided in the appendix.\n\nThe empirical claims are also well supported by comprehensive experiments and ablation studies, demonstrating improvements in DAG accuracy (SHD and F1 scores) and better satisfaction of path constraints compared to naive methods and baseline NOTEARS. Ablations specifically isolate the effects of the proposed masked constraint and order-guided initialization, validating each independently.", "methods_and_evaluation_criteria": "I think the proposed methods and evaluation criteria are appropriate. The authors select established differentiable learners (NOTEARS, DAGMA, GOLEM) as baselines, conduct extensive evaluations using synthetic benchmarks varying graph sizes/types and amounts of prior knowledge, and utilize standard accuracy metrics (SHD, TPR, FDR, F1). Importantly, they explicitly measure a \"path recovery rate\", directly assessing constraint satisfaction--a reasonable metric for their problem setting.", "theoretical_claims": "I checked in fair depth the theoretical claims provided in the main text and skimmed the appendix. The authors' derivations seem sound.", "experimental_designs_or_analyses": "The experimental design was sound and supports the authors' claims. Experiments varied constraints, initializations, and thresholds, thoroughly validating robustness and highlighting specific advantages. Minor points were noted, such as the absence of explicit testing for the scenario with incorrect priors (which could influence practical applicability). Nevertheless, I think the overall empirical evidence was compelling.", "relation_to_broader_scientific_literature": "I think the work is well-situated within existing literature, clearly bridging classical approaches (eg. constraint-based or score-based methods utilizing ancestral constraints) with modern differentiable structure learning methods. It identifies clear limitations of previous differentiable methods and improves on recent works by offering a general, theoretically sound approach for arbitrary ancestral constraints.", "essential_references_not_discussed": "In general the authors do a good job on referencing relevant literature. I think the authors could consider citing [1], which is an older foundational work on structural priors and partial orders, as well as [2], which is a more recent work also dealing with partial orders and notears-like differentiable structure learning.\n\n[1] Heckerman, et al. \"Learning Bayesian networks: The combination of knowledge and statistical data.\" Machine learning 1995.\n\n[2] Deng et al. \"Optimizing notears objectives via topological swaps\". ICML 2023.", "other_strengths_and_weaknesses": "Key strengths include the originality and theoretical rigor of the proposed masked path formulation, systematic empirical validation, robust experimental design, and clear presentation. The authors identified fundamental limitations of naive differentiable constraints and clearly justified their proposed solutions. The resulting method demonstrated practical effectiveness, especially in scenarios with limited data but high-quality expert knowledge.\n\nWeaknesses primarily involve computational complexity ($O(d^4)$), limiting scalability to large graphs (though GPU acceleration partly mitigates this), reliance on threshold hyperparameters $(\\epsilon,\\epsilon_0)$, and unaddressed robustness to incorrect or noisy priors. These aspects, however, are openly acknowledged by the authors and represent reasonable future directions rather than critical flaws.", "other_comments_or_suggestions": "No minor comments.", "questions_for_authors": "1. How sensitive are your results to the choice of edge threshold $\\epsilon_0$ used for binary masks, and how should practitioners select it in practice?\n\n2. How would the algorithm behave if provided ancestral constraints are incorrect or contradictory? Can it gracefully handle noisy or uncertain priors?\n\n3. Did the choice of DAG from partial-order initialization significantly affect the final results when multiple DAGs satisfy given partial orders? Should multiple initializations be tried?\n\n4. Could the growing strength of the acyclicity penalty potentially override satisfaction of path constraints during optimization? How was this handled?\n\n5. Do you have ideas or preliminary results on efficiently approximating or reducing computational complexity ($O(d^4)$) of the path existence formulation to scale beyond graphs of 50 nodes?", "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": "1pLySRhZD7", "reviewer": "Reviewer_tD5o", "summary": "The paper addresses the challenge of integrating ancestral constraints into differentiable structure learning for causal directed acyclic graphs (DAGs). The key problem is how to incorporate prior knowledge about the existence or absence of paths between variables (ancestral constraints) into the learning process, which is typically formulated as a continuous optimization problem. The authors identify two main issues: the non-equivalence of relaxed characterizations for representing path existence and the order violations among paths during optimization.\n\nTo tackle these challenges, the paper proposes a **binary-masked characterization method** and an **order-guided optimization strategy**. The binary-masked method ensures an equivalent representation of path existence by selectively activating constraints based on whether a path already exists. The order-guided strategy enforces partial order constraints implied by path existence, ensuring that the optimization process avoids order-violating paths and converges to favorable optima.\n\n### Key Contributions:\n1. **First Systematic Approach**: This is the first paper to systematically address the integration of ancestral constraints into differentiable structure learning, allowing the use of abstract prior knowledge to guide the discovery of fine-grained causal mechanisms.\n   \n2. **Binary-Masked Characterization**: The authors propose a binary-masked continuous relaxation that accurately represents path existence, addressing the non-equivalence issue in previous relaxed characterizations.\n\n3. **Order-Guided Optimization**: The paper introduces an optimization strategy that enforces partial order constraints derived from path existence, ensuring that the optimization process avoids suboptimal solutions caused by order violations.\n\n### Methodology:\n- **Path Existence Constraints**: The authors formulate the problem of path existence constraints using a continuous relaxation of the path existence condition. They show that previous relaxed characterizations fail to equivalently represent path existence and propose a binary-masked method to address this issue.\n  \n- **Order-Guided Optimization**: The optimization strategy begins by enforcing partial order constraints implied by path existence, deriving a DAG that satisfies all specified path orders. This order-consistent DAG is then used as the initial adjacency matrix to optimize the path existence-constrained problem.\n\n### Theoretical and Empirical Validation:\n- The paper provides theoretical justification for the correctness of the proposed approach, showing that the binary-masked characterization and order-guided optimization strategy effectively address the challenges of integrating ancestral constraints.\n  \n- Experimental evaluations on both synthetic and real-world datasets demonstrate the effectiveness of the proposed method. The results show that the approach outperforms baseline methods and ablation variants, achieving better adherence to path existence constraints and higher accuracy in recovering causal structures.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed review and thoughtful comments. Here are our responses.\n\n### 1. Non-Differentiability of Binary Mask\n\nWe provide empirical evidence that incorporating the binary masked path existence loss, $\\bar{p}(W)\\circ b(W)$, does not compromise optimization stability. To evaluate this, we define an edge as *unstable* if its weight lies near the threshold $\\epsilon_0 = 0.3$ used to compute $b(W)$. Here, an edge is unstable when $|W_{i,j}| \\in [2.9, 3.1]$.\n\nWe then report the proportion of unstable edges relative to the total recovered edges for both PE-NOTEARS (which employs the binary mask) and the original NOTEARS method. Settings are: sample size $n=20$, ER2 graphs, Gaussian noise, and a path percentage $p=80$.\n\n| @Node    | NOTEARS         | PE-NOTEARS      |\n| ---- | --------------- | --------------- |\n| 10   | $3.4 \\pm 2.7$%  | $5.5 \\pm 4.7$%  |\n| 20   | $5.8 \\pm 3.1$%  | $5.7 \\pm 2.6$%  |\n| 30   | $5.5 \\pm 1.8$%  | $5.4 \\pm 1.5$%  |\n| 50   | $10.0 \\pm 2.0$% | $10.0 \\pm 2.1$% |\n\nThe results show that the proportion of unstable edges in PE-NOTEARS is comparable to that in NOTEARS. If the non-differentiability of $b(W)$ were to introduce instability, we would expect a significantly higher number of edges with weights near the threshold, where the binary mask could abruptly flip between 0 and 1. However, the results indicate that this is not the case.\n\nThus, by demonstrating that weights rarely fall into the narrow unstable interval, we confirm that the binary masked loss remains stable. The stable behavior of the underlying continuous function $\\bar{p}(W)$ ensures that most updates occur in regions where $b(W)$ is constant, preserving smooth optimization dynamics. This evidence supports that the binary mask $b(W)$ does not adversely affect the stability of the optimization process.\n\nWe also explored a *purely continuous formulation* for characterizing path existence, as detailed in Appendix B.2. This approach leverages the logical duality between path presence and absence, ensuring a strict correspondence with the existence of at least one path. However, the dual formulation involves computing a product over terms that grows exponentially with the number of nodes, which leads to numerical stability issues in practice.\n\n### 2. Gradient Conflicts\n\nThe gradient conflict arises inherently between path existence and acyclicity constraints, as illustrated in Proposition 4. When enforcing path existence, we push edge weights toward larger absolute values, whereas the acyclicity constraint forbids cycles, thereby pushing edge weights in the opposite direction. A loss in gradient consistent with acyclicity thus **cannot simultaneously enforce the existence of specific paths**.\n\nYour suggested formulation—the absence of reversed paths—actually represents partial ordering implied by path existence, which is a **weaker** condition that does not enforce explicit paths. Indeed, optimizing with partial-order constraints serves as the first part in our method to derive order-consistent initializations for paths, as detailed in Sec. 4.2.\n\nWe also empirically compare partial-order-based and path-existence-based structure learning in Fig. 12 (Appendix D). Results demonstrate that partial-order-based methods satisfy fewer path-existence constraints than our explicit path-existence-based method. See point 4, responses to Reviewer mwJt for more details.\n\n### 3. Computational Complexity\n\nThank you for your suggestion. We implemented the accelerated matrix power (and gradient) computation algorithm—fast TMPI with $O(d^3\\log d)$ complexity—proposed in *Truncated Matrix Power Iteration for Differentiable DAG Learning*. Below, we compare fast TMPI against the original direct matrix power operation under the setting: ER2 graph, linear SEM with Gaussian noise, and 80% prior paths. Results are presented as **Direct Matrix Power / fast TMPI** for PE-NOTEARS.\n\n| @Node    | 10          | 20           | 30            | 50            |\n| -------- | ----------- | ------------ | ------------- | ------------- |\n| Time (s) | 29.8 / 26.7 | 106.4 / 90.3 | 269.3 / 188.3 | 973.6 / 500.8 |\n| F1       | 0.87 / 0.88 | 0.77 / 0.77  | 0.68 / 0.68   | 0.61 / 0.61   |\n\nWe observe that PE-NOTEARS with fast TMPI achieves a significant speedup on large-scale graphs while maintaining comparable performance. This confirms that fast TMPI integrates effectively into our approach, reducing time complexity from $O(d^4)$ to $O(d^3\\log d)$, making it competitive with the $O(d^3)$ complexity of NOTEARS.\n\n### 4. Discussion on Path Absence Constraints\n\nWe will further discuss the connection between path absence constraints and partial orders to provide deeper insights. Additionally, we will present a direct comparison between path existence and path absence constraints (currently shown in separate figures) to improve clarity.", "claims_and_evidence": "To the best of my knowledge, there is sufficient evidence to the claims.", "methods_and_evaluation_criteria": "#### **Strengths:**\n\n1. **Novel Contribution to Differentiable Structure Learning**:\n   - The paper makes a significant contribution by addressing the integration of **ancestral constraints** (path existence constraints) into differentiable structure learning. This is a novel and important extension of existing methods, as it allows for the incorporation of abstract prior knowledge about causal relationships, which is often available in real-world applications.\n   - The proposed **binary-masked characterization** and **order-guided optimization strategy** are innovative solutions to the challenges of representing path existence and avoiding order violations during optimization.\n\n2. **Theoretical Justification**:\n   - The paper provides a strong theoretical foundation for the proposed methods, including proofs and lemmas that justify the correctness of the binary-masked characterization and the order-guided optimization strategy. This theoretical rigor enhances the credibility of the approach.\n\n3. **Empirical Validation**:\n   - The authors conduct extensive experiments on both **synthetic and real-world datasets**, demonstrating the effectiveness of their approach. The results show that the proposed method outperforms baseline methods and ablation variants, particularly in terms of **path recovery rate** and **adherence to path existence constraints**.\n   - The experiments also highlight the robustness of the method across different settings, including varying numbers of nodes, edge densities, and sample sizes.\n\n4. **Generalizability**:\n   - The proposed method is shown to be compatible with different backbone differentiable structure learning algorithms, such as **NOTEARS**, **DAGMA**, and **GOLEM**. This demonstrates the broad applicability of the approach across various frameworks.\n\n5. **Addressing Order Violations**:\n   - The **order-guided optimization strategy** is a key strength, as it effectively addresses the issue of order violations among paths, which can lead to suboptimal solutions. By enforcing partial order constraints, the method ensures that the optimization process converges to solutions that respect the specified path existence constraints.\n\n---\n\n#### **Weaknesses:**\n\n1. **Non-Differentiability of Binary Mask**:\n   - A significant drawback of the proposed method is that the **binary mask** $ b(\\mathbf{W}) $ is **not differentiable**. This undermines the core idea of differentiable structure learning, as the optimization process relies on gradient-based methods. The non-differentiability of $ b(\\mathbf{W}) $ could lead to instability during optimization and make the method less effective in practice.\n   - The authors should consider alternative approaches to ensure differentiability, such as using smooth approximations of the binary mask or exploring other differentiable representations of path existence.\n\n2. **Gradient Conflicts**:\n   - The proposed constraints for ensuring path existence can lead to **gradient conflicts** with the acyclicity loss. This is a critical issue, as gradient conflicts can hinder the optimization process and result in suboptimal solutions.\n   - A simpler and more effective solution would be to relax the problem by constraining the **absence of the reverse edge** $(j, i)$ instead of enforcing the existence of the path $(i, j)$. This can be done by setting $ p(W)_{ij} = 0 $, which avoids gradient conflicts and is easier to optimize. The authors should consider adding this approach as a baseline in their experiments.\n\n\n3. **Computational Complexity**:\n   - The proposed method involves computing $ p(W) = \\sum_{k=1}^{d} |W|^k $, which has a time complexity of $ O(d^4) $. This is significantly higher than the $ O(d^3) $ complexity of standard acyclicity losses, making the method computationally expensive, especially for large graphs. One possible way is to use the approach in Zhang, Zhen, et al. \"Truncated matrix power iteration for differentiable DAG learning.\" Advances in Neural Information Processing Systems 35 (2022): 18390-18402, which should be $O(d^3 \\log d )$. A possibily further speed up can be find in Zhang et. al. Analytic DAG Constraints for Differentiable DAG Learning, ICLR 2025, which is $O(d^3)$. \n\n\n   - While the authors suggest that GPU acceleration can mitigate this issue, the high computational cost remains a limitation, particularly for large-scale applications.\n\n4. **Limited Discussion on Path Absence Constraints**:\n   - The paper briefly mentions path absence constraints but does not explore them in depth. Path absence constraints are easier to enforce and align well with the acyclicity loss, as they do not cause gradient conflicts. The authors should consider expanding their discussion on path absence constraints and comparing their performance with path existence constraints.\n\n---\n\n#### **Suggestions for Improvement**:\n1. **Address Non-Differentiability**:\n   - The authors should explore differentiable approximations of the binary mask $ b(\\mathbf{W}) $ or alternative representations of path existence that are fully differentiable. This would improve the stability and effectiveness of the optimization process.\n\n2. **Incorporate Constraints without Gradient Conflicting**:\n   - The authors should consider adding the simpler approach of constraining the absence of the reverse edge $(j, i)$ as a baseline. This approach avoids gradient conflicts and is easier to optimize, providing a useful comparison to the proposed method.\n\n3. **Better Time Complexity**\n  - The time complexity of the approach may be reduced to $O(d^3)$.", "theoretical_claims": "I have checked the proof in detail and they should be correct.", "experimental_designs_or_analyses": "The experimental design is good and sound.", "relation_to_broader_scientific_literature": "I did not find a issue in the part.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See above weakness and strengths.", "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": "D2MV0qb4YM", "reviewer": "Reviewer_mwJt", "summary": "This paper introduces a framework for integrating ancestral constraints into differentiable structure learning of causal DAGs, addressing challenges in representing path existence and order violations. The authors propose a binary-masked characterization method and an order-guided optimization strategy to improve constraint adherence. Theoretical analysis and empirical evaluations on synthetic and real-world datasets demonstrate the method’s effectiveness.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful review. Here are our responses.\n\n# Responses\n\n2. Wang et al. formulate the path existence loss as $\\text{ReLU}(\\epsilon - |W|^k_{i,j})$ (Eq. (22) in their paper), assuming a known path length $k$. Without this assumption, the formulation naturally generalizes to $\\text{ReLU}(\\epsilon - \\sum_k |W|^k_{i,j})$, precisely matching the intuitive function $\\bar{p}(W)$ introduced in Sec. 3.1. Thus, the ablation labeled *-intuitive* reflects Wang et al.'s method under unknown path length. We will clarify this explicitly in the revised manuscript.\n\n3. See point 5.\n\n4. Specifying path existence (PE) benefits the recovery of missing edges without need of exactly identifying them, but it also risks introducing extra edges along the path. The observed degradation in F1 (or increased SHD) when adding constraints arises because the number of newly introduced extra edges outweighs the number of correctly recovered missing edges. However, since our method begins optimization from a good solution obtained by integrating partial order (PO) constraints—where extra edges have already been mitigated—FDR of PE-NOTEARS consistently improves compared to NOTEARS.\n\n   For a clear insight, we report the results (including a new case of 200 nodes) of structure learning under PO and PE constraints as **PO-NOTEARS / PE-NOTEARS (/ NOTEARS)**. Settings are ER2 graphs, 20 samples, linear Gaussian SEM, and 80% paths.\n\n   | @Node        | 10          | 20          | 30          | 50          | 200                |\n   | ------------ | ----------- | ----------- | ----------- | ----------- | ------------------ |\n   | TPR          | 0.78 / 0.81 | 0.74 / 0.79 | 0.69 / 0.75 | 0.62 / 0.66 | 0.39 / 0.42 / 0.21 |\n   | FDR          | 0.09 / 0.13 | 0.13 / 0.19 | 0.15 / 0.19 | 0.22 / 0.26 | 0.20 / 0.24 / 0.53 |\n   | PathRecovery | 0.96 / 0.99 | 0.84 / 0.98 | 0.81 / 0.96 | 0.74 / 0.89 | 0.46 / 0.61 / 0.12 |\n\n   PE constraints improve the TPR over PO-NOTEARS and recover more missing causal paths, but they can also increase the FDR. Nevertheless, **PE-NOTEARS consistently outperforms NOTEARS**, including the case of 200 nodes. Importantly, explicitly enforcing path existence is crucial in scenarios where **uncovering previously unknown causal mechanisms** is prioritized over simply ensuring correctness for all identified causal edges.\n5. You are correct. The reported runtimes for PO-NOTEARS and PE-NOTEARS-path reflect the two stages of PE-NOTEARS separately. We'll include the total PE-NOTEARS runtime in the revised manuscript. Iterations remain similar (~20–30) across NOTEARS, PO-NOTEARS, and PE-NOTEARS-path.\n   Additionally, we've reduced complexity to $O(d^3 \\log d)$, as addressed in point 3 for reviewer tD5o.\n## **Partial responses to Reviewer MDE7**\n## Methods\nWe assume you refer to Eq. (18) (path existence-based DCD) rather than Eq. (25) in step (2).\n1. The main contribution is identifying this order-violation issue and effectively utilizing partial orders to mitigate it, rather than proposing a novel partial order-based DCD algorithm itself.\n2. Proposition 7 states that arbitrary optima of NOTEARS correspond precisely to optima under certain total orderings, fundamentally differing from Proposition 3 by Ban et al. (which states convexity given a total ordering). This clarifies that total orderings fully characterize NOTEARS optima, highlighting that partial orders refine total orderings towards better solutions.\n### Experiments\n1. Score-and-search methods perform poorly on SEM-generated data due to scoring mismatch (e.g., BIC). Thus, we evaluate performance on real-world data (Sachs-500), reporting the F1 scores below under the same set of random paths.\n   | @Paths           | 0    | 25   | 50   | 75   |\n   | ---------------- | ---- | ---- | ---- | ---- |\n   | Li et al. (2018) | 0.33 | 0.43 | 0.41 | 0.48 |\n   | PENOTEARS        | 0.42 | 0.42 | 0.49 | 0.54 |\n2. The method in Wang et al. (2024) corresponds exactly to our intuitive path existence formulation without known path-lengths (See point 2, responses to reviewer mwJt). Hence, the ablation labeled *-intuitive* reflects their approach, which will be noted.\n## References\nWe will introduce the relevant work by Deng et al. (2024) in the paper.\n## Weaknesses\nWe will explicitly cite Proposition 6 as Proposition 2 from Ban et al. (2024). However, Eq. (16) is independent of Ban et al. (2024): it defines a threshold-based binary mask indicating absent paths, following standard practice in DCD (originally from NOTEARS' acyclicity loss forbidding self-loops, see Sec. 2.3). Although Ban et al. (2024) also use path absence, their intent (partial orders) differs from ours, where we introduce $b(W)$ specifically to address the unnecessary issue of in path-existence characterization.\n## Suggestions\n- We will add these citations in Sec. 3.1.\n- We apologize for the oversight regarding DAGMA codes and will correct it.\n- We will include a summary algorithm highlighting key contributions.", "claims_and_evidence": "All claims in the paper are well motivated and supported with theoretical analysis.", "methods_and_evaluation_criteria": "1. The proposed method appears well-motivated and reasonable for integrating ancestral constraints into differentiable structure learning.\n2. Would it be possible to compare with Wang et al.’s work?\n3. What are the additional computational overheads (e.g., running time, number of iteration to converge) compared to standard NOTEARS?\n4. Section 5.4: Why does adding more constraints sometimes lead to suboptimal performance? Some discussion on this trade-off would be helpful. For example, given a large dataset with over 200 nodes, would incorporating constraints overwhelm the optimization process and lead to a performance downgrade?\n5. D.1. Time Complexity: The comparison appears somewhat vague. Can I interpret the actual running time as **PO-NOTEARS + PE-NOTEARS-path**? If so, the comparison between PE-NOTEARS-path and NOTEARS seems unfair, as PE-NOTEARS-path benefits from a well-optimized initial guess.", "theoretical_claims": "I have not examined the proofs in detail.", "experimental_designs_or_analyses": "Please refer to my comments above.", "relation_to_broader_scientific_literature": "The work is important because it provides a solid foundation for differentiable causal structure learning by enabling the incorporation of constraints beyond simple edge presence or absence.", "essential_references_not_discussed": "I’d encourage the authors to discuss “Scalable Differentiable Causal Discovery in the Presence of Latent Confounders with Skeleton Posterior” in the related work, as it offers an alternative approach to incorporating edge constraints into the optimization process without directly setting W_ij=0.", "other_strengths_and_weaknesses": "Strengths\n- The paper is well organized and the presentation is very clear.\n- The method is clean and supported with theoretical analysis.\n\nWeaknesses\n- Some concerns in the evaluation. Please refer to my comments above.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please refer to my questions in \"Methods And Evaluation Criteria.\"", "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": "E47kogsuHo", "reviewer": "Reviewer_MDE7", "summary": "The paper proposes a method to integrate prior knowledge of presence/absence of certain edges or paths into differentiable structural learning frameworks. The paper presents theoretical analyses of several strategies, and the related issues, for handling such constraints in a continuous optimization regime. The authors then propose an alternative continuous characterization of the constraints along with an order-guided optimization strategy to mitigate the identified issues.\n\n### Update after rebuttal: \nI retain my view regarding the novelty of the practical algorithm of the method, which to me is a incremental, rather limited, extension of the existing frameworks (those mentioned in the discussions). I understand that the other reviewers may hold a different viewpoint regarding this. However, I highly value the theoretical analysis of the problem at hand and I think it can contribute to the understanding of optimization behavior induced by order constraints. \n\nAfter reading the authors' comment, I am slightly more positive about the work and decided to raise my score to 3, though honestly a score of 2.5 would better justify the update. This is also to encourage the authors to clarify the similarities/differences of the approach compared to existing methods, if the authors in fact leverage their results.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review. We first address your major concerns regarding novelty and technical differences. We abbreviate differentiable structure learning for causal discovery as DCD.\n\n# Novelty over Partial Orders (Ban et al. (2024))\nYou consider path existence as part of partial orders. In fact, path existence imposes a **stronger** constraint than partial ordering for DCD; it is partial ordering that forms a subset of path existence constraints. Consider this example:\n\nSuppose variables $A$ and $B$ are not reachable through any directed path in the true graph. Still, there exists a total ordering $\\pi$ satisfying the true topological order where $A \\prec B$. Here, the partial order constraint $A \\prec B$ is correct (not contradicting ground truth), yet the path $A\\leadsto B$ does not exist.\n\nSince the existence of path $A \\leadsto B$ implies $A \\prec B$, but not vice versa, path existence provides strictly stronger structural information. Additionally, optimizing DCD with path existence constraints introduces unique challenges (inequivalence and inherent gradient conflicts) absent in partial-order-based DCD.\n\nTherefore, DCD with ancestral (path existence) constraints represents a novel, significantly more challenging task than DCD with partial ordering.\n\n# Essential Technical Differences from Prior Work\n- Chen et al. (2016) consider discrete score-and-search methods, not encountering differentiability or the related issues described in Sec. 1.\n- Sun et al. (2023) focus exclusively on edge constraints.\n- Wang et al. (2024) assume the length of the path $(i,j)$ is known beforehand and formulate the loss as $\\text{ReLU}(\\epsilon - |W|^k_{i,j})$. Even ignoring this strong assumption, their formulation is theoretically incorrect and suffers from the same inequivalence issue as the naive loss $\\text{ReLU}(\\epsilon - \\sum_k |W|^k_{i,j})$ discussed in Sec. 3.1. Moreover, they do not address the critical order-violation issue.\n\nThus, it is rational to state that this work is the first to systematically (correctly) address DCD with ancestral constraints.\n# Evidence on Oder-Violation\nWe now provide explicit evidence of the order-violation issue. Specifically, we report:\n\n- **@OrderViolation**: Number of constraints specifying paths that violate the recovered ordering (i.e., reversed paths).\n- **@FailedPaths**: Number of unsatisfied constraints.\n- **Data loss**, F1 score and SHD.\n\nWe compare PE-NOTEARS-zero (zero initialization) with PE-NOTEARS (order-guided optimization) across varying path loss weights. Results (30 nodes, ER2 graph, linear SEM with Gaussian noise, 80% paths) are summarized below as **PE-NOTEARS / PE-NOTEARS-zero**.\n\n| PE loss weight  | 1           | 10          | 50          | 100          | 500          |\n| --------------- | ----------- | ----------- | ----------- | ------------ | ------------ |\n| F1              | 0.68 / 0.60 | 0.68 / 0.41 | 0.68 / 0.22 | 0.68 / 0.19  | 0.68 / 0.17  |\n| Data Loss       | 8.4 / 21.3  | 9.0 / 45.9  | 9.1 / 115.1 | 10.3 / 160.5 | 11.4 / 276.6 |\n| @OrderViolation | 0.0 / 0.1   | 0.0 / 0.8   | 0.0 / 3.7   | 0.0 / 6.7    | 0.0 / 19.0   |\n| @FailedPaths    | 0.3 / 9.3   | 0.2 / 10.7  | 0.5 / 27.2  | 1.2 / 22.2   | 0.7 / 24.2   |\n\nThe order-violation issue from Example 1 and Proposition 5 occurs when path loss significantly impacts optimization. To simulate this, we vary the path-loss weight from 1 to 500. As the path-loss weight increases, @OrderViolation (the count of order-violating paths) grows substantially, dominating @FailedPaths, aligning with our identified issue. In this case, reducing path-loss impact with zero initialization leads to improved optimization. In contrast, PE-NOTEARS with order guidance consistently achieves stable and strong performance even under significant path-loss weights, aligning well with stable prior-based structure learning.\n\nThese results clearly illustrate the order-violation issue arising from zero initialization and demonstrate the effectiveness of order guidance in resolving this issue.\n\n# Questions\n\nPropositions 4 and 5 also hold in the nonlinear setting:\n\n**Proposition 4:** Nonlinear models typically define edge weights $ W $ from parameters $ \\theta $ through non-negative transformations, e.g., $ W_{i,j} = \\sqrt{\\sum_{q=1}^m\\theta_{i,j,q}^2} $. In such cases, the absolute value of edge weights directly correlates with the magnitude of parameters. Since path existence constraints and acyclicity constraints push $ |W_{i,j}| $ in opposite directions, they consequently push parameters $ \\theta_{i,j,q} $ in opposing directions. Thus, the gradient conflict identified in Proposition 4 persists in nonlinear settings.\n\n**Proposition 5:** In nonlinear models, regularization ensures parameters $ \\theta $ remain bounded, implying edge weights $ W $ are also bounded. Thus, the argument presented for Proposition 5 directly applies.\n\n# Other Responses\nDue to the character limit, please see responses to Reviewer mwJt for this part.", "claims_and_evidence": "The paper provides solid theoretical results for most of the key claims and extensive empirical evidence overall to substantiate the effectiveness of the proposed method. However, the following points are problematic to me.  \n\n1. In Section 4.1, the authors point out an issue of violating paths when directly optimize Eq. (18) due to the sensitivity to different intializations for $W$. In the original implementation of NOTEARS or DAGMA, which the authors are also using, $W$ is often initialized at zeros and this has so far been shown to work sufficiently well in many settings. Furthermore, while the case in Proposition 5 may arise, a positive view from Proposition 5 is that if the current graph contains correct paths, the loss will help prevent edges that causes conflicting paths. To fully establish it as a motivation for the proposed method, the authors should provide some empirical results for the prevalence of such issue in practice, which is currently lacking in the manuscript. \n\n2. The claim this is the first work that addresses the integration of ancestral constraints into differentiable structure learning is rather misleading. At least based on the authors' discussions of related works in Appendix A, we have works with same problem setup like Wang et al. (2024), Sun et al. (2023), Ban et al. (2024) (where ancestral constraints are part of the partial order constraints).", "methods_and_evaluation_criteria": "My understanding from Section 4.2 is that the proposed method involves two steps: (1) solve for $W$ with path absence constraints by Eq (23), (2) use the resulting $W$ as initial points and solve for final graph by Eq (25) with path presence constraints. \n\nFrom Section 4.2, the task is reformulated into an structure learning objective with partial order constraints, which Ban et al. (2024) have already addressed, also stated so by the authors in lines 736 - 738. Furthermore, Eq. (25) corresponds to the optimization problem with total ordering constraint and it is the relaxation of such constrained optimization problem proposed in Eq. (7) of Ban et al. Therefore, Proposition 7 seems to me purely a re-statement of Proposition 3 of Ban et al. (2024). Furthermore, the insight from Proposition 7 is not new in that acyclicity constraint is no longer needed given the knowledge of total ordering, which has been actively exploited; some recent works include Deng et al., (2023), Shahverdikondori et al. (2024)\n\n*Deng, C., Bello, K., Aragam, B., & Ravikumar, P. K. (2023, July). Optimizing notears objectives via topological swaps. In International Conference on Machine Learning (pp. 7563-7595). PMLR.*\n\n*Shahverdikondori, M., Mokhtarian, E., and Kiyavash, N.QWO: Speeding up permutation-based causal discovery in liGAMs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024*", "theoretical_claims": "There is no issue with the correctness of the theoretical claims.", "experimental_designs_or_analyses": "The authors conduct experiments on well-established benchmarks and report the standard metrics for evaluation. \n\nMy main concern is in the lack of baseline comparison and that the paper only reports the performance of the proposed method. It is not surprising that incorporating additional order-based constraints yield performance improvement, which is expected. As mentioned above, there are other algorithms for integrating constraints, certainly with different specifications and not necessarily fully differentiable (e.g., O’Donnell et al., 2006, Chen et al., 2016).  Therefore, it is important to have an empirical assessment of these methods as baselines to understand how well the proposed method works. In particular, the authors should compare the method with Wang et al. (2024), Sun et al. (2023) to empirical verify the sub-optimality of the ReLU characterization.", "relation_to_broader_scientific_literature": "The paper introduces a method to incorporate general ancestral constraints into differentiable structure learning frameworks. There are previous works addressing ancestral constraints yet with some limitations, namely Wang et al., which assumes knowledge of path lengths or Chen et al., (2016) which do not consider differentiable frameworks.", "essential_references_not_discussed": "As for order-based constrained optimization, Deng et al. (2024) is a recent work that improves NOTEARS by leveraging prior knowledge of topological ordering. The authors can consider this method as an alternative for the currently proposed one in step 2. \n\n*Deng, C., Bello, K., Aragam, B., & Ravikumar, P. K. (2023, July). Optimizing notears objectives via topological swaps. In International Conference on Machine Learning (pp. 7563-7595). PMLR.*", "other_strengths_and_weaknesses": "**Strengths:**\n\nThe paper offers a systematic analysis of the challenges associated with incorporating ancestral constraints into differentiable causal discovery frameworks, both from a theoretical and empirical perspective. In my view, this is the key point of differentiation of this work compared to previous studies. While the concept of applying binary masking in causal discovery is not new, the in-depth theoretical analysis presented here is particularly interesting. Given the maturity of the gradient-based causal discovery literature, it is crucial to explore the optimization behavior and the role that different constraints play in the optimization process.\n\n**Weaknesses:**\n\nAs mentioned above, the proposed objective to me bears striking resemblances with the previous results, particularly Ban et al. (2024). Apart from those, the result in Eq (16) is also highly relevant. The proposed binary-masked characterization is a threshold-dependent relaxed equivalence of the characterization in Proposition 4 of Ban et al. which states that no directed path from $X_i$ to $X_j$ if and only $(\\sum_{k=1}^{d} (W \\circ W)_{i,j}=0$. Here $|W|$ and $W \\circ W$ are different ways to ensure positivity of the weighted adjacency matrix (Wei et al., 2020). \n\nIt is acceptable to build on or reuse existing results, but proper citations need including, especially when the authors have acknowledged these works in the paper.", "other_comments_or_suggestions": "I currently vote for a weak reject mainly due to the questionable novelty of the proposed theoretical results in relation to the existing works. However, I am willing to raise the score if the authors could provide explanations as well as additional empirical evidence to demonstrate the competitiveness or superiority of the proposed method. Some further comments are: \n\n1. In line 734, the ReLU constraints are discussed in works like Wang et al. (2024) and Sun et al. (2024), which also need to be explicitly cited in the Section 3.1 discussion. \n\n2. Furthermore, I do not find the implementation of DAGMA in the provided code. Despite the filename, the codes have NOTEARS implementation.\n\n3. The authors should summarize the final algorithm to highlight what the key contribution is.", "questions_for_authors": "The current theoretical analyses are conducted in the linear case. Could the authors further comment on the optimization behavior for the non-linear case, with respect to the results in Proposition 4 and 5?", "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 studies the problem of incorporating ancestral constraints into differentiable causal structure learning, focusing on NOTEARS-style algorithms. The authors identify two key issues with existing differentiable formulations: a non-equivalence issue in previous continuous relaxations of path-existence constraints, and an order-violation issue where constraints might fail during gradient-based optimization. The authors' contributions consist of (i) a principled framework for differentiable causal discovery with arbitrary ancestral constraints, (ii) a new equivalently valid path constraint formulation, and (iii) an order-guided optimization strategy to satisfy constraints and achieve higher accuracy. The reviewers appreciate the originality and theoretical rigor of the proposed masked path formulation, systematic empirical validation, robust experimental design, and clear presentation.
Decision: Accept (poster)