Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this paper, the authors consider the problem of learning Gaussian latent tree models when the nodes of the tree are vector variables and the observations are arbitrarily corrupted. The paper uses the algorithms of Choi et al. (2011) as the base and extends their results (which are for the case when the nodes in the tree are scalar and there is no corruption) to vector variables with an arbitrarily corrupted subset of samples. Furthermore, they provide a more refined sample complexity analysis and highlight the advantage of using Chow-Liu based initialization in the sample complexity. They also provide novel impossibility results.
main_review: Originality:

Not novel– Graph-theoretic aspects of the algorithms RG, NJ, SNJ, and CLRG have all been exactly used as they exist in the literature. 

Incremental Novelty- Once we have an additive distance metric these algorithms are straightforward to follow. Thus the extension of the results to vector random variables is a straightforward case of plugging the distance measure (proposed in Huang et al. (2020)) into the existing algorithms. Similarly imparting robustness is also a straightforward application of Chen et al. (2013) in the estimation of distance.

Novelty- (i) Sample complexity results that highlight the exponential dependence on the number of iterations for RRG. (ii) The potential improvement in the HMM case when initialized with Chow-Liu tree. (iii) The insight that the Chow-Liu tree is not the same as the MST of the distance metrics and the class of graphical models for which they are the same.

Quality:

My current understanding is that in the RRG algorithm, the authors should consider only a subset of the active nodes which have a distance below a given threshold at each iteration following on the lines relaxed RG algorithm of Choi et al. (2011).
In that direction, it would be great if the authors can answer this question – The proposed RRG algorithm considers all the nodes in the active set while making decisions about sibling or parent child relationships in the nodes (line 5,7,8 of Algorithm 1) which seems to be motivated by the RG algorithm of Choi et al. (2011). However, shouldn’t the authors build upon the relaxed RG algorithm of Choi et al. (2011) which is developed for the finite sample setting and only considers nodes in the active set that have distance smaller than a threshold while determining parent child or sibling relationships? Would this change the sample complexity – in particular, will the exponential dependence on the number of iterations of RRG continue to be the case? 

Furthermore, my understanding of the RG algorithm of Choi et al. (2011) is that it is the steppingstone to the (better) CLRG algorithm. Thus, the extensive discussion of the RG algorithm in this paper would only make sense if the CLRG algorithm does not apply to some settings. Indeed, as per the discussion in the paper about the potential non-monotonicity of the distance with the mutual information, it seems that CLRG might not be applicable in general. However, I could not really understand why do we have to initialize with the MST of the mutual information. My understanding is that the algorithm would go through just fine if we simply initialized with the MST of the empirical distances and did not worry about the mutual information (yes, this tree would not be the Chow-Liu tree). I might be missing something and I would really appreciate it if the authors can point to what would break down if I used the above approach. 

A minor point is that the authors seem to paint the picture that their setting is more challenging compared to [7-11] because they consider arbitrary corruption (lines 40-41, 99). While the setting of arbitrary corruptions is a very interesting setting especially when the corruptions can be present in the different components, it feels misleading to present it as a more difficult problem. While in the setting of [7-11] there are restrictions on the noise model, $all$ the samples are noisy, unlike the setting in this paper where only a small ($\mathcal{O}(\sqrt{n})$) $subset$ of the samples are noisy.

Clarity: 

The paper is clearly written and easy to follow.

Significance: 

According to my understanding of the paper right now, the results in this paper are incremental. Answering the questions in the Quality section would help in highlighting the significance of the contributions of this paper.

I am happy to change my evaluation if the authors can answer the above questions.

limitations_and_societal_impact: The paper does not seem to have any negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Summary:

The paper studies the structural learning problems on latent tree models, in which a subset of vector observations have been arbitrarily corrupted. The paper proposes a series of "robustified" algorithms, including the robustified recursive grouping (RRG), robustified Chow-Liu recursive grouping (CLRG), robustified neighbor joining (RNJ), and robustified spectral neighbor joining (RSNJ). The authors analyze the sample complexity of the algorithms and show that a number of corruptions up to the square root of the number of clean samples can be tolerated. The paper also provides an information theoretic lower bound for this class of graphical models.
main_review: Strength:

It seems there are a series of solid results presented in this paper, namely the robustified algorithms and the corresponding upper limits for recovery. 

The assumption of an arbitrary corruption pattern is interesting and, arguably, more challenging in analysis compared to, say, uniform corruptions. This is also more desirable from an application point of view. The related discussion in the appendix is interesting.

According to the paper the information theoretic lower bound in Theorem 5 is novel for its class, although it seems the Fano's inequality proof is standard. 


Weakness:

Given the current state the paper suffers from the writing, which can be improved a lot. 

- This paper deals with corruptions in graphical models, however I cannot find the formal definition of corruption. This is never defined in Section 2. Please let me know if I misunderstood something. 

- Boldface x_i: Is this a vector or an entry? See Line 67 vs Line 75.

- Use the full names of the algorithms instead of the acronyms for their first appearance in the introduction section.
    Here are a few:
    - Line 23: NJ -> Neighbor Joining (NJ)
    - Line 26: RG -> Recursive Grouping (RG)
    - Line 46: CLRG ->  Chow-Liu Recursive Grouping 

- Consider rephrasing Line 75 - 78.

Regarding Line 343 - 349: What else can be said about the gap in RRG and RSNJ? Is it because of the analysis not being tight, or the original RG and SNJ algorithm not being optimal?

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors introduce various theoretical results for learning latent trees including the following: a) extends RG to be applicable to GGMs (sec 3.2), b) reduce sample complexity for RG using Chow-Liu initialization, which depends of random vectors that fulfill a monotonic property (sec 3.4), and c) present an impossibility result that is useful for comparing theoretical results and directing future effort on this topic. Experimental results with synthetic data mirror the theoretical results, and both RCLRG and RSNJ perform markedly better than the baselines.
main_review: Strengths

- All claims seem to be valid, although I may have missed any subtle errors.
- This is clearly a substantial extension of previous work, and is relevant to many researchers who work on closely or loosely related areas. Graphical models are relevant to most if not all of the ML community.
- The related work is well organized and presented clearly to highlight the exact contributions of this paper. The entire paper is highly technical, yet well written and easy to follow.
- The detailed appendix is incredibly helpful. It includes additional details for proofs, algorithms, and results.

Weaknesses

- Minor complaint. It would benefit the reader to briefly explain why noisy samples are important in this context even if it is touched upon in related work (e.g. the intro from Choi et al.).

limitations_and_societal_impact: The authors thoroughly address limitations by the nature of their theoretical results, but also clearly describe assumptions where applicable.
review_title: null

Meta-review: This paper studies the problem of learning Gaussian latent tree models where the nodes are vector-valued random variables and there are corruptions. There were differing opinions among the reviewers, but in aggregate they agreed that the extension of existing works (notably the algorithms of Choi et al.) from the scalar-valued to vector-valued case was interesting and non-trivial. They also show how the Chow-Liu Recursive Grouping algorithm (as opposed to the Recursive Grouping algorithm) leads to improved dependence on the diameter of the underlying tree. Finally they give robustified algorithms based on the thresholded inner-product, whereby they can tolerate a total number of corruptions of about the squareroot of the number of clean samples. This paper has a nice mix of contributions and would make a solid addition to the conference. 
Decision: Accept (Poster)