Robustifying Algorithms of Learning Latent Trees with Vector Variables
Authors: Fengzhuo Zhang
Vincent Tan
Venue: NeurIPS 2021 Poster (2021)
Keywords: graphical model
latent trees
arbitrary corruptions

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.

Robustifying Algorithms of Learning Latent Trees with Vector Variables
Fengzhuo Zhang
Department of Electrical and Computer Engineering National University of Singapore fzzhang@u. nus edu
.us.edu
Vincent Y. F. Tan Department of Electrical and Computer Engineering Department of Mathematics
National University of Singapore vtanõnus edu, sg
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 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 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 the square root of the number of clean samples. Finally, we derive the first known instance-dee -eeeaneeedeeddentt 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.
Introduction
Latent graphical models provide succinct representation of the dependencies among observed and latent variables. Each node in the graphical model represents random variable or a random vector, and the dependencies among these variables 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 the structure learning problem of latent tree-structured Gaussian graphical models (GGM) in which the node observations are random vectors and subset of the observations 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 [I] 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 lastance-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
since there is instance-dependent
35th Conference on Neural Information Processing Systems (NcurIPS 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 Pmax have not been found.
The success of the previously- mentrioood algorithms relies the assumption that the observations are i..dd samples from the generating distribution. The structure learning of latent graphical models in presence of (random or adversarial) noise remains 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 specified in [8 and the independence and/or distribution of the noise is assumed in 111 71. 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 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 (3)) We explore the dependence of the sample complexities on the parameters of the graph. Compared with 44 Theorem 12), the derived sample complexities are applicable a wider class of latent trees and capture the dependencies on more parameters of the underlying graphical models, such as Pmaxx- the maximum distance between any two nodes, and dmin 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 is O (lam(T)))) to O log Diam (T)), where Diam(T) is the tree diameter.
Secondly, robustify RG, CLRG, NJ and SNJ by using the truncated inner product [1] to estimate the information distances in the presence of arbitrary corruptions. We derive their sample complexities and show that they can tolerate 1 (
corruptions, where n2 is the number of clean samples.
log 112
Finally, we derive the first known cesstacc--ependee impossibility result for learning latent trees. The dependencies on the number of observed nodes [Vobel and the maximum distance Pmax 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 for some archetypal latent tree structures.
Notation We use san-serif letters æ, boldface letters x, and bold uppercase letters X denote variables, vectors and matrices, respectively. The notations [x]; [X]ij- [X]. and diag(X) are respectively the 7th entry of vector x, the (i, entry of X, the jth column of X, and the diagonal entries of matrix X. The notation (kk represents the htth sample of x. ||x||o is the la norm of the vector x, i.e., the number of non-zero terms in x. The set {l,..., n) is denoted as [n]] For tree T T= (V,& 8). the internal (non-leaf) nodes, the maximal degree and the diameter of T. are denoted as (T). Deg(T)) and (T), respectively. We denote the closed neighborhood and the degree of x; as nbd[2z [z;; T] and deg(i), respectively. The length of the (unique) path connecting I; and xy is denoted as dy Iz),
2 Preliminaries and problem statement
A GGM 16 17 is a multivariate Gaussian distribution that factorizes according to an undirected graph G = (V,8) E). More precisely, a Jaun-dimeesional random vector x = [x]"..., x X; E 1gl. and 4aum = ΣP 1 4, follows a Gaussian distribution (0 E), and it is said to be Markov on graph G ()) with vertex set V {zI...., Ip} and edge set E S ( and (2,, E if
where

---

and only if the (2. block b5 of the precision ② = Σ is not the zero matrix O. We focus on tree-structured graphical models, which factorize according to acyclic and connected (tree) graphs.
special class of graphical models the set of latens graphical models G = (V, The vertex set V is decomposed as V = Vhid U Vobs- We only have access to 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 Viid and how they are connected to the observed nodes.
2.1 System model for arbitrary corruptions
We consider tree-structured GGMs T = (V,E) with observed nodes Vobe = {o1, ....... Fo} and hidden nodes Vhid = foo+1. .. Both ), where V = Vuia U Vots and & S (b) Each node x; represents random vector X, E R The concatenation of these random vectors is a multivariate Gaussian random vector with zero mean and covariance matrix E with size 4um x 4uum-
We have n i.i.d. samples X, [x , Xo X.'TTT E IR/ ,j 1. ,....,. drawn from the observed
nodes Vat = {.1.... ; ] However, the observed data matrix X = [X,,... ,X,]] E RR TRuxllum 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 (Level-m arbitrary corruption). For the data matrix X E TR formed by n clean samples of k random variables (or random vector of dimension k), an level-m arbitrary corruption transforms X7 into X E nx such that
|| (x S m for all i= i
Definition] I iiplies that there are at most /2 corrupted terms in each column of X²; the remaining n /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. B3 all the samples in the corresponding rows are corrupted: these are called outliers. Obviously, outliers form 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 constraint on the statistical dependence patterns of the corruptions. Unlike fixing the covariance matrix of the noise [8] or keeping the noise independent [ 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
2.2 Structural and distributional assumptions
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...., x,) is sufficient to construct the tree. The distribution p(x1..... Xo+h) of the observed and hidden nodes is said to have redundant hidden node zy if the distribution of the observed nodes p(xI...., ... remains the same after we marginalize over Ty. 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 [8]: (C1) Each hidden
node has least three neighbors; the set of such latent trees denoted Tz3; (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 Imax-
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 I I
Assumption 2. For every Zi,I, E V, the covariance matrix Eij = B[xxx]] has full rank, and the smallest singular value of Σng is lower bounded by Tmin i.e.,
Olans (Eiz)= 2 Tmin for all Iz, D, E V,
(2)
where o; (E(E) is the 7th largest singular value E. Σ.
This assumption is a strengthening of Condition (C2) when each node represents random vector.
3

---

Assumption 3. The determinant of the covariance matrix of any node Eg = E is lower bounded by Suin and the diagonal terms of the covariance matrix are upper bounded by a i.e.
min det (Ex) 2 8min and max diag (2:) S o
(3)
$.EV
Assumption 3 is natural; otherwise, Eū may be arbitrarily close to singular matrix.
Assumption 4. The degree of each node is upper bounded by dmaax i.e., Deg(TT S dmax-
2.3 Information distance
We define the information distance for Gaussian random vectors and prove that it is additive for trees. Definition 2. The information distance between nodes I; and z- is
((I;, = log I Tk Eii))
(4)
V dct Ea)det (my)
Condition (C2) can be equivalently restated as constraints on the information distance.
Assumption 5. There exist two constants 0 < Pmin I Pmax < Do such that.
Pmin d(z,, S Pmax for all 24, V.
(5)
Assumptions 2 and both describe the properties of the correlation between random vectors from different perspectives. In fact, relate the constraints in these two assumptions follows:
Tmin Proax/ / Hmax 2 81/lmaxe
(6)
min
Proposition 1. If Assumptions 7 and 2 hold, d(.,-) defined in Definition is additive the tree- structured GGM T = E) In other words, d(x,, 2xk = d(z,, + d( Ik) holds for any two nodes I5. 2g V and any node 2j on the path connecting z; and Fę 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
Robustifying latent tree structure learning algorithms
3.1 Robust estimation of information distances
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 basis for the robust latent tree structure learning algorithmss Given a, b E R" and an integer nı we compute q a&b; for 1,2, index set of the ni smallest Iqil's. The truncated inner product is (a. b).,, = =Eier 9s- Note that the implementation of the truncated inner product requires the knowledge of corruption level ni.
and sort {lq:]) Let Y be the
To estimate the information distance defined in Definition 2 we implement the truncated inner product estimate each term Σ,y, i.e., [E,yle n- Then the information distance is computed based on this estimate of Σig as
(X l..t- 1) [Xf]. 1) +x)
Lanx
d(r, 22) = - log II or (En)) + 2 log det (Ex) - log log det (E₁)).
(7)
2
The truncated inner product guarantees that Eig converges in probability to Eij, which further ensures the convergence of the singular values and the determinant of Eij to their nominal values. Proposition 2. If d'Assumptions [andZhole the estimate of the information distance between and Iÿ based the truncated inner product d(z,, 2.)) satisfies
P ((( d(z,, 2r)]
212 (t1 + +ta) 212
max
SHQ 21 IUNAS
12
max
(8)
Vmia
where to < R. = max pmnu), and is absolute constant.
The first and second parts of originate from the corrupted and clean samples respectively.

---

3.2 Robust Recursive Grouping algorithm
The RG algorithm was proposed in 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 Ii, I, and Tk. the difference between the information distances d(x;, FK.) and (x.) is denoted as Iijk d(r;, T&) - d(zr.. FT.).
T.) Lemma 3. (4) For information distances d(x;; 2z) for all nodes I;, 2; E V in a tree T E T23- Pigk has following two properties: (1) Piik d(z;, for all I&k (1, F3) } if and only if s4 a leaf node and 3; is the parent of 2j and (2) -d -d(x,, R;)) < Pijk' = -iik < d( Iz)) for all Ik, Fy E
for
V (M if and only if x; and zjj are leaves and share the same parent.
RRG initializes the active set I to be the set of all observed nodes. In the 2th iteration, shown in Algorithm|1 [ RRG adopts Lemma 3 to identify relationships among nodes in active set I and removes the nodes identified siblings and children from I" and adds newly introduced hidden nodes to form the active set D in the (i + 1)st iteration. The procedure of estimating the distances between the newly-introduced hidden node Nnew and other nodes is follows, For the node x; which is the child of Tnew, i.e., I; E C(Inew), ), the information distance is estimated as
a(zi, Fnow) 2([C(Fnew)
a(z; xT) +
(9)
K
@EE((mno))
REKi,
where Kij = {Ix E V1(2,,2, 23 max (d(z;, xx)), a( xx)} < Ty & C( the distance is estimated as
<T} for some threshold 7 >> 0. For
å(z; know) { Ex a(v2) d(d)
if xy E Vobs
[C(F )1
(10)
d(2k. ( -( (aow) - die, mc)
((
otherwise
[C [(Fuew)]]((()
The set K;y 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 of KC; over all nodes 24, E V can be found, and we denote this as i..... [Kii] S N,-
The observed nodes are placed in the 9th layer. The hidden nodes introduced in 7th iteration are placed in zth layer. The nodes in the hhh layer are in the active set [++1 in the (i + 1)at iteration, but nodes in ri+1 can be nodes created in the 5th iteration, where < i. For example, in Fig. [ nodes T12, I14 and 115 are created in the 1st iteration, and they are in T2. Nodes I1, and are also in 2 which are observed nodes. Eqns. (9) and (10) imply that the estimation error in the 9th 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
15
An illustration of the active set. The shaded nodes the observed nodes and the rest are hidden nodes.
Figure 1:
f(x) A 212 maaxe
BZANN
+
12 M
ae be ua?
where A 2/2 maxx Prmas// / /bmax /82/haxx
2/2 max and b = 12 max To assess the proximity of the estimates d(r;; )nww) ) in (9) and 10 to their nominal versions, we define
3nz 32ARn1
(x) 2 st f(m'xx) s (ae um'z 'x + be um um² for all 1 [O)
(11)
where s dera + 2d3 F (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 With Assumptions 7 if we implement the truncated inner product to estimate the information distance among observed nodes and adopt 9 and (10) estimate the information
5

---

distances related to newly introduced hidden nodes, then the information distance related to the hidden nodes Nnew created in the 1ob layer d(zi, Fnew) satisfies
TP (P)ā( Fnew) d Fnow) > > < h (e) for all I2 P.ETT E and LE LENU(() (12)
We note that Proposition demonstrates that the coefficient of exponential terms in 12 grow exponentially with increasing layers (i.e., m' and m² in (Tp), which requires a commensurately large number of samples to control the tail probabilities.
Theorem 1. Under Assumptions
RRG learns the correct latent tree with probability 1 1 if
112 == 52
max Pmpae / x²2
(
2L log
Vaba 1 and nn = ( Vn2
(13)
22 2/1maxx min
Pmin
log 122
where LR is the number of iterations of RRG needed to construct the tree.
Theorem D 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. [
n2 is exponential in the depth of the tree with high probability for structure learning succeed. The sample complexity of RRG depends
e20mnx/luns and the exponential
relationship with Pmax will be shown to be unavoidable in view of our impossibility result in Theorem Huang 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 n = O (//2// 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. addition, the sample complexity is applicable to wide class of graphical models that satisfies the Assumptions 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 Vatel-
3.3 Robust Neighbor Joining and Spectral Neighhor Joining algorithms
The NJ algorithm [ 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 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 I. EVobs Vols
|d(z;, d(1;, S Pmin/ 22.
(14)
Unlike RG, NJ does not identify the parent relationship among nodes, so only applicable to binary trees in which each node has at most two children.
Theorem 2. If Assumptions 7 hold and all the nodes have exactly two children, RNJ constructs the correct latent tree with probability at least 11 if
1 122 (2
max e / 2
Vobal 2) ) and =0(
VT2
log
(15)
2/beax 8min
Pmiin
n
llog T22
Theorem 2 indicates that the sample complexity of RNJ grows as log (obsll which is much better than RRG. Similarly to RRG, the sample complexity has an exponential dependence on Pmax.
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 E R [o |x /Vooal,, where R(i,j) cxp(-d(x;, )ry)) for all 2;, Iy E Vols. 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
Although SNJ was designed for discrete random variables, the additivity of the information distance proved Proposition | guarantees the consistency 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 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 S ((VVabal Pmiin Pmmxx);
(16)
where
{
1/2 (2e Prnox) 122e-oox)logg(111 )lo8g(1/2) ePmoo Pmoo 2Pmin) 2Pmax < 0.5
g( Punin: Pmax))
e 3pmax (1 - 3ppmin
e 2Pmax > 0.5
Similar with RNJ, RSNJ also does not identify the parent relationship between nodes, so it only applies binary trees. To state the next result succinctly, assume that Pmnx log 2; this is the regime interest because we consider large trees which implies that Pmax is typically large.
Theorem 3.
hold, Pmax 2 log 2, and all the nodes have exactly two children, RSNJ reconstructs the correct latent tree with probability at least 1 7) if
If Assumptions 7
122 = (
14 max 22 Pinox Bnna Hlgg, 12)++) n²
log
Vobel
and n1 = 0
V log 122
(17)
22f1mox min
Theorem 3 indicates that the sample complexity of RSNJ grows as poly([Vota)). Specifically, in the binary tree case, the sample complexity grows exponentially with the depth of the tree. Also, the de- pendence of sample complexity on Pmax is exponential, i.e., (e2((1/mmxx (00011/mmxxxttup (Vongg/Voool/)e//ee
). but the coefficient of Pmax is larger than those of RRG and RNJ, which are OpePPaax/'en (mnx) ). Compared to the sample complexity of SNJ in [6. the sample complexity of RSNJ has the same dependence on the number of observed nodes Vots) which means that the robustification of SNJ using the truncated
inner product is able to tolerate ( Tog corruptions.
3.4 Robust Chow-Liu Recursive Grouping
In this section, we show that the exponential dependence on LR. in Theorem I can be provably mitigated with an accurate initialization of the structure. Different from RRG, RCLRG takes Chow- Liu algorithm as the initialization stage, shown in Algorithm 3 The Chow-L.iu 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(V D) = arg min
Σ (EI.E))TT
((1,,,))
(18)
TETv
where Tri is the set of all the trees with node set Vohs we recall the definition of the surrogate node from [4].
To describe the process of finding the MST,
Definition 3. Given the latent T = EV,E) and any node x; E V, the surrogate node 4 of 3g Sg(2;; T, Vobs) = arg ming 2, Voobe A(I;,
We introduce a new notion of distance that quantifies the sample complexity of RCLRG.
Definition 4. Given the latent tree T = EV,E) and any node vi E V, the contrastive distance af; with respect to Vobe is defined as
det (zz4 T, Vobs) Vye (SR())))))..))
min
d(z;,
min ((x,);;))
(19)
Definitions and liplyy that the surrogate node Sg(z,; T, Vobe) of any observed node z; is itself Ie and its contrastive distance is the information distance between the closest observed node and itself. It is shown that the Chow-Liu tree MST(V.ss: 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 its contrastive distance is small. Under this scenario, more accurate estimates the information distances are required to construct the correct Chow-Liu tree MST(Vots: D).
7

---

Proposition 7. The Chow-Liu tree MSS(Vobs: D) is constructed correctly if
d(æ; mz) d( 2;)] < AMST/2 /2 for all Ti,25 E Vobs
(20)
where AMST elm det (zy;; T, Vobe).
Hence, the contrastive distance describes the difficulty of learning the correct Chow-Liu tree.
RCLRG constructs the correct latent tree with probability at Theorem 4. With Assumptions Z 1 2Prroxx Hemox R²
least 1 - 17 if
112 = - max
1
2Le
log
Vobal
and 71 =0 Vn2
(21)
Pmin
MIST
min
22/1eaxe
1
log 122
where Le is the maximum number of iterationn of RRG (over each internal node of the constructed Chow-Liu tree) in RCLRG needed to construct the tree.
we implement RCLRG with true information distances, Le S Dege Theorem 4 indicates that the sample complexity of RCLRG grows exponentially in Le < LR- Compared with [4 Theorem 12], the sample complexity of RCLRG in Theorem applicable to a wide class of graphical models that satisfy Assumptions to while the 4 Theorem 12] requires the assumption that the effective depths of latent trees are bounded in Vobel, which rather restrictive.
D)) 17.
3.5 Comparison of robust latent tree learning algorithms
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
some representative tree structures. These and RNJ are not able to identify the parent relationship among nodes, so they are only applicable to trees whose maximal degrees are 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 2 3) and the double star. Derivations and more detailed discussions of the sample complexities are deferred Appendix K
illustrated in Fig. [5] RSNJ
10.
Algorithm
RRG
RCLRG
RSNJ
RNJ
Tree
Double binary tree
O (1)
O Diam(T)
2022pmax Diam (T))
(
HMM
( 2 Diamt()
( log Diam(T))
Ole Ppmax log Diam(T)
( log (Tam(T))
Full m-tree
O (is
Ol (T)
N.A.
N.A.
Double star
Ol log dmaax)
O & log dmas)
N.A.
N.A.
Table The sample complexities of RRG, RCLRG, RSNJ and RNJ on the double-binary tree, the
HMM, the full m-tree and the double star. We ub 2pmar Rmaxe and O(mix + log [ohee)).
3.6 Experimental results
We present simulation results to demonstrate the efficacy of the robustified algorithms. Samples are generated from a HMM with 4max = and Diam(T) = 80. The Robinson-Fowd Foulds distance [21] between the true and estimated trees is adopted to measure the performances of the algorithms. For the implementations CLRG and RG, we use the code from [4]. Other settings and more extensive experiments are given in Appendix D
We consider three corruption patterns here. (i) Uniform corruptions are independent additive noises in 22,, 2A]: (ii) Constant magnitude corruptions are also independent additive noises but taking values (A) with probability 0.5. These two types noises are distributed randomly in X (iii) HMM corruptions are generated by a HMM which has the same structure as the original HMM has different parameters. They replace the entries in X with samples generated by the variables in the same positions. In our simulations, A is set to 60, and the number of corruptions n; is 100.

---

AV
Sue
(a) Uniform corruptions
(b) Constant magnitude corruptions
(c) HMM corruptions
Figure 2: Robinson-Foulds distances of robustified and original algorithms averaged over 100 trials
Fig. 2 (error bars are in Appendix L.I) demonstrates the superiority of RCLRG learning HMMs compared other algorithms. The robustified algorithms also result in smaller estimation errors (Robinson-Foulds distances) compared to their unrobustified counterparts in presence of corruptions.
Impossibility result
Given triple ([Vohs), I Pmnax lmnx), the T(Vooss Pmaxy mmax) consists of all multi- variate Gaussian distributions (0, Σ) such that: (1) The underlying graph T = (V,E) is tree T23, and the size of the set of observed nodes is (Vobal. (2) The distribution N (0, E) satisfies Assumptions 3nd parameters max and Pinax.
Definition 5.
For the given class of graphical models T(Vobel) Pmax lmax). nature chooses some parameter 0 Σ and generates i.i.d. samples X from I'g. The goal of the statistician is to use the observations X to learn the underlying graph T. which entails the design of decoder Φ R Vahellmax - Tivetll
where Tivonl is the set of latent trees whose size of the observed node set Votall-
Theorem 5. Consider the class of graphical models T([Vons) I Pmaxx lmax), where [Vohel 2 3. If
there exists graph decoder learns from i...d samples such that
max
POCTT (0) X * (T)) <
(22)
((T)ET((Volll Pmax Smax)
then (as Pmax + 0o and (ooel + 20).
max { 8)e Toug [oobsll Jamax
Gmax log (ot (). 8)e 3lmax }
(23)
Theorem 5 implies that the optimal sample complexity grows as ([log (obsl)) as |oobll grows. To prove this theorem, construct several classes of Gaussian latent trees parametrized linear dynamical systems (see Appendix M) and apply the ubiquitous Fano technique to derive the desired impossibility result. Table I indicates that the sample complexity of RCLRG when the underlying latent tree is full m-tree (for m 2 3) or HMM is optimal in the dependence on [obell The sample complexity of RNJ is also optimal derived sample complexities of RRG and RSNJ are suboptimal in relation to Theorem
Votal for double binary trees and HMMs. In contrast, the
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 Pmax grows, Theorem Sannoremmmjndeee iiddicates that the optimal sample complexity grows as Q(E 2Pmax 3lmmxx ). Table shows the sample complexities of RRG, RCLRG and RNJ grow as Oie² 2 Tmax ), which has the alike dependence as the impossibility result. However, the sample complexity of RSNJ grows O (e which is larger (looser) than that prescribed by Theorem 5
5 Conclusions and future works
In this paper, we first derived the more refined sample complexities of RG and CLRG. The effective- ness of CLRG was observed to be due to the reduction in the effective length that the error propagates,

---

i.e., from LR to Le & 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 / arbitrary corruptions. The varying efficacies of these robustified algorithms were level-O log mg
then corroborated through extensive simulations with different types of corruptions and on different graphs. Finally, we derived the first known instance-dependen impossibility result for learning latent trees. The optimalities of RCLRG and RNJ in their dependencies on Votel 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 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. particular, the exponential behavior of the sample complexity of RG can also refnnd by performing more careful analysis of the error propagation through the learned tree.
Acknowledgements We would like to thank the NeurlPS reviewers for their valuable and detailed reviews. This work is supported by a National University of Singapore (NUS) President's 's Graduate Fellowship. Singapore National Research Foundation (NRF) Fellowship (R-263-000-D02-22) Singapore Ministry Education (MoE) AcRF Tier Grant (R-263-000-E80- 114), and a Singapore MoE AcRF Tier 2 Grant 04-263-000--C3--113
References
[1] N. Saitou and M. Nei. The neighbor-joining method: new method for reconstructing phyloge- netic trees. Mol. Bio. Evol., 4(4):406-425, 1987.
[2] D. Tang, H. J. Chang, A. Tejani, and T. Kim. Latent regression forest: Structured estimation of 3d articulated hand posture. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pages
2014.
[3] Eisenstein, B. O' O'Connor N. A. Smith, and Xing. latent variable model for geographic lexical variation. In Proc. Conf. Empirical Methods in Natural Language Processing, pages 1277-1287, 2010.
[4] M. J. Choi, V. Y. F. Tan, A. Anandkumar, and A. S. Willsky, Learning latent tree graphical models, Journal of Machine Learning Research, 12:1771-1812, 2011.
[5] A. Anandkumar, K. Chaudhuri, D. Hsu, S. M. Kakade M, L. Song, and T. Zhang. Spectral methods for learning multivariate latent tree structure. arXiv preprint 107. 2011.
[6] A. Jaffe, N. Amsel, Y. Aizenbud, B. Nadler, J. Chang, and Y. Kluger. Spectral neighbor joining for reconstruction of latent tree models. SIAM Journal Mathematics of Data Science, 3 2021.
[7] M. Casanellas, M. Garrote-Lopez, and P. Zwiemnik. Robust estimation of tree structured models. arXiv:2102.05472v [stat.MI.], Feb. 2021.
[8] A. Katiyar, J. Hoffmann, and C. Caramanis. Robust estimation of tree structured gaussian graphical models. In International Conference Machine Learning, pages 3292-3300. PMLR, 2019.
[9] K. E. Nikolakakis, D. S. Kalogerias, and A.D. Sarwate. Learning tree structures from noisy data. In Proc. Artificial Intelligence and Statistics, pages 1771-1782. PMLR, 2019.
[10] A. Tandon, V. Y. F. Tan, and S. Zhu. Exact asymptotics for learning tree-structured graphical models: Noiseless and noisy samples. IEEE Journal on Selected Areas of Information Theory, 133):700-77,, 2020.
10

---

[11] A. Tandon, A. H. J. Yuan, and V. Y. F. Tan. SGA: A robust algorithm for partial recovery of tree-structured graphical models with noisy samples. In International Conference on Machine Learning. PMLR, 2021.
[12] L. Wang and Q Gu. Robust gaussian graphical model estimation with arbitrary corruption. In International Conference on Machine Learning, pages 3617-3626. PMLR, 2017.
[13] A. Parikh, L. Song, and E. P. Xing. A spectral algorithm for latent tree graphical models. In International Conference Machine Learning, pages 1065-1072, Jun. 2011.
[14] C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE Trans. Inform. Theory, 14(3):62-467, 1968.
[15] Y. Chen, C. Caramanis, and S. Mannor, Robust high dimensional sparse regression and matching pursuit. arXiv preprint arXiv: 1301.2225, 2013.
[16] L. Lauritzen. Graphical models, volume 17. Clarendon Press, 1996.
[17] V. Y. F. Tan, A. Anandkumar, and A. S. Willsky. Learning Gaussian tree models: Analysis of exponents and extremal structures. IEEE Transactions Signal Processing. 58(10):2701- 2714, 2010.
[18] P. Judea. Probabilistic reasoning in intelligent systems: Networks of plausible inference. Elsevier, 2014.
[19] Huang, N. U. Naresh, Perros, Chen, Sun, and A. Anandkumar. Guaranteed scalable learning of latent tree models. In Uncertainty in Artificial Intelligence, pages 883-893, PMIR, 2020.
[20] K. Atteson. The performance of neighbor-joining methods of phylogenetic reconstruction. Algorithmica, 25(2):251-22 1999.
[21] D. F. Robinson and L. R. Foulds. Comparison of phylogenetic trees. Mathematical Biosciences, 53(1-2):131-177, 1981.
[22] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. University Press, New York, NY, 2010.
Cambridge
[23] G. H. Golub and C. Van Loan. Matrix Computations. The Johns Hopkins University Press, Maryland, US, 2013.
[24] G. W. Stewart. Perturbation theory for the singular value decomposition. SVD and Signal Processing, II: Algorithmss Analysis and Applications, pages 99-109, 1991.
[25] S. Pettie and V. Ramachandran. An optimal minimum spanning tree algorithm. J. ACM, 49(1):16-34, 2002.
[26] W. Wang, M. J. Wainwright, and K. Ramchandran. Information-thhooeti bounds on model selection for Gaussian markov random fields. In Proc. IEEE Int. Symp. on Inf. Theory, pages 1373-1377 Austin, Texas, USA. Jun. 2010. IEEE.
[27] M. Mareus and W. Gordon. An extension the Minkowski determinant theorem, Proceedings of the Edinburgh Mathematical Society, 17(4):321-322 1971.


Reviews:
[{"review_id": "nxVJcjvjYdb", "reviewer": "Reviewer_fher", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nNot novel– Graph-theoretic aspects of the algorithms RG, NJ, SNJ, and CLRG have all been exactly used as they exist in the literature. \n\nIncremental 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.\n\nNovelty- (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.\n\nQuality:\n\nMy 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).\nIn 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? \n\nFurthermore, 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. \n\nA 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.\n\nClarity: \n\nThe paper is clearly written and easy to follow.\n\nSignificance: \n\nAccording 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.\n\nI am happy to change my evaluation if the authors can answer the above questions.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not seem to have any negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "CZZ73hPrN0k", "reviewer": "Reviewer_jt2c", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n- All claims seem to be valid, although I may have missed any subtle errors.\n- 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.\n- 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.\n- The detailed appendix is incredibly helpful. It includes additional details for proofs, algorithms, and results.\n\nWeaknesses\n\n- 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.).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors thoroughly address limitations by the nature of their theoretical results, but also clearly describe assumptions where applicable.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "BmDVppIxD-_", "reviewer": "Reviewer_YapK", "summary": "Summary:\n\nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\nIt seems there are a series of solid results presented in this paper, namely the robustified algorithms and the corresponding upper limits for recovery. \n\nThe 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.\n\nAccording 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. \n\n\nWeakness:\n\nGiven the current state the paper suffers from the writing, which can be improved a lot. \n\n- 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. \n\n- Boldface x_i: Is this a vector or an entry? See Line 67 vs Line 75.\n\n- Use the full names of the algorithms instead of the acronyms for their first appearance in the introduction section.\n    Here are a few:\n    - Line 23: NJ -> Neighbor Joining (NJ)\n    - Line 26: RG -> Recursive Grouping (RG)\n    - Line 46: CLRG ->  Chow-Liu Recursive Grouping \n\n- Consider rephrasing Line 75 - 78.\n\nRegarding 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)