Venue: NeurIPS 2022 Conference

Reviews:

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 present a method that under certain assumptions with respect to the graph structure, and an assumption of linear relationships between variables, guarantees identifiability of the Markov equivalent class of the hierarchical latent graph structure. The authors' method produce superior results to the nearest alternatives.
strengths_and_weaknesses: The authors present a method that under certain assumptions with respect to the graph structure and form of the relationships between variables, guarantees identifiability up to MEC for latent hierarchical models - the method presented is potentially of interest to conference audience as it constitutes an improvement over prior methods. 

What I was less clear on is in what scenarios would this method be useful for modeling observational data. When exactly would it be advantageous for a model selection to be conducted using this procedure? What would be the adventages compared to other methods for inferring latent structure. What is the extra adventage of having linear hierarchical latent variables? Or, do the authors consider this development as a potential foundation for other methods? Without these discussions, the method seems to be of interest to only a limited community of researchers.

How advantageous is the authors' method in terms of computational complexity compared to similar methods presented in the text? Are there any prohibitive trade-off's that come with the additional identifiability guarantees that the authors provide?

Lastly, I think the paper would benefit from improvements to its presentation. The authors present a lot of concepts (e.g. Defs 2,3,4) without any reference to their semantics with respect to the upcoming theoretical results. This leads the reader to do a lot of backtracking while examining the authors method. 
questions: Please see the section above for the questions presented to authors.
limitations: The authors briefly discuss the limitations of their work in the Conclusion section. Additional discussion might include the points raised above.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes a new method to deal with causal discovery when latent confounds exist. The graph is assumed to be with hierarchical structure, and by incorporating the rank deficiency constraints, the method is able to learn the graph and some properties of the latent variables, which has been verified by experiments.

strengths_and_weaknesses: Strengths:
1.	The paper is well formulated mathematically. Many definitions are clear and the theoretical analysis is sound.
2.	There are many examples to ease the understanding of the readers on the main concept of the paper. 

Weaknesses:
1.	The experimental results are slightly weak. It seems only very simple toy data are evaluated.
2.	The efficiency of the method is not well studied. There are multiple phases of the method and the authors are better to show the computational aspects of the paper.

questions: 1. How common do we meet the case that the causal structure is hierarchical？
2. It seems that def 2 is not neccessary.
3. I feel that even with phase 2, the rule 1 recovered graph may be incorrect since not all atomic covers are accessed. How to fix this problem?
4. From lemma 6, how to guarantee that the colliders are all identified?
limitations: No obvious limitations.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: ## Summary of paper:

This work deals with the task of causal discovery of linear additive models in the presense of latent (hidden) variables. Under various assumptions on the graph structure, this work proposes an algorithm to recover the Markov equivalence class of the underlying graph and they show that the recovered graph is asymptotically correct up to certain graph theoretic operators. Most prior works either assume the absence of latent variables (which almost always fails in real-life) or do not necessarily recover the causal structure among the latent variables. It's worth noting that few works have also attempted the latter difficult task of recovering the latent causal structure -- for the linear case, see [1], [2] and for the nonlinear case, see [3].

This work deals with the linear case. The basic strategy is to use rank constraints (which can be exploited because of the linearity assumption) to build the latent graph. Such approaches have been utilized before in other works, e.g. [4], [5]. The algorithm has 3 parts - (a) find "atomic" clusters of latent variables using a greedy approach; (b) fixing incorrect clusters that could be formed; and finally, (c) fix the local structure using the proposed cross-cover test and v-structure test. The overall algorithm proposed here seems similar in spirit to the work of [2] but is technically more involved. With this algorithm, they are able to recover a latent causal graph and show that in the infinite data limit, the graph they recover is in the same equivalence class as the true graph, up to the "minimal graph" and "skeleton" operators (definitions 9-10).

### References:

[1] Animashree Anandkumar, Daniel Hsu, Adel Javanmard, and Sham Kakade. Learning linear bayesian networks with latent variables. In International Conference on Machine Learning, pages 249–257, 2013

[2] Feng Xie, Ruichu Cai, Biwei Huang, Clark Glymour, Zhifeng Hao, and Kun Zhang. Generalized independent noise condition for estimating latent variable causal graphs. In Advances in Neural Information Processing Systems, pages 14891–14902, 2020

[3] Bohdan Kivva, Goutham Rajendran, Pradeep Ravikumar, and Bryon Aragam. Learning latent causal graphs via mixture oracles. Advances in Neural Information Processing Systems, 34, 2021

[4] Ricardo Silva, Richard Scheine, Clark Glymour, and Peter Spirtes. Learning the structure of linear latent variable models. Journal of Machine Learning Research, 7(Feb):191–246, 2006

[5] Erich Kummerfeld and Joseph Ramsey. Causal clustering for 1-factor measurement models. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1655–1664. ACM, 2016.
strengths_and_weaknesses: ## Summary of evaluation

The paper obtains nontrivial and potentially useful results. However, the paper is poorly written, with some misleading remarks and definitions. Moreover, the main condition is a bit hard to interpret without diving deep into the proofs and also, there is insufficient comparison to [3], which I think is doing a fairly more complicated setting than this one (although with different assumptions). See the weaknesses section for more details. Despite this, I appreciate the difficulty surpassed in this work, which I believe is inherent for this difficult task of latent causal discovery, that is slowly gaining traction in the community.

## Strengths:
1. Although the work builds on various known ideas such as exploiting rank deficiency and identifying v-structures, there is significant technical novelty in this work such as the 3-step algorithm that gradually builds the latent graph.
2. The guarantees improve on some prior works such as [1], [2] on a technical level by weakening the required number of observed children for latent variables. That said, other assumptions are made especially regarding the graph structure.
3. The algorithms are clear to follow and are illustrated with examples (see appendix G and H)

## Weaknesses:
1. It is claimed in the introduction that previous works do not handle hierarchical structures (also L66-67 in the appendix). Unfortunately, this doesn't seem right because both [2], [3] that are cited here do seem to handle such structures (see figure 1 in either paper). Moreover, these works handle far more complicated latent structures than the ones considered here (see the point below). Could the authors comment on this?
2. Based on my understanding, the first and foremost assumption in this work is that the graph has a hierarchical structure. Note very importantly that this is a **strict subset** of directed acyclic graphs (DAGs). Therefore, this work does not handle general DAGs. This assumption should be explicitly stated and clarified.
3. In the entire abstract and introduction, it is not mentioned that this paper is dealing with a **linear** model. It only shows up in the formal statement in Section 2. However, this is a highly crucial assumption that *significantly* simplifies the task of causal discovery. For instance, say we want to handle nonlinear models  using the same idea. A first stumbling block in this general setting is whether identifying rank-deficiencies, the engine of this paper, can be exploited again.
4. The first definition Definition 2 is confusing. The phrase "Variables V are pure children of variables L" is defined. However, at this point, I don't see why V is uniquely defined, there could be multiple such Vs. Therefore the next sentence "we denote the pure children of L by PCh_G(L)" does not make sense. Could the authors clarify this?
5. More concretely, it's not clear how the Pure Children definition works if L has connections within itself. For example, take figure 1(a) and assume that the edge L1->L3 is not present for now. Suppose L = {L_1, L_3}. Then PCh_G(L) = {L2, L7, L8, L9}. At this point, since L2 and L7 are connected, I don't understand what PCh_G(PCh_G(L)) is. Because of this, how do we define pure descendants of L?
6. The assumptions of condition 1 (which builds on definition 4) seem hard to interpret. I may be missing something here, but based on my understanding, Appendix G.2, G.3 (in particular L297-298, L311-313) seems to explain how they are relevant *for the proposed algorithm to work*, but not as to why they are *reasonable* assumptions to make. It would be good if the authors could clarify this.
7. Building on the above point, these graph theoretic assumptions are stated to be mild. Why are they mild assumptions?
8. A proper comparison to [3] in appendix E should be added. As stated earlier, it seems like [3] handle general DAGs, not just hierarchical DAGs. Moreover, they handle general non-linear causal relationships instead of just linear and also report the more natural SHD metrics (see below). So its important to clarify which fiber of research this line of work develops on a conceptual level.
9. The reported error metric is the percentage of correctly identified causal clusters over measured variables. Is there a reason a standard metric such as Structural Hamming Distance is not reported? Although I agree with L82-83 in that measuring accuracy is tricky for this problem, other works such as [3] have reported the SHD metric.
questions: Main questions are raised in the strengths and weaknesses part above.

## Other questions/comments:
1. In L98, what is meant by L and pure children being fully connected? Every pair of vertices from within L, within its pure children and across L and its pure children are all connected by an edge?
2. What is the objective of appendix G.1? It doesn't seem to explain Definition 3 as the algorithm in G.1 seems to modify the graph (esp. L287-288). But Definition 3 is for a static graph.
3. In theorem 7, what is meant by a R-2H graph?
4. Theorem 7 says that the correct Markov equivalence class is learned asymptotically. In the proof of theorem 7, it'd be good to clarify why the algorithm works in the limit. In other words, it's not clear where the asymptotic is coming from.
5. How are the latent graphs constructed in the synthetic examples? Moreover, the code is not released so it's impossible to figure out how the synthetic examples were generated.
6. What is the running time of the algorithm? It seems like Algorithm 2 for phase 1 seems to take exponential time in the input size but this should be clarified.
7. The work [2] seems most closely related to this work. There is a comparison to it in Appendix E. The way it's stated, the main difference seems technical - reducting the number of observed variables needed for latent variables. Is there some other conceptual difference between the works?
8. The caption for figure 12 is written over the page number in the appendix.
limitations: Limitations of the theory are addressed and the authors state there are no potential negative societal impacts. I tend to agree as this is predominantly a theoretical paper.
review_title: null

Meta-review: metareview: All reviewers and AC agree that this work is clearly of interest to NeurIPS. 
Two out of three reviewers increased their score after their concrnes were successfully addressed 
during the rebuttal. Reviewer's eq5G main concern was the weakness of the experimental results. 
After reading the authors' response, the AC believes that the authors could introduce the additional supplementary
experiments they ran to cover the concern. A suggestion for better presentaiton is also communicated ot the authors. 
Acceptance is recommended.
confidence: Certain
Decision: Accept