- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper considers the problem of identifying interventional distributions in graphical models when the underlying DAG is not fully known. One such setting is when the DAG is known only up to its Markov Equivalence Class (MEC), which is a natural setting since using purely observational data, a graphical model can only be distinguished up to its MEC. It is well known that such an MEC can be described in terms of a partially directed mixed graph (sometimes called CPDAG) in which the directed edges are those for which every DAG in the MEC has the same direction.
The paper considers the more interesting setting where in addition to the Markov Equivalence Class, background knowledge of the the directions of some of the edges left undirected in the description of the MEC is available. Such extra information can, for example, from domain knowledge.
The paper builds upon earlier work of Perkovic and Guo and Perkovic who consider the problem of which interventions remain identifiable, in the MEC and MEC with background knowledge settings respectively. Here, identifiability means that the intervention distribution has the same value in all the DAGs in the MEC (or the MEC restricted by the available background knowledge). This paper asks a more fine-grained question: when does the number of possibles values of the intervention distribution decrease when background knowledge is added.
The results involve use of combinatorial properties of Markov equivalence (in the form of the classical Meek's rules), to reduce the problem (at least in part) to the work of Guo of Perkovic (e.g. in the proof of one of the main theorems, Theorem 4.3, in the appendix). Towards this, the paper also isolates some important combinatorial properties of MPDAGs (the version of CPDAGs with background knowledge) in Section 3.
Critical strengths
-
The problem studied is quite natural, and the paper gives a satisfying answer.
-
The paper also gives some numerical examples of how the reduction in the number of possible interventional distributions turns out in practice in some standard benchmark models.
Critical weaknesses
-
The main results (Algorithm 1, Theorems 4.3/4.4) only consider a very special class of background knowledge: we are trying to identity the effect of node X on Y, and the background knowledge edges are all incident on X. What happens if background knowledge edges elsewhere in the graph are revealed?
-
some parts of the paper may benefit from adding further discussion of related work/notions. These are described in the Questions section.
Questions for authors
-
Section 3. The results in this section are reminiscent of similar ideas used in various previous works on the combinatorial properties of CPDAGs; in particular results such as Wienöbst, M., Bannach, M., & Liskiewicz, M., "Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs." AAAI 2021. https://doi.org/10.1609/aaai.v35i13.17448, and follow up works extending it to the setting of background knowledge.
One reason to believe why such a connection may exist is that there is a short proof of Corollary 3.3 of the paper under review that follows easily from the above previous results, bypassing all the machinery in paper under review. To see this, we start with a characterization of Andersson et al. (1997) which says that a CPDAG is a mixed graph in which, in particular, the undirected components are chordal. It also follows from their characterization that (see, e.g., the Wienöbst et al. paper cited above) the DAGs in the MEC represented by the CPDAG are all obtained by directing each chordal component independently according to a perfect elimination ordering of the component. In the setting of Corollary 3.3, is a clique in a chordal component containing and , and hence standard algorithms for constructing perfect elimination orderings of chordal graphs (such as maximum cardinality search or lexicographic breadth first search) imply that there is a perfect elimination ordering of the component containing that starts with , followed by . In the DAG corresponding to this ordering, we thus have , and hence the corollary follows.
I could not immediately find a similar simple proof of Theorem 3.2 of the paper. However, I think it would further strengthen the paper to include a discussion of these connections.
-
Comparison to Perkovic 2020. l.304. The identifiability criterion of Perkovic (2020) does not seem to be a direct corollary of Theorem 4.3 as stated here since in Theorem 4.3, X and Y are singleton sets while the criterion in Perkovic (2020) is stated for the more general case where X and Y can be sets of nodes (I believe this is Theorem 3.6 in Perkovic (2020)). See also the first comment in the "Weaknesses" section.
-
Complexity of the algorithm. In the final discussion section, the paper highlights how the combinatorial results yield finally a polynomial time algorithm. But if only a polynomial time algorithm is needed, wouldn't just completing what the paper calls the "Meek cascade" by brute force (known to be in polynomial time) and then applying the criterion of Theorems 4.3/4.4 (existence of "possible mediator", a notion also present in the cited works of Perkovic and Guo and Perkovic) also work in polynomial time, without any of the combinatorial optimizations coming from the results in Section 3? (Of course, these results are also important for the proof of Theorem 4.3.)
Minor typos etc.
- l. 234. The notion of a "semi-directed" cycle has been used undefined.
- l. 310. "consistent to" -> "consistent with"
- l. 789. "an DAG" -> "a DAG"
- l. 798-805. "contradicts with" -> "contradicts"
- l. 807. "only orient" -> "only orients"
- l. 817-818: "connection" -> "concatenation"
- Proof of Lemma A.5, l. 993. In cases 2, 3 and 4, shouldn't one only explicitly exclude the case that one of the directed edges in the "triggering" configuration was already directed in ? The proof I think is correct: this cannot be true for both the directed edges, and picking either works. But the wording of the proof seems to ignore this possibility.
3 comments
Thanks for the response. I maintain my original positive rating for the paper.
Thank you very much for your positive feedback and support!
Thank you very much for your positive feedback and support! We sincerely appreciate your constructive suggestions, which have greatly helped us improve the paper.
Reply to Reviewer fyi8
We sincerely thank the reviewer for the careful reading, the positive assessment, and the insightful and constructive comments. We address each point as follows.
W1: background knowledge revealed elsewhere in the graph.
This is a good question. Background knowledge outside the B-component [4] of X cannot affect the locality of X: [1, Theorem 10] shows that the local structure around X is unchanged, so our criterion is unaffected. For knowledge inside the B-component of X, one can run Meek's rules within that component to derive the knowledge incident on X and then apply Algorithm 1; since the B-component of X is typically small, this remains efficient.
Our focus on knowledge incident on X follows the local identification literature: the parent set of X is a standard choice of back-door set, and IDA and its variants identify the possible causal effects by enumerating the parent sets of X arising in the DAGs of the MEC. Knowledge incident on X is precisely what changes those parent sets directly.
Q1: relation to Wienöbst et al. (2021).
We thank the reviewer for this observation, which is correct for Corollary 3.3: [2] gives a much shorter argument than the one in the paper, and we have added this argument, with the citation, immediately before Corollary 3.3.
It seems difficult to extend to Theorem 3.2. In a CPDAG no directed edge joins two siblings of X, so the second condition of Theorem 3.2 cannot fail and a perfect elimination ordering of the undirected component settles validity. In an MPDAG that condition is exactly what rules out a directed cycle through X. Indeed, this is one of the largest differences between MPDAGs and CPDAGs.
Q2: comparison with Perkovic (2020).
We agree and thank the reviewer for the correction. The criterion of [3] is stated for node sets X,Y, whereas Theorem 4.3 handles only singletons. We have removed the claim that [3] is a special case of ours; the set-valued case is left for future work.
Q3: is the Section 3 machinery necessary for a polynomial-time algorithm?
We agree that the alternative route you describe is polynomial. The submitted version answered this question with practical differences only: deciding by local orientations at X requires fewer applications of Meek's rules, and the procedure never materialises the “Meek cascade”. The revised version replaces that answer with a stronger one.
Theory. We added Theorem 4.10, which shows that PM(X,Y,G∗)=PM(X,Y,G′) if and only if PM(X,Y,G∗)∩⋃i=15Si=∅. The sets S1,…,S5 of Section 3 are therefore not merely an implementation device: they are exactly the local quantities that determine whether the PM set changes, whereas two global closures tell us only that it changed, not why.
Algorithm. Algorithm 1 was rewritten corresponding to this theorem. Whether PM changes is now decided by performing a single set intersection after the initial PM is found. As a result, Algorithm 3 is no longer needed.
Experiments. The empirical evaluation was re-run on this rewritten algorithm, so every reported number corresponds to the procedure described in the revised paper.
A detailed complexity comparison with MIDA is given in Appendix C.4.
Minor typos. We thank the reviewer for these corrections. All of them have been corrected in the revised version.
On Lemma A.5 (cases 2–4): we agree with the reviewer's reading of the proof, and we thank the reviewer for pointing out the gap in the wording. The proof should explicitly exclude the case where one of the two directed edges in the triggering configuration was already directed in G∗ — the two cannot both have been present, and either may be chosen. We have added this exclusion to the wording; the argument itself is unchanged.
We hope that our clarifications have adequately addressed your concerns, and would greatly appreciate it if you would consider revisiting your initial rating.
References
[1] Zheng, Q., Liu, Y., & He, Y. (2026). Local Causal Discovery With Background Knowledge. IEEE Transactions on Pattern Analysis and Machine Intelligence, 48(7), 7969–7980.
[2] Wienöbst, M., Bannach, M., & Liskiewicz, M. (2021). Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13).
[3] Perkovic, E. (2020). Identifying causal effects in maximally oriented partially directed acyclic graphs. In Conference on Uncertainty in Artificial Intelligence (UAI), pp. 530–539.
[4] Fang, Z., Zhao, R., Liu, Y., & He, Y. (2025). On the Representation of Pairwise Causal Background Knowledge and Its Applications in Causal Inference. Journal of Machine Learning Research, 26(229), 1–73.