Robustifying Algorithms of Learning Latent Trees with Vector Variables

Abstract:
We consider learning the structures of Gaussian latent tree models with vector observations when a subset of them are arbitrarily corrupted. First, we present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG) without the assumption that the effective depth is bounded in the number of observed nodes, significantly generalizing the results in Choi et al. (2011). We show that Chow-Liu initialization in CLRG greatly reduces the sample complexity of RG from being exponential in the diameter of the tree to only logarithmic in the diameter for the hidden Markov model (HMM). Second, we robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product. These robustified algorithms can tolerate a number of corruptions up to the square root of the number of clean samples. Finally, we derive the first known instance-dependent impossibility result for structure learning of latent trees. The optimalities of the robust version of CLRG and NJ are verified by comparing their sample complexities and the impossibility result.

heading: 1 Introduction
text: Latent graphical models provide a succinct representation of the dependencies among observed and latent variables. Each node in the graphical model represents a random variable or a random vector, and the dependencies among these variables are captured by the edges among nodes. Graphical models are widely used in domains from biology [1], computer vision [2] and social networks [3].
This paper focuses on the structure learning problem of latent tree-structured Gaussian graphical models (GGM) in which the node observations are random vectors and a subset of the observations can be arbitrarily corrupted. This classical problem, in which the variables are clean scalar random variables, has been studied extensively in the past decades. The first information distance-based method, NJ, was proposed in [1] to learn the structure of phylogenetic trees. This method makes use of additive information distances to deduce the existence of hidden nodes and introduce edges between hidden and observed nodes. RG, proposed in [4], generalizes the information distance-based methods to make it applicable for the latent graphical models with general structures. Different from these information distance-based methods, quartet-based methods [5] utilize the relative geometry of every four nodes to estimate the structure of the whole graph. Although experimental comparisons of these algorithms were conducted in some works [4, 6, 7], since there is no instance-dependent
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
impossibility result of the sample complexity of structure learning problem of latent tree graphical models, no thorough theoretical comparisons have been made, and the optimal dependencies on the diameter of graphs and the maximal distance between nodes ρmax have not been found.
The success of the previously-mentioned algorithms relies on the assumption that the observations are i.i.d. samples from the generating distribution. The structure learning of latent graphical models in presence of (random or adversarial) noise remains a relatively unexplored problem. The presence of the noise in the samples violates the i.i.d. assumption. Consequently, classical algorithms may suffer from severe performance degradation in the noisy setting. There are some works studying the problem of structure learning of graphical models with noisy samples, where all the nodes in the graphical models are observed and not hidden. Several assumptions on the additive noise are made in these works, which limit the use of these proposed algorithms. For example, the covariance matrix of the noise is specified in [8], and the independence and/or distribution of the noise is assumed in [9–11, 7]. In contrast, we consider the structure learning of latent tree graphical models with arbitrary corruptions, where assumptions on the distribution and independence of the noise across nodes are not required [12]. Furthermore, the corruptions are allowed to be presented at any position in the data matrix; they do not appear solely as outliers. In this work, we derive bounds on the maximum number of corruptions that can be tolerated for a variety of algorithms, and yet structure learning can succeed with high probability.
Firstly, we derive the sample complexities of RG and CLRG where each node represents a random vector; this differs from previous works where each node is scalar random variable (e.g., [4, 13]). We explore the dependence of the sample complexities on the parameters of the graph. Compared with [4, Theorem 12], the derived sample complexities are applicable to a wider class of latent trees and capture the dependencies on more parameters of the underlying graphical models, such as ρmax, the maximum distance between any two nodes, and δmin, the minimum over all determinants of the covariance matrices of the vector variables. Our sample complexity analysis clearly demonstrates and precisely quantifies the effectiveness of the Chow-Liu [14] initialization step in CLRG; this has been only verified experimentally [4]. For the particular case of the HMM, we show that the Chow-Liu initialization step reduces the sample complexity of RG which isO ( ( 92 )
Diam(T)) toO( log Diam(T)), where Diam(T) is the tree diameter. Secondly, we robustify RG, CLRG, NJ and SNJ by using the truncated inner product [15] to estimate the information distances in the presence of arbitrary corruptions. We derive their sample complexities and show that they can tolerate n1 = O ( √n2 logn2 ) corruptions, where n2 is the number of clean samples.
Finally, we derive the first known instance-dependent impossibility result for learning latent trees. The dependencies on the number of observed nodes |Vobs| and the maximum distance ρmax are delineated. The comparison of the sample complexities of the structure learning algorithms and the impossibility result demonstrates the optimality of Robust Chow-Liu Recursive Grouping (RCLRG) and Robust Neighbor Joining (RNJ) in Diam(T) for some archetypal latent tree structures.
Notation We use san-serif letters x, boldface letters x, and bold uppercase letters X to denote variables, vectors and matrices, respectively. The notations [x]i, [X]ij , [X]:,j and diag(X) are respectively the ith entry of vector x, the (i, j)th entry of X, the jth column of X, and the diagonal entries of matrix X. The notation x(k) represents the kth sample of x. ‖x‖0 is the l0 norm of the vector x, i.e., the number of non-zero terms in x. The set {1, . . . , n} is denoted as [n]. For a tree T = (V, E), the internal (non-leaf) nodes, the maximal degree and the diameter of T are denoted as Int(T), Deg(T), and Diam(T), respectively. We denote the closed neighborhood and the degree of xi as nbd[xi;T] and deg(i), respectively. The length of the (unique) path connecting xi and xj is denoted as dT(xi, xj).

heading: 2 Preliminaries and problem statement
text: A GGM [16, 17] is a multivariate Gaussian distribution that factorizes according to an undirected graph G = (V, E). More precisely, a lsum-dimensional random vector x = [x>1 , . . . ,x>p ]>, where xi ∈ Rli and lsum = ∑p i=1 li, follows a Gaussian distribution N (0,Σ), and it is said to be Markov
on a graph G = (V, E) with vertex set V = {x1, . . . , xp} and edge set E ⊆ (V
2
) and (xi, xj) ∈ E if
and only if the (i, j)th block Θij of the precision Θ = Σ−1 is not the zero matrix 0. We focus on tree-structured graphical models, which factorize according to acyclic and connected (tree) graphs.
A special class of graphical models is the set of latent graphical models G = (V, E). The vertex set V is decomposed as V = Vhid ∪ Vobs. We only have access to n i.i.d. samples drawn from the observed set of nodes Vobs. The two goals of any structure learning algorithm are to learn the identities of the hidden nodes Vhid and how they are connected to the observed nodes.

heading: 2.1 System model for arbitrary corruptions
text: We consider tree-structured GGMs T = (V, E) with observed nodes Vobs = {x1, · · · , xo} and hidden nodes Vhid = {xo+1, · · · , xo+h}, where V = Vhid ∪ Vobs and E ⊆ (V 2 ) . Each node xi represents a random vector xi ∈ Rli . The concatenation of these random vectors is a multivariate Gaussian random vector with zero mean and covariance matrix Σ with size lsum × lsum.
We have n i.i.d. samples X̃j = [x̃ (j)> 1 , · · · , x̃ (j)> o ]> ∈ Rlsum , j = 1, . . . , n drawn from the observed nodes Vobs = {x1, · · · , xo}. However, the observed data matrix X̃n1 = [X̃1, · · · , X̃n]> ∈ Rn×lsum may contain some corrupted elements. We allow an level-(n1/2) arbitrary corruption in the data matrix. This is made precise in the following definition.
Definition 1 (Level-m arbitrary corruption). For the data matrix X̃n1 ∈ Rn×k formed by n clean samples of k random variables (or a random vector of dimension k), an level-m arbitrary corruption transforms X̃n1 into X n 1 ∈ Rn×k such that
‖[X̃n1 ];,i − [Xn1 ];,i‖0 ≤ m for all i = 1, . . . , k. (1)
Definition 1 implies that there are at most n1/2 corrupted terms in each column of Xn1 ; the remaining n− n1/2 samples in this column are clean. In particular, the corrupted samples in different columns need not to be in the same rows. If the corruptions in different columns lie in the same rows, as shown in (the left of) Fig. 3, all the samples in the corresponding rows are corrupted; these are called outliers. Obviously, outliers form a special case of our corruption model. Since each variable has at most n1/2 corrupted samples, the sample-wise inner product between two variables has at least n2 = n− n1 clean samples. There is no constraint on the statistical dependence or patterns of the corruptions. Unlike fixing the covariance matrix of the noise [8] or keeping the noise independent [9], we allow arbitrary corruptions on the samples, which means that the noise can have unbounded amplitude, can be dependent, and even can be generated from another graphical model (as we will see in the experimental results in Section 3.6).

heading: 2.2 Structural and distributional assumptions
text: To construct the correct latent tree from samples of observed nodes, it is imperative to constrain the class of latent trees to guarantee that the information from the distribution of observed nodes p(x1, . . . ,xo) is sufficient to construct the tree. The distribution p(x1, . . . ,xo+h) of the observed and hidden nodes is said to have a redundant hidden node xj if the distribution of the observed nodes p(x1, . . . ,xo) remains the same after we marginalize over xj . To ensure that a latent tree can be constructed with no ambiguity, we need to guarantee that the true distribution does not have any redundant hidden node(s), which is achieved by following two conditions [18]: (C1) Each hidden node has at least three neighbors; the set of such latent trees is denoted as T≥3; (C2) Any two variables connected by an edge are neither perfectly dependent nor independent. Assumption 1. The dimensions of all the random vectors are all equal to lmax.
In fact, we only require the random vectors of the internal (non-leaf) nodes to have the same length. However, for ease of notation, we assume that the dimensions of all the random vectors are lmax. Assumption 2. For every xi, xj ∈ V , the covariance matrix Σij = E [ xix > j ] has full rank, and the smallest singular value of Σij is lower bounded by γmin, i.e.,
σlmax(Σij) ≥ γmin for all xi, xj ∈ V, (2)
where σi(Σ) is the ith largest singular value of Σ.
This assumption is a strengthening of Condition (C2) when each node represents a random vector.
Assumption 3. The determinant of the covariance matrix of any node Σii = E [ xix > i ] is lower bounded by δmin, and the diagonal terms of the covariance matrix are upper bounded by σ2max, i.e.,
min xi∈V det(Σii) ≥ δmin and max xi∈V
diag ( Σii ) ≤ σ2max. (3)
Assumption 3 is natural; otherwise, Σii may be arbitrarily close to a singular matrix. Assumption 4. The degree of each node is upper bounded by dmax, i.e., Deg(T) ≤ dmax.

heading: 2.3 Information distance
text: We define the information distance for Gaussian random vectors and prove that it is additive for trees. Definition 2. The information distance between nodes xi and xj is
d(xi, xj) = − log ∏lmax k=1 σk ( Σij )√
det ( Σii ) det ( Σjj ) . (4) Condition (C2) can be equivalently restated as constraints on the information distance. Assumption 5. There exist two constants 0 < ρmin ≤ ρmax <∞ such that.
ρmin ≤ d(xi, xj) ≤ ρmax for all xi, xj ∈ V. (5)
Assumptions 2 and 5 both describe the properties of the correlation between random vectors from different perspectives. In fact, we can relate the constraints in these two assumptions as follows:
γmine ρmax/lmax ≥ δ1/lmaxmin . (6)
Proposition 1. If Assumptions 1 and 2 hold, d(·, ·) defined in Definition 2 is additive on the treestructured GGM T = (V, E). In other words, d(xi, xk) = d(xi, xj) + d(xj , xk) holds for any two nodes xi, xk ∈ V and any node xj on the path connecting xi and xk in T.
This additivity property is used extensively in the following algorithms. It was first stated and proved in Huang et al. [19]. We provide an alternative proof in Appendix G.

heading: 3 Robustifying latent tree structure learning algorithms

heading: 3.1 Robust estimation of information distances
text: Before delving into the details of robustifying latent tree structure learning algorithms, we first introduce the truncated inner product [15], which estimates the correlation against arbitrary corruption effectively and serves as a basis for the robust latent tree structure learning algorithms. Given a,b ∈ Rn and an integer n1, we compute qi = aibi for i = 1, 2, . . . , n and sort {|qi|}. Let Υ be the index set of the n− n1 smallest |qi|’s. The truncated inner product is 〈a,b〉n1 = ∑ i∈Υ qi. Note that the implementation of the truncated inner product requires the knowledge of corruption level n1.
To estimate the information distance defined in Definition 2, we implement the truncated inner product to estimate each term of Σij , i.e., [Σ̂ij ]st = 1n−n1 〈[X n 1 ]:,(i−1)lmax+s, [X n 1 ]:,(j−1)lmax+t〉n1 . Then the information distance is computed based on this estimate of Σij as
d̂(xi, xj) = − log lmax∏ k=1 σk ( Σ̂ij ) + 1 2 log det ( Σ̂ii ) + 1 2 log det ( Σ̂jj ) . (7)
The truncated inner product guarantees that Σ̂ij converges in probability to Σij , which further ensures the convergence of the singular values and the determinant of Σij to their nominal values. Proposition 2. If Assumptions 1 and 2 hold, the estimate of the information distance between xi and xj based on the truncated inner product d̂(xi, xj) satisfies
P (∣∣d̂(xi, xj)− d(xi, xj)∣∣ > 2l2max
γmin (t1 + t2)
) ≤ 2l2maxe − 3n216κn1 t1 + l2maxe −cn2 κ2 t22 , (8)
where t2 < κ = max{σ2max, ρmin}, and c is an absolute constant.
The first and second parts of (8) originate from the corrupted and clean samples respectively.

heading: 3.2 Robust Recursive Grouping algorithm
text: The RG algorithm was proposed in [4] to learn latent tree models with additive information distances. We extend the RG to be applicable to GGMs with vector observations and robustify it to learn the tree structure against arbitrary corruptions. We call this robustified algorithm Robust Recursive Grouping (RRG). RRG makes use of the additivity of information distance to identify the relationship between nodes. For any three nodes xi, xj and xk, the difference between the information distances d(xi, xk) and d(xj , xk) is denoted as Φijk = d(xi, xk)− d(xj , xk). Lemma 3. [4] For information distances d(xi, xj) for all nodes xi, xj ∈ V in a tree T ∈ T≥3, Φijk has following two properties: (1) Φijk = d(xi, xj) for all xk ∈ V\{xi, xj} if and only if xi is a leaf node and xj is the parent of xj and (2) −d(xi, xj) < Φijk′ = Φijk < d(xi, xj) for all xk, xk′ ∈ V\{xi, xj} if and only if xi and xj are leaves and share the same parent.
RRG initializes the active set Γ1 to be the set of all observed nodes. In the ith iteration, as shown in Algorithm 1, RRG adopts Lemma 3 to identify relationships among nodes in active set Γi, and it removes the nodes identified as siblings and children from Γi and adds newly introduced hidden nodes to form the active set Γi+1 in the (i+ 1)st iteration. The procedure of estimating the distances between the newly-introduced hidden node xnew and other nodes is as follows. For the node xi which is the child of xnew, i.e., xi ∈ C(xnew), the information distance is estimated as
d̂(xi, xnew) = 1 2 ( |C(xnew)| − 1 )( ∑ j∈C(xnew) d̂(xi, xj) + 1 |Kij | ∑ k∈Kij Φ̂ijk ) , (9)
where Kij = { xk ∈ V\{xi, xj} : max { d̂(xi, xk), d̂(xj , xk) } < τ } for some threshold τ > 0. For xi /∈ C(xnew), the distance is estimated as
d̂(xi, xnew) =  ∑ xk∈C(xnew) d̂(xk,xi)−d̂(xk,xnew) |C(xnew)| . if xi ∈ Vobs∑
(xk,xj)∈C(xnew)×C(i) d̂(xk,xj)−d̂(xk,xnew)−d̂(xj ,yi) |C(xnew)||C(i)| otherwise . (10)
The set Kij is designed to ensure that the nodes involved in the calculation of information distances are not too far, since estimating long distances accurately requires a large number of samples. The maximal cardinality ofKij over all nodes xi, xj ∈ V can be found, and we denote this as Nτ , i.e., |Kij | ≤ Nτ .
The observed nodes are placed in the 0th layer. The hidden nodes introduced in ith iteration are placed in ith layer. The nodes in the ith layer are in the active set Γi+1 in the (i+ 1)st iteration, but nodes in Γi+1 can be nodes created in the jth iteration, where j < i. For example, in Fig. 1, nodes x12, x14 and x15 are created in the 1st iteration, and they are in Γ2. Nodes x1, x2 and x5 are also in Γ2, which are observed nodes. Eqns. (9) and (10) imply that the estimation error in the 0th layer will propagate to the nodes in higher layers, and it is necessary to derive concentration results for the information distance related to the nodes in higher layers. To avoid repeating
complicated expressions in the various concentration bounds to follow, we define the function
f(x) , 2l2maxe − 3n232λκn1 x + l2maxe −c n2 4λ2κ2 x2 =: ae−wx + be−ux 2 ,
where λ = 2l2maxe ρmax/lmax/δ 1/lmax min , w = 3n2 32λκn1 , u = c n24λ2κ2 , a = 2l 2 max and b = l 2 max. To assess the proximity of the estimates d̂(xi, xnew) in (9) and (10) to their nominal versions, we define
h(l)(x) , slf(mlx) = sl ( ae−wm lx + be−um 2lx2 ) for all l ∈ N ∪ {0}. (11)
where s = d2max + 2d 3 max(1 + 2Nτ ) and m = 2/9. The following proposition yields recursive estimates for the errors of the distances at various layers of the learned latent tree. Proposition 4. With Assumptions 1–5, if we implement the truncated inner product to estimate the information distance among observed nodes and adopt (9) and (10) to estimate the information
distances related to newly introduced hidden nodes, then the information distance related to the hidden nodes xnew created in the lth layer d̂(xi, xnew) satisfies
P (∣∣d̂(xi, xnew)− d(xi, xnew)∣∣ > ε) < h(l)(ε) for all xi ∈ Γl+1 and l ∈ N ∪ {0}. (12)
We note that Proposition 4 demonstrates that the coefficient of exponential terms in (12) grow exponentially with increasing layers (i.e., ml and m2l in (11)), which requires a commensurately large number of samples to control the tail probabilities. Theorem 1. Under Assumptions 1–5, RRG learns the correct latent tree with probability 1− η if
n2 = Ω̃ ( l4maxe2ρmax/lmaxκ2
δ 2/lmax min ρ 2 min
(9 2 )2LR log |Vobs|3 η ) and n1 = O ( √n2 log n2 ) , (13)
where LR is the number of iterations of RRG needed to construct the tree.
Theorem 1 indicates that the number of clean samples n2 required by RRG to learn the correct structure grows exponentially with the number of iterations LR. Specifically, for the full m-tree illustrated in Fig. 5, n2 is exponential in the depth of the tree with high probability for structure learning to succeed. The sample complexity of RRG depends on e2ρmax/lmax , and the exponential relationship with ρmax will be shown to be unavoidable in view of our impossibility result in Theorem 5. Huang et al. [19, Lemma 7.2 ] also derived a sample complexity result for learning latent trees but the algorithm is based on [5] instead of RG. RRG is able to tolerate n1 = O( √ n2/ log n2) corruptions. This tolerance level originates from the properties of the truncated inner product; similar tolerances will also be seen for the sample complexities of subsequent algorithms. We expect this is also the case for [19], which is based on [5], though we have not shown this formally. In addition, the sample complexity is applicable to a wide class of graphical models that satisfies the Assumptions 1 to 5, while the sample complexity result [4, Theorem 11], which hides the dependencies on the parameters, only holds for a limited class of graphical models whose effective depths (the maximal length of paths between hidden nodes and their closest observed nodes) are bounded in |Vobs|.

heading: 3.3 Robust Neighbor Joining and Spectral Neighbor Joining algorithms
text: The NJ algorithm [1] also makes use of additive distances to identify the existence of hidden nodes. To robustify the NJ algorithm, we adopt robust estimates of information distances as the additive distances in the so-called RNJ algorithm. We first recap a result by Atteson [20]. Proposition 5. If all the nodes have exactly two children, NJ will output the correct latent tree if
max xi,xj∈Vobs ∣∣d̂(xi, xj)− d(xi, xj)∣∣ ≤ ρmin/2. (14) Unlike RG, NJ does not identify the parent relationship among nodes, so it is only applicable to binary trees in which each node has at most two children. Theorem 2. If Assumptions 1–5 hold and all the nodes have exactly two children, RNJ constructs the correct latent tree with probability at least 1− η if
n2 = Ω ( l4maxe2ρmax/lmaxκ2
δ 2/lmax min ρ 2 min
log |Vobs|2
η
) and n1 = O ( √n2 log n2 ) . (15)
Theorem 2 indicates that the sample complexity of RNJ grows as log |Vobs|, which is much better than RRG. Similarly to RRG, the sample complexity has an exponential dependence on ρmax.
In recent years, several variants of NJ algorithm have been proposed. The additivity of information distances results in certain properties of the rank of the matrix R ∈ R|Vobs|×|Vobs|, where R(i, j) = exp(−d(xi, xj)) for all xi, xj ∈ Vobs. Jaffe et al. [6] proposed SNJ which utilizes the rank of R to deduce the sibling relationships among nodes. We robustify the SNJ algorithm by implementing the robust estimation of information distances, as shown in Algorithm 2.
Although SNJ was designed for discrete random variables, the additivity of the information distance proved in Proposition 1 guarantees the consistency of Robust Spectral NJ (RSNJ) for GGMs with vector variables. A sufficient condition for RSNJ to learn the correct tree can be generalized from [6].
Proposition 6. If Assumptions 1–5 hold and all the nodes have exactly two children, a sufficient condition for RSNJ to recover the correct tree from R̂ is
‖R̂−R‖2 ≤ g(|Vobs|, ρmin, ρmax), (16)
where
g(x, ρmin, ρmax) =
{ 1 2 (2e
−ρmax)log2(x/2)e−ρmax(1− e−2ρmin), e−2ρmax ≤ 0.5 e−3ρmax(1− e−2ρmin), e−2ρmax > 0.5 .
Similar with RNJ, RSNJ also does not identify the parent relationship between nodes, so it only applies to binary trees. To state the next result succinctly, we assume that ρmax ≥ 12 log 2; this is the regime of interest because we consider large trees which implies that ρmax is typically large.
Theorem 3. If Assumptions 1–5 hold, ρmax ≥ 12 log 2, and all the nodes have exactly two children, RSNJ reconstructs the correct latent tree with probability at least 1− η if
n2 = Ω ( l4maxe2ρmax(1/lmax+log2(|Vobs|/2)+1)κ2
δ 2/lmax min e
2ρmin log |Vobs|2 η
) and n1 = O ( √n2 log n2 ) . (17)
Theorem 3 indicates that the sample complexity of RSNJ grows as poly(|Vobs|). Specifically, in the binary tree case, the sample complexity grows exponentially with the depth of the tree. Also, the dependence of sample complexity on ρmax is exponential, i.e., O ( e2(1/lmax+log2(|Vobs|/2)+1)ρmax ) , but
the coefficient of ρmax is larger than those of RRG and RNJ, which are O ( e2ρmax/lmax ) . Compared to the sample complexity of SNJ in [6], the sample complexity of RSNJ has the same dependence on the number of observed nodes |Vobs|, which means that the robustification of SNJ using the truncated inner product is able to tolerate O ( √n2 logn2 ) corruptions.

heading: 3.4 Robust Chow-Liu Recursive Grouping
text: In this section, we show that the exponential dependence on LR in Theorem 1 can be provably mitigated with an accurate initialization of the structure. Different from RRG, RCLRG takes ChowLiu algorithm as the initialization stage, as shown in Algorithm 3. The Chow-Liu algorithm [14] learns the maximum likelihood estimate of the tree structure by finding the maximum weight spanning tree of the graph whose edge weights are the mutual information quantities between these variables. In the estimation of the hidden tree structure, instead of taking the mutual information as the weights, we find the minimum spanning tree (MST) of the graph whose weights are information distances, i.e.,
MST(Vobs; D) := arg min T∈TVobs ∑ (xi,xj)∈T d(xi, xj), (18)
where TVobs is the set of all the trees with node set Vobs. To describe the process of finding the MST, we recall the definition of the surrogate node from [4].
Definition 3. Given the latent tree T = (V, E) and any node xi ∈ V , the surrogate node [4] of xi is Sg(xi;T,Vobs) = arg minxj∈Vobs d(xi, xj).
We introduce a new notion of distance that quantifies the sample complexity of RCLRG.
Definition 4. Given the latent tree T = (V, E) and any node xi ∈ V , the contrastive distance of xi with respect to Vobs is defined as
dct(xi;T,Vobs) = min xj∈Vobs\{Sg(xi;T,Vobs)} d(xi, xj)− min xj∈Vobs d(xi, xj). (19)
Definitions 3 and 4 imply that the surrogate node Sg(xi;T,Vobs) of any observed node xi is itself xi, and its contrastive distance is the information distance between the closest observed node and itself. It is shown that the Chow-Liu tree MST(Vobs; D) is equal to the tree where all the hidden nodes are contracted to their surrogate nodes [4], so it will be difficult to identify the surrogate node of some node if its contrastive distance is small. Under this scenario, more accurate estimates of the information distances are required to construct the correct Chow-Liu tree MST(Vobs; D).
Proposition 7. The Chow-Liu tree MST(Vobs; D̂) is constructed correctly if∣∣d̂(xi, xj)− d(xi, xj)∣∣ < ∆MST/2 for all xi, xj ∈ Vobs, (20) where ∆MST := minxj∈Int(T) dct(xj ;T,Vobs).
Hence, the contrastive distance describes the difficulty of learning the correct Chow-Liu tree.
Theorem 4. With Assumptions 1–5, RCLRG constructs the correct latent tree with probability at least 1− η if
n2 =Ω̃
( max { 1 ρ2min (9 2 )2LC , 1 ∆2MST } l4maxe2ρmax/lmaxκ2 δ
2/lmax min
log |Vobs|3
η
) and n1 =O ( √n2 log n2 ) , (21)
where LC is the maximum number of iterations of RRG (over each internal node of the constructed Chow-Liu tree) in RCLRG needed to construct the tree.
If we implement RCLRG with true information distances, LC ≤ d 12Deg(MST(Vobs; D̂)) − 1e. Theorem 4 indicates that the sample complexity of RCLRG grows exponentially in LC LR. Compared with [4, Theorem 12], the sample complexity of RCLRG in Theorem 4 is applicable to a wide class of graphical models that satisfy Assumptions 1 to 5, while the [4, Theorem 12] requires the assumption that the effective depths of latent trees are bounded in |Vobs|, which is rather restrictive.

heading: 3.5 Comparison of robust latent tree learning algorithms
text: Since the sample complexities of RRG, RCLRG, RSNJ and RNJ depend on different parameters and different structures of the underlying graphs, it is instructive to compare the sample complexities of these algorithms on some representative tree structures. These trees are illustrated in Fig. 5. RSNJ and RNJ are not able to identify the parent relationship among nodes, so they are only applicable to trees whose maximal degrees are no larger that 3, including the double-binary tree and the HMM. In particular, RNJ and RSNJ are not applicable to the full m-tree (for m ≥ 3) and the double star. Derivations and more detailed discussions of the sample complexities are deferred to Appendix K.

heading: 3.6 Experimental results
text: We present simulation results to demonstrate the efficacy of the robustified algorithms. Samples are generated from a HMM with lmax = 3 and Diam(T) = 80. The Robinson-Foulds distance [21] between the true and estimated trees is adopted to measure the performances of the algorithms. For the implementations of CLRG and RG, we use the code from [4]. Other settings and more extensive experiments are given in Appendix L.
We consider three corruption patterns here. (i) Uniform corruptions are independent additive noises in [−2A, 2A]; (ii) Constant magnitude corruptions are also independent additive noises but taking values in {−A,+A} with probability 0.5. These two types of noises are distributed randomly in Xn1 ; (iii) HMM corruptions are generated by a HMM which has the same structure as the original HMM but has different parameters. They replace the entries in Xn1 with samples generated by the variables in the same positions. In our simulations, A is set to 60, and the number of corruptions n1 is 100.
Fig. 2 (error bars are in Appendix L.1) demonstrates the superiority of RCLRG in learning HMMs compared to other algorithms. The robustified algorithms also result in smaller estimation errors (Robinson-Foulds distances) compared to their unrobustified counterparts in presence of corruptions.

heading: 4 Impossibility result
text: Definition 5. Given a triple (|Vobs|, ρmax, lmax), the set T (|Vobs|, ρmax, lmax) consists of all multivariate Gaussian distributions N (0,Σ) such that: (1) The underlying graph T = (V, E) is a tree T ∈ T≥3, and the size of the set of observed nodes is |Vobs|. (2) The distribution N (0,Σ) satisfies Assumptions 1 and 5 with parameters lmax and ρmax.
For the given class of graphical models T (|Vobs|, ρmax, lmax), nature chooses some parameter θ = Σ and generates n i.i.d. samples Xn1 from Pθ. The goal of the statistician is to use the observations Xn1 to learn the underlying graph T, which entails the design of a decoder φ : Rn×|Vobs|lmax → T|Vobs|, where T|Vobs| is the set of latent trees whose size of the observed node set is |Vobs|. Theorem 5. Consider the class of graphical models T (|Vobs|, ρmax, lmax), where |Vobs| ≥ 3. If there exists a graph decoder learns from n i.i.d. samples such that
max θ(T)∈T (|Vobs|,ρmax,lmax)
Pθ(T)(φ(Xn1 ) 6= T) < δ, (22)
then (as ρmax →∞ and |Vobs| → ∞), n = max { Ω ( (1− δ)e ρmax blog3 |Vobs|clmax log |Vobs| ) ,Ω ( (1− δ)e 2ρmax 3lmax )} . (23)
Theorem 5 implies that the optimal sample complexity grows as Ω(log |Vobs|) as |Vobs| grows. To prove this theorem, we construct several classes of Gaussian latent trees parametrized as linear dynamical systems (see Appendix M) and apply the ubiquitous Fano technique to derive the desired impossibility result. Table 1 indicates that the sample complexity of RCLRG when the underlying latent tree is a full m-tree (for m ≥ 3) or a HMM is optimal in the dependence on |Vobs|. The sample complexity of RNJ is also optimal in |Vobs| for double binary trees and HMMs. In contrast, the derived sample complexities of RRG and RSNJ are suboptimal in relation to Theorem 5. However, one caveat of our analyses of the latent tree learning algorithms in Section 3 is that we are not claiming that they are the best possible for the given algorithm; there may be room for improvement.
When the maximum information distance ρmax grows, Theorem 5 indicates that the optimal sample complexity grows as Ω(e 2ρmax 3lmax ). Table 1 shows the sample complexities of RRG, RCLRG and RNJ grow as O(e2 ρmax lmax ), which has the alike dependence as the impossibility result. However, the sample
complexity of RSNJ grows as O ( e2tρmax ) , which is larger (looser) than that prescribed by Theorem 5.

heading: 5 Conclusions and future works
text: In this paper, we first derived the more refined sample complexities of RG and CLRG. The effectiveness of CLRG was observed to be due to the reduction in the effective length that the error propagates,
i.e., from LR to LC LR. Second, to combat potential adversarial corruptions in the data matrix, we robustified RG, CLRG, NJ and SNJ by adopting the truncated inner product technique. The derived sample complexity results showed that all the common latent tree learning algorithms can tolerate level-O ( √n2 logn2 ) arbitrary corruptions. The varying efficacies of these robustified algorithms were then corroborated through extensive simulations with different types of corruptions and on different graphs. Finally, we derived the first known instance-dependent impossibility result for learning latent trees. The optimalities of RCLRG and RNJ in their dependencies on |Vobs| were also discussed in the context of various latent tree structures.
There are several promising avenues for future research. First, the design and analysis of the initialization process of CLRG can be further improved. The correctness of CLRG relies only on the fact that if a hidden node is contracted to an observed node, then all the hidden nodes on the path between the hidden node and the observed nodes are contracted to the same observed node. One can conceive of a more general initialization algorithm other than that using the MST of the weighted graph with weights being the information distances. Second, the analysis of RG can be tightened with more sophisticated concentration bounds. In particular, the exponential behavior of the sample complexity of RG can also refined by performing a more careful analysis of the error propagation through the learned tree.
Acknowledgements We would like to thank the NeurIPS reviewers for their valuable and detailed reviews. This work is supported by a National University of Singapore (NUS) President’s Graduate Fellowship, Singapore National Research Foundation (NRF) Fellowship (R-263-000-D02-281), a Singapore Ministry of Education (MoE) AcRF Tier 1 Grant (R-263-000-E80-114), and a Singapore MoE AcRF Tier 2 Grant (R-263-000-C83-112).

Review summaries:
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.

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.