- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies the causal edge orientation problem based on a Markov equivalent class. In particular, the paper defines the breakdown radius concept that measures the distance between a base MPDAG and the closest MPDAG that triggers a change of the causal effect estimation, aiming to measure a causal model’s resistance to problematic orientation knowledge. The work shows an algorithm that exactly computes the breakdown radius, the correlation between the breakdown radius and adjustment set validity, and the relationship between breakdown radius and causal effect estimation bias, by theory and experiments.
Critical strengths
- The work is well motivated. It aims to propose a metric for causal discovery such that the metric measures the constructed causal model’s robustness against problematic orientation knowledge. This direction is potentially important for LLM-assisted causal discovery methods.
- The research framework is relatively complete, covering metric computing, validity, and impact on causal effect estimation.
Critical weaknesses
- One of my main concerns is the high computational complexity of the breakdown radius. A shortcoming of the paper is the absence of the complexity analysis. However, I would expect significant hardness for computing the metric. This also limits its implementation.
- The breakdown radius mainly considers the so defined closure orientation. It measures the error tolerance of a proposed causal model to possible problematic orientations, in terms of a target causal effect estimation task. However, it does not specify the accuracy of the proposed causal model. In other words, the paper assumes that the Markov equivalent class is correct, however, this is a strong assumption. Under this assumption, the metric neglects the bias caused by the recovery of the CPDAG.
- The contribution is mild. Although the paper establishes nontrivial theoretical analysis for the exact computation of the breakdown radius, the framework of graph-space distances for assessing adjustment robustness has already been explored in existing work. The theoretical novelty therefore mainly lies in specialising this framework to expert/LLM knowledge oriented causal graphs.
- The experimental results are not fully convincing. For instance, (1) a large part of the graphs are small networks, limiting the scope of the investigation. (2) The breakdown radius should be sensitive to the selection of the treatment/outcome pair, however, the pair selection process is not clear in the experiments on published networks.
Questions for authors
See the weakness part.
4 comments
Comment 2 of 2.
W3. Novelty against existing graph-space distances
The framework of graph-space distances is due to Taeb et al. (2026), and Section 2 credits it as our closest predecessor. The results of the paper do not follow from that framework; they hold because of the structure of the space we apply it to.
A graded space. The general MPDAG poset of Taeb et al. is not graded. The poset of knowledge states over a fixed CPDAG is, which gives the distance in closed form (Corollary 1).
Search by retraction only. The nearest failure is always reached by withdrawing orientations from the analyst's state (Theorem 1). This is what makes exact computation possible without enumerating the space.
What the radius means. All valid adjustment sets share one radius (Proposition C.7.1), and the radius is the distance to the nearest state that is not amenable. It is therefore a property of the query and the knowledge, not of the chosen set.
A certificate for the analyst. The output is not only a distance: it names the orientations whose retraction breaks , and within the radius the committed set carries no identification bias under a linear-Gaussian model (Theorem 2). Empirically, the radius ranks survival inside a fixed knowledge state, where counts of orientations, SHD and claim accuracy are constant (Table 1).
W4(1). Mostly small networks
The size of the graph does not limit the method, and the revision adds two checks at scale. On generated graphs of up to 400 nodes, the hybrid answers almost every query in under one second (Appendix D.2). On the five largest published networks (link and four munin variants, 724 to 1,041 nodes), the radius is computed exactly on every query that admits a certificate, the slowest in 55 s (Appendix I). The survival ranking of Table 1 stays on the 24 networks where survival was scored. The synthetic graphs are small by design: they are generated to spread instances across radius levels, and their radii reach the depths where the solver is needed.
W4(2). Selection of treatment–outcome pairs on the published networks
We agree that the rule was not stated; it is now in Appendix I.
The rule. A pair enters Table 1 when:
- lies in or next to an undirected component of the CPDAG;
- descends from in the true graph;
- the empty set is not a valid adjustment set;
- withdrawing one true orientation from complete knowledge invalidates the optimal set.
These conditions keep the queries where background knowledge matters for the adjustment. The rule is applied to every ordered pair on networks of at most 56 nodes and to a fixed seeded sample on larger ones. No step looks at a radius.
A check without the true graph. Because this rule reads the true graph, we repeated the ranking on the 528 released queries, which are chosen from the CPDAG alone. There the radius ranks survival within knowledge states at (Section 6.3, Appendix I). The ranking therefore also holds on queries selected without the true graph.
I appreciate the authors’ answers. Most of my concerns and questions have been addressed. I am happy to raise my score to 3.
A follow-up question for the authors is: Could the authors clarify whether Appendix H.4 counts disagreements only within the true ancestral subgraph or across a full DAG completion of the learned CPDAG? If the count is local, I do not see how the guarantee follows from Remark 8(i), since matching the true orientations near the query may force additional changes elsewhere.
Thank you for your careful assessment and for raising your score. Your review improved the paper on several points, and your follow-up question helps us state Appendix H.4 more precisely.
The count is global, over a full DAG completion of the learned CPDAG. For each committed set we build one DAG in four steps:
- Impose the true orientations on .
- Close under Meek’s rules.
- Add the analyst’s closure orientations that still close.
- Complete to a DAG.
We then count over the whole graph. Any change elsewhere that is forced by matching the truth near the query is part of . If it contradicts one of the analyst’s closure orientations, it is counted. Using one completion rather than the best one can only make the condition harder to meet.
Why the guarantee follows.
- If (or ), then is valid in , by Corollary 1(c) (or 1(b)).
- The localisation is only in the comparison between and . Every edge of is an edge of with the same orientation. Deleting from every edge outside keeps valid, by the edge-deletion argument of Remark 8(i) applied to the full DAG .
- What remains is plus isolated vertices. is ancestral in and contains every causal path from to , every forbidden node in , and every path that could be open given . So validity of in is decided on , and is valid in .
Empirically, the guarantee held in all 46,838 cases. In the camera-ready version we will define the count and give this argument explicitly in Appendix H.4, and we will reword “as Remark 8(i) implies” accordingly.
Thank you again for the rigorous discussion and for the time invested across the window.
Comment 1 of 2.
We thank the reviewer for the thorough review. We are glad that the reviewer finds the framework complete, and we share the view that a robustness measure for orientation knowledge matters for LLM-assisted causal discovery, where such knowledge is cheap to obtain and hard to check. The concerns raised led to an addition in the revision: a complexity analysis, and the pair selection rule. We answer each point below.
W1 Complexity analysis
We agree that the analysis was missing. It is now in a new Appendix C.8, with a pointer from Section 5.
What we prove. For one treatment and one outcome, the setting of the paper, the radius is computable in polynomial time. The validity of Z depends on the parents of the treatment only, and the nearest failure is always one change of the treatment’s parent set away from the analyst’s state (Proposition C.5; argument in Appendix C.9, complete proofs in Appendix J). On all 679,047 instances whose treatment component has at most six vertices, this returns the same radius as the search over every parent set.
What the experiments ran. Algorithm 1, which is also exact, so every reported radius is unchanged. Its explicit search costs ∣KG0∣O(rval)⋅poly(∣V∣), where KG0 is the set of closure orientations of the analyst's state (Proposition C.3). This exponent bounds the algorithm, not the problem (Remark C.2), and in practice it is rarely reached (timings of Appendix D.2):
link, 724 nodes*Projected from the number of DAGs tested per second when listing does not finish within its limit; on 30 classes run for 1,800 s the projection was within a factor of 2 of the measured rate. The ratio is the ratio of the two medians. On the five published networks of 724 to 1,041 nodes, Algorithm 1 is exact on all 388 query–state units that admit a certificate, the slowest in 55 s.
Proposition C.5 is an analysis of the problem, and we kept Algorithm 1 for two reasons. First, its search uses a single property of failure, that it is upward-closed (Theorem 1), so the same search also computes the bias-tolerance radius of Section 7, whereas the argument of Proposition C.5 relies on the form of the adjustment criterion and is specific to validity. Second, the exponent is paid only by deep radii, and there the solver stage takes over; our answer to Reviewer qQYf (W1) discuss when the solver is preferable to the search and how it compares with other exact solvers.
What remains open. With several treatments or outcomes the argument no longer applies; we leave that case, including an analysis of NP-hardness, to future work (Remark C.2).
W2. The correct equivalence class is a strong assumption
We agree that it is an assumption, and the paper states it as a limitation (Section 8). Two remarks on its role.
It is the assumption of the estimate itself. An adjustment set read off an MPDAG is valid only if the class is correct, with or without a radius. The radius adds no assumption to those of the estimate it accompanies. It addresses the second source of error, the background knowledge, which the data cannot check. It measures robustness to that knowledge, not the accuracy of the graph (Section 1).
How much of the class it needs. A new Appendix H.4 examines this, learning the class with ten CPDAG learners on four Gaussian networks (n = 100 to 100,000). An extra adjacency cannot break Z within the certified budget, while a missing adjacency or a wrong v-structure can (Remark 8). When the learned class has no missing or reversed edge among the ancestors of X, Y and Z, the certificate held in all 46,838 such cases, so it rests on the class being correct around the query, not everywhere. This also improves with data: under GRaSP the share of invalid committed sets falls from 0.63 at n = 100 to 0.06 at n = 100,000, and the radius on the learned class equals the true-class radius on 91% of queries. We recommend reporting the radius with the discovery method and sample size.