Causal Effect Identification in Uncertain Causal Networks

Summary

This paper considers two problems: 1. Finding the most probable graph that makes a desired causal query identifiable. 2. Finding the graph with the highest aggregate probability over its edge-induced subgraphs makes a desired causal query identifiable. This paper shows that both problems reduce to a special combinatorial optimization problem called the edge ID problem. They prove that the edge ID problem is NP-hard, implying that both of the problems are also NP-hard. The paper presents several exact and heuristic algorithms for these problems and evaluates their performances through different experiments. The experiments note that the heuristic algorithms performed remarkably well across all metrics. The paper also discusses the application of these algorithms to four real-world datasets.

Strengths

- The paper addresses a complex causal inference problem, specifically identifying the most probable graph that makes a desired causal query identifiable. This is a significant contribution to the field. - The authors provide a detailed analysis of the problem's complexity, demonstrating that it reduces to a special combinatorial optimization problem, the edge ID problem, which they prove to be NP-hard. This rigorous theoretical analysis is a strength of the paper. - The authors propose several exact and heuristic algorithms to solve the problem and evaluate their performance through different experiments. The heuristic algorithms, in particular, performed remarkably well across all metrics, demonstrating the practical applicability of the proposed methods. - The paper also applies the proposed algorithms to real-world datasets, further demonstrating their practical utility. The authors provide a detailed comparison of runtimes, solution costs, and failure rates, offering valuable insights into the performance of the algorithms in real-world scenarios.

Weaknesses

- The authors made the assumption that the edges in the graph are mutually independent. This assumption may not be held in all cases. - The external validity of the derived subgraph is not guaranteed. This means that the subgraph may not be correctly specified with respect to the corresponding real-world process. This could limit the applicability of the results in practical scenarios. - The EDGEID algorithm, one of the exact algorithms proposed in the paper, had large runtime variance, which depended heavily on the specifics of the graph under evaluation, particularly for graphs with fewer vertices. This could limit its utility in certain scenarios. - The EDGEID algorithm also timed out on all but one of the real-world structures tested, indicating that it may not be as consistent as other algorithms in terms of runtime. - The runtimes for the MCIP variants exceeded the HEID variants due to the required transformation. This could be a potential drawback in scenarios where computational efficiency is a priority.

Questions

Could you elaborate on the assumption of mutual independence of edges in the graph? How might the results change if this assumption does not hold? The external validity of the derived subgraph is not guaranteed. Could you discuss potential strategies for validating these subgraphs in real-world scenarios? - The EDGEID algorithm showed large runtime variance and often timed out on real-world structures. Are there any plans to improve the performance of this algorithm in future work? - The paper mentions that the heuristic algorithms performed remarkably well across all metrics. Could you provide more details on the specific scenarios or types of data where these heuristic algorithms are most effective? - The paper suggests that future work should explore cases where the assumption of mutual independence of edges does not hold. Could you provide some insights into how this exploration might be conducted? - The paper applies the proposed algorithms to four real-world datasets. Are there plans to test these algorithms on a wider variety of datasets, particularly those with different characteristics or from different domains? - The paper presents a detailed analysis of the problem's complexity. Could you discuss the implications of this complexity for the practical application of the proposed algorithms?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

- The authors made the assumption that the edges in the graph are mutually independent. This assumption may not hold in all cases, and the authors themselves acknowledge that future work should explore scenarios where this assumption does not hold. - The external validity of the derived subgraph is not guaranteed. This means that the subgraph may not be correctly specified with respect to the corresponding real-world process. This could limit the applicability of the results in practical scenarios. - The EDGEID algorithm, one of the exact algorithms proposed in the paper, had large runtime variance which depended heavily on the specifics of the graph under evaluation, particularly for graphs with fewer vertices. This could limit its utility in certain scenarios.

Summary

This paper is about causal identification in a setup where the assumption of reliable knowledge of the causal graph is relaxed. The authors assign a probabilistic weight to the possible confounders. The combinatorial task of finding the most probable causal graph such that a given causal query is identifiable is considered. The same probable with an aggregate probability over the induced subgraph is also considered. Not surprisingly, both these problems are hard. The authors first deliver an exact solution. Two approximate procedures are obtained: (i) a recursion calling min-cut; (ii) a reduction to MCIP. Experiments on real and synthetic data are finally discussed.

Strengths

The idea of an uncertain causal network with distributive semantics looks very reasonable. The hardness results are not surprising, but they appear important for properly characterising the problem. The heuristics presented are non-trivial and effective.

Weaknesses

- Both heuristic algorithms lack a worst-case complexity characterisation. - In the case of MCIP, it needs to be clarified whether the polynomial reduction considered by Proposition 4.2 can be implemented in practice. - Problems 1 and 2 are not necessarily the only/best ways to cope with uncertain causal networks. No robust discussions to advocate such a choice are reported.

Questions

I understand that min-cut has a poly solution, but what is the overall complexity of the first heuristic algorithm? Similarly, is it possible to implement the polynomial transformation in Proposition 4.2, and if so, which is the overall complexity of reducing the problem to MCIP and solving the corresponding instance? The authors assume that the query should be identifiable, and in this perspective, Problems 1 and 2 are very reasonable ways to face the problem. But why should the query be identifiable? There is a lot of literature on non-identifiable queries. E.g., if the output is identifiable only in a very unlikely graph, how should we proceed?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

I don't see relevant issues on this point.

Summary

The paper considers a setting in which we have a probabililty distribution over causal graphs. This paper considers the problem of finding the most probable subgraph in which a given query is identified, and then that subgraph with the highest sum of probabilities of its own subgraphs in which the query is identified. (The latter problem is significant since the result of the identification must agree among all these subgraphs.) A reduction is given to a known NP-hard problem for which various algorithms are evaluated empirically.

Strengths

The paper is well-written and the results are clearly set out, extensive, and correct as far as I can tell.

Weaknesses

I had a little bit of difficulty understanding the problem initially. I am currently a little dubious about the paper's ultimate significance, but if the authors can make the links to structure learning more explicit then it will represent an interesting synthesis with the other approach in which ADMG encapsulates "a priori" facts about the causal structure that are known for certain.

Questions

- Can the authors point to any other literature besides citation [12] in which probability distributions over ADMGs are considered? Or provide motivating examples perhaps involving statistical tests in structure learning. - Line 47: "to addresses" -> "to address"

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes, they have (for instance, the assumption of independence between edges).

Summary

The paper studies the problem of causal identification in a setting which the structure of a causal graph (of interest) is probabilistically uncertain i.e., only known per a certain degree of belief or with a degree of confidence of a particular statistical set, asking the most likely subgraph in which causal effect identifiable. In doing so, paper reduces it the combinatorial optimisation problem i.e., edge ID (as they call it) whose computational complexity is shown to be NP-hard through a reduction from minimum-vertex cover problem. Authors also introduce exact and approximate algorithm and show empirically that the algorithms work good as well.

Strengths

- Deep theoretical paper. - The theoretical results are complemented with good empirical evaluation. - Good exposition.

Weaknesses

I did not spot any major weakness. Only very few minor issues: - causal query better be formally mentioned in *the introduction* (i.e., how does it look like formally) -problem To be surmountable (missing dot) -In Figure 1 caption, also mention the longer version of Q[y] to help following it. -Definition 2.2: explain what you mean when you say functional (again formally). - (potential typo): In Example 1, I sense the direction of the subset to be other way around Gˆ⊆G1 -Assumption 2.1: form (1) -> Equation 1 -In the next [s]ection

Questions

-how about NP-completeness case? -Can the work of Eiter Lukasiewicz 2001 be any useful/connect for further results in your setting?

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

I did not see any particular limitation.

Summary

The authors consider the problem of causal effect identification assuming the given causal graph G is probabilistic where each edge (directed or bi-directed) is associated with a measure of confidence. Under this setting, the objective is to identify a subgraph of G with the highest plausibility such that the target causal effect Q[Y] is identifiable. The authors propose an exact algorithm that is asymptotically exponential, two heuristic approaches, and a reduction to an NP-hard problem that has approximation algorithms. Finally, they evaluate the proposed methods on synthetic and real-world graphs.

Strengths

The formulated problem of identifying the most plausible subgraph where a target effect is identifiable is algorithmically interesting and the author highlight its complexity by showing it to be NP-hard. Moreover, the paper is well-written, for the most, with examples and discussions to illustrate the problem (i.e., Section 2.1). The experimental evaluation of the heuristic algorithms shows favourable performance.

Weaknesses

1- Motivation for the problem: Whenever the target causal effect is not identifiable in the full graph G, it is not justifiable why we would drop edges from G just to make the effect identifiable; an alternative to exact identification could be bounding the target effect. The authors can provide more motivation in the introduction to justify their approach. 2- Lack of performance guarantees for the heuristic approaches: There is no theoretical analysis for the heuristic algorithms discussed in Section 4.2 in terms of upper bound on the cost.

Questions

1- "when $w^{th} = 0$, Algorithm 1 will output the optimal solution": Suppose we have G={Z -> X, X -> Y, X <--> Z, Z <--> Y}, $W_G$={$\infty, \infty, 10, 1$}, $w^{ub}=\infty$, and $w^{th}=0$. Running this example does not lead to any solution unless I'm mistaken. It should optimally return the subgraph after removing the bi-directed between Z and Y. Unless you mean that whenever $w^{th} = 0$, then an alternative formulation of Algorithm 1 is run which discards the threshold and simply searchers for the optimal solution. 2- Implication of Remark 2.1: Can you elaborate on the need for this assumption to only consider Q[Y] instead of general causal queries? Is it a necessary assumption for the problem to be defined or are general queries more challenging? 3- Typos: + Line 68: period after "and open problem" + Line 224: (Line 12) --> (Line 13)

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

Yes

Thanks for the clarification. I will keep my positive score.

I thank for authors for their rebuttal and their detailed clarifications. I am happy to maintain my positive recommendation (weak accepts).