Venue: NeurIPS 2022 Conference

Reviews:

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 proposed recovering and verification of causal graphs via sufficient hard interventions with unlimited data.  Contributions are constructing bounds on the “minimum verification number” of a graph G belonging to the Markov equivalent class of the underlying ground truth.  Compared to existing approaches, their method could deal with general graph.  They characterize the verifying intervention sets via separation of un-oriented cover edges of the input essential graph. 

They also consider a relative new setting, i.e. verifying if an expert provided causal graph is correct using minimal interventions. 

Furthermore, they use an objective function to measure the optimality of intervention policies by trading  off the additive weights of verification inventions as well as the size of the verification set. 
The main contribution of this paper seems to theoretical, by proving a strengthened version of previous work. 

The paper is well written with clean explanations, the contributions are summarized clearly, lemmas correspondence to existing works are well indicated. 

There is no conclusion section, for page limit, it looks like algorithms could still be moved to appendix to save some space for another summary at the end if the authors did not find this unnecessary. 
strengths_and_weaknesses: Strengths: 




Strengths:
S1. They extend previous results to general graphs and provide tighter bounds
S2. They also consider a relative new setting, i.e. verifying if an expert provided causal graph is correct using minimal interventions. 
S3. They derived richer results  beyond single vertex intervention. 



Weakness:

W1. The paper assume causal sufficiency, which is usually not true in reality. 
As noted in the introduction part, the hard intervention is also not a realistic assumption. 

W2. If I did not miss it, there seems to be no empirical study to support the claims made in the paper, compared to SMG 20, PSS 22.


questions: Q1. I believe a tighter bound would give better guidance in practice, before verification/adaptive search, for the experiment carrier to evaluate how many resources one might need to allocate to finish the experiment, i.e. identify the causal graph. 

What would be the future work of this work, consider if this paper get cited in the future, what would be the improvements based on this paper? 

Q2. If I did not miss it, there seems to be no empirical study to support the claims made in the paper, compared to SMG 20, PSS 22.
Regarding the new scheme used in this contribution, does the author think it might be helpful to carry out empirical studies to validate those bounds or show the superiority of the new policy?

Q3. In line 351, what does “arefi9x” mean?
Q4. it seems that there is no conclusion of the paper?


limitations: L1:
I would suggest conducting an empirical study validating the proposed algorithm alongside the theorems.
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: The authors study the problems of verification and search for identifying causal DAGs from minimal-cost interventions. Using the concept of covered edges, they provide a theoretical result characterizing verifying sets, as well as a practical method for constructing such sets optimally. For the problem of search, the paper provides a novel algorithm for search, with complexity bounded by a connection to the minimum cost verifying set.
strengths_and_weaknesses: Overall, this is a strong theoretical work which provides novel perspectives on minimal-cost identification of causal DAGs. The authors make a number of novel connections between the verification and search problems, some of which in particular are very interesting and even surprising:
- Thm 9, which states that it is N+S to separate all covered edges in G to verify G (reduce G’s I-MEC to a singleton); this is a stronger version of prior results on the search problem (e.g. Thm 1 in [KDV17]) which say it is N+S to separate all edges to find the true graph (reduce all I-MECs to singletons).
- That the search problem can be algorithmically linked to the verification problem by Lemma 21, with a strategy of intervening on cliques whose size can be bounded by intervention sizes for the verification problem.

The theoretical connections also give rise to efficient algorithms for performing verification and search on general graphs, which are a significant advance over prior approaches.

From a presentation standpoint, the paper is generally well written with clear presentation of the results and comparison to prior work. However, it is also very dense, particularly with the novel results and algorithms, which are packed into the final 4 pages of the paper. For instance, Algorithm 1 would benefit from explanation of the function/intuition behind each step, as well as bounding the complexity. I would suggest that the authors move some of the (arguably) more peripheral content to the Appendix (e.g. lines 258-277), to make more space to explain the key results. 
questions: 1) Have the authors considered adaptive solutions for the verification problem also, and whether this might provide further benefit?

limitations: Yes, limitations and social impact have been addressed explicitly in the text.
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: This paper considers the problem of recovering causal graphs from interventional data (search problem). Additionally to recovering of an unknown causal graph, the authors studied the problem of verifying whether a given directed causal graph is indeed the correct one using an optimal number of interventions (verification problem). They proposed lower bounds for both of the considered questions which are based on the minimum verification number. Finally, they proposed an algorithm for both problems and derived bounds on the number of performed interventions.
strengths_and_weaknesses: Strength: 
- The authors studied an interesting connection between the optimal number of interventions that are needed to verify whether the given directed causal graph is correct and the optimal number of interventions that one needs to recover the causal graph. Furthermore, they compare their results with existing works.

Weaknesses: 
- Despite there is an example that the minimum verification number is larger than the lower bounds derived in [PSS22], it is not clear how much this bound is better. It seems that the difference between these two values may be just a constant or just a constant ratio. 
- Lemma 35 is different from the lemma introduced in [SMG+20] and it is not obvious how it is possible to get Lemma 35 from Lemma 6 in [SMG+20]. Lemma 35 is then used for the proof of Lemma 21, which are one of the main results in comparing achieved lower bounds with another work.
- The proposed algorithm is fully composed of steps irrelevant to the minimum verification number. Moreover, the whole analysis of the algorithm follows the theorems from the other works, and it is not unclear how this algorithm is different from already existent ones and why it would have better performance. 
- No experiments were done for comparing the proposed algorithm with already existing algorithms.
- Some of the results about minimum verification number are easy corollaries of already existing theorems (such as Theorem 11 and 12).

questions: - Lemma 35 looks different from Lemma 6 in [SMG+20], but in the paper, it is asserted that they are the same. How can Lemma 35 be obtained from Lemma 6 [SMG+20]?
- Why the proposed search algorithm is better than already existing algorithms and what are the main differences between them?

limitations: The authors briefly mentioned possible limitations for transferring the results to the real world, which are reasonable. All the limitations do not have a negative social impact.
review_title: null

Meta-review: metareview: This paper's reviews as it stands are divergent. The scores are 7, 5 and 4. The paper has seen discussion between reviewers with negative opinion and the authors. One reviewer who engaged in discussion revised the score up by 1.

The most unfavorable reviewer's main issue was lack of empirical evaluations comparing the authors algorithms to close competitors [SMG 20, PSS 22]. - Authors have responded turning in a quick implementation with plots comparing performance of their algorithm with competitors. Authors attached it plots and a readme in the form of an anonymous Drive folder (I looked at it briefly).  It seems like their algorithm is very competitive with state of the art and infact in terms of runtime is faster than even random in some cases. Experiments seem reasonably comprehensive.  I would have ideally liked the authors to include the contents of the drive folder into the main paper and uploaded a revision (I am not sure if authors are aware that one can update the paper during the rebuttal).  
I would consider this issue sort of taken care of. Empirical simulations do clearly show that the proposed algorithms are effective for random graphs of different size.

Other concerns (even after a long discussion with reviewers) are: How significant are the theoretical results in comparison to [SMG 20, PSS 22]. 
1) Does it follow from many theorems about covered edges [Chi 95] classically known and other theorems from these two recent references ? 
Authors responded saying - they are the first to give an *exact* algorithm to perform adaptive interventions to verify if a given graph is indeed the true one exactly characterizing the instance optimal number of interventions. I agree with the authors that this is not known and relation to covered edges does not directly follow from existing classical results (as authors have explained and I did see the proofs in the supplement.)
So results for exact instance optimal verification are certainly new and novel and previous works only provided bounds on the verification number.

2) How novel are the search results ?  - Here, it is true that for proving approximation guarantee they do rely on a slight modification of a lower bound, i.e. Lemma 21 in the paper as observed by one reviewer in the discussion. However, authors also point out that theirs is the first algorithm which has instance wise O(log n) approximation to the best adaptive rate for arbitrary graphs.

 I believe this was an open problem. Previous works like [SMG+20] could not make a general argument due to their reliance on directed clique trees and some orientation properties of the directed clique trees. Current work takes a different approach using clique separators and authors very easily extend the results to interventions of bounded size (which was also not known in general).

3) Experiments were added in an anonymous drive folder (I would strongly suggest the authors to add a few to the main camera ready + put the rest in supplement and discuss in detail about runtime benefits etc. Currently the only discussion is in the readme file).  

For all the three concerns, I feel authors have adequately addressed the concerns. This paper simplifies adaptive interventional design with many interesting observations and generalizations in addition to particularly novel contributions to the verification problem. 

Hence, I am positive about this paper.

To the authors: Please do include the figures and discuss the experiments in the camera ready. Your anonymous folder contents must go into the paper (split between main paper and supplement) at the very least. Authors may think their theoretical contribution is the main point of the paper. However, experimentally seeing competitiveness to the baselines AND runtime benefits for various graph sizes is an important contribution. Unlike many other theory results, interventional complexity is unlike sample or computational complexity. Therefore, actual gains do matter (even multiplicative constants) and I do appreciate authors putting in the effort during rebuttal. It has definitely helped with one of the chief reviewer concerns.
 




confidence: Certain
Decision: Accept