Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper addresses problems of probabilistic reasoning about uncertainty in causal diagrams. In particular, given a simple distribution over ADMGs, and a causal effect query, the authors consider 1) finding the most likely graph that is identifiable; and 2) finding the identifiability formula with the greatest probability of being valid. They show that 1) and a relaxation of 2) are equivalent to the edge-ID problem, which they show to be NP-hard (in particular, equivalent to the minimum-cost intervention problem). In view of this, they provide a number of heuristic algorithms to solve the edge-ID problem, demonstrating their efficacy on both simulated graphs and real-world datasets.
strengths_and_weaknesses: Overall, this is a technically strong and interesting paper which introduces a number of new ideas. The authors introduce the novel problem of evaluating (maximal) probabilities of identifiability under graph uncertainty, and provide both clear formal results on hardness as well as practical heuristic algorithms. 

Form a theoretical perspective, the reductions to and from MCIP (Thm 1 and Thm 2) are quite non-trivial and provide an interesting computational link between the problems of choosing minimal cost interventions and most likely edge-subgraphs for identifiability. The authors study the problem under the restrictive assumption of independent edges, but also introduce a clever extension to distributions with perfect negative correlations. Algorithmically, the backtracking exact algorithm is simple but sensible, while the heuristic algorithms make clever use of the properties of hedge structures.

The presentation of the paper has clearly been thought out carefully; in particular, the technical clarity of the main paper and appendix proofs is excellent. However, in terms of telling the story, the paper as written seems to rely on a lot of implicit context to be fully understood, which could perhaps be spelled out more explicitly. To give a few examples, with the aim of providing constructive suggestions for improving readability:
- Definition 4 of a hedge appears to be non-standard, as a specific case of the full definition where G[Y] forms a c-component and the intervention is on all other nodes V\Y; while I understand the authors’ desire to set up the intuition, it would be helpful to explicitly state this.
- Theorem 1 appears before the MCIP problem is defined or even mentioned; in my opinion, given that the relationship between these two problems is so close as shown in the proofs of Thm 1 and 2, it would be useful to explicitly mention this and give some intuition in the main paper.
- The MCIP problem formulation is not intuitive (“minimum cost set of interventions”) without the context in [1] about why the stated formulation is consistent; this could be stated explicitly.

My main criticism of the paper is with regards to the motivation of the edge-ID problem, and as a result the degree to which the paper breaks new ground beyond [1]. In particular, it is not clear why one would want to find the most likely identifiable graph. Unless this probability is very high, it would be unreasonable to rely on identification formulae based on that graph. Finding the identification formula that is most likely to be valid is more compelling, but unfortunately (and understandably from a computational perspective) a rather crude relaxation is used, which could have very different solutions. 

In this sense, I would have liked to have seen some experiments demonstrating the utility of the edge-ID problem, by putting it in the context of the original problems. In particular, it might be useful to see the raw probabilities associated with the most likely graph/most likely aggregate graphs; or perhaps, in cases where exact computation is feasible, the gap between the probability of the most likely identification formula and the solution to Problem 2. 

Nonetheless, this is an extremely solid work overall that provides new understanding of the computational issues regarding probabilistic reasoning about identifiability.

[1] S. Akbari, J. Etesami, and N. Kiyavash. Minimum cost intervention design for causal effect identification.  	 	 		
		
questions: 1) What practical applications can the authors envisage for their methods?
2) In all experiments, the probability of an edge is restricted to lie in [0.51, 1]. Is this because an edge with probability <0.5 would always be removed? If so, do the authors consider this a limitation of their formulation of the problem (in that positive correlations between edges are not possible)?
limitations: The authors appropriately acknowledge the limitations of their method (independent edges, approximation made by Problem 2).
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper addresses the problem of causal identification under structural uncertainty. In particular the authors assume that the probability of edge existence is given and provide an algorithm to find the most probable configuration for a given causal query of interest. Empirical results show promise. 
strengths_and_weaknesses: Strengths:

* Novel and interesting task. Structural uncertainty and misspecification is commonplace, and addressing this for identification is a very important problem area. 
* Well described problem setup and the authors provide both exact and heuristic solutions. 

Weaknesses:

* Approach seems fraught in dense graphs. 
* Experimental evidence could be more compelling, would especially like to see a comparison with more naive approaches. 
questions: In many practical settings I would imagine that there are a large number of dense graphs that appears (i.e., many non-zero probabilities) do the authors have ideas or guidance on how to reduce the size of the search space?
limitations: The authors address limitations of the proposed approach well.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper considers a setting where one does not have access to a fully specified causal ADMG but a probabilistic causal graph in which the directed/bidirected edges are assigned probabilities. It studies two questions under this setting:  Given a probabilistic graph and a specific causal effect of interest, (1)  which subgraph has the highest plausibility and (2) which subgraph has the highest aggregate probability over its edge-induced subgraphs for which the causal effect is identifiable? The paper shows that both problems reduce to an NP-hard combinatorial optimization problem, provides several exact and heuristic algorithms, and empirically evaluates the proposed algorithms.

strengths_and_weaknesses: Originality

The paper introduces a new causal inference setting represented by probabilistic causal graphs that capture uncertainties in the existence of edges. The setting relaxes the restrictive requirement that one must have access to a fully specified causal graph in the majority of works on causal effect identification. To the best of my knowledge, this problem setting is novel.

Quality of work

The technical results look sound. The proposed algorithms look reasonable. The empirical evaluation is largely adequate.

Clarity

The paper is clearly written. The presentation is excellent.

Significance

The main weakness of the paper is in its significance. Although the results are of some interest, it looks to me the paper does not really solve the problem it claims to be solving. 

-It looks to me that the results are limited to causal queries of the form Q[Y] instead of arbitrary causal effects $P_X(Y)$. Remark 1 appears to address this issue and claims ``They can be applied to general causal queries of the form $P_X(Y )$ if the directed edges of G and therefore the set $Anc_{G\setminus X}(Y)$ are known.'' It’s not clear what this claim means. Are the results of the paper applicable to general $P_X(Y )$ only if all the directed edges are fixed with probability 1?

-Problem 2 does not solve the problem of deriving an identification formula for a given causal query that holds with the highest probability. Solving Problem 2 finds a lower bound on the plausibility of an identification formula since there may exist other types of graphs with the same identification formula.
questions: Are the results limited to causal queries of the form Q[Y] or applicable to arbitrary causal effects $P_X(Y)$? Please clarify Remark 1.

In the experiments, the edge probabilities $p_e$ are sampled uniformly between 0.51 and 1.0. Why making $p_e > 0.5$? I believe this makes the graph samples biased. In fact, I suspect making all edge probabilities larger than 0.5 might make certain optimization problems easy to solve (just a guess), but any reason keeping $p_e > 0.5$?

Line 111, {z, t} should be {z, x}?

limitations: If the results are indeed limited to causal queries of the form Q[Y] instead of arbitrary causal effects $P_X(Y)$, then this limitation should be made clear in the abstract/introduction, etc.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: 1. Given uncertainties about the existence of edges in a causal diagram, this paper consider two problems:

* finding the most probable graph that renders a desired causal query identifiable.

* finding the graph with the highest aggregate probability over its edge-induced subgraphs that renders a desired causal query identifiable.

2. Then, the authors introduce a combinatorial optimization problem which they call the edge ID problem and show that it is NP-hard. Further, they show that the two problems mentioned above are also NP-hard by reducing them to the edge ID problem. 

3. Finally, the authors propose several exact and heuristic algorithms for the aforementioned problems.
strengths_and_weaknesses: Strengths: 
1. This paper introduces three new problems and prove that they are NP-hard:
* finding the most probable graph that renders a desired causal query identifiable.
* finding the graph with the highest aggregate probability over its edge-induced subgraphs that renders a desired causal query identifiable.
* finding the set of edges $E$ with minimum aggregated weight that renders a desired causal query identifiable in the graph resulting from removing $E$ (i.e., the edge ID problem).
2. As a consequence of their work, the authors also show that if an identification formula is valid w.r.t a causal graph, it is also valid w.r.t all its edge-induced subgraphs. 
3. Further, they also establish a bi-directional link between the edge ID problem and the minimum-cost intervention problem. Therefore, the algorithms proposed here could be useful to solve the minimum-cost intervention problem as well.

Originality:

The paper is technically solid and brings a significant originality of ideas. However, I am a little concerned about the importance of the questions considered. See the limitation section below.

Clarity:

The paper is mostly well-written. There are certain places where the writing could be improved/made clear. Please see 'Suggestions / typos' below.

Weakness:
1. **Relevance of the problem setup:** As mentioned in the paper, most algorithms proposed to identify causal effect assume access to a correctly specified causal diagram. This assumption includes knowing the presence of every edge in a causal diagram with probability 0 or with probability 1 i.e., $p_e = 0$ or $p_e = 1$. While this paper does not need to know a binary $p_e$, it still needs to know a continuous valued $p_e$ i.e., $p_e \in [0,1]$ for every edge in a causal diagram. In my opinion, such information is difficult to obtain in most real-world applications. The authors sample $p_e$ uniformly between 0.51 and 1.0 in all of their experiments and mention that these uncertainties may reflect the confidence of a particular statistical test. However, how would one obtain such information for bi-directed edges even from statistical tests? I would encourage the authors to think more carefully about this requirement and include real-world scenarios where this requirement would be satisfied. 

2. **Type of causal queries studied:**  In Remark 1, the authors mention that their results are not limited to causal queries of the form $Q[Y]$. They can be applied to general queries of the form $P_X(Y)$ when the directed edges of the causal diagram are known. However, in this case, the authors are inherently eliminating any uncertainties associated with the directed edges of the causal diagram which seems against the spirit of the paper.

questions: Questions:
1. In line 52, the authors say 'selecting the most plausible subgraph in which the assumption holds true'. Could they justify or elaborate on why this is the case? In other words, I fail to see the point being made here.

2. What happens when the uncertainties associated with the edges are such that $p_e = 0$ or $p_e = 1$ instead of $p_e \in [0,1]$? It is clear that the weights in Lemma 1 are either 0 or $\infty$. Would the recursive algorithm or the heuristic algorithms simplify? Would the solutions of three problems considered in this work simplify? Would the solutions/algorithms map to some existing work?

3. Could the authors provide more insight regarding Lemma 1? More specifically, is there any intuition behind the weights of the edge ID problem that Problems 1 and 2 map to?

4. Depending on the number of vertices and edges in the underlying causal diagram, the probability in (1) for any subgraph might be very small. For example, the values for Problem 1 for $G_1$ and $G_2$ are 0.049 and 0.081 respectively. Further, it is also likely that the aggregate probabilities in Problem 2 for two graphs are not very different. In that case, instead of a single identification formula, it might be useful to find a bunch of such formulae. In other words, it might be useful to derive interval bounds for the causal effect than a point estimate. Could the uncertainties about the existence of the edges and/or the problems analyzed in this work be useful towards this?

5. As mentioned in lines 148-149, Problem 2 is a surrogate to recovering the identification formula with the highest plausibility. Do the authors have a sense of how far away is this lower bound from the true value?

6. I understand that the Assumption 1 could be expanded to allow edges with perfect negative or positive correlation as mentioned in lines 158-159. But a perfect correlation between two edges basically makes the probability of one of the two edges irrelevant/useless. I don't have any major concern with Assumption 1 but it may be useful to comment on how relevant this assumption is in practice. 

Suggestions / typos:
1. The authors might want to introduce certain notation before using them e.g., $P_X(Y)$ in line 47, $P_X^M(Y)$ in line 97, ...  
2. The authors introduce the notation $[G]_{Id(P_X(Y))}$ in line 102 as the set of ADMGs in which $P_X(Y)$ is identifiable. Is each element of this set an edge-induced subgraph of $G$? The authors might want to clarify this. 
3. In line 111, the authors mention that the set including $z$ and $t$ forms a hedge for $Q[x]$. Is this correct? Should $x$ not be a part of the hedge for $Q[x]$? 
4. The authors might want to clarify 'the ID algorithm' mentioned on line 192.
5. Based on lines 268-276, it seems that there exists a hedge for $Q[Y^{mcip}]$ in ADMG $H$ in Figure 2b. Is this true? Does $Y^{mcip}$ form a district in $H[Y^{mcip}]$?
6. What is $n$ on lines 289 and 320?
7. It might be useful to provide more details about the real-world datasets used in this work. Why are the outcome variables in these datasets not fixed? Is there a particular reason why these specific datasets were used?
limitations: In its current form, this work has some limitations which are not addressed. For example, see the two points made in the weaknesses above. 

Further, I am also concerned about the relevance of the Problems studied here. In Problem 1, the authors are interested in finding the most probable causal diagram in which the causal effect is identifiable. In Problem 2, the authors are interested in finding (a lower bond on) the most probable causal effect. These problems makes sense when there exists no way to find the causal effect (under the assumption that only the uncertainties associated with the edges are known).

While most algorithms proposed to identify causal effect assume access to a correctly specified causal diagram, there has been a line of work for identifying causal effect using only an anchor variable when the underlying causal diagram is not known. For example: (1) Entner et al 2013 -- Data-driven covariate selection for nonparametric estimation of causal effects [https://proceedings.mlr.press/v31/entner13a.html], (2) Cheng et al 2020 -- Towards unique and unbiased causal effect estimation from data with hidden variable [https://arxiv.org/pdf/2002.10091.pdf], (3) Shah et al 2021 -- Finding Valid Adjustments under Non-ignorability with Minimal DAG Knowledge [https://arxiv.org/pdf/2106.11560.pdf].

In light of these works, I am concerned about the relevance of the two problems studied in this work. First, by requiring uncertainty for *every* edge in a causal diagram, this paper require global knowledge of the underlying causal diagram which may be too much to ask for as described in first weakness above. In contrast, the aforementioned works require only local knowledge of the underlying causal diagram concerning the anchor variable. Second, and more importantly, consider a scenario where the aforementioned works are able to find a valid identification formula for a causal effect of interest. In that case, no matter what the rest of the causal diagram looks like, the identification formula remains valid. On the other hand, this may not be true for the two problems studied in this work. Consider the example 1 on page 4. If one were to solve Problem 1, they may choose $F_2$ over $F_1$ and if one were to solve Problem 2, they may choose $F_1$ over $F_2$. However, it is certainly possible that the true underlying causal diagram is $G$ in Figure 1a and neither $F_1$ nor $F_2$ are valid identification formulae. To conclude, what is the validity of the causal effect / identification formula returned by the two problems considered in this work? I understand that this may not be apples to apples comparison with the three works mentioned above, my question in the previous sentence stands. How would the outputs of the Problems considered here be used in a real-world application?
review_title: null

Meta-review: metareview: This paper studies the problem of causal identifiability in probabilistic causal models, where each edge is associated with a probability value that indicate the uncertainty about the existence of edge and whether a given causal effect is identifiable. Two technical problems are considered: 1) finding the most probable graph that renders a desired causal query identifiable, and 2) finding the graph with the highest aggregate probability over its edge-induced subgraphs that renders a desired causal query identifiable.

A reasonable amount of discussions took place between the authors and the reviewers, and among the reviewers themselves. At the end, we get four confident (4) reviews with ratings 5, 6, 6, and 7: 
The reviewers appreciate the novel problem setting, interesting complexity results, reasonable algorithms and clear presentation.

However, there is also concern that since the paper solves a surrogate problem than the one it sets out to solve, there needs to be more acknowledgement and up front discussion about this gap in the paper, and discussion on potential ways to bridge this gap. In general, a broader discussion on the practical utility of the work developed here, rather than just the ideal question is expected in the final revision, along with other reviewer feedback.

confidence: Less certain
Decision: Reject