column of $\widehat{Z}$. Due to the sparse and heterogeneous nature of
$\widehat{Z}$ and $X$, simple correlations are unstable. The “best feature
function” (bff) [Wang and Rohe, 2016] shows better performance in real data
analysis. It measures the importance of word $l$ for factor $j$ as

$\text{{bff}
}(j,l)=\sqrt{\frac{\sum_{i\in\text{in}(j)}\widehat{Z}_{ij}X_{ij}}{\sum_{i\in\text{in}(j)}\widehat{Z}_{ij}}}-\sqrt{\frac{\sum_{i\in\text{out}(j)}\widehat{Z}_{ij}X_{ij}}{\left|\text{out(j)}\right|}},$

where sets $\text{in}(j)$ and $\text{out}(j)$ for block $j$ are defined as
$\text{in}(j)=\\{i:\widehat{Z}_{ij}\geq 0\\}$,
$\text{out}(j)=\\{i:\widehat{Z}_{ij}<0\\}$.

###  D.3 Linking Pattern of the Wikipedia page link network

Figure 19 presents the linking pattern of the wikipedia page link network.
This tree presents similar clustering structure as the being linked pattern
tree (Figure 9).

Figure 19: Tree recovered from the linking pattern of Wikipedia pages. There
are many “list of something” pages in the tree. Though the structure is not as
clear as the being linked tree, there are still similar patterns. The bottom
half of the tree is the North American cluster and the upper half of the tree
is the European cluster, the Asian cluster, and the animal/plant cluster are
mixed together on the right of the tree.

##  Appendix E Robustness with respect to the selection of $k$

The consistency of step 1 (vsp) in synthesis relies on two things: $k$ remains
constant as $n$ increases and the correct $k$ is chosen as input. However,
synthesis exhibits satisfying performance in both simulation and real data
examples when these two conditions are violated.

###  E.1 Robustness to $k$ in simulated data: balanced binary tree and non-
balanced tree

This section briefly discusses the robustness of synthesis by conducting
simulations of ${\mathbb{T}}$ being a binary balanced tree and non-balanced
tree in the ${\mathbb{T}}$-Stochastic Graph.

Consider a ${\mathbb{T}}$-Stochastic Graph with ${\mathbb{T}}$ being a $n$
leaf node binary balanced tree, then in the equivalent
${\mathbb{T}}$-Graphical Blockmodel, the number of blocks $k=n/2$, and there
are only two nodes in each block. This is an example of $k$ increasing at the
same rate as $n$. In this situation, it is not plausible to choose the true
$k$ as the input. However, synthesis with an underestimated $k$ as input can
still recover some top-level structures of the tree.

Figure 20: Performance of the first step algorithm on a balanced binary tree
with $n=2048$ leaf nodes. The true $k=1024$ in this case and we test our
algorithm with $k=8$, hoping to recover the top structure of the tree. Leaf
nodes are colored by their estimated clusters. As the average degree goes
higher, the leaf nodes get finer clusters

Figure 20 plots the clustering result of the first step algorithm when
$n=2048$ (true $k=1024$), and we choose $k=8$ as the input. The true
underlying tree structure (balanced binary tree) is plotted and leaf nodes are
colored by the clustering result. Since we choose $k=8$, we would hope the
algorithm to recover the first 3 levels of the tree. That is, descendants of
the same nodes in the 3rd level should be clustered into the same block. To
explore how the performance is affected by the average degree, we plot the
results of average degree = 20, 50, and 100 from left to right. We can observe
that the first-step clustering results are still trustworthy with an
underestimated $k$, and as the average degree increases, the clusters become
more refined.

This tree example is relatively easy and clear due to its balanced and
symmetric properties. Under more general cases where ${\mathbb{T}}$ is a
random tree, synthesis still gives reasonable clustering results.

(a)  (b)

Figure 21: Performance of the first step algorithm on an unbalanced binary
tree with $n=2048$ leaf nodes. We test our algorithm with
$k=4,8,16,32,64,128$. In Subfigure (a), leaf nodes are colored by their
estimated clusters, In Subfigure (b), leaf nodes are plotted against their
estimated clusters. As $k$ increases, the clusters get more refined.

Figure 21 presents the result of a randomly generated tree with $n=2048$ leaf
nodes. In Subfigure (a), the true underlying tree shape is plotted and leaf
nodes are colored by their cluster. A good estimation result should present
similar color for leaf nodes that are close. In Subfigure (b), the estimated
clusters are plotted versus the leaf node index. Still, a good result should
cluster nodes with close indexes together. When $k=4$, there is some
inconsistency in the tree presented in Subfigure (a). In the upper half of the
tree, the light blue color is cut into two parts by the dark blue color; in
the lower half of the tree, the red is mixed with the light blue color. This
light blue color corresponds to the third cluster in Subfigure (b), and we can
observe that this cluster contains three discontinuous parts of the tree.
Similar inconsistency can be observed when $k=8$, and the result gets better
as $k$ increases.

###  E.2 Robustness to $k$ in real data: Journal Citation network

In this section, we examine a journal citation network derived from the
Semantic Scholar dataset [Ammar et al., 2018], which comprises over 200
million academic publications. To analyze the journal citation patterns, we
aggregate the paper citation network by journals and identify unique journal
names by converting all letters to lowercase and removing punctuation. To
simplify computation, we randomly sampled 5% of the paper citations and set
$A_{ij}=1$ if there were more than five citations (in this random sample) from
papers in journal $i$ to papers in journal $j$. After sampling and
thresholding, the original dataset containing approximately 100,000 journals
was reduced to 22,688.

While $A$ is a square matrix, it is not a symmetric matrix. We deal with this
by applying synthesis to $A^{undir}=A^{T}+A$. More details about dealing with
asymmetric matrices can be found in Appendix D.1. Due to the heterogeneous row
and column sums, we also apply the degree-normalization and renormalization
steps proposed in [Rohe and Zeng, 2022]. All trees in this section are
estimated with $\widehat{B}^{nn}=\widehat{Z}_{+}^{T}A\widehat{Z}_{+}$ in the
first step and a simple NJ algorithm in the second step. Leaf nodes are
labeled with the most important word measured by bff (see Appendix D.2 for
more details about bff ).

An important question here, and also in any other real data analysis, is how
do we choose $k$? In applied multivariate statistics, estimating the number of
latent dimensions is a fundamental problem. Most solutions try to find $k$ by
locating a gap between eigenvalues, the widely used scree plot technique
[Cattell, 1966] is a representative example. However, the real dataset hardly
presents an eigengap. Figure 22 presents the eigenvalues of the degree
normalized adjacency matrix $L$ for this dataset.

Figure 22: The first 300 eigenvalues of the normalized adjacency matrix for
the journal citation network, with lines at $k=30,100,200$. No clear eigengap
can be observed.

With the ${\mathbb{T}}$-Stochastic graph and the synthesis algorithm proposed,
another way to think about this problem is to ask: are tree structures robust
with respect to different choices of $k$? An ideal case is that as $k$
increases, the algorithm outputs more refined clusters and detailed tree
structures. Though with some disturbance, we find that the general structure
is stable across different selections of $k$ in this journal citation network.

Figure 23: Journal citation tree with $k=30$. This tree presents similar
clustering structures as the journal citation tree with $k=100$ (Figure 1).

Figure 1 plots the tree recovered from this dataset with $k=100$. While there
are more detailed group structures and connections, in general, the tree can
be summarized as large clusters about social science (economics, management),
math, engineering, earth science, psychology, and medical science. Figure 23
plots the tree recovered with $k=30$, this smaller tree presents similar
clusters and structures. The same pattern can be observed in journal citation
trees with $k=70$ and $k=200$, presented in Figure 25 and 24, accordingly.
Additionally, Figure 24 also presents the detection of potentially non-tree-
like structures.

Comparing the estimated tree distance matrix and the TSGdist estimation is
helpful in detecting non-tree like structures

Figure 24: This is the Journal citation tree with $k=70$ and its diagnosis.
There are notable differences between the tree estimation and the TSGdist
estimation around the engineering cluster and the physics/material cluster.
Such differences usually indicate the existence of some non-tree-like
structures that the neighbor-joining algorithm can’t reconstruct. We
conjecture that this is caused by the wide cross-disciplinary application of
math/statistics. The statistics/combinatory factors are joined together with
the engineering cluster whereas the mathematical/arxiv factors are combined
with the physics/material clusters. Figure 25: This figure presents the
journal citation tree with $k=200$. By comparing to Figure 23, 1, and 25, we
can observe that recovered journal citation trees with different $k$ have
similar structures.

##  Appendix F Proof for equivalence between six alternative models

In a tree graph ${\mathbb{T}}=(V,E)$, if we take any two nodes $p,q\in V$,
then there is only one path that connects them (without backtracking). Denote
the set of nodes on this path, including nodes $p$ and $q$, as $V(p,q)$, and
the set of edges along this path as $E(p,q)$.

Though the following sections, we use $\lambda_{ij}^{TSG},\
\lambda_{ij}^{GB},\ \lambda_{ij}^{OB}$ to represent $\lambda_{ij}$’s in
${\mathbb{T}}$-Stochastic Graphs, ${\mathbb{T}}$-Graphical Blockmodels, and
${\mathbb{T}}_{r}$-Overlapping Blockmodel respectively. And denote the
corresponding population adjacency matrix as
$\mathscr{A}^{TSG},\mathscr{A}^{GB},\mathscr{A}^{OB}$.

###  F.1 ${\mathbb{T}}$-Graphical Blockmodel: Proof of Theorem 3.2,
Proposition 3.1 and 3.2

The proof of Theorem 3.2 involves two directions:

  1. 1.

proving every ${\mathbb{T}}$-Graphical Blockmodel is a
${\mathbb{T}}$-Stochastic Graph,

  2. 2.

proving every ${\mathbb{T}}$-Stochastic Graph is a ${\mathbb{T}}$-Graphical
Blockmodel.

These two parts are established separately in the following sections (Appendix
F.1.1 and Appendix F.1.2). To demonstrate the first part, Proposition 3.1 is
utilized, while the second part is shown using Proposition 3.2. The proof of
Proposition 3.1 and Proposition 3.2 can be found in Appendix F.1.3 and
Appendix F.1.4, respectively.

####  F.1.1 Every ${\mathbb{T}}$-Graphical Blockmodel is a
${\mathbb{T}}$-Stochastic Graph

Given any ${\mathbb{T}}$-Graphical Blockmodel, construct a
${\mathbb{T}}$-Stochastic Graph with edge weight $w_{uv}$ such that

  1. 1.

$w_{uv}=-\log(|\Sigma_{uv}|)$ for any pair of internal nodes $u,v$,

  2. 2.

$w_{i,p(i)}=-\log(\theta_{i})$ for any leaf node $i\in V_{\ell}$ and its
parent $p(i)$.

It’s easy to check that $w_{uv}$ is positive for all internal edges $(u,v)$ as
$|\Sigma_{uv}|\in(0,1)$. The proof is complete by

$\displaystyle\lambda^{TSG}_{ij}$ $\displaystyle=\exp(-d(i,j))$
$\displaystyle=\exp\left(-w_{i,p(i)}\right)\exp\left(-w_{i,p(i)}\right)\exp(-d(p(i),p(j)))$
$\displaystyle=\theta_{i}\theta_{j}\exp(-d(p(i),p(j)))$
$\displaystyle=\theta_{i}\theta_{j}\exp\left(\sum_{(u,v)\in
E(p(i),p(j))}-\log\left(|\Sigma_{uv}|\right)\right)\quad\text{(by the
construction above)}$
$\displaystyle=\theta_{i}\theta_{j}|\Sigma_{p(i),p(j)}|\quad\text{(by
Proposition \ref{prop:cov->dist})}$
$\displaystyle=\theta_{i}\theta_{j}|\Sigma_{z(i),z(j)}|=\theta_{i}\theta_{j}B_{z(i),z(j)}\quad\text{(by
Definition \ref{def:tgb})}$ $\displaystyle=\lambda^{GB}_{ij}$

######  Remark F.1.

In the above proof for Theorem 3.2, we construct edge weight on ${\mathbb{T}}$
such that $w_{i,p(i)}=log(1/\theta_{i})$ for leaf node $i$. This means that
when $\theta_{i}>1$, the edge weight between leaf nodes $i$ and its parent is
negative. In fact, one can multiply all $\theta_{i}$ by a constant $\sqrt{c}$
such that

$\lambda_{ij}^{GB}=c\,\theta_{i}\theta_{j}B_{z(i),z(j)}=c\exp(-d(i,j)),$

that explains why considering $\lambda_{ij}^{TSG}=c\exp(-d(i,j))$ is
equivalent to allowing $w_{i,p(i)}<0$ for any leaf node $i$.

####  F.1.2 Every ${\mathbb{T}}$-Stochastic Graph is a
${\mathbb{T}}$-Graphical Blockmodel

This part also serves as a complete proof for Theorem 3.1 as every
${\mathbb{T}}$-Graphical Blockmodel is a DCSBM by definition. Specifically,
the matrix $B$ defined in Section 3.1 is a principal submatrix of the matrix
$\Sigma$ defined in Proposition 3.1 and therefore is full rank.

To show that every ${\mathbb{T}}$-Stochastic Graph is a
${\mathbb{T}}$-Graphical Blockmodel, consider any ${\mathbb{T}}$-Stochastic
Graph with additive distance $d(\cdot,\cdot)$. Define $\Sigma$ as

$\Sigma_{ij}=\exp(-d(i,j)).$ (13)

Then by Proposition 3.2, $\Sigma$ is positive definite, and the multivariate
Gaussian distribution with covariance matrix $\Sigma$ is a GGM on
${\mathbb{T}}$. Therefore, one can construct a ${\mathbb{T}}$-Graphical
Blockmodel with $\Sigma$, following Definition 6. Furthermore, define
$\theta_{i}=\exp(-d(i,p(i)))$ for any leaf node $i$ and its parent $p(i)$.

The proof is completed by

$\displaystyle\lambda_{ij}^{GB}$
$\displaystyle=\theta_{i}\theta_{j}B_{z(i),z(j)}=\theta_{i}\theta_{j}B_{p(i),p(j)}=\theta_{i}\theta_{j}\left|\Sigma_{p(i),p(j)}\right|\quad\text{(by
Definition \ref{def:tgb})}$
$\displaystyle=\theta_{i}\theta_{j}\Sigma_{p(i),p(j)}\quad\text{(since
$\Sigma_{p(i),p(j)}$ is positive by Equation \eqref{eq:construct_sigma})}$
$\displaystyle=\theta_{i}\theta_{j}\exp(-d(p(i),p(j)))\quad\text{(by
Proposition \ref{prop:dist->cov})}$
$\displaystyle=\exp(-d(i,p(i)))\exp(-d(j,p(j)))\exp(-d(p(i),p(j)))\quad\text{(by
the construction above)}$ $\displaystyle=\lambda_{ij}^{TSG}$

####  F.1.3 Proof of Proposition 3.1

Proposition 3.1 is a direct result of Lemma F.1, which is a rephrase of
Proposition 3 in [Choi et al., 2011] and is first discussed in [Erdős et al.,
1999]. Lemma F.1 shows that under a Gaussian Graphical Model, a negative log
transformation of correlations builds an additive distance. Since Definition 5
assumes $\Sigma_{ii}=1$, correlations are equal to covariance and thus the
proof is complete. Discussions about non-unit variance ($\Sigma_{ii}\neq 1$)
can be found in Appendix G.2

######  Lemma F.1.

(Erdős et al. [1999]) If a Multivariate Gaussian distribution
$\mathcal{P}(\cdot)$ is a GGM on tree ${\mathbb{T}}=(V,E)$, denote the
correlation between any two nodes (not necessarily neighbors) $p,q\in V$ as
$\rho_{pq}$ and define

$d(p,q)=-\log\left(\lvert\rho_{pq}\rvert\right),$

then $d(\cdot,\cdot)$ is an additive distance on ${\mathbb{T}}$ in the sense
that:

$d(p,q)=\sum_{(u,v)\in E(p,q)}d(u,v),\quad\forall p,q\in V,$ (14)

where $E(p,q)$ is the set of all edges along the path between nodes $k$ and
$l$.

######  Remark F.2.

Although the definitions of additive distance in our paper and in [Erdős et
al., 1999] are presented differently, they are actually equivalent. It’s easy
to check that distances define in our approach satisfy Equation (14), and thus
is an additive distance in [Erdős et al., 1999]. On the other had, given any
$d(\cdot,\cdot)$ that is additive as defined in [Erdős et al., 1999]
(satisfies Equation (14)), let edge weights $w_{uv}=d(u,v)$ for all edges
$(u,v)\in E$, and define distance $d_{w}(\cdot,\cdot)$ using $\\{w_{uv}\\}$,
then $d_{w}(p,q)=d(p,q)$ for any pair of nodes $p,q\in V$.

####  F.1.4 Proof of Proposition 3.2

The proof of Proposition 3.2 requires the following two lemmas.

######  Lemma F.2.

Consider a tree ${\mathbb{T}}=(V,E)$ with $n$ leaf nodes and a set of non-
negative edge weights $\\{w_{uv}\geq 0\\}$ (we allow $w_{uv}=0$ in this
lemma), define $\Sigma^{\ell}\in{\mathbb{R}}^{n\times n}$ as

$\Sigma^{\ell}_{ij}=\exp(-d(i,j)),$

for any pair of leaf nodes $i,j\in V_{\ell}$. Then $\Sigma^{\ell}$ is positive
semidefinite.

######  Lemma F.3.

A multivariate Gaussian distribution $N(0,\Sigma)$ is local Markov131313The
definition of local Markov can be found in Appendix F.1.5 on tree
${\mathbb{T}}=(V,E)$ if the correlations between any pair of nodes $p,q\in V$
are multiplicative:

$\rho_{pq}=\prod_{(u,v)\in E(p,q)}\rho_{uv},\quad\forall p,q\in V.$ (15)

To prove Proposition 3.2, consider an additive distance $d(\cdot,\cdot)$ on
${\mathbb{T}}=(V,E)$. Without loss of generality, assume $V=[N]$ and the set
of leaf nodes $V_{\ell}=[n]$. Define the matrix
$\Sigma\in{\mathbb{R}}^{N\times N}$ as

$\Sigma_{ij}=\exp(-d(i,j))$

for any pair of nodes $i,j\in V$. Construct a new tree
$\widetilde{\mathbb{T}}=\left(\widetilde{V},\widetilde{E}\right)$ by attaching
twigs with zero edge weight to all internal nodes in $V$, that is

$\widetilde{V}=V\cup\\{N+1,N+2,\cdots,2N-n\\},\
\widetilde{E}=E\cup\\{(n+i,N+i):i\in[N-n]\\}$
$\widetilde{w}_{u,v}=\begin{cases}w_{u,v}&\text{if $u,v\in[N]$}\\\
0&\text{otherwise}\end{cases}.$

Define the matrix $\widetilde{\Sigma}^{\ell}\in{\mathbb{R}}^{N\times N}$ as

$\widetilde{\Sigma}^{\ell}_{ij}=\exp\left(-\widetilde{d}(i,j)\right)$

for any pair of leaf nodes $i,j\in\widetilde{V}_{\ell}$, then
$\widetilde{\Sigma}^{\ell}=\Sigma$. By Lemma F.2, $\widetilde{\Sigma}^{\ell}$
is positive semidefinite, therefore $\Sigma$ is positive semidefinite.

Since $\Sigma$ is positive semidefinite, we can define a multivariate Gaussian
distribution $\mathcal{P}(\cdot)$ with mean zero and variance $\Sigma$. Then
by Lemma F.3, $\mathcal{P}(\cdot)$ is local Markov on ${\mathbb{T}}$.

What is left is to show that $\Sigma$ is invertible. This is because when
$\Sigma$ is invertible, the joint probability density function is continuous
and positive, thus the local Markov property implies the global Markov
property. Together with the fact that zero entry in the inverse covariance
matrix of a joint Gaussian distribution implies conditional independence, the
proof is completed.

The proof of $\Sigma$ being invertible is by contradiction. Since $\Sigma$ is
the covariance matrix of a Gaussian distribution, if $\Sigma$ is not full
rank, then there exists a random variable $X$ that can be represented as a
linear combination of others. Given the local Markov property, $X$ is
independent of all other nodes given its neighbor nodes. Therefore $X$ must be
a linear combination of its neighbor nodes. Denote the neighbors of $X$ as
$Z_{1},Z_{2},\cdots,Z_{m}$, then there exists $c=(c_{1},\cdots,c_{m})^{T}$
such that

$X=c_{1}Z_{1}+c_{2}Z_{2}\cdots+c_{m}Z_{m},$ (16)

Denote correlations $\rho_{X,Z_{i}}$ as $z_{i}$, then

$Cov(X,Z_{1},\cdots,Z_{m})=\begin{bmatrix}1&z_{1}&z_{2}&\cdots&z_{m}\\\
z_{1}&1&z_{1}z_{2}&\cdots&z_{1}z_{m}\\\
z_{2}&z_{1}z_{2}&1&\cdots&z_{2}z_{m}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
z_{m}&z_{1}z_{m}&z_{2}z_{m}&\cdots&1\end{bmatrix}=\begin{bmatrix}1&z^{T}\\\
z&\Gamma\\\ \end{bmatrix}$ (17)

where $z=(z_{1},\cdots,z_{m})^{T}$, $\Gamma=Cov(Z_{1},\cdots,Z_{m})$. Notice
that

$\Gamma={\underbrace{\textstyle\text{diag}(1-z_{1},\cdots,1-z_{m})}_{\displaystyle\mathclap{D}}}+zz^{T},$
(18)

where $\text{diag}(x)$ is a diagonal matrix with its $i$th diagonal elements
being $x_{i}$.

By the Sherman Morrison formula [Bartlett, 1951] and the decomposition in
Equation (18), $\Gamma$ is invertible and

$\Gamma^{-1}=D^{-1}-\frac{D^{-1}zz^{T}D^{-1}}{1+z^{T}D^{-1}z}.$ (19)

Other than this, Equation (16) and (17) implies

$\begin{cases}z=\Gamma c,\\\ 1=z^{T}c\end{cases}.$ (20)

By Equation (19) and (20),

$1=z^{T}\Gamma^{-1}z.$ (21)

It’s easy to calculate

$\left[\Gamma^{-1}\right]_{ij}=\begin{dcases}\frac{1}{1-z_{i}^{2}}-\left.z_{i}^{2}\middle/\left(\left(1-z_{i}^{2}\right)^{2}\left(1+\sum_{i=1}^{m}\frac{z_{i}^{2}}{1-z_{i}^{2}}\right)\right)\right.,&i=j\\\
-\left.z_{i}z_{j}\middle/\left(\left(1-z_{i}^{2}\right)\left(1-z_{j}^{2}\right)\left(1+\sum_{i=1}^{m}\frac{z_{i}^{2}}{1-z_{i}^{2}}\right)\right)\right.,&i\neq
j\\\ \end{dcases},$ (22)

let $C_{i}=\dfrac{z_{i}^{2}}{1-z_{i}^{2}}$, then the right side of Equation
(21) does not equal to its left side:

$\displaystyle z^{T}\Gamma^{-1}z$
$\displaystyle=\sum_{i=1}^{m}\left(C_{i}-\dfrac{C_{i}^{2}}{1+\sum_{\ell=1}^{m}C_{\ell}}\right)-2\sum_{i\neq
j}\dfrac{C_{i}C_{j}}{1+\sum_{\ell=1}^{m}C_{\ell}}$
$\displaystyle=\dfrac{1}{1+\sum_{\ell=1}^{m}C_{\ell}}\left(\left(1+\sum_{i=1}^{m}C_{i}\right)\sum_{i=1}^{m}C_{i}-\sum_{i=1}^{m}C_{i}^{2}-2\sum_{i\neq
j}C_{i}C_{j}\right)$
$\displaystyle=\dfrac{\sum_{\ell=1}^{m}C_{\ell}}{1+\sum_{\ell=1}^{m}C_{\ell}}\neq
1$

####  F.1.5 Proof of Lemma F.3

######  Definition 17.

A probability distribution $\mathcal{P}(\cdot)$ is local Markov with respect
to ${\mathbb{T}}$ if the conditional distribution of any node $X_{i}$ given
its neighbors is independent of the remaining nodes, i.e.
$X_{i}\perp\\!\\!\\!\perp X_{V/\\{i\cup nbd(i)\\}}|X_{nbd(i)}$.

Consider $X$ be any node in tree ${\mathbb{T}}$, let $Y$ be one of its non-
neighbor nodes, and let $Z_{0},Z_{1},\cdots,Z_{m}$ be the neighbor nodes of
$X$. By definition, the shortest path between $X$ and $Y$ must go through some
$Z_{i}$, w.l.o.g. assume the path between $X$ and $Y$ go through $Z_{0}$.
Denote $\rho_{X,Z_{0}}=x,\rho_{Y,Z_{0}}=y,\rho_{X,Z_{i}}=z_{i},i=1,\cdots,m$.

We first consider the case where $X,Y,Z_{0},\cdots,Z_{m}$ all have unit
variance, then

$Cov(Z_{0},Y,X,Z_{1},\cdots,Z_{m})=\begin{bmatrix}1&y&x&xz_{1}&\cdots&xz_{m}\\\
y&1&xy&xyz_{1}&\cdots&xyz_{m}\\\ x&xy&1&z_{1}&\cdots&z_{m}\\\
xz_{1}&xyz_{1}&z_{1}&1&\cdots&z_{1}z_{m}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
xz_{m}&xyz_{m}&z_{m}&z_{1}z_{m}&\cdots&1\end{bmatrix}$

.

Let $W_{1}=(Y,X,Z_{1},\cdots,Z_{m})$, $W_{2}=Z_{0}$, then

$\displaystyle\Sigma_{1|2}$
$\displaystyle=\Sigma_{11}-\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}$
$\displaystyle=\begin{bmatrix}1&xy&xyz_{1}&\cdots&xyz_{m}\\\
xy&1&z_{1}&\cdots&z_{m}\\\ xyz_{1}&z_{1}&1&\cdots&z_{1}z_{m}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
xyz_{m}&z_{m}&z_{1}z_{m}&\cdots&1\end{bmatrix}-\begin{bmatrix}y\\\ x\\\
xz_{1}\\\ \vdots\\\
xz_{m}\end{bmatrix}\begin{bmatrix}y&x&xz_{1}&\cdots&xz_{m}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}1-y^{2}&\mathbf{0}_{1\times m}\\\
\mathbf{0}_{m\times 1}&A_{m\times m}\end{bmatrix}(A\text{ is
}Cov(X,Z_{1},\cdots,Z_{m}|Z_{0}))$

Since $(Z_{0},Y,X,Z_{1},\cdots,Z_{m})$ follows multivariate normal
distribution, a zero covariance matrix implies independence, i.e.
$Y\perp\\!\\!\\!\perp X,Z_{1},\cdots,Z_{m}|Z_{0}$. By weak union rules of
conditional independence, this implies $Y\perp\\!\\!\\!\perp
X|Z_{0},Z_{1},\cdots,Z_{m}$.

Therefore, for any non-neighbor nodes $Y$, $Cov(Y,X|Z_{0},Z_{1},\cdots
Z_{m})=0$, denote all non-neighbor nodes as $Y_{1},\cdots,Y_{l}$, then
$Cov((Y_{1},\cdots,Y_{l}),X|Z_{0},Z_{1},\cdots Z_{m})=\mathbf{0}_{l\times 1}$.
Since all nodes follows multivariate normal distribution, this implies
$X_{i}\perp\\!\\!\\!\perp X_{V/\\{i\cup nbd(i)\\}}|X_{nbd(i)}$ for any nodes
$X_{i}$.

For variables $X,Y,Z_{0},\cdots,Z_{m}$ that don’t have unit variance, just
consider
$X^{*}=X/\sigma_{X},Y^{*}=Y/\sigma_{Y},Z_{0}^{*}=Z_{0}/\sigma_{Z_{0}},\cdots,Z_{m}^{*}=Z_{m}/\sigma_{Z_{m}}$,
the conditional independence between $X^{*}$ and $Y^{*}$ given
$Z_{0}^{*},\cdots,Z_{m}^{*}$ implies the conditional independence between $X$
and $Y$ given $Z_{0},\cdots,Z_{m}$.

####  F.1.6 Proof of Lemma F.2

For notation simplicity, we drop the superscript $\ell$ on $\Sigma^{\ell}$ and
use $\Sigma$ to represent the matrix defined for all leaf nodes. The proof is
established through induction on the number of internal nodes.

##### Lemma F.2 is true if ${\mathbb{T}}$ is a star shaped tree.

For any star-shaped tree with $n$ leaf nodes $1,\cdots,n$, and one internal
nodes $n+1$, let $\theta_{i}=\exp(-d(i,n+1))$ for any leaf nodes $i\in[n]$,
then

$\Sigma=\begin{bmatrix}1&\theta_{1}\theta_{2}&\cdots&\theta_{1}\theta_{n}\\\
\theta_{1}\theta_{2}&1&\cdots&\theta_{2}\theta_{n}\\\
\vdots&\vdots&\ddots&\vdots\\\
\theta_{1}\theta_{n}&\theta_{2}\theta_{n}&\cdots&1\end{bmatrix}=\theta\theta^{T}+D,$

where $\theta=(\theta_{1},\theta_{2},\cdots,\theta_{n})$ and $D$ is a diagonal
matrix with $D_{ii}=1-\theta_{i}^{2}$. When $w_{uv}\geq 0$,
$\theta_{i}\in(0,1]$ for any $i\in[n]$. It’s easy to verify that both
$\theta\theta^{T}$ and $D$ is semi-positive definite and thus $\Sigma$ is also
semi-positive definite.

##### If Lemma F.2 is true for $m\geq 1$ internal nodes, it is also true for
$m+1$ internal nodes.

For any tree with $n$ leaf nodes and $m+1$ internal nodes, there exists two
internal nodes $p$ and $q$ that are neighbors. Delete edge $(p,q)$ splits tree
${\mathbb{T}}$ into two components, w.l.o.g., we assume

$\Sigma=\begin{bmatrix}\Sigma_{11}&\Sigma_{12}\\\
\Sigma_{12}^{T}&\Sigma_{22}\end{bmatrix},$ (23)

where $\Sigma_{11}$ and $\Sigma_{22}$ are the sub-matrices corresponding to
leaf nodes in the first component and the second component, respectively. Now
construct a new tree
$\widetilde{\mathbb{T}}=\left(\widetilde{V},\widetilde{E}\right)$ with edge
weights $\widetilde{w}$ and $\widetilde{\Sigma}$ by shrinking edge $(p,q)$ to
zero and deleting node $p$. That is,

$\widetilde{V}=V\setminus\\{p\\},\
\widetilde{E}=E\mathbin{\big{\backslash}}{\underbrace{\\{(p,z):\forall z\text{
such that }(p,z)\in
E\\}}_{\displaystyle\mathclap{E_{p}}}}\bigcup{\underbrace{\\{(q,z):\forall
z\neq q\text{ such that }(p,z)\in E\\}}_{\displaystyle\mathclap{E_{q}}}}$

For any edge $(q,z)$ in the newly added edge set $E_{q}$, let
$\widetilde{w}_{qz}=w_{pz}$; for all edges $(u,v)\in\widetilde{E}$ that are
originally presented in $E$, let $\widetilde{w}_{uv}=w_{uv}$.

Then $\widetilde{\Sigma}$ has a relationship to $\Sigma$:

$\widetilde{\Sigma}=\begin{bmatrix}\widetilde{\Sigma}_{11}&\widetilde{\Sigma}_{12}\\\
\widetilde{\Sigma}_{12}^{T}&\widetilde{\Sigma}_{22}\end{bmatrix}=\begin{bmatrix}\Sigma_{11}&\left.\Sigma_{12}\middle/\theta_{pq}\right.\\\
\left.\Sigma_{12}^{T}\middle/\theta_{pq}\right.&\Sigma_{22}\end{bmatrix},$

where $\theta_{pq}=\exp(-w_{pq})\in(0,1]$. This implies that

$\Sigma=\theta_{pq}\widetilde{\Sigma}+\begin{bmatrix}(1-\theta_{pq})\widetilde{\Sigma}_{11}&0\\\
0&(1-\theta_{pq})\widetilde{\Sigma}_{22}\end{bmatrix}.$

Notice that $\widetilde{\mathbb{T}}$ is a tree with $m$ internal nodes,
therefore $\widetilde{\Sigma}$ is positive semidefinite. As principal
submatrices of $\widetilde{\Sigma}$, $\widetilde{\Sigma}_{11}$ and
$\widetilde{\Sigma}_{22}$ are also positive semidefinite. This suggests that
$\Sigma$ is the summation of two positive semidefinite matrices and thus is
positive semidefinite.

###  F.2 ${\mathbb{T}}_{r}$-Overlapping Blockmodel: Proof of Theorem 3.4 and
Theorem 3.5

For any two nodes $i,j\in{\mathbb{T}}_{r}$, define the nearest common ancestor
of $i$ and $j$, $i\wedge j$, as the node in $V(i,j)$ that is closest to the
root $r$.

####  F.2.1 Proof of Theorem 3.4

Consider any ${\mathbb{T}}$-Stochastic Graph and a rooted tree
${\mathbb{T}}_{r}$ with $r$ being any internal node in $V$. We want to
construct a ${\mathbb{T}}_{r}$-Overlapping Blockmodel that is equivalent.

In order to achieve this, we define $\theta_{i}$ for any node $i\in V$,
excluding the root node, as $\theta_{i}=\exp(-d(i,r))$. For the root node $r$,
we set $\theta_{r}=1$. These $\theta_{i}$ values will be used in our
construction of the ${\mathbb{T}}_{r}$-Overlapping Blockmodel.

Specifically, we use the $\theta_{i}$ values for leaf nodes as the degree
corrected parameter, while the $\theta_{i}$ values for internal nodes are used
to define the connectivity matrix $B$. In particular, let $B$ be a diagonal
matrix with

$B_{uu}=\begin{dcases}\frac{1}{\theta_{u}^{2}}-\frac{1}{\theta_{p(u)}^{2}}&u\neq
r\\\ 1&u=r\end{dcases}$ (24)

for any internal node $u\neq r$ and let $B_{rr}=1$. We can verify that
$B_{uu}>0$ since

$\frac{\theta_{u}}{\theta_{p}(u)}=\exp\left(-d(u,r)+d(p(u),r)\right)=\exp\left(-w_{u,p(u)}\right)<1$

Then the following inequalities complete the proof

$\displaystyle\lambda_{ij}^{OB}$
$\displaystyle=\theta_{i}\theta_{j}Z_{i}^{T}BZ_{j}$ (25)
$\displaystyle=\theta_{i}\theta_{j}\sum_{\scaleto{u\,\in\,V(r,i\wedge
j)}{9.5pt}}B_{uu}$
$\displaystyle=\theta_{i}\theta_{j}\left(1+\sum_{\scaleto{u\,\in\,V(r,i\wedge
j)\setminus\\{r\\}}{9.5pt}}\left(\frac{1}{\theta_{u}^{2}}-\frac{1}{\theta_{p(u)}^{2}}\right)\right)$
$\displaystyle=\frac{\theta_{i}\theta_{j}}{\theta_{i\wedge
j}^{2}}=\exp(-d(i,j))=\lambda^{TSG}_{ij}$

####  F.2.2 Proof of Theorem 3.5

Given any ${\mathbb{T}}_{r}$-Overlapping Blockmodel with diagonal $B$ and node
specific parameter $\theta_{i}$, construct $\theta_{u}$ for every internal
node $u$ through the following procedure:

  1. 1.

set $\theta_{r}=1$ for root $r$,

  2. 2.

for any internal node $u$ with $\theta_{p(u)}$ defined, let
$\theta_{u}=\left.1\middle/\sqrt{(B_{uu}+1/\theta^{2}_{p(u)})}\right.$,

  3. 3.

repeat step 2 until $\theta_{u}$ is defined for all internal node $u$.

Then $\theta_{u}$ satisfy Equation (24).

Now we construct a ${\mathbb{T}}$-Stochastic Graph by defining edge weight
$w_{uv}$. For any pair of neighbor nodes $(u,v)\in V$, one of them must be the
parent of the other in ${\mathbb{T}}_{r}$, without loss of generality, assume
$u=p(v)$ and construct edge weight $w_{uv}$ as

$w_{uv}=-\log(\theta_{u})+\log\left(\theta_{p(u)}\right).$

Since $\theta_{u}$ satisfy Equation (24) and $B_{uu}\in{\mathbb{R}}^{+}$,
$w_{uv}$ is positive if $u$ and $v$ are all internal nodes. The proof is
completed using the same equalities (Equation (25)) as in the pervious
section.

###  F.3 Stochastic Processes that generate graphs with equivalent
distributions

Lemma F.4 [Rohe et al., 2018] is useful to prove equivalence between
${\mathbb{T}}$-Stochastic Graphs and edge generators. With Lemma F.4, the
equivalence proof only need to show that the probability of sampling edge
$(i,j)$ is proportional to $\lambda^{TSG}_{ij}$.

Specifically, for any random graph $A$ such that
$A_{ij}\overset{i.d.}{\sim}\text{Poisson}(\lambda_{ij})$, if an edge generator
$\mathcal{P}(\cdot)$ samples edge $(i,j)$ with probability proportional to
$\lambda_{ij}$, then Algorithm 1 with sparsity parameter $\zeta=\sum_{i\neq
j}\lambda_{ij}$ and edge generator $\mathcal{P}(\cdot)$ generates graphs with
the same distribution as $A$.

On the other direction, given a sparsity parameter $\zeta$ and an edge
generator $\mathcal{P}(\cdot)$ such that the probability $\mathcal{P}(\cdot)$
samples $(i,j)$ is proportional to $\lambda^{TSG}_{ij}$ for some
${\mathbb{T}}$-Stochastic Graph. Define another random graph $A$ with

$\lambda_{ij}=c\lambda^{TSG}_{ij},$

where

$c=\frac{\zeta}{\sum_{i\neq j}\lambda^{TSG}_{ij}}.$

Then $A$ is also a ${\mathbb{T}}$-Stochastic Graph by Theorem G.1 (consider
$w^{1}$ being the edge weight in the original ${\mathbb{T}}$-Stochastic Graph,
and construct $w^{2}$ with $\delta_{i}\equiv-\log\left(\sqrt{c}\right)$).
Further, $\lambda_{ij}$ in this new graph $A$ satisfies $\zeta=\sum_{i\neq
j}\lambda_{ij}$.

######  Lemma F.4.

(Lemma 1 in [Rohe et al., 2018]) Let $A\in{\mathbb{R}}^{n\times n}$ be a
random graph with $A_{ij}\overset{i.d.}{\sim}\text{Poisson}(\lambda_{ij})$ for
any $i\neq j$. Then conditioned on $\sum_{i\neq j}A_{ij}=m$,

$(A_{12},A_{13},\cdots,A_{n-1,n})\sim\text{Multinomial}\left(m,\
\lambda\middle/\sum_{i\neq j}\lambda_{ij}\right),$

where $\lambda=(\lambda_{12},\lambda_{13},\cdots,\lambda_{n-1,n})$.

####  F.3.1 ${\mathbb{T}}_{r}$-Top Down Stochastic Process: Definitions

######  Definition 18.

The ${\mathbb{T}}_{r}$-Top Down Stochastic Process is a Markov process $X_{t}$
such that

  1. 1.

the state space consists of all the internal nodes in ${\mathbb{T}}_{r}$ plus
an absorbing state $S$,

  2. 2.

it always starts from the root, i.e., $X_{0}=r$,

  3. 3.

it only goes to the absorbing state or a child node, i.e., $X_{t+1}\in\
S\cup\mathcal{C}(X_{t})$.

######  Definition 19.

The ${\mathbb{T}}_{r}$-Top Down Generator is parameterized by a
${\mathbb{T}}_{r}$-Top Down Stochastic Process and a set of degree parameters
$\theta_{i}\in{\mathbb{R}}^{+}$ for each leaf node $i$. Specifically, it
generates random edge $(I,J)$ with probability

$\displaystyle{\mathbb{P}}\left(I=i,J=j\mid
X_{\tau-1}\right)\propto\theta_{i}\theta_{j}\mathds{1}\left\\{i,j\in\text{desc}(X_{\tau-1})\right\\},\
\forall i\neq j\in V_{\ell}$ (26)

####  F.3.2 ${\mathbb{T}}_{r}$-Top Down Stochastic Process: Proof of Theorem
3.6

Theorem 3.6 is a direct result of Lemma F.4, Lemma F.5, Lemma F.6, and the
equivalence between ${\mathbb{T}}_{r}$-Overlapping Blockmodels and
${\mathbb{T}}$-Stochastic Graphs (Theorem 3.4 and Theorem 3.5). Specifically,
we introduce a Bridge Generator (Definition 20) to connect the
${\mathbb{T}}_{r}$-Top Down Generator and the ${\mathbb{T}}_{r}$-Graphical
Overlapping Blockmodel.

The proof of Lemma F.5 and F.6 can be found in Appendix F.3.3 and F.3.4.

######  Definition 20.

The ${\mathbb{T}}_{r}$-Bridge Generator is parameterized by a random variable
$X$ that takes values in all internal nodes in ${\mathbb{T}}_{r}$ and a set of
degree parameters $\theta_{i}\in{\mathbb{R}}^{+}$ for each leaf node $i$.
Specifically, it generates random edge $(I,J)$ with probability

$\displaystyle{\mathbb{P}}\left(I=i,J=j\mid
X\right)\propto\theta_{i}\theta_{j}\mathds{1}\left\\{i,j\in\text{desc}(X)\right\\},\
\forall i\neq j\in V_{\ell}$ (27)

######  Lemma F.5.

Any ${\mathbb{T}}_{r}$-Bridge Generator has an equivalent
${\mathbb{T}}_{r}$-Top Down Generator, and vice versa. Two edge generators are
equivalent if they sample edges with the same probability distribution.

######  Lemma F.6.

Any ${\mathbb{T}}_{r}$-Bridge Generator has an equivalent
${\mathbb{T}}_{r}$-Overlapping Blockmodel with diagonal $B$ matrix in the
sense that

${\mathbb{P}}((I,J)=(i,j))\propto\lambda^{OB}_{ij},$

and vice versa.

####  F.3.3 Proof of Lemma F.5

Given any ${\mathbb{T}}_{r}$-Top Down Generator with Markov process $X_{t}$
and parameters $\theta_{i}$, define a Bridge Generator with the same set of
$\theta_{i}$ and random variable $X$ such that

${\mathbb{P}}(X=m)={\mathbb{P}}(X_{\tau-1}=m)$ (28)

for any internal nodes $m$. Then $X_{\tau-1}$ and $X$ has the same
distribution and these two generators are equivalent.

Now consider any ${\mathbb{T}}_{r}$-Bridge Generator with random variable $X$
and parameters $\theta_{i}$. Define a ${\mathbb{T}}_{r}$-Top Down Generator
with the same set of $\theta_{i}$ and a Markov process $X_{t}$ such that

${\mathbb{P}}(X_{t+1}=h\mid
X_{t}=g)=\begin{dcases}\frac{{\mathbb{P}}(X=h)}{\mathscr{S}(h)}&h\text{ is the
absorbing state $S$}\\\ \frac{\mathscr{S}(g)}{\mathscr{S}(h)}&h\text{ is an
internal node}\end{dcases},$ (29)

where

$\mathscr{S}(h)=\sum_{\displaystyle
m\in\,\\{h\\}\cup\text{desc}(h)}{\mathbb{P}}(X=m).$

Consider any internal node $m$ at level $k$ of the tree, denote nodes on the
path from root node $r$ to $m$ as $u_{0},u_{1},u_{2},\cdots,u_{k}$, where
$u_{0}=r$ and $u_{k}=m$. For notation simplicity, define

${\mathbb{P}}(g\rightarrow h)\coloneqq{\mathbb{P}}(X_{t+1}=h\mid X_{t}=g),$

then the following equalities shows that $X_{\tau-1}$ and $X$ has the same
distribution.

$\displaystyle{\mathbb{P}}(X_{\tau-1}=u_{k})$
$\displaystyle={\mathbb{P}}(u_{k}\rightarrow
S)\prod_{i=0}^{k}{\mathbb{P}}(u_{i}\rightarrow u_{i+1})$
$\displaystyle=\frac{{\mathbb{P}}(X=u_{k})}{\mathscr{S}(u_{k})}\prod_{i=0}^{k}p(u_{i}\rightarrow
u_{i+1})$ $\displaystyle=\frac{{\mathbb{P}}(X=u_{k})}{\mathscr{S}(u_{k})}\
{\mathbb{P}}(u_{k-1},u_{k})\prod_{i=1}^{k-1}{\mathbb{P}}(u_{i}\rightarrow
u_{i+1})$
$\displaystyle=\frac{{\mathbb{P}}(X=u_{k})}{\mathscr{S}(u_{k})}\frac{\mathscr{S}(u_{k})}{\mathscr{S}(u_{k-1})}\prod_{i=0}^{k-1}{\mathbb{P}}(u_{i}\rightarrow
u_{i+1})$
$\displaystyle=\frac{{\mathbb{P}}(X=u_{k})}{\mathscr{S}(u_{k-1})}\prod_{i=0}^{k-1}{\mathbb{P}}(u_{i}\rightarrow
u_{i+1})$ $\displaystyle=\frac{{\mathbb{P}}(X=u_{k})}{\mathscr{S}(u_{0})}$
$\displaystyle={\mathbb{P}}(X=u_{k})$

####  F.3.4 Proof of Lemma F.6

Given a ${\mathbb{T}}_{r}$-Overlapping Blockmodel with
$\lambda_{ij}^{OB}=\theta_{i}\theta_{j}Z_{i}^{T}BZ_{j}$, where
$Z_{i}\in\\{0,1\\}^{K}$ is defined as
$Z_{iu}=\mathds{1}\\{i\in\text{desc}(u)\\}\\}$ and $B\in{\mathbb{R}}^{K\times
K}$ is a diagonal matrix. Denote $\vartheta(u)$ as the summation of
$\theta_{i}\theta_{j}$ for all leaf node descedent of $u$, i.e.,

$\vartheta(u)=\sum_{\scaleto{i\neq j\text{ and }i,j\in\text{desc}(u)\cap
V_{\ell}}{9.5pt}}\theta_{i}\theta_{j}.$

Define a ${\mathbb{T}}_{r}$-Bridge Generator with the same set of $\theta_{i}$
and random variable $X$ such that

${\mathbb{P}}(X=u)\propto B_{uu}\,\vartheta(u).$

Then the probability that this ${\mathbb{T}}_{r}$-Bridge Generator selects
leaf nodes $i$, $j$ is proportional to $\lambda_{ij}^{OB}$

$\displaystyle{\mathbb{P}}(I=i,J=j)$
$\displaystyle=\sum_{\scaleto{u\,\in\,V(r,i\wedge
j)}{9.5pt}}{\mathbb{P}}(X=u)\frac{\theta_{i}\theta_{j}}{\vartheta(u)}$ (30)
$\displaystyle\propto\sum_{\scaleto{u\,\in\,V(r,i\wedge
j)}{9.5pt}}B_{uu}\theta_{i}\theta_{j}$
$\displaystyle=\theta_{i}\theta_{j}\sum_{\scaleto{u\,\in\,V(r,i\wedge
j)}{9.5pt}}B_{uu}$ $\displaystyle=\theta_{i}\theta_{j}Z_{i}^{T}BZ_{j}$
$\displaystyle=\lambda_{ij}^{OB}$

Similarly, given any ${\mathbb{T}}_{r}$-Bridge Generator with a set of
$\theta_{i}$ and a random variable $X$, one can define a
${\mathbb{T}}_{r}$-overlapping Blockmodel with the same set of $\theta_{i}$
and

$B_{uu}={\mathbb{P}}(X=u)/\vartheta(u).$

Then by the above equalities (Equation (30)), $\lambda_{ij}^{OB}$ of this
${\mathbb{T}}_{r}$-Overlapping Blockmodel is proportional to the probability
that the ${\mathbb{T}}_{r}$-Bridge Generator selects leaf nodes $i$, $j$.

####  F.3.5 ${\mathbb{T}}$-Bottom Up Stochastic Process: Definitions

######  Definition 21.

The ${\mathbb{T}}$-Bottom Up Stochastic Process is a Markov process $X_{t}$
such that

  1. 1.

the state space consists of all the directed edges in ${\mathbb{T}}_{dir}$,

  2. 2.

each leaf node $i$ is assigned with a probability $\pi_{i}$ s.t. $\sum_{i\in
V_{\ell}}\pi=1$ and

${\mathbb{P}}(\,X_{0}=\langle i,p(i)\rangle\,)=\pi_{i},$ (31)

  3. 3.

any edge that ends at a leaf node is an absorbing state,

  4. 4.

there exists a set of constants $\\{c_{uv}:(u,v)\in E\\}$ with $c_{uv}=c_{vu}$
such that for any non-absorbing state $\langle r,s\rangle$,

${\mathbb{P}}(X_{t+1}=\langle u,v\rangle\mid X_{t}=\langle r,s\rangle)\propto
c_{uv}\mathds{1}\\{s=u,v\neq r\\}.$ (32)

Notice that $c_{uv}=c_{vu}$ here.

######  Definition 22.

The ${\mathbb{T}}$-Bottom Up Generator is fully parameterized by a
${\mathbb{T}}$-Bottom Up Stochastic Process. It generates edge $(I,J)$ with
probability

${\mathbb{P}}(I=i,J=j)={\mathbb{P}}(X_{0}=\langle
i,p(i)\rangle,X_{\tau}=\langle p(j),j\rangle)$

To simplify notations, the following notation is used in all subsequent
sections about ${\mathbb{T}}$-Bottom Up Stochastic Process (Appendix F.3.6,
F.3.8, F.3.7, and F.3.9). Consider any two nodes $s$, $t$ connected by the
path $(u_{0}=s,u_{1},u_{2},\cdots,u_{k}=t)$, and another node $w$ that is a
neighbor of node $s$. Given that the current state $X_{t}=\langle w,s\rangle$,
the random walk can only reach $\langle u_{k-1},u_{k}=t\rangle$ after exactly
$k$ steps. For notation simplicity, we define

${\mathbb{P}}(s\rightarrow t\mid w)\coloneqq{\mathbb{P}}\left(X_{t+k}=\langle
u_{k-1},v\rangle\mid X_{t}=\langle w,u\rangle\right),$ (33)

where $k$ is the number of edges in $E(s,t)$. Notice that when $w=u_{1}$,
${\mathbb{P}}(s\rightarrow t\mid w)=0$ since the random walk is non-
backtracking; when $k=0$, that is, $s=t$, ${\mathbb{P}}(s\rightarrow t\mid
w)=1$. For any leaf node $i\in V_{\ell}$, we employ a further simplification

${\mathbb{P}}(i\rightarrow u)\coloneqq{\mathbb{P}}(p(i)\rightarrow u\mid i).$
(34)

####  F.3.6 ${\mathbb{T}}$-Bottom Up Stochastic Process: Proof of Theorem 3.7

Consider a ${\mathbb{T}}$-Stochastic Graph with additive distance
$d(\cdot,\cdot)$, this proof constructs an equivalent ${\mathbb{T}}$-Bottom up
process by defining a set of $\\{c_{uv}:(u,v)\in E\\}$ and $\\{\pi_{i}:i\in
V_{\ell}\\}$. We employ the notation ${\mathbb{P}}(i\rightarrow u)$ defined in
Appendix F.3.5 (Equation (34)).

The proof proceeds by first defining a set of $\\{\widetilde{c}_{uv}:(u,v)\in
E\\}$ where $\widetilde{c}_{uv}$ does not necessarily equals to
$\widetilde{c}_{vu}$, but satisfy Equation (38) (the existence is by Lemma
F.7). Then define $\\{c_{uv}:(u,v)\in E\\}$ using algorithm 4. By Equation
(39), $\\{c_{uv}\\}$ adjust $\\{\widetilde{c}_{uv}\\}$ to be symmetric, that
is, $c_{uv}=c_{vu}$, without altering the local ratio, that is, consider any
node $u$, $c_{uw}\propto\widetilde{c}_{uw}$ for all of its neighbor $w$.
Therefore, $\\{c_{uv}\\}$ defines a ${\mathbb{T}}$-Bottom Up Stochastic
Process that satisfy Equation (38).

With this ${\mathbb{T}}$-Bottom Up Stochastic Process, we can construct a
${\mathbb{T}}$-Bottom Up Generator by defining $\\{\pi_{i},i\in V_{\ell}\\}$
as

$\pi_{i}=\dfrac{\mathscr{C}(i)}{\sum_{k=1}^{n}\mathscr{C}(k)}\,,$ (35)

where $\mathscr{C}(i)$ is the summation of $\lambda_{ij}$ for all other $j\neq
i$:

$\mathscr{C}(i)=\sum_{\\{j:j\neq i\\}}\lambda_{ij}.$

Then the ${\mathbb{T}}$-Bottom Up Generator is symmetric as

$\displaystyle\frac{\pi_{i}{\mathbb{P}}(i\rightarrow
j)}{\pi_{j}{\mathbb{P}}(j\rightarrow i)}$
$\displaystyle=\left.\left(\pi_{i}\frac{\lambda_{ij}}{\mathscr{C}(i)}\right)\middle/\left(\pi_{j}\frac{\lambda_{ji}}{\mathscr{C}(j)}\right)\right.\text{
(by Equation \eqref{eq:prop_bu})}$ (36)
$\displaystyle=\left.\left(\frac{\pi_{i}}{\mathscr{C}(i)}\right)\middle/\left(\frac{\pi_{j}}{\mathscr{C}(j)}\right)\right.\text{
(since $\lambda_{ij}=\lambda_{ji}$)}$ $\displaystyle=1\text{ (by Equation
\eqref{eq:define_pi_bu})}.$

We can verify that the probability of choosing edge $(i,j)$ is proportional to
$\lambda_{ij}$ as

$\displaystyle{\mathbb{P}}((I,J)=(i,j))$
$\displaystyle=\pi_{i}{\mathbb{P}}(i\rightarrow
j)+\pi_{j}{\mathbb{P}}(j\rightarrow i)$ (37)
$\displaystyle=2\,\pi_{i}\,{\mathbb{P}}(i\rightarrow j)$
$\displaystyle=2\,\dfrac{\mathscr{C}(i)}{\sum_{k=1}^{n}\mathscr{C}(k)}\,\frac{\lambda_{ij}}{\mathscr{C}(i)}$
$\displaystyle=2\,\dfrac{\lambda_{ij}}{\sum_{k=1}^{n}\mathscr{C}(k)}$
$\displaystyle=\dfrac{\lambda_{ij}}{\sum_{i\neq j}\lambda_{ij}}\,.$

######  Lemma F.7.

For any ${\mathbb{T}}$-Stochastic Graph, there exists a ${\mathbb{T}}$-Bottom
Up Stochastic Process $X_{t}$ with a set of constants
$\left\\{\widetilde{c}_{uv}:(u,v)\in E\right\\}$ where
$\widetilde{c}_{uv}=\widetilde{c}_{vu}$ not necessarily hold, such that for
any leaf node $i$,

${\mathbb{P}}(i\rightarrow j)\propto\lambda_{ij},$ (38)

where $j\neq i$ is another leaf node in ${\mathbb{T}}$.

Input: $\\{\widetilde{c}_{uv}:(u,v)\in E\\}$ with no guarantee for
$c_{uv}=c_{vu}$

Output: $\\{c_{uv}:(u,v)\in E\\}$ with $c_{uv}=c_{vu}$

1 choose any internal node $r$ as the root, and consider the rooted tree
${\mathbb{T}}_{r}$, denote the level of ${\mathbb{T}}_{r}$ as $L$, denote
$\mathscr{L}^{(i)}$, $i\in[L]$, as the set of level $i$ nodes in
${\mathbb{T}}_{r}$;

2 set $c_{ru}=\widetilde{c}_{ru}$ for all $u\in\mathscr{L}^{(1)}$;

3 for  _$i\leftarrow 1$ to $L$_ do

4 for  _$u\in\mathscr{L}^{(i)}$_ do

5 set $c_{uw}$ for any node $w$ that is a neighbor of $u$ as
$\scaleto{c_{uw}=\frac{c_{p(u),u}\,\widetilde{c}_{uw}}{\widetilde{c}_{u,p(u)}}}{30pt}$
(39)

6

Algorithm 4 Symmetrize edge constant $c_{uv}$

####  F.3.7 Proof of Lemma F.7

We use the notation $\theta_{uv}$ to denote $\exp(-d(u,v))$ for any two nodes
$u,v\in V$, notice that $\theta_{ij}=\lambda_{ij}$ for any two leaf nodes
$i,j\in V_{\ell}$. We also employ the notations ${\mathbb{P}}(s\rightarrow
t\mid w)$ and ${\mathbb{P}}(i\rightarrow u)$ defined in Appendix F.3.5
(Equation (33) and (34)). This proof aims to construct a ${\mathbb{T}}$-Bottom
Up Stochastic Process with $\left\\{\widetilde{c}_{uv}:(u,v)\in E\right\\}$
that satisfy Equation (38). Importantly, there is no requirement for
$\widetilde{c}_{uv}=\widetilde{c}_{vu}$. Throughout the proof, the term
“${\mathbb{T}}$-Bottom Up Stochastic Process” refer to the Stochastic Process
in Definition 21 without the requirement for
$\widetilde{c}_{uv}=\widetilde{c}_{vu}$.

The key idea is to define $\widetilde{c}_{uv}$ sequentially, starting from
edges connected to leaf nodes. To do this, we introduce the following
definition of “half-tree”.

######  Definition 23.

For any two neighbor nodes $r$ and $w$ in tree ${\mathbb{T}}$, deleting edge
$(r,w)$ splits the tree into two subtrees. Root these subtrees at node $r$ and
$w$, and denote the rooted trees as ${\mathbb{T}}_{r/w}$ and
${\mathbb{T}}_{w/r}$. We call any tree created in this fashion a half-tree of
${\mathbb{T}}$. Some examples of half trees are displayed in Figure 26.

######  Definition 24.

We say a ${\mathbb{T}}$-Bottom Up Stochastic Process is properly defined on a
half-tree ${\mathbb{T}}_{r/w}$ if

${\mathbb{P}}(r\rightarrow i\mid w)\propto\theta_{ri}$ (40)

for any leaf node $i$ in ${\mathbb{T}}_{r/w}$

######  Definition 25.

We say a ${\mathbb{T}}$-Bottom Up Stochastic Process is level $k$ properly
defined if it is properly defined on all half-trees with level $\leq k$.

The proof proceeds by induction on the level of half trees. The level of a
tree is defined as the maximum level of all its nodes. For the definition of
the level of a particular node, please refer to Appendix B.1. The induction is
achieved by proving Lemma F.8 and Lemma F.9 below. By these two lemmas, a
${\mathbb{T}}$-Bottom Up Stochastic Process can be defined on tree
${\mathbb{T}}$ such that it is properly defined on all half trees. Lemma F.7
is an immediate result of this by noticing that

$\frac{\lambda_{ij}}{\lambda_{i\ell}}=\frac{\theta_{p(i),j}}{\theta_{p(i),\ell}}$

for any leaf nodes $i,j,\ell$, and that ${\mathbb{T}}_{p(i)/i}$ for any leaf
node $i$ is a half tree of ${\mathbb{T}}$.

######  Lemma F.8.

Any ${\mathbb{T}}$-Bottom Up Stochastic Process is level 0 half properly
defined.

###### Proof.

For any level 0 half tree ${\mathbb{T}}_{r,w}$, there is only one leaf node,
which is $r$, and ${\mathbb{P}}(r\rightarrow r\mid w)=1$. ∎

######  Lemma F.9.

If there exists a level $k$ properly defined ${\mathbb{T}}$-Bottom Up
Stochastic Process, then there exists a level $k+1$ properly defined
${\mathbb{T}}$-Bottom Up Stochastic Process.

###### Proof.

Given a level $k$ properly defined ${\mathbb{T}}$-Bottom Up Stochastic
Process, we construct a level $k+1$ properly defined ${\mathbb{T}}$-Bottom Up
Stochastic Process by redefining all $\widetilde{c}_{ru}$ for neighbor nodes
$(r,u)$ such that ${\mathbb{T}}_{u/r}$ is a level $k$ tree.

Specifically, for each ${\mathbb{T}}_{u/r}$ that is a level $k$ tree, select a
leaf node in ${\mathbb{T}}_{u/r}$ and denote it as $\ell(u/r)$, define

$\widetilde{c}_{ru}=\frac{\theta_{r,\
\ell(u/r)}}{{\mathbb{P}}(u\rightarrow\ell(u/r)\mid r)}.$

As this definition does not change $c_{uv}$ in any level $\leq k$ half trees,
the ${\mathbb{T}}$-Bottom Up Stochastic Process is still level $k$ properly
defined. We just need to show it is properly defined on all level $k+1$ half
trees.

Consider any two leaf nodes $i$ and $j$ that belong to a level $k+1$ half tree
${\mathbb{T}}_{r/w}$. If they also belongs to the same level $\leq k$ half
tree ${\mathbb{T}}_{p/q}$ that is a subtree of ${\mathbb{T}}_{r/w}$, then

$\displaystyle\frac{{\mathbb{P}}(r\rightarrow i\mid
w)}{{\mathbb{P}}(r\rightarrow j\mid w)}$
$\displaystyle=\frac{{\mathbb{P}}(r\rightarrow p\mid
w){\mathbb{P}}(p\rightarrow i\mid q)}{{\mathbb{P}}(r\rightarrow p\mid
w){\mathbb{P}}(p\rightarrow j\mid q)}$ (41)
$\displaystyle=\frac{{\mathbb{P}}(p\rightarrow i\mid
q)}{{\mathbb{P}}(p\rightarrow j\mid q)}=\frac{\theta_{pi}}{\theta_{pj}}\text{
(because the process is properly defined on ${\mathbb{T}}_{p/q}$)}$
$\displaystyle=\frac{\theta_{pi}\theta_{rp}}{\theta_{pj}\theta_{rp}}=\frac{\theta_{ri}}{\theta_{rj}}\,.$

If nodes $i$ and $j$ are not part of the same level $\leq k$ half tree, then
they must belong to two distinct level $k$ half trees, as shown in Figure 26.

Figure 26: Triangles are subtrees and circles are internal nodes. Node $i$,
$j$ are leaf nodes in subtree ${\mathbb{T}}_{s/r}$ and ${\mathbb{T}}_{t/r}$.
Nodes $a=\ell(r/s)$, $b=\ell(r/t)$ are leaf nodes that help defining
$\widetilde{c}_{rs}$ and $\widetilde{c}_{rt}$.

Specifically, we denote the subtrees containing nodes $i$ and $j$ as
${\mathbb{T}}_{s/r}$ and ${\mathbb{T}}_{t/r}$. We also use $a$ and $b$ to
denote the leaf nodes that help define $\widetilde{c}_{rs}$ and
$\widetilde{c}_{rt}$, that is, $a=\ell(s/r)$ and $b=\ell(t/r)$. Then we have

$\displaystyle\frac{{\mathbb{P}}(r\rightarrow i\mid
w)}{{\mathbb{P}}(r\rightarrow j\mid w)}$
$\displaystyle=\dfrac{{\mathbb{P}}(r\rightarrow s\mid
w)\,{\mathbb{P}}(s\rightarrow i\mid r)}{{\mathbb{P}}(r\rightarrow t\mid
w)\,{\mathbb{P}}(t\rightarrow j\mid r)}$
$\displaystyle=\dfrac{\widetilde{c}_{rs}\,{\mathbb{P}}(s\rightarrow i\mid
r)}{\widetilde{c}_{rt}\,{\mathbb{P}}(t\rightarrow j\mid r)}\text{ (transition
probabilities are proportional $\widetilde{c}_{uv}$ by definition)}$
$\displaystyle=\left.\left(\frac{\theta_{ra}}{{\mathbb{P}}(s\rightarrow a\mid
r)}\,{\mathbb{P}}(s\rightarrow i\mid
r)\right)\middle/\left(\frac{\theta_{rb}}{{\mathbb{P}}(t\rightarrow b\mid
r)}\,{\mathbb{P}}(t\rightarrow j\mid r)\right)\right.\text{ (plug in
$\widetilde{c}_{ru}$ and $\widetilde{c}_{rv}$)}$
$\displaystyle=\left.\left(\frac{\theta_{ra}\,\theta_{si}}{\theta_{sa}}\right)\middle/\left(\frac{\theta_{rb}\,\theta_{tj}}{\theta_{tb}}\right)\right.\text{
(the process is level $k$ properly defined)}$
$\displaystyle=\dfrac{\theta_{rs}\theta_{si}}{\theta_{rt}\theta_{tj}}=\frac{\theta_{ri}}{\theta_{rj}}\,.$
(42)

The proof is completed by combining Equation (41) and Equation (42), which
together demonstrate that Equation (40) is valid for all level $k+1$ half
trees.

∎

####  F.3.8 ${\mathbb{T}}$-Bottom Up Stochastic Process: Proof of Theorem 3.8

This section employs the notations ${\mathbb{P}}(s\rightarrow t\mid w)$ and
${\mathbb{P}}(i\rightarrow u)$ defined in Appendix F.3.5 (Equation (33) and
(34)).

We begin by demonstrating that $\\{\pi_{i}:i\in V_{\ell}\\}$ can be defined to
make the ${\mathbb{T}}$-Bottom Up Generator symmetric. Choose a leaf node $i$
and set $c_{i}=1$; for any other leaf node $j$, define $c_{j}$ as follows:

$c_{j}=\frac{c_{i}{\mathbb{P}}(i\rightarrow j)}{{\mathbb{P}}(j\rightarrow
i)}.$

Normalize $c_{i}$ to obtain $\pi_{i}$:

$\pi_{i}=\frac{c_{i}}{\sum_{k}c_{k}}.$

It is evident that the symmetric condition in Equation (5) holds for leaf node
$i$ and any other leaf node $j\neq i$:

$\frac{{\mathbb{P}}(X_{0}=\langle i,p(i)\rangle,X_{\tau}=\langle
p(j),j\rangle)}{{\mathbb{P}}(X_{0}=\langle j,p(j)\rangle,X_{\tau}=\langle
p(i),i\rangle)}=\frac{\pi_{i}{\mathbb{P}}(i\rightarrow
j)}{\pi_{j}{\mathbb{P}}(j\rightarrow i)}=1.$ (43)

To demonstrate that the symmetric condition also holds for two leaf nodes
$j,\ell$ that are distinct from node $i$, additional notations are introduced,
as shown in Figure 27.

Figure 27: Triangles are subtrees and circles are internal nodes. Node
$i,j,\ell$ are leaf nodes in the corresponding subtrees. Node $r$ is the
median node of leaf nodes $i,j,\ell$, and nodes $r_{i},r_{j},r_{\ell}$ are
neighbor nodes of $r$ that lie on the path between them.

Specifically, we denote the median node141414the definition of median node can
be found in Section 3.6, Definition 11 of $i,j$, and $\ell$ as $r$; we also
use $r_{i}$, $r_{j}$, and $r_{\ell}$ to denote neighbor nodes of $r$ that lie
on the paths $(r,i)$, $(r,j)$, and $(r,\ell)$, respectively. Then we have

$\displaystyle\frac{\pi_{j}}{\pi_{\ell}}$
$\displaystyle=\left.\frac{{\mathbb{P}}(i\rightarrow
j)}{{\mathbb{P}}(j\rightarrow
i)}\middle/\frac{{\mathbb{P}}(i\rightarrow\ell)}{{\mathbb{P}}(\ell\rightarrow
i)}\right.\ (\text{by the construction of $\pi_{j}$ above})$
$\displaystyle=\frac{{\mathbb{P}}(i\rightarrow
j)}{{\mathbb{P}}(i\rightarrow\ell)}\times\frac{{\mathbb{P}}(\ell\rightarrow
i)}{{\mathbb{P}}(j\rightarrow i)}$
$\displaystyle=\frac{{\mathbb{P}}(i\rightarrow r)\ {\mathbb{P}}(r\rightarrow
j\mid r_{i})}{{\mathbb{P}}(i\rightarrow r)\ {\mathbb{P}}(r\rightarrow\ell\mid
r_{i})}\times\frac{{\mathbb{P}}(\ell\rightarrow r)\ {\mathbb{P}}(r\rightarrow
i\mid r_{\ell})}{{\mathbb{P}}(j\rightarrow r)\ {\mathbb{P}}(r\rightarrow i\mid
r_{j})}$ $\displaystyle=\frac{{\mathbb{P}}(\ell\rightarrow r)\
{\mathbb{P}}(r\rightarrow j\mid r_{i})\ {\mathbb{P}}(r\rightarrow i\mid
r_{\ell})}{{\mathbb{P}}(j\rightarrow r)\ {\mathbb{P}}(r\rightarrow\ell\mid
r_{i})\ {\mathbb{P}}(r\rightarrow i\mid
r_{j})}\times\frac{{\mathbb{P}}(r\rightarrow j\mid r_{\ell})\
{\mathbb{P}}(r\rightarrow\ell\mid r_{j})}{{\mathbb{P}}(r\rightarrow j\mid
r_{\ell})\ {\mathbb{P}}(r\rightarrow\ell\mid r_{j})}$ (cancel out
${\mathbb{P}}(i\rightarrow r)$, rearrange the equation, and multiply by one)
$\displaystyle=\frac{{\mathbb{P}}(\ell\rightarrow r)\
{\mathbb{P}}(r\rightarrow j\mid r_{\ell})}{{\mathbb{P}}(j\rightarrow r)\
{\mathbb{P}}(r\rightarrow\ell\mid r_{j})}\times\frac{{\mathbb{P}}(r\rightarrow
j\mid r_{i})\ {\mathbb{P}}(r\rightarrow\ell\mid r_{j})\
{\mathbb{P}}(r\rightarrow i\mid r_{\ell})}{{\mathbb{P}}(r\rightarrow\ell\mid
r_{i})\ {\mathbb{P}}(r\rightarrow i\mid r_{j})\ {\mathbb{P}}(r\rightarrow
j\mid r_{\ell})}\text{ \, (rearrange)}$
$\displaystyle=\frac{{\mathbb{P}}(\ell\rightarrow r)\
{\mathbb{P}}(r\rightarrow j\mid r_{\ell})}{{\mathbb{P}}(j\rightarrow r)\
{\mathbb{P}}(r\rightarrow\ell\mid
r_{j})}\times\frac{c_{rj}c_{r\ell}c_{ri}}{c_{r\ell}c_{ri}c_{rj}}\text{ \,
(transition probabilities are proportional to $c_{uv}$)}$
$\displaystyle=\frac{{\mathbb{P}}(\ell\rightarrow
j)}{{\mathbb{P}}(j\rightarrow\ell)}\,.$ (44)

When considered together, Equation (43) and Equation (44) demonstrate that the
${\mathbb{T}}$-Bottom Up generator is symmetric. Our next task is to prove
that this generator produces graphs that are ${\mathbb{T}}$-HSE. Denote the
probability of sampling edge $(i,j)$ as $\lambda_{ij}^{BU}$, then

$\displaystyle\frac{\lambda^{BU}_{i\ell}}{\lambda^{BU}_{j\ell}}$
$\displaystyle=\frac{\pi_{i}{\mathbb{P}}(i\rightarrow\ell)+\pi_{\ell}{\mathbb{P}}(\ell\rightarrow
i)}{\pi_{j}{\mathbb{P}}(j\rightarrow\ell)+\pi_{\ell}{\mathbb{P}}(\ell\rightarrow
j)}$ $\displaystyle=\frac{2\pi_{\ell}{\mathbb{P}}(\ell\rightarrow
i)}{2\pi_{\ell}{\mathbb{P}}(\ell\rightarrow j)}$
$\displaystyle=\frac{{\mathbb{P}}(\ell\rightarrow
i)}{{\mathbb{P}}(\ell\rightarrow j)}$
$\displaystyle=\frac{{\mathbb{P}}(\ell\rightarrow r)\
{\mathbb{P}}(r\rightarrow i\mid r_{\ell})}{{\mathbb{P}}(\ell\rightarrow r)\
{\mathbb{P}}(r\rightarrow j\mid r_{\ell})}$
$\displaystyle=\frac{c_{ri}}{c_{rj}}.$

Since the last line, $c_{ri}/c_{rj}$, only depends on $\ell$ through the
median node $r$, thus the proof is completed by defining
$c_{ij}^{(r)}=c_{ri}/c_{rj}$.

####  F.3.9 ${\mathbb{T}}$-Bottom Up Stochastic Process: an equivalent
condition for negative edge weights

######  Theorem F.1.

(Equivalent condition for negative edge weights) Consider any internal edge
$(e,f)$ and neighbor nodes labeled as in Figure 28, then

$w_{ef}<0\Longleftrightarrow\frac{{\mathbb{P}}(X_{t+1}=\langle e,b\rangle\mid
X_{t}=\langle a,e\rangle)}{{\mathbb{P}}(X_{t+2}=\langle f,d\rangle\mid
X_{t}=\langle a,e\rangle)}<\frac{{\mathbb{P}}(X_{t+2}=\langle e,b\rangle\mid
X_{t}=\langle c,f\rangle)}{{\mathbb{P}}(X_{t+1}=\langle f,d\rangle\mid
X_{t}=\langle c,f\rangle)}$

Figure 28: An example of local structures for internal edge $(e,f)$. Triangles
are subtrees and circles are leaf nodes. Nodes $A,B,C,D$ are leaf nodes in the
corresponding subtrees.

###### Proof.

This proof utilize the notations ${\mathbb{P}}(s\rightarrow t\mid w)$ and
${\mathbb{P}}(i\rightarrow u)$ defined in Appendix F.3.5 (Equation (33) and
(34)). Consider the tree structure displayed in Figure 28, where nodes
$A,B,C,D$ represent leaf nodes from subtrees linked to nodes $a,b,c,d$,
respectively, then the proof is complete by the following equivalences:

$\frac{{\mathbb{P}}(e\rightarrow b\mid a)}{{\mathbb{P}}(e\rightarrow d\mid
a)}<\frac{{\mathbb{P}}(f\rightarrow b\mid c)}{{\mathbb{P}}(f\rightarrow d\mid
c)}$ $\big{\Updownarrow}$ $\frac{{\mathbb{P}}(A\rightarrow e)\
{\mathbb{P}}(e\rightarrow b\mid a)\ {\mathbb{P}}(b\rightarrow B\mid
e)}{{\mathbb{P}}(A\rightarrow e)\ {\mathbb{P}}(e\rightarrow d\mid a)\
{\mathbb{P}}(d\rightarrow D\mid e)}<\frac{{\mathbb{P}}(C\rightarrow f)\
{\mathbb{P}}(f\rightarrow b\mid c)\ {\mathbb{P}}(b\rightarrow B\mid
e)}{{\mathbb{P}}(C\rightarrow f)\ {\mathbb{P}}(f\rightarrow d\mid c)\
{\mathbb{P}}(d\rightarrow D\mid e)}$ $\big{\Updownarrow}$
$\frac{\lambda^{TSG}_{AB}}{\lambda^{TSG}_{AD}}<\frac{\lambda^{TSG}_{CB}}{\lambda^{TSG}_{CD}}$
$\big{\Updownarrow}$ $\exp\\{-d(A,B)+d(A,D)\\}<\exp\\{-d(C,B)+d(C,D)\\}$
$\big{\Updownarrow}$
$\exp\\{-d(A,e)-d(e,B)+d(A,e)+d(e,f)+d(f,D)\\}<\exp\\{-d(C,f)-d(f,e)-d(e,B)+d(C,f)+d(f,D)\\}$
$\big{\Updownarrow}$ $\exp(2d(e,f))<1$ $\big{\Updownarrow}$ $d(e,f)<0.$

∎

###  F.4 Hierarchical Stochastic Equivalence: Proof of Theorem 3.9 and Theorem
3.10

####  F.4.1 Proof of Theorem 3.9

Before proceeding to the formal proof, we first offer some insight of it.
Consider a graph $A$ with $\lambda_{ij}$ such that $A$ is ${\mathbb{T}}$-HSE.
The aim is to create positive values $\theta_{uv}$ on all edges $(u,v)$ in
${\mathbb{T}}$ such that $\lambda_{ij}$ is equal to the product of the
$\theta_{uv}$’s for all edges $(u,v)\in E(i,j)$. Then an equivalent
${\mathbb{T}}$-Stochastic Graph can be constructed by defining edge weights
$w_{uv}$ as $-\log(\theta_{uv})$.

We would construct $\theta$ values layer by layer, starting from leaf nodes.
Consider any two leaf nodes $i$ and $j$ that share the same parent node,
denoted as $r$. Then, for any other leaf node $\ell$, the median node of nodes
$i$, $j$, and $\ell$ is node $r$, as displayed in Figure 29. Given the
$\lambda$ values, we have two equations and two unknowns (which can be
solved):

$\begin{dcases}\lambda_{ij}=\theta_{ir}\theta_{rj},\\\\[5.0pt]
\dfrac{\lambda_{i\ell}}{\lambda_{j\ell}}=\frac{\theta_{ir}}{\theta_{rj}}.\end{dcases}$
(45)

Figure 29: The triangle represents a subtree. Nodes $i,j$ are leaf nodes; node
$r$ is the parent of $i,j$, that is, $r=p(i)=p(j)$; node $\ell$ is another
leaf node in the rest part of the tree.

Because the $\lambda_{ij}$ are positive, the $\theta$’s can be solved as
positive values too. After constructing these $\theta$’s for all leaf nodes,
we proceed to construct the $\theta$’s for the edges above their parents.
Iteratively, solving these equations constructs $\theta$ values that are
consistent with the $\lambda$’s and defines edge weights $w$ for an equivalent
${\mathbb{T}}$-Stochastic Graph.

The formal proof is carried out using induction on the tree level. To ensure
that “levels” are appropriately defined, Lemma F.10 and Lemma F.11 discuss
Theorem 3.10 under a rooted tree ${\mathbb{T}}_{r}$. It is noteworthy that
${\mathbb{T}}_{r}$-HSE and ${\mathbb{T}}$-HSE are equivalent for any root node
$r$, as the definition of HSE (Definition 12) does not involve the root node.
The level of a tree is defined as the maximum level of all its nodes. For the
definition of the level of a particular node, please refer to Appendix B.1.

######  Lemma F.10.

Theorem 3.9 holds if ${\mathbb{T}}_{r}$ is a level one tree.

###### Proof.

To begin with, it is important to observe that a level one tree is a star-
shaped tree consisting of a single internal node that also serves as the root
node $r$. Furthermore, for any triplet of leaf nodes $i,j,\ell$, it holds that
$m(i,j,\ell)=r$ and thus

$\lambda_{i,\ell}/\lambda_{j,\ell}=c^{(r)}_{ij}$ (46)

For notation simplification, we drop the superscript $(r)$ in $c^{(r)}_{ij}$
in the following proof (this is valid as all triplets of leaf nodes share the
same median node).

Pick any two leaf nodes $i,j$ and define

$\begin{dcases}\theta_{ir}=\sqrt{\lambda_{ij}c_{ij}},\\\\[5.0pt]
\theta_{jr}=\sqrt{\lambda_{ij}/c_{ij}}.\end{dcases}$ (47)

For any other leaf node $\ell$, define

$\theta_{\ell r}=\lambda_{i\ell}/\theta_{ir}$ (48)

Now we want to show that under this definition,
$\lambda^{HSE}_{pq}=\theta_{qr}\theta_{pr}$ for any two leaf nodes $p$ and
$q$. We prove this by discussing all possibilities of how $(p,q)$ involves
nodes $(i,j)$:

  1. 1.

$p=i,q=j$: plug in Equation (47) for $\theta_{ir}$ and $\theta_{jr}$,

$\theta_{ir}\theta_{jr}=\lambda_{ij}$

  2. 2.

$p=i,q\neq j$: plug in Equation (48) for $\theta_{qr}$,

$\theta_{ir}\theta_{qr}=\theta_{ir}\times\lambda_{iq}/\theta_{ir}=\lambda_{iq}$
(49)

  3. 3.

$p=j,q\neq i$: the second equality uses the result in Equation (49), the last
equality follows from the HSE property in Equation (46)

$\theta_{jr}\theta_{qr}=\frac{\theta_{jr}}{\theta_{ir}}\times\theta_{ir}\theta_{qr}=\frac{1}{c_{ij}}\times\lambda_{iq}=\lambda_{jq}$

  4. 4.

$p,q\neq i,j$:

$\displaystyle\theta_{pr}\theta_{qr}$
$\displaystyle=\frac{\lambda_{ip}\lambda_{iq}}{\theta_{ir}^{2}}\quad\text{(plug
in Equation \eqref{eq:hse_level1_2})}$
$\displaystyle=\frac{\lambda_{ip}}{\lambda_{pq}}\times\frac{\lambda_{iq}\lambda_{pq}}{\theta_{ir}^{2}}\quad\text{(multiply
both the numerator and the denominator by $\lambda_{pq}$)}$
$\displaystyle=\frac{\lambda_{ij}}{\lambda_{jq}}\times\frac{\lambda_{iq}\lambda_{pq}}{\theta_{ir}^{2}}\quad\text{(by
HSE property)}$
$\displaystyle=\frac{\lambda_{iq}}{\lambda_{jq}}\times\frac{\lambda_{ij}\lambda_{pq}}{\theta_{ir}^{2}}\quad\text{(rearrange)}$
$\displaystyle=\frac{c_{ij}\lambda_{ij}\lambda_{pq}}{\theta_{ir}^{2}}\quad\text{(by
HSE property)}$ $\displaystyle=\lambda_{pq}\quad\text{(by Equation
\eqref{eq:hse_level1_1})}$

∎

######  Lemma F.11.

If Theorem 3.9 holds when ${\mathbb{T}}_{r}$ is a level $k$ tree, then it also
holds when ${\mathbb{T}}_{r}$ is a level $k+1$ tree.

###### Proof.

Given a set of $\lambda_{ij}$ that is HSE on a $k+1$-level tree
${\mathbb{T}}_{r}$, denote the set of nodes at level $\ell$ as
$\mathscr{L}^{\ell}$. Notice that $\mathscr{L}^{k+1}$ only contains leaf
nodes, that is, $\mathscr{L}\subset V_{\ell}$. Deleting all nodes in
$\mathscr{L}^{k+1}$ creates a level $k$ tree, denote this tree as
${\mathbb{T}}^{k}_{r}$ and denote the set of leaf nodes of
${\mathbb{T}}^{k}_{r}$ as $V_{\ell}^{k}$. See Figure 30 for an example of
${\mathbb{T}}_{r}$.

Figure 30: An example of 3-level rooted tree ${\mathbb{T}}_{r}$

The proof can be summarized into three steps

  1. 1.

define $\theta_{i,p(i)}$ values for each level $k+1$ leaf node
$i\in\mathscr{L}^{k+1}$ (edges in the blud triangles in Figure 30),

  2. 2.

create a set of $\\{\lambda_{uv}^{k}:u,v\in V_{\ell}^{k}\\}$ values such that
$\lambda_{uv}^{k}$ is ${\mathbb{T}}_{r}^{k}$-HSE. Since ${\mathbb{T}}_{r}^{k}$
is a level $k$ tree, there exists a set of $\theta$’s for edges in
${\mathbb{T}}_{r}^{k}$ (edges in the red rectangle in Figure 30),

  3. 3.

show that $\theta_{uv}$ constructed in the first step and the second step
together defines a set of valid $\theta$’s for ${\mathbb{T}}_{r}$.

##### Define $\theta_{i,p(i)}$

: For each node $u\in V_{\ell}^{k}\setminus V_{\ell}$, there must exists at
least two level $k+1$ leaf nodes connected to it, denote them as $i$ and $j$.
Then the median node of $i,j$, and any other leaf nodes $\ell\in V_{\ell}$ is
node $u$. Define

$\begin{dcases}\theta_{iu}=\sqrt{\lambda_{ij}c^{(u)}_{ij}},\\\\[5.0pt]
\theta_{ju}=\sqrt{\lambda_{ij}/c^{(u)}_{ij}},\\\\[5.0pt] \theta_{\ell
u}=\lambda_{i\ell}/\theta_{iu}\quad\text{for $\forall\ell\in V_{\ell}$}.\\\
\end{dcases}$ (50)

It is easy to verify that for any two leaf nodes $p,q\in V_{\ell}$,

$\theta_{up}\theta_{uq}=\lambda_{pq}$ (51)

holds if at least one of the nodes $p,q$ is a neighbor node of node $u$. The
details are omitted since it is similar to the proof of Lemma F.10. Notice
that this procedure defines more $\theta_{ui}$ values than we need (we only
need $\theta_{ui}$ for $i\in\mathscr{L}^{k+1}$), those $\theta_{ui}$ defined
for $i\in V_{\ell}\setminus\mathscr{L}^{k+1}$ are used to define
$\lambda_{uv}$’s in the following step.

##### Define $\lambda_{uv}$ for ${\mathbb{T}}_{r}^{k}$

: Consider two nodes $u,v$ that are leaf nodes in ${\mathbb{T}}^{k}_{r}$.
Depending on whether $u,v$ are also leaf nodes in ${\mathbb{T}}_{r}$, there
are three cases for defining $\lambda^{k}_{uv}$:

  1. 1.

If both $u$ and $v$ belong to $V_{\ell}$, define

$\lambda^{k}_{uv}=\lambda_{uv}$ (52)

  2. 2.

If only one of the nodes belongs to $V_{\ell}$, then the other node belongs to
$V_{\ell}^{k}\setminus V_{\ell}$. In this case, we define

$\lambda^{k}_{uv}=\theta_{uv}$ (53)

where $\theta_{uv}$ is defined in the previous step.

  3. 3.

If neither $u$ nor $v$ belongs to $V_{\ell}$, then both $u,v\in
V_{\ell}^{k}\setminus V_{\ell}$. This implies that, for each of them, there
must be one leaf node in ${\mathbb{T}}_{r}$ connected to it, denoted the leaf
nodes connected to $u$ and $v$ as $\mathscr{L}(u)$ and $\mathscr{L}(v)$,
accordingly. Then we define

$\lambda_{uv}^{k}=\frac{\lambda_{\mathscr{L}(u),\mathscr{L}(v)}}{\theta_{u,\mathscr{L}(u)}\theta_{v,\mathscr{L}(v)}},$
(54)

where $\theta_{u,\mathscr{L}(u)}$ values are defined in the previous step.

We will now demonstrate that $\lambda^{k}$ is HSE on ${\mathbb{T}}_{r}^{k}$.
To begin, consider any three leaf nodes, $u$, $v$, and $w$, in
${\mathbb{T}}_{r}^{k}$. Let $i$, $j$, and $\ell$ denote the leaf nodes in
${\mathbb{T}}_{r}$ that are neighbors to, or identical with, nodes $u$, $v$,
and $w$, respectively. For instance, if $u$ is also a leaf node in
${\mathbb{T}}_{r}$, then $i=u$; if $u$ is not a leaf node in
${\mathbb{T}}_{r}$, then $i$ is a leaf node in ${\mathbb{T}}_{r}$ that is a
neighbor node of $u$, specifically, we would choose $i=\mathscr{L}(u)$, where
$\mathscr{L}(u)$ is the notation used in Equation (54). Under this setup,

$m(u,v,w)=m(i,j,\ell).$

To establish the HSE of $\lambda^{k}$, we consider all possible cases of
whether nodes $u$, $v$, and $w$ belong to $V_{\ell}$. We show that, under all
cases,

$\frac{\lambda^{k}_{uw}}{\lambda^{k}_{vw}}=\psi_{uv}\cdot\frac{\lambda_{i\ell}}{\lambda_{j\ell}},$
(55)

where $\varphi_{uv}$ is a constant that only depends on $i$ and $j$. Then the
HSE of $\lambda^{k}$ comes from the fact that $\lambda$ is HSE.

  1. 1.

If both $u,v$ belong to $V_{\ell}$, Equation (55) holds with $\psi_{uv}=1$

     * •

when $w\in V_{\ell}$, by definition in Equation (52),

$\lambda^{k}_{uw}/\lambda^{k}_{vw}=\lambda_{i\ell}/\lambda_{j\ell}$

     * •

when $w\in V_{k}\setminus V_{\ell}$, we have

$\lambda^{k}_{uw}/\lambda^{k}_{vw}=\theta_{iw}/\theta_{jw}=\dfrac{\theta_{iw}\theta_{w\ell}}{\theta_{jw}\theta_{w\ell}}=\lambda_{i\ell}/\lambda_{j\ell},$

where the first equality is by definition in Equation (53) and last equality
is by Equation (51).

  2. 2.

If only one of $u,v$ belongs to $V_{\ell}$, without loss of generality, assume
$u\in V_{\ell}$ and $v\in V_{k}\setminus V_{\ell}$. Equation (55) holds with
$\psi_{ij}=\theta_{vj}$, notice that $j=\mathscr{L}(v)$, therefore
$\theta_{vj}$ only depends on $v$.

     * •

when $w\in V_{\ell}$,

$\lambda^{k}_{uw}/\lambda^{k}_{vw}=\lambda_{i\ell}/\theta_{v\ell}=\theta_{vj}\frac{\lambda_{i\ell}}{\theta_{vj}\theta_{v\ell}}=\theta_{vj}\frac{\lambda_{i\ell}}{\lambda_{j\ell}},$

where the first equality is by definition in Equation (52) and (53), and the
last equality is by Equation (51).

     * •

when $w\in V_{k}\setminus V_{\ell}$,

$\lambda^{k}_{uw}/\lambda^{k}_{vw}=\frac{\theta_{iw}}{\lambda_{j\ell}/\left(\theta_{vj}\theta_{w\ell}\right)}=\theta_{vj}\frac{\theta_{iw}\theta_{w\ell}}{\lambda_{j\ell}}=\theta_{vj}\frac{\lambda_{i\ell}}{\lambda_{j\ell}},$

where the first equality is by definition in Equation (53) and (54), and the
last equality is by Equation (51).

  3. 3.

If neither $u$ nor $v$ belongs to $V_{\ell}$. Equation (55) holds with
$\psi_{uv}=\theta_{vj}/\theta_{ui}$, notice that $j=\mathscr{L}(v)$ and
$i=\mathscr{L}(u)$, therefore $\psi_{uv}$ only depends on $u,v$.

     * •

when $w\in V_{\ell}$,

$\lambda^{k}_{uw}/\lambda^{k}_{vw}=\theta_{u\ell}/\theta_{v\ell}=\frac{\theta_{vj}}{\theta_{ui}}\cdot\frac{\theta_{u\ell}\theta_{ui}}{\theta_{v\ell}\theta_{vj}}=\frac{\theta_{vj}}{\theta_{ui}}\cdot\frac{\lambda_{i\ell}}{\lambda_{j\ell}},$

where the first equality is by definition in Equation (53), and the last
equality is by Equation (51).

     * •

when $w\in V_{k}\setminus V_{\ell}$,

$\lambda^{k}_{uw}/\lambda^{k}_{vw}=\frac{\lambda_{i\ell}/\left(\theta_{ui}\theta_{w\ell}\right)}{\lambda_{j\ell}/\left(\theta_{vj}\theta_{w\ell}\right)}=\frac{\theta_{vj}}{\theta_{ui}}\cdot\frac{\lambda_{i\ell}}{\lambda_{j\ell}},$

where the first equality is by definition in Equation (54).

##### Verify the product of $\theta$’s equals to $\lambda_{ij}$

: We want to show that

$\lambda_{ij}=\prod_{(u,v)\in E(i,j)}\theta_{uv}$ (56)

for any pair of nodes $i,j\in V_{\ell}$. Notice that the product of
$\theta_{uv}$’s defined for edges in ${\mathbb{T}}^{k}_{r}$ equals to
$\lambda^{k}$. When at least one of nodes $i,j$ are in $V_{\ell}^{k}$,
Equation (56) holds by the definition of $\lambda^{k}$’s in Equation (52) and
(53). When both $i$ and $j$ are in $V_{\ell}\setminus V_{k}$, denote their
parent nodes as $u$, $v$, accordingly, then find another node $\ell\in
V_{\ell}$.

$\displaystyle\prod_{(u,v)\in E(i,j)}\theta_{uv}$
$\displaystyle=\theta_{iu}\,\theta_{jv}\,\lambda^{k}_{u,v}$
$\displaystyle=\frac{\theta_{iu}\,\theta_{jv}\,\lambda_{\mathscr{L}(u),\mathscr{L}(v)}}{\theta_{\mathscr{L}(u),u}\theta_{\mathscr{L}(v),v}}\quad\text{(by
definition in Equation \eqref{eq:hse_levelk_def_3})}$
$\displaystyle=\frac{\theta_{iu}\,\theta_{uj}\,\theta_{jv}\,\theta_{vi}\,\lambda_{\mathscr{L}(u),\mathscr{L}(v)}}{\theta_{\mathscr{L}(u),u}\,\theta_{uj}\,\theta_{\mathscr{L}(v),v}\,\theta_{vi}}$
$\displaystyle=\frac{\lambda_{ij}\,\lambda_{ij}\,\lambda_{\mathscr{L}(u),\mathscr{L}(v)}}{\lambda_{\mathscr{L}(u),j}\,\lambda_{\mathscr{L}(v),i}}\quad\text{(by
Equation \eqref{eq:hse_levelk_prod})}$
$\displaystyle=\lambda_{ij}\cdot\frac{\lambda_{ij}\,\lambda_{\mathscr{L}(u),\mathscr{L}(v)}}{\lambda_{\mathscr{L}(u),j}\,\lambda_{\mathscr{L}(v),i}}$
$\displaystyle=\lambda_{ij}\cdot\scaleto{\frac{c_{i,\,\mathscr{L}(u)}^{m\left(i,\,\mathscr{L}(u),\,j\right)}}{c_{i,\,\mathscr{L}(u)}^{m\left(i,\,\mathscr{L}(u),\,\mathscr{L}(v)\right)}}}{50pt}\quad\text{(since
$\lambda$ is ${\mathbb{T}}_{r}$-HSE)}$
$\displaystyle=\lambda_{ij}\quad\text{(since
$m(i,\mathscr{L}(u),\mathscr{L}(v))=m(i,\mathscr{L}(u),j)$)}.$

∎

####  F.4.2 Proof of Theorem 3.10

Suppose we have three leaf nodes $i,j,\ell$ and the path from $i$ to $\ell$
passes through the median node $m$. So, $d(i,\ell)=d(i,m)+d(m,\ell)$.
Similarly for $j$ and $\ell$. Because $e^{x+y}=e^{x}e^{y}$, both the numerator
and the denominator in the ratio (6), contain $\exp(-d(m,\ell))$. Canceling
these terms removes any dependence on $\ell$.

##  Appendix G Additional Notes about Models

###  G.1 Negative edge weight

In a tree ${\mathbb{T}}$, we say an edge is an internal edge if it connects
two internal nodes, and an external edge if it connects a leaf node and its
parent. Negative distances for internal edges and external edges are very
different. The subsequent lemma is useful for demonstrating why modifying the
weights of external edges has minimal impact on the overall structure.

######  Theorem G.1.

Consider a tree ${\mathbb{T}}=(V,E)$ and two sets of edge weights
$\\{w^{1}_{uv}\\}$ and $\\{w^{2}_{uv}\\}$ on ${\mathbb{T}}$ such that

  1. 1.

$w^{1}_{uv}=w^{2}_{uv}$ for any pair of non leaf nodes $u,v$,

  2. 2.

$w^{1}_{i,p(i)}=w^{2}_{i,p(i)}+\delta_{i}$ for any leaf nodes $i$ and its
parent $p(i)$.

Let $d^{1}$, $d^{2}$ be two additive distances defined by $w^{1},w^{2}$,
respectively. Define two matrices
$\Sigma^{1},\Sigma^{2}\in{\mathbb{R}}^{N\times N}$ as
$\Sigma^{f}_{ij}=\exp(-d^{f}(i,j))$ for $f=1,2$. Then

$\Sigma^{1}=C\Sigma^{2}C,$ (57)

where $C$ is a diagonal matrix with

$C_{ii}=\begin{cases}\exp(-\delta_{i})&\text{if $i$ is a leaf node}\\\
1&\text{otherwise}\end{cases}$ (58)

###### Proof.

The proof can be achieved by verifying Equation (57) directly. ∎

The following corollary is a direct result of Theorem G.1.

######  Corollary G.1.1.

Consider a ${\mathbb{T}}$-Stochastic Graph with $\lambda_{ij}=\exp(-d(i,j))$
for any pair of leaf nodes $i,j\in V_{\ell}$. If $d(\cdot,\cdot)$ is an
additive distance on ${\mathbb{T}}$ with all internal edge weights being
positive (external edge weights can be negative), then there exists an
additive distance $\widetilde{d}(\cdot,\cdot)$ on ${\mathbb{T}}$ with all edge
weights being positive (external edge weights are also negative) and a
constant $c>0$ such that

$\lambda_{ij}=\exp(-d(i,j))=c\exp\left(-\widetilde{d}(i,j)\right)$

###### Proof.

Using Theorem G.1 and consider $w^{1}$ and $w^{2}$ such that $\delta_{i}\equiv
1-\min_{j\in V_{\ell}}w^{1}_{j,p(j)}$ for all $i\in V_{\ell}$. The proof is
complete by considering $d=d^{1}$ and $\widetilde{d}=d^{2}$. ∎

Corollary G.1.1 shows that for any ${\mathbb{T}}$-Stochastic Graph with
negative external edge weights, one can construct a set of new edge weights
$\widetilde{w}_{uv}>0$ such that
$\lambda_{ij}=c\exp\left(-\widetilde{d}(i,j)\right)$. However, this is not the
case for negative internal edge weights.

Figure 31: four leaf node tree with internal edge weights being negative

We show this by contradiction. Consider a binary tree ${\mathbb{T}}$ with four
leaf nodes shown in Figure 31. When the internal edge weight $w_{ef}$ is
negative, we have

$d(a,b)+d(c,d)>d(a,c)+d(b,d)=d(a,d)+d(b,c).$ (59)

If there exists $\widetilde{w}_{uv}>0$ such that
$\lambda_{ij}=c\exp\left(-\widetilde{d}(i,j)\right)$, then

$\widetilde{d}(a,b)+\widetilde{d}(c,d)<\widetilde{d}(a,c)+\widetilde{d}(b,d)=\widetilde{d}(a,d)+\widetilde{d}(b,c).$
(60)

However, $d(i,j)=\widetilde{d}(i,j)+log(1/c)$ for any pair of leaf nodes
$i,j$, this means Equation (59) and (60) contradict with each other.

In fact, Equation (60) is also known as the four-point condition in
phylogenetic studies and is widely used to identify topology structure in tree
reconstruction problems.

####  G.1.1 Negative edge weight in HSE

Negative internal edge weights are inevitable in HSE graphs. One can find that
the proof of Theorem 3.10 doesn’t require edge weights to be positive. In
other words, any ${\mathbb{T}}$-Stochastic Graph with some negative internal
edges is still HSE.

This aligns with the original Stochastic Equivalence condition proposed by
Holland et al. [1983]. In SBMs, diagonal elements in the connectivity matrix
$B$ are not required to be larger than off-diagonal elements, that is, edges
within the same block could be sparser than edges between blocks.

Consider an SBM with 2 blocks and 4 nodes, where each block contains two
nodes, and the connectivity matrix $B$ is defined as
$B=\begin{bmatrix}0.25&0.5\\\ 0.5&0.25\end{bmatrix}$. Also, consider a
${\mathbb{T}}$-Stochastic Graph with ${\mathbb{T}}$ being a four leaf node
tree as in Figure 31, and define edge weight $w_{uv}$ as

$\displaystyle w_{uv}=\begin{cases}\log(0.5)\qquad&\text{if $u$ and $v$ are
all internal nodes,}\\\ \log(2)&\text{otherwise}.\end{cases}$

It can be verified that these two models are equivalent, and this is an
example of a ${\mathbb{T}}$-Stochastic Graph with negative internal edge
weight ($\log(0.5)$ is negative) being Stochastic Equivalent and Hierarchical
Stochastic Equivalent.

###  G.2 None zero mean vector and general covariance matrix for Gaussian
Graphical Model

Definition 5 constrains $\mu=0$ and $\Sigma_{ii}=1$ for all $i$. This section
shows that the equivalence between models can be extended to the general cases
without these two assumptions. Since GGMs are only involved in the definitions
of the ${\mathbb{T}}$-Graphical Blockmodel and the ${\mathbb{T}}$-Graphical-
RDPG, we are going to discuss the equivalence between these two models and the
${\mathbb{T}}$-Stochastic Graph. Specifically, we show that

  1. 1.

When $\mu\neq 0$, Theorem 3.2 remains valid, Theorem 3.3 holds if we applies a
centering step to the latent positions.

  2. 2.

When $\Sigma_{ii}\neq 1$, both Theorem 3.2 and Theorem 3.3 remain valid.

####  G.2.1 Non zero mean vector ($\mu\neq 0$)

#####  ${\mathbb{T}}$-Graphical Blockmodel

: Since Definition 6 solely considers $\Sigma$ and does involve $\mu$, the
validity of Theorem 3.2 remains unaffected when removing the constraint of
$\mu=0$.

#####  ${\mathbb{T}}$-Graphical RDPG

: If the mean vector $\mu\neq 0$, a centering step can be taken for all
features. Specifically, instead of using $x_{i}$ as the latent position for
node $i$, we consider $x_{i}-\bar{x}_{i}$, where $\bar{x}_{i}$ is the mean of
all elements in $x_{i}$. According to the Law of Large Numbers, Theorem 3.3
holds as $<x_{i}-\bar{x}_{i},x_{j}-\bar{x}j>/q$ converges asymptotically to
$\Sigma{ij}$.

####  G.2.2 Non unit variance in the covariance matrix ($\Sigma_{ii}\neq 1$)

Since this extension only affects the ${\mathbb{T}}$-Graphical RDPG and the
${\mathbb{T}}$-Graphical Blockmodel, we only need to show one direction of the
equivalence: any ${\mathbb{T}}$-Graphical RDPG (or ${\mathbb{T}}$-Graphical
Blockmodel) defined by a GGM with general covariance matrix is a
${\mathbb{T}}$-Stochastic Graph.

#####  ${\mathbb{T}}$-Graphical Blockmodels with $\Sigma_{ii}\neq 1$ are
${\mathbb{T}}$-Stochastic Graphs.

In a ${\mathbb{T}}$-Graphical Blockmodel, $\mathscr{A}=ZBZ^{T}$ with
$B=\Sigma$. If we have a general covariance matrix $\Sigma=SRS$, where $R$ is
the corresponding correlation matrix and $S$ is a diagonal matrix with
$S_{ii}=\sqrt{\Sigma_{ii}}$, then $\mathscr{A}=Z\Sigma
Z^{T}=ZSRSZ^{T}=Z_{S}RZ_{S}^{T}$, where $Z_{S}=ZS$. Since $R$ can be
considered as a covariance matrix with unit variance, and $Z_{S}$ is a valid
block membership matrix for DCSBM, this ${\mathbb{T}}$-Graphical Blockmodel is
equivalent to a ${\mathbb{T}}$-Graphical Blockmodel with a unit variance GGM.
Hence any ${\mathbb{T}}$-Graphical Blockmodel with a general covariance matrix
is still a ${\mathbb{T}}$-Stochastic Graph.

#####  ${\mathbb{T}}$-Graphical RDPGs with $\Sigma_{ii}\neq 1$ are
${\mathbb{T}}$-Stochastic Graphs.

Using the same notation as in Section 3.3, let $s_{i}=\sqrt{\Sigma_{ii}}$ and
denote $x_{i}/s_{i}$ as $\widetilde{x}_{i}$. By the Law of Large Numbers and
Proposition 3.1, there exists an additive distance
$\widetilde{d}(\cdot,\cdot)$ on ${\mathbb{T}}$ such that

$\left|\langle\widetilde{x}_{i},\widetilde{x}_{j}\rangle\right|\xrightarrow{q\rightarrow\infty}\exp\left(-\widetilde{d}(i,j)\right),$

Consider a ${\mathbb{T}}$-Stochastic Graph with edge weights $w_{uv}$ defined
as

$\displaystyle w_{uv}=\begin{cases}\widetilde{d}(u,v)\qquad\qquad&\text{if
both $u$ and $v$ are internal nodes,}\\\
\widetilde{d}(u,v)+log(1/s_{u})&\text{if $u$ is a leaf node and $v$ is the
neighbor node of $u$, i.e. $v=p(u)$,}\\\
\widetilde{d}(u,v)+log(1/s_{v})&\text{if $v$ is a leaf node and $u$ is the
neighbor node of $v$, i.e. $u=p(v)$.}\\\ \end{cases}$

The proof is completed by the following equalities

$\displaystyle\widetilde{\lambda}_{ij}^{RDPG}$ $\displaystyle=q^{-1}|\langle
x_{i},x_{j}\rangle|$ $\displaystyle=s_{i}s_{j}q^{-1}|\langle
x^{*}_{i},x^{*}_{j}\rangle|$ $\displaystyle\rightarrow
s_{i}s_{j}\exp\left(-\widetilde{d}(i,j)\right)$
$\displaystyle=\exp\left(-\widetilde{d}(i,j)-\log(1/s_{i})-\log(1/s_{j})\right)$
$\displaystyle=\exp(-d(i,j))$ $\displaystyle=\lambda^{TSG}_{ij}$

##  Appendix H Algorithms: vsp and SpaseNJ

###  H.1 vsp: consistent estimation of DCSBMs

The Vintage Sparse PCA (vsp) algorithm proposed by Rohe and Zeng [2022]
estimates $Z$ through two primary steps: spectral embedding and Varimax
rotation. The first step applies eigen decomposition on $A$ to construct a
matrix $U$ that shares the same column space as $Z$; the second step finds an
orthogonal rotation matrix $R_{U}$ by maximizing the Varimax function
$v(R,U)$, which is defined as

$v(R,U)=\sum_{l=1}^{k}\frac{1}{n}\sum_{i=1}^{n}\left([UR]^{4}_{il}-\left(\frac{1}{n}\sum_{q=1}^{n}[UR]_{ql}^{2}\right)^{2}\right),$
(61)

and outputs $\widehat{Z}=UR_{U}$. It should be noted that the Varimax
objective function remains unchanged when the columns of $UR$ are reordered or
flipped in sign. As a result, the maximizer of Varimax is an equivalence class
that allows for sign flips and column reordering.

The original vsp algorithm does not include a sign-adjustment step since it
studies the more general semi-parametric setting where $Z_{ij}$ is allowed to
be negative. In the context of ${\mathbb{T}}$-Stochastic Graphs, the column
signs are identifiable as the DCSBM assumes nonnegative values for
$\theta_{i}$. We utilize this fact to add a sign-adjustment step. This
additional step removes the dependence on sign flip operation while not
affecting the asymptotic performance of $\widehat{Z}$. Proofs can be found in
Appendix I.5.1.

Input:

adjacency matrix $A\in{\mathbb{R}}^{n\times n}$;

number of blocks $k$.

Output:

block membership matrix $\widehat{Z}\in{\mathbb{R}}^{n\times k}$.

1 Spectral Embedding: compute the top $k$ eigenvectors
$u_{1},\cdots,u_{k}\in{\mathbb{R}}^{n}$ of $A$ and place them into columns of
$U\in{\mathbb{R}}^{n\times k}$;

2 Varimax Rotation: find an orthogonal matrix $R_{U}$ that maximize the
Varimax function,  $R_{U}=\mathrm{argmax}_{R\in\mathcal{O}(k)}\ v(R,U),$ where
$\mathcal{O}(k)=\\{R\in\mathbb{R}_{k\times k}:R^{T}R=RR^{T}=I_{k}\\}$ is the
set of orthogonal matrices in ${\mathbb{R}}^{k\times k}$;

3 Sign Adjustment: let $\widehat{Z}=\sqrt{n}UR_{U}$, calculate a diagonal
matrix $\widehat{D}\in{\mathbb{R}}^{k\times k}$ with
$\widehat{D}_{jj}=\text{sgn}\left(\sum_{i=1}^{n}\widehat{Z}_{ij}\right)$,
where $\text{sgn}(0)=0$ and if $x\neq 0$, $\text{sgn}(x)=x/|x|$; then, set
$\widehat{Z}\leftarrow\widehat{Z}\widehat{D}$;

Algorithm 5 vsp (step 1)

###  H.2 SparseNJ: NJ and edge thresholding

The NJ algorithm is an agglomerative clustering method that iteratively
combines a pair of nodes iteratively. It consists of two main parts: the
selection criterion and the updating criterion. Algorithm 6 provides a
detailed outline of the NJ procedure, with superscript $(t)$ indicating the
quantities at the $t$th iteration. Algorithm 7 describes the procedure of the
SparseNJ algorithm, which involves applying NJ first and then shrinking short
edges to zero.

Input:

pairwise distances $\widehat{D}\in{\mathbb{R}}^{k\times k}$ between nodes in
$V_{o}$

Output:

binary tree
$\widehat{\mathbb{T}}_{nj}=\left(\widehat{V}_{nj},\widehat{E}_{nj}\right)$
with edge distances
$\left\\{\widehat{d}(u,v):(u,v)\in\widehat{E}_{nj}\right\\}$

1 Initialization: let $\widehat{V}_{nj}\leftarrow V_{o}$,
$\widehat{E}_{nj}=\\{\\}$, $V_{o}^{(1)}=V_{o}$,
$\widehat{d}^{(1)}(i,j)\leftarrow\widehat{D}_{ij}$ for any pair of nodes
$i,j\in V_{o}$;

2 for  _$t\leftarrow 1$ to $k-2$_ do

3 Selection: choose the pair of nodes $\left(i^{(t)},j^{(t)}\right)\in
V_{o}^{(t)}$ such that the following criterion is minimized
$S^{(t)}_{i,j}=(k-2)\widehat{d}^{(t)}(i,j)-\sum_{m=1}^{k}\widehat{d}^{(t)}(i,m)-\sum_{m=1}^{k}\widehat{d}^{(t)}(j,m),$
and combine nodes $i^{(t)}$ and $j^{(t)}$ by adding a new node $x^{(t)}$ as
their parent:  $\displaystyle V_{o}^{(t+1)}\leftarrow
V_{o}^{(t)}\cup\\{x^{(t)}\\}\setminus\left\\{i^{(t)},j^{(t)}\right\\},$
$\displaystyle\widehat{V}_{nj}\leftarrow\widehat{V}_{nj}\cup\\{x^{(t)}\\},\quad\widehat{E}_{nj}\leftarrow\widehat{E}_{nj}\cup\left\\{(i^{(t)},x^{(t)}),(j^{(t)},x^{(t)})\right\\};$
Updating: update the pairwise distances between nodes in $V_{o}$ as
$\widehat{d}^{(t+1)}(u,\ell)=\begin{dcases}\widehat{d}^{(t)}(u,\ell)&\text{ if
$u,\ell\neq x^{(t)}$}\\\
\frac{1}{2}\,\widehat{d}^{(t)}\left(u,i^{(t)}\right)+\frac{1}{2}\,\widehat{d}^{(t)}\left(u,j^{(t)}\right)&\text{
if $u=x^{(t)}$}\end{dcases}.$ (62) Then estimate the distance of
$\left(i^{(t)},x^{(t)}\right)$ as
$\displaystyle\widehat{d}\left(i^{(t)},x^{(t)}\right)$
$\displaystyle=\frac{1}{2}\,\widehat{d}^{(t)}\left(i^{(t)},j^{(t)}\right)+\frac{1}{2}\,\widehat{d}^{(t)}_{-j}\left(i^{(t)}\right)-\frac{1}{2}\,\widehat{d}^{(t)}_{-i}\left(j^{(t)}\right)$
(63)
$\displaystyle\qquad-\frac{1}{2}\,\sum_{m=1}^{t-1}\mathds{1}\left\\{i^{(t)}=x^{(m)}\right\\}\,\widehat{d}^{(m)}\left(i^{(m)},j^{(m)}\right),$
where $\widehat{d}^{(t)}_{-j}\left(i^{(t)}\right)$ is the mean of the
distances between node $i$ and any other node $u\neq i^{(t)},j^{(t)}$, that is
$\widehat{d}^{(t)}_{-j}\left(i^{(t)}\right)=\frac{1}{k-t-1}\sum_{\scaleto{u\,\in\,\left.V^{(t)}_{o}\middle\backslash\left\\{i^{(t)},j^{(t)}\right\\}\right.}{18pt}}\widehat{d}^{(t)}\left(i^{(t)},u\right).$
The same idea holds for estimating $\widehat{d}\left(j^{(t)},x^{(t)}\right)$;

4

After $k-2$ iteration, there are only two nodes left in $V_{o}^{(k-1)}$,
denote them as $u$ and $v$, then update
$\widehat{E}_{nj}\leftarrow\widehat{E}_{nj}\cup\left\\{(u,v)\right\\}$ and
estimate the edge distance as
$\widehat{d}(u,v)=d^{(k-1)}(u,v)-\frac{1}{2}\,d^{(k-2)}\left(i^{(k-2)},j^{(k-2)}\right).$
(64)

Algorithm 6 Neighbor Joining

Input:

pairwise distances $\widehat{D}$ between nodes in $V_{o}$;

cutoff value $\varphi$.

Output:

tree estimation $\widehat{\mathbb{T}}=\left(\widehat{V},\widehat{E}\right)$.

1 Estimation: apply the NJ algorithm on $\widehat{D}$ to reconstruct a tree
$\widehat{\mathbb{T}}_{nj}=\left(\widehat{V}_{nj},\widehat{E}_{nj}\right)$ and
edge distances $\left\\{\widehat{d}(u,v):(u,v)\in\widehat{E}_{nj}\right\\}$
(Algorithm 6 provides the detailed NJ algorithm);

2 Shrinking: set $\widehat{V}\rightarrow\widehat{V}_{nj}$,
$\widehat{E}=\widehat{E}_{nj}$, then update them by looping through all edges
in $\widehat{E}_{nj}$

3 for  _$(u,v)\in\widehat{E}_{nj}$_ do

4 if  _$\widehat{d}\left(u,v\right)\leq\varphi$_ then

5 combine nodes $u$ and $v$ by
$\displaystyle\widehat{V}\leftarrow\widehat{V}\setminus\\{u\\}$
$\displaystyle\widehat{E}\leftarrow\widehat{E}\mathbin{\big{\backslash}}\left\\{(u,z):\forall
z,\text{ s.t. }(u,z)\in\widehat{E}\right\\}\bigcup\left\\{(v,z):\forall z\neq
u,\text{ s.t. }(v,z)\in\widehat{E}\right\\}$

6

Algorithm 7 SparseNJ (step 3)

##  Appendix I Asymptotic Behaviour of synthesis (Algorithm 2)

###  I.1 Proof of Theorem 4.1

We first show that

$\left\|\widehat{B}-P_{n}^{T}BP_{n}\right\|_{F}=O_{p}(e_{n}).$ (65)

This can be decomposed into two parts: the first part shows that
$\widehat{B}^{nn}$ and $\rho_{n}B$ are close up to a scaling matrix
(Proposition I.1); the second part (presented in this section) shows that
$\widehat{S}^{-1}$ is a good estimate of $S$ and thus
$\widehat{B}=\left[\widehat{S}^{-1}\widehat{B}^{nn}\widehat{S}^{-1}\right]_{\leq
1}$ is a good estimate of $B$. The proof of Proposition I.1 can be found in
Appendix I.2.

######  Proposition I.1.

Under the conditions in Theorem 4.1, there exists a sequence of reordering
matrix $P_{n}\in\mathscr{P}(k)$ such that

$\left\|\widehat{B}^{nn}-\rho_{n}P_{n}^{T}SBSP_{n}\right\|_{F}=O_{p}\left(\rho_{n}e_{n}\right),$

where $S$ is a random diagonal matrix with positive elements such that
$S_{jj}\asymp 1$, and $\widehat{B}^{nn}$ can be one of three options: the
original estimator proposed in Algorithm 3 or the two alternatives discussed
in Remark 4.5.

######  Proposition I.2.

Under the conditions in Theorem 4.1, let $S$ and $P_{n}$ be the same diagonal
matrix and reordering matrices as in Proposition I.1, then

$\left\|\widehat{S}^{-1}-\rho_{n}^{-.5}P_{n}^{T}S^{-1}P_{n}\right\|_{F}=O_{p}\left(\rho_{n}^{-.5}e_{n}\right),$
(66) $\left\|\widehat{S}^{-1}\right\|_{F}=O_{p}(\rho_{n}^{-.5}).$ (67)

###### Proof.

Let $a=\left[\widehat{B}^{nn}\right]_{jj}$,
$b=\rho_{n}\left[P_{n}^{T}SBSP_{n}\right]_{jj}$, by Proposition I.1,

$\left|a-b\right|=O_{p}\left(\rho_{n}e_{n}\right).$ (68)

Given that both matrices $B$ is fixed, $P_{n}\in\mathscr{P}(k)$, and
$S_{jj}\asymp 1$, we have $|b|\asymp\rho_{n}$, which implies that
$|a|\asymp\rho_{n}$. Therefore

$\left|\frac{1}{a}\right|=O_{p}\left(\rho_{n}^{-1}\right),\quad\left|\frac{1}{b}\right|=O_{p}\left(\rho_{n}^{-1}\right).$
(69)

Since $B$ has unit diagonal elements,

$S_{jj}=\sqrt{\left[SBS\right]_{jj}}\,.$ (70)

By step 3 (scaling step) in Algorithm 3,

$\widehat{S}_{jj}=\sqrt{\widehat{B}^{nn}_{jj}}\,.$ (71)

Taken Equation (69), (70), and (71) together, we have

$\displaystyle\left|\left[\widehat{S}^{-1}\right]_{jj}-\left[\rho_{n}^{-.5}P_{n}^{T}S^{-1}P_{n}\right]_{jj}\right|$
$\displaystyle=\left|\frac{1}{\sqrt{a}}-\frac{1}{\sqrt{b}}\right|=\left|\frac{\sqrt{a}-\sqrt{b}}{\sqrt{ab}}\right|$
$\displaystyle=\left|\frac{a-b}{(\sqrt{a}+\sqrt{b})\sqrt{ab}}\right|$
$\displaystyle=O_{p}\left(\rho_{n}^{-.5}e_{n}\right).$

Since the above statement holds for $\forall j\in[k]$, we proved Equation
(66). Equation (67) follows directly from Equation (66) by noting that

$\left\|\rho_{n}^{-.5}P_{n}^{T}S^{-1}P_{n}\right\|_{F}=O_{p}(\rho_{n}^{-.5}).$

∎

######  Proposition I.3.

For $M,\widehat{M}\in\mathbb{R}^{p_{1}\times p_{2}}$, If $M_{ij}\geq 0$,

$\left\|\widehat{M}_{+}-M\right\|_{2\rightarrow\infty}\leq\left\|\widehat{M}-M\right\|_{2\rightarrow\infty}.$

If $M_{ij}\leq 1$,

$\left\|\widehat{M}_{\leq
1}-M\right\|_{F}\leq\left\|\widehat{M}-M\right\|_{F}.$

###### Proof.

If $M_{ij}\geq 0$,
$\left|\left[\widehat{M}_{+}\right]_{ij}-M_{ij}\right|\leq\left|\widehat{M}_{ij}-M_{ij}\right|$.
By Proposition 6.1 in [Cape et al., 2019], $\|N\|_{2\rightarrow\infty}$
corresponds to the maximum row-wise Euclidean norm of $N$, therefore
$\|\widehat{M}_{+}-M\|_{2\rightarrow\infty}\leq\|\widehat{M}-M\|_{2\rightarrow\infty}$.
The argument for $M_{ij}\leq 1$ is similar, just notice that
$\|N\|_{F}=\sum_{ij}N_{ij}^{2}$. ∎

Proposition I.1 bounds the distance between $B^{nn}$ and $\rho_{n}B$, the
detailed proofs are in Appendix I.2. Proposition I.2 gives the asymptotic
behavior of the estimated scaling matrix. Proposition I.3 provides
justification for element-wise projection, it shows that projection only
shortens the distance between the estimate and the underlying true value.

To simplify notations, denote $SBS$ as $B_{S}$. With Proposition I.1, I.2, and
I.3, the bound for $\left\|\widehat{B}-P^{T}_{n}BP_{n}\right\|_{F}$ can be
derived as follows.

$\displaystyle\left\|\widehat{B}-P_{n}^{T}BP_{n}\right\|_{F}=\left\|\left[\widehat{S}^{-1}\widehat{B}^{nn}\widehat{S}^{-1}\right]_{\leq
1}-P_{n}^{T}S^{-1}B_{S}S^{-1}P_{n}\right\|_{F}$
$\displaystyle\leq\left\|\widehat{S}^{-1}\widehat{B}^{nn}\widehat{S}^{-1}-P_{n}^{T}S^{-1}B_{S}S^{-1}P_{n}\right\|_{F}\quad(\text{by
Proposition \ref{prop:projection}})$
$\displaystyle\leq\left\|\widehat{S}^{-1}\widehat{B}^{nn}\widehat{S}^{-1}-\rho_{n}\widehat{S}^{-1}P_{n}^{T}B_{S}P_{n}\widehat{S}^{-1}\right\|_{F}+\left\|\rho_{n}\widehat{S}^{-1}P_{n}^{T}B_{S}P_{n}\widehat{S}^{-1}-P_{n}^{T}S^{-1}B_{S}S^{-1}P_{n}\right\|_{F}$
$\displaystyle\leq\left\|\widehat{S}^{-1}\left(\widehat{B}^{nn}-\rho_{n}P_{n}^{T}B_{S}P_{n}\right)\widehat{S}^{-1}\right\|_{F}+\left\|\rho_{n}\widehat{S}^{-1}P_{n}^{T}B_{S}P_{n}\widehat{S}^{-1}-P_{n}^{T}S^{-1}P_{n}(P_{n}^{T}B_{S}P_{n})P_{n}^{T}S^{-1}P_{n}\right\|_{F}$
$\displaystyle\leq\left\|\widehat{S}^{-1}\left(\widehat{B}^{nn}-\rho_{n}P_{n}^{T}B_{S}P_{n}\right)\widehat{S}^{-1}\right\|_{F}+\left\|\rho_{n}\widehat{S}^{-1}P_{n}^{T}B_{S}P_{n}\widehat{S}^{-1}-\rho_{n}^{.5}\widehat{S}^{-1}(P_{n}^{T}B_{S}P_{n})P_{n}^{T}S^{-1}P_{n}\right\|_{F}$
$\displaystyle\qquad+\left\|\rho_{n}^{.5}\widehat{S}^{-1}(P_{n}^{T}B_{S}P_{n})P_{n}^{T}S^{-1}P_{n}-P_{n}^{T}S^{-1}P_{n}(P_{n}^{T}B_{S}P_{n})P_{n}^{T}S^{-1}P_{n}\right\|_{F}$
$\displaystyle\leq\left\|\widehat{S}^{-1}\right\|_{F}\left\|\widehat{B}^{nn}-\rho_{n}P_{n}^{T}B_{S}P_{n}\right\|_{F}\left\|\widehat{S}^{-1}\right\|_{F}+\left\|\rho_{n}^{.5}\widehat{S}^{-1}P_{n}^{T}B_{S}P_{n}\right\|_{F}\left\|\rho_{n}^{.5}\widehat{S}^{-1}-P_{n}^{T}S^{-1}P_{n}\right\|_{F}$
$\displaystyle\qquad+\left\|\rho_{n}^{.5}\widehat{S}^{-1}-P_{n}^{T}S^{-1}P_{n}\right\|_{F}\left\|(P_{n}^{T}B_{S}P_{n})P_{n}^{T}S^{-1}P_{n}\right\|_{F}$
$\displaystyle\leq
O_{p}(\rho_{n}^{-.5})O_{p}(\rho_{n}e_{n})O_{p}(\rho_{n}^{-.5})+O_{p}(1)O_{p}(e_{n})+O_{p}(e_{n})O_{p}(1)\quad(\text{by
Proposition \ref{prop:tildeB} and \ref{prop:S}})$
$\displaystyle=O_{p}\left(e_{n}\right)$

Now we show

$\left\|\widehat{D}-P_{n}^{T}DP_{n}\right\|_{F}=O_{p}(e_{n}).$ (72)

Since all elements in the covariance matrix of a GGM are positive, there
exists a constant $\gamma>0$ such that $\min_{ij}B_{ij}>\gamma$. Since
$\left\|\widehat{B}-P_{n}^{T}BP_{n}\right\|_{F}=O_{p}(e_{n})$, the probability
that $\min_{ij}\widehat{B}_{ij}>\gamma$ goes to one. Equation (72) can be
proved by noticing that $\widehat{D}_{ij}=-\log\left(\widehat{B}_{ij}\right)$
and

$\left|\log(x)-\log(y)\right|\leq\frac{1}{\gamma}\left|x-y\right|$

for any $x,y\in[\gamma,\infty)$ with $\gamma>0$.

###  I.2 Proof of Proposition I.1

The proof of Proposition I.1 requires several lemmas. Lemma I.1 is a rephrase
of Proposition 6.3 in [Cape et al., 2019]. The proof of Lemma I.2 to Lemma I.7
are contained in Appendix I.3.

To simplify notation, denote

$\widehat{\Sigma}=\widehat{Z}_{+}^{T}\widehat{Z}_{+},\ \Sigma=Z^{T}Z/n.$

We introduce the symbol $\,\widetilde{\cdot}\,$ to represent matrices that
have been scaled by the matrix $C$, and utilize the subscript $P$ to denote
matrices that have been reordered by the permutation matrix $P_{n}$.
Specifically, we define

$\widetilde{Z}=ZC,\ \
\widetilde{\Sigma}=\widetilde{Z}^{T}\widetilde{Z}/n=C\Sigma C,\ \
\widetilde{B}=C^{-1}BC^{-1},$ $\widetilde{Z}_{P}=\widetilde{Z}P_{n},\ \
\widetilde{\Sigma}_{P}=\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}/n=P_{n}^{T}\widetilde{\Sigma}P_{n},\
\ \widetilde{B}_{P}=P_{n}^{T}\widetilde{B}P_{n}.$

Notice that

$\mathscr{A}=ZBZ^{T}=\widetilde{Z}\widetilde{B}\widetilde{Z}^{T}=\widetilde{Z}_{P}\widetilde{B}_{P}\widetilde{Z}^{T}_{P},$

This section shows that all

$\widehat{B}^{nn}_{1}=\left[\widehat{\Sigma}_{Z}^{-1}\widehat{Z}_{+}^{T}A\widehat{Z}_{+}\widehat{\Sigma}_{Z}^{-1}\right]_{+},\
\widehat{B}^{nn}_{2}=\frac{1}{n^{2}}\widehat{Z}_{+}^{T}A\widehat{Z}_{+},\
\text{and }\
\widehat{B}^{nn}_{3}=\frac{1}{n^{2}}\left[\widehat{Z}^{T}A\widehat{Z}\right]_{+},$

are close to $\rho_{n}B$ up to rows and columns permutations, and scaling
matrices

$S_{1}=C^{-1},\ S_{2}=\widetilde{\Sigma}C^{-1},\ \text{and }\
S_{3}=\widetilde{\Sigma}C^{-1},$

respectively.

######  Lemma I.1.

(Proposition 6.3 in Cape et al. [2019]) For $M\in\mathbb{R}^{p_{1}\times
p_{2}}$, then

$\|M\|_{2\rightarrow\infty}\leq\|M\|_{2}\leq\min\\{\sqrt{p_{1}}\|M\|_{2\rightarrow\infty},\sqrt{p_{2}}\|M^{T}\|_{2\rightarrow\infty}\\}$

######  Lemma I.2.

There exists a sequence of permutation matrix $P_{n}\in\mathcal{P}(k)$, such
that

$\left\|\widehat{Z}-\widetilde{Z}_{P}\right\|_{2\rightarrow\infty}=O_{p}\left(e_{n}\right),$
(73)
$\left\|\widehat{Z}_{+}-\widetilde{Z}_{P}\right\|_{2\rightarrow\infty}=O_{p}\left(e_{n}\right).$
(74)

######  Lemma I.3.

$\left\|A-\mathscr{A}\right\|_{2}=O_{p}\left(n\rho_{n}e_{n}\right)$

######  Lemma I.4.

$\left\|\widetilde{B}_{P}\right\|_{2}=O_{p}(1)$

######  Lemma I.5.

$\left\|\widetilde{Z}_{P}\right\|_{2}=O_{p}\left(n^{.5}\right)$

######  Lemma I.6.

$\left\|\widehat{Z}\right\|_{2}=O_{p}(n^{.5})$,
$\left\|\widehat{Z}_{+}\right\|_{2}=O_{p}(n^{.5})$,
$\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\right\|_{2}=O_{p}\left(n^{-.5}\right)$

######  Lemma I.7.

$\left\|\widehat{Z}_{+}^{T}\widetilde{Z}_{P}-n\widetilde{\Sigma}_{P}\right\|_{2}=O_{p}\left(ne_{n}\right)$,
$\left\|\widehat{Z}^{T}\widetilde{Z}_{P}-n\widetilde{\Sigma}_{P}\right\|_{2}=O_{p}\left(ne_{n}\right)$,

$\displaystyle\left\|\widehat{B}^{nn}_{1}-\rho_{n}P_{n}^{T}S_{1}BS_{1}P_{n}\right\|_{2}=\left\|\left[\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}A\widehat{Z}_{+}\widehat{\Sigma}^{-1}\right]_{+}-\rho_{n}\widetilde{B}_{P}\right\|_{2}$
$\displaystyle\leq\sqrt{k}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}A\widehat{Z}_{+}\widehat{\Sigma}^{-1}-\rho_{n}\widetilde{B}_{P}\right\|_{2}\quad(\text{Proposition
\ref{prop:projection} and Lemma \ref{lemma:norm2}})$
$\displaystyle\leq\sqrt{k}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}A\widehat{Z}_{+}\widehat{\Sigma}^{-1}-\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\mathscr{A}\widehat{Z}_{+}\widehat{\Sigma}^{-1}\right\|_{2}+\sqrt{k}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\mathscr{A}\widehat{Z}_{+}\widehat{\Sigma}^{-1}-\rho_{n}\widetilde{B}_{P}\right\|_{2}$
$\displaystyle=\sqrt{k}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}A\widehat{Z}_{+}\widehat{\Sigma}^{-1}-\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\mathscr{A}\widehat{Z}_{+}\widehat{\Sigma}^{-1}\right\|_{2}+\sqrt{k}\rho_{n}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\widetilde{Z}_{P}\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}_{+}\widehat{\Sigma}^{-1}-\widetilde{B}_{P}\right\|_{2}$
$\displaystyle\leq\sqrt{k}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}(A-\mathscr{A})\widehat{Z}_{+}\widehat{\Sigma}^{-1}\right\|_{2}+\sqrt{k}\rho_{n}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\widetilde{Z}_{P}\widetilde{B}_{P}\widetilde{Z}^{T}_{P}\widehat{Z}_{+}\widehat{\Sigma}^{-1}-\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}_{+}\widehat{\Sigma}^{-1}\right\|_{2}$
$\displaystyle\qquad+\sqrt{k}\rho_{n}\left\|\widetilde{B}_{P}\widetilde{Z}^{T}_{P}\widehat{Z}_{+}\widehat{\Sigma}^{-1}-\widetilde{B}_{P}\right\|_{2}$
$\displaystyle\leq\sqrt{k}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}(A-\mathscr{A})\widehat{Z}_{+}\widehat{\Sigma}^{-1}\right\|_{2}+\sqrt{k}\rho_{n}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\left(\widetilde{Z}_{P}-\widehat{Z}_{+}\right)\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}_{+}\widehat{\Sigma}^{-1}\right\|_{2}$
$\displaystyle\qquad+\sqrt{k}\rho_{n}\left\|\widetilde{B}_{P}\left(\widetilde{Z}_{P}-\widehat{Z}_{+}\right)^{T}\widehat{Z}_{+}\widehat{\Sigma}^{-1}\right\|_{2}$
$\displaystyle\leq\sqrt{k}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\right\|_{2}^{2}\left\|A-\mathscr{A}\right\|_{2}+\sqrt{k}\rho_{n}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\right\|^{2}_{2}\left\|\widetilde{Z}_{P}-\widehat{Z}_{+}\right\|_{2}\left\|\widetilde{B}_{P}\right\|_{2}\left\|\widetilde{Z}_{P}\right\|_{2}$
$\displaystyle\qquad+\sqrt{k}\rho_{n}\left\|\widetilde{B}_{P}\right\|_{2}\left\|\widetilde{Z}_{P}-\widehat{Z}_{+}\right\|_{2}\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\right\|_{2}$
$\displaystyle\leq
O_{p}(n^{-1})O_{p}\left(n\rho_{n}e_{n}\right)+\rho_{n}O_{p}(n^{-1})O_{p}\left(n^{.5}e_{n}\right)O_{p}(1)O_{p}(n^{.5})+\rho_{n}O_{p}(n^{-1})O_{p}(1)O_{p}\left(n^{.5}e_{n}\right)O_{p}(n^{-.5})$
$\displaystyle\qquad(\text{Lemma \ref{lemma:norm2} to Lemma
\ref{lemma:hatZZ_Sigma}, the transformation from $\|\cdot\|_{2}$ to
$\|\cdot\|_{2\rightarrow\infty}$ introduce an extra $n^{.5}$})$
$\displaystyle=O_{p}\left(\rho_{n}e_{n}\right)$

$\displaystyle\left\|\widehat{B}^{nn}_{2}-\rho_{n}P_{n}^{T}S_{2}BS_{2}P_{n}\right\|_{2}=\left\|\frac{1}{n^{2}}\widehat{Z}_{+}^{T}A\widehat{Z}_{+}-\rho_{n}P_{n}^{T}\widetilde{\Sigma}\widetilde{B}\widetilde{\Sigma}P_{n}\right\|_{2}$
$\displaystyle\leq\left\|\frac{1}{n^{2}}\widehat{Z}_{+}^{T}A\widehat{Z}_{+}-\frac{1}{n^{2}}\widehat{Z}_{+}^{T}\mathscr{A}\widehat{Z}_{+}\right\|_{2}+\left\|\frac{1}{n^{2}}\widehat{Z}_{+}^{T}\mathscr{A}\widehat{Z}_{+}-\rho_{n}\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{\Sigma}_{P}\right\|_{2}$
$\displaystyle=\frac{1}{n^{2}}\left\|\widehat{Z}_{+}^{T}A\widehat{Z}_{+}-\widehat{Z}_{+}^{T}\mathscr{A}\widehat{Z}_{+}\right\|_{2}+\rho_{n}\left\|\frac{1}{n^{2}}\widehat{Z}_{+}^{T}\widetilde{Z}_{P}\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}_{+}-\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{\Sigma}_{P}\right\|_{2}$
$\displaystyle\leq\frac{1}{n^{2}}\left\|\widehat{Z}_{+}^{T}(A-\mathscr{A})\widehat{Z}_{+}\right\|_{2}+\rho_{n}\left\|\frac{1}{n^{2}}\widehat{Z}_{+}^{T}\widetilde{Z}_{P}\widetilde{B}_{P}\widetilde{Z}^{T}_{P}\widehat{Z}_{+}-\frac{1}{n}\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}_{+}\right\|_{2}+\rho_{n}\left\|\frac{1}{n}\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}_{+}-\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{\Sigma}_{P}\right\|_{2}$
$\displaystyle\leq\frac{1}{n^{2}}\left\|\widehat{Z}_{+}^{T}(A-\mathscr{A})\widehat{Z}_{+}\right\|_{2}+\frac{\rho_{n}}{n^{2}}\left\|\left(\widehat{Z}_{+}^{T}\widetilde{Z}_{P}-n\widetilde{\Sigma}_{P}\right)\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}_{+}\right\|_{2}+\frac{\rho_{n}}{n}\left\|\widetilde{\Sigma}_{P}\widetilde{B}_{P}\left(\widetilde{Z}_{P}^{T}\widehat{Z}_{+}-n\widetilde{\Sigma}_{P}\right)\right\|_{2}$
$\displaystyle\leq\frac{1}{n^{2}}\left\|\widehat{Z}_{+}\right\|_{2}^{2}\left\|A-\mathscr{A}\right\|_{2}+\frac{\rho_{n}}{n^{2}}\left\|\widehat{Z}_{+}^{T}\widetilde{Z}_{P}-n\widetilde{\Sigma}_{P}\right\|_{2}\left\|\widetilde{B}_{P}\right\|_{2}\left\|\widetilde{Z}_{P}\right\|_{2}\left\|\widehat{Z}_{+}\right\|_{2}$
$\displaystyle\qquad+\frac{\rho_{n}}{n}\left\|\widetilde{\Sigma}_{P}\widetilde{B}_{P}\right\|_{2}\left\|\left(\widehat{Z}_{+}^{T}\widetilde{Z}_{P}-n\widetilde{\Sigma}_{P}\right)^{T}\right\|_{2}$
$\displaystyle\leq\frac{1}{n^{2}}O_{p}\left(n\right)O_{p}\left(n\rho_{n}e_{n}\right)+\frac{\rho_{n}}{n^{2}}O_{p}\left(ne_{n}\right)O_{p}\left(1\right)O_{p}\left(n^{.5}\right)O_{p}\left(n^{.5}\right)+\frac{\rho_{n}}{n}O_{p}\left(1\right)O_{p}\left(ne_{n}\right)$
$\displaystyle\qquad(\text{Lemma \ref{lemma:norm2} to Lemma
\ref{lemma:hatZZ_Sigma}})$ $\displaystyle=O_{p}\left(\rho_{n}e_{n}\right)$

$\displaystyle\left\|\widehat{B}^{nn}_{3}-\rho_{n}P_{n}^{T}S_{3}BS_{3}P_{n}\right\|_{2}=\left\|\frac{1}{n^{2}}\left[\widehat{Z}^{T}A\widehat{Z}\right]_{+}-\rho_{n}P_{n}^{T}\widetilde{\Sigma}\widetilde{B}\widetilde{\Sigma}P_{n}\right\|_{2}$
$\displaystyle\leq\sqrt{k}\left\|\frac{1}{n^{2}}\widehat{Z}^{T}A\widehat{Z}-\rho_{n}\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{\Sigma}_{P}\right\|_{2}(\text{Proposition
\ref{prop:projection} and Lemma \ref{lemma:norm2}})$
$\displaystyle\leq\sqrt{k}\left\|\frac{1}{n^{2}}\widehat{Z}^{T}A\widehat{Z}-\frac{1}{n^{2}}\widehat{Z}^{T}\mathscr{A}\widehat{Z}\right\|_{2}+\sqrt{k}\left\|\frac{1}{n^{2}}\widehat{Z}^{T}\mathscr{A}\widehat{Z}-\rho_{n}\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{\Sigma}_{P}\right\|_{2}$
$\displaystyle=\frac{\sqrt{k}}{n^{2}}\left\|\widehat{Z}^{T}(A-\mathscr{A})\widehat{Z}\right\|_{2}+\sqrt{k}\rho_{n}\left\|\frac{1}{n^{2}}\widehat{Z}^{T}\widetilde{Z}_{P}\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}-\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{\Sigma}_{P}\right\|_{2}$
$\displaystyle\leq\frac{\sqrt{k}}{n^{2}}\left\|\widehat{Z}^{T}(A-\mathscr{A})\widehat{Z}\right\|_{2}+\sqrt{k}\rho_{n}\left\|\frac{1}{n^{2}}\widehat{Z}^{T}\widetilde{Z}_{P}\widetilde{B}_{P}\widetilde{Z}^{T}_{P}\widehat{Z}-\frac{1}{n}\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}\right\|_{2}+\sqrt{k}\rho_{n}\left\|\frac{1}{n}\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}-\widetilde{\Sigma}_{P}\widetilde{B}_{P}\widetilde{\Sigma}_{P}\right\|_{2}$
$\displaystyle\leq\frac{\sqrt{k}}{n^{2}}\left\|\widehat{Z}^{T}(A-\mathscr{A})\widehat{Z}\right\|_{2}+\frac{\sqrt{k}\rho_{n}}{n^{2}}\left\|\left(\widehat{Z}^{T}\widetilde{Z}_{P}-n\widetilde{\Sigma}_{P}\right)\widetilde{B}_{P}\widetilde{Z}_{P}^{T}\widehat{Z}\right\|_{2}+\frac{\sqrt{k}\rho_{n}}{n}\left\|\widetilde{\Sigma}_{P}\widetilde{B}_{P}\left(\widetilde{Z}_{P}^{T}\widehat{Z}-n\widetilde{\Sigma}_{P}\right)\right\|_{2}$
$\displaystyle\leq\frac{\sqrt{k}}{n^{2}}\left\|\widehat{Z}\right\|_{2}^{2}\left\|A-\mathscr{A}\right\|_{2}+\frac{\sqrt{k}\rho_{n}}{n^{2}}\left\|\widehat{Z}^{T}\widetilde{Z}_{P}-n\widetilde{\Sigma}_{P}\right\|_{2}\left\|\widetilde{B}_{P}\right\|_{2}\left\|\widetilde{Z}_{P}\right\|_{2}\left\|\widehat{Z}\right\|_{2}$
$\displaystyle\qquad+\frac{\rho_{n}}{n}\left\|\widetilde{\Sigma}_{P}\widetilde{B}_{P}\right\|_{2}\left\|\left(\widehat{Z}^{T}\widetilde{Z}_{P}-n\widetilde{\Sigma}_{P}\right)^{T}\right\|_{2}$
$\displaystyle\leq\frac{1}{n^{2}}O_{p}\left(n\right)O_{p}\left(n\rho_{n}e_{n}\right)+\frac{\rho_{n}}{n^{2}}O_{p}\left(ne_{n}\right)O_{p}\left(1\right)O_{p}\left(n^{.5}\right)O_{p}\left(n^{.5}\right)+\frac{\rho_{n}}{n}O_{p}\left(1\right)O_{p}\left(ne_{n}\right)$
$\displaystyle\qquad(\text{Lemma \ref{lemma:norm2} to Lemma
\ref{lemma:hatZZ_Sigma}})$ $\displaystyle=O_{p}\left(\rho_{n}e_{n}\right)$

###  I.3 Proof of Lemma I.2 to I.7

####  I.3.1 Proof of Lemma I.2, I.3, and I.4

Lemma I.3 and Equation (73) in Lemma I.2 are assumptions in Theorem 4.1.
Equation (74) in Lemma I.2 holds by Proposition I.3. Lemma I.4 is evident
given that $C$, $B$ are fixed matrix and $P_{n}\in\mathscr{P}(k)$.

####  I.3.2 Proof of Lemma I.5

######  Lemma I.8.

(Matrix Bernstein Inequality [Tropp, 2012]) Let $X_{1},X_{2},\cdots,X_{n}$ be
independent random $n\times n$ symmetric matrix. Assume
$\|X_{i}-\mathbb{E}(X_{i})\|_{2}\leq M,\forall i$. Write
$v^{2}=\|\sum_{i}Var(X_{i})\|_{2}$, $X=\sum_{i}X_{i}$. Then for any $a>0$,

$\mathbb{P}(\|X-\mathbb{E}(X)\|_{2}\geq a)\leq
2n\exp\left(-\frac{a^{2}}{2v^{2}+2Ma/3}\right)$

Let $\widetilde{Z}_{i}$ be the $i$th row of $\widetilde{Z}$. Define
$X_{i}=\widetilde{Z}_{i}^{T}\widetilde{Z}_{i}$, $X=\sum_{i}X_{i}$. Notice that
$X_{i}$ are independently identically distributed and
$X=\widetilde{Z}^{T}\widetilde{Z}$. Since $Z_{ij}$ follows bounded
distribution and $C$ is a fixed scaling matrix. There exist constants
$C_{1},C_{2}$ such that $\widetilde{Z}_{1j}^{2}\leq C_{1},\
Var(\widetilde{Z}_{1j}^{2})\leq C_{2},\ \forall j\in[k]$. Therefore,

$\|X_{i}-E(X_{i})\|_{2}=\left\|X_{i}-\widetilde{\Sigma}\right\|_{2}\leq
C_{1},$ $\displaystyle v^{2}$
$\displaystyle=\left\|\sum_{i}Var(X_{i})\right\|_{2}$
$\displaystyle=n\|Var(X_{1})\|_{2}$
$\displaystyle=n\max_{j}Var(\widetilde{Z}_{1j}^{2})$ $\displaystyle\leq
nC_{2}.$

Denote ${\mathbb{E}}\left(\widetilde{Z}_{i}^{T}\widetilde{Z}_{i}\right)$ as
$\mathscr{Z}$, then by Lemma I.8,

$\mathbb{P}\left(\left\|\widetilde{Z}^{T}\widetilde{Z}-n\mathscr{Z}\right\|_{2}\geq
a\right)\leq 2k\exp\left(-\frac{a^{2}}{2nC_{2}+2C_{1}a/3}\right).$

This implies
$\left\|\widetilde{Z}^{T}\widetilde{Z}-n\mathscr{Z}\right\|_{2}=O_{p}\left(n^{.5}\right)$,
thus

$\displaystyle\left\|\widetilde{Z}\right\|_{2}$
$\displaystyle=\sqrt{\left\|\widetilde{Z}^{T}\widetilde{Z}\right\|_{2}}$
$\displaystyle\leq\sqrt{\left\|\widetilde{Z}^{T}\widetilde{Z}-n\mathscr{Z}\right\|_{2}+\left\|n\mathscr{Z}\right\|_{2}}$
$\displaystyle=\sqrt{O_{p}\left(n^{.5}\right)+O_{p}\left(n\right)}$
$\displaystyle=O_{p}\left(n^{.5}\right).$

Since $\widetilde{Z}_{P}=\widetilde{Z}P_{n}$,
$\left\|\widetilde{Z}_{P}\right\|_{2}=O_{p}(n^{.5})$

####  I.3.3 Proof of Lemma I.6

######  Lemma I.9.

(Equation 1.1 in [El Ghaoui, 2002]) For $M,\ \Delta
M\in\mathbb{R}^{p_{1}\times p_{1}}$, $\det M\neq 0$, $\det(M+\Delta M)\neq 0$,
then

$\left\|(M+\Delta
M)^{-1}-M^{-1}\right\|_{2}\leq\left\|M^{-1}\right\|^{2}_{2}\left\|\Delta
M\right\|_{2}$

The proof of Lemma I.5 implies

$\left\|\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}/n-\mathscr{Z}_{P}\right\|_{2}=O_{p}\left(n^{-.5}\right),$
(75)

where
$\mathscr{Z}_{P}=P_{n}^{T}\mathscr{Z}P_{n}={\mathbb{E}}(\widetilde{Z}^{T}_{P}\widetilde{Z}_{P}/n)$.
Also,

$\displaystyle\left\|\widehat{Z}_{+}\right\|_{2}$
$\displaystyle\leq\left\|\widehat{Z}_{+}-\widetilde{Z}_{P}\right\|_{2}+\left\|\widetilde{Z}_{P}\right\|_{2}$
$\displaystyle\leq\sqrt{n}\left\|\widehat{Z}_{+}-\widetilde{Z}_{P}\right\|_{2\rightarrow\infty}+\left\|\widetilde{Z}_{P}\right\|_{2}$
$\displaystyle=O_{p}\left(n^{.5}e_{n}\right)+O_{p}\left(n^{.5}\right)$
$\displaystyle=O_{p}\left(n^{.5}\right),$

and

$\displaystyle\left\|\widehat{\Sigma}-\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}\right\|_{2}$
$\displaystyle=\left\|\widehat{Z}_{+}^{T}\widehat{Z}_{+}-\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}\right\|_{2}$
$\displaystyle\leq\left\|\widehat{Z}_{+}^{T}\widehat{Z}_{+}-\widehat{Z}^{T}_{+}\widetilde{Z}_{P}\right\|_{2}+\left\|\widehat{Z}_{+}^{T}\widetilde{Z}_{P}-\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}\right\|_{2}$
$\displaystyle\leq\left\|\widehat{Z}_{+}\right\|_{2}\left\|\widehat{Z}_{+}-\widetilde{Z}_{P}\right\|_{2}+\left\|\widehat{Z}_{+}-\widetilde{Z}_{P}\right\|_{2}\left\|\widetilde{Z}_{P}\right\|_{2}$
$\displaystyle\leq
O_{p}\left(n^{.5}\right)O_{p}\left(n^{.5}e_{n}\right)+O_{p}\left(n^{.5}e_{n}\right)O_{p}\left(n^{.5}\right)$
$\displaystyle\leq O_{p}\left(n\right).$

Equation (75) implies that for $\forall\epsilon>0$, $\exists\ C_{\epsilon}$
such that

$\sup_{n}\mathbb{P}\left(\left\|\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}/n-\mathscr{Z}_{P}\right\|_{2}\geq
C_{\epsilon}n^{-.5}\right)<\epsilon.$

Therefore by Weyl’s inequality,

$\left\|\left(\widetilde{Z}^{T}_{P}\widetilde{Z}_{P}/n\right)^{-1}\right\|_{2}=O_{p}(1),\
\left\|\left(\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}\right)^{-1}\right\|_{2}=O_{p}\left(n^{-1}\right).$

By Lemma I.9,

$\displaystyle\left\|\widehat{\Sigma}^{-1}\right\|_{2}$
$\displaystyle\leq\left\|\widehat{\Sigma}^{-1}-\left(\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}\right)^{-1}\right\|_{2}+\left\|\left(\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}\right)^{-1}\right\|_{2}$
$\displaystyle\leq\left\|\left(\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}\right)^{-1}\right\|_{2}^{2}\left\|\widehat{\Sigma}-\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}\right\|_{2}+O_{p}\left(n^{-1}\right)$
$\displaystyle\leq
O_{p}\left(n^{-2}\right)O_{p}\left(n\right)+O_{p}\left(n^{-1}\right)$
$\displaystyle=O_{p}\left(n^{-1}\right).$

Therefore

$\left\|\widehat{\Sigma}^{-1}\widehat{Z}_{+}^{T}\right\|_{2}\leq\left\|\widehat{\Sigma}^{-1}\right\|_{2}\left\|\widehat{Z}_{+}\right\|_{2}\leq
O_{p}\left(n^{-.5}\right)$

####  I.3.4 Proof of Lemma I.7

This is a direct result of Lemma I.1, Lemma I.2, and Lemma I.5.

$\displaystyle\left\|\widehat{Z}_{+}^{T}\widetilde{Z}_{P}-n\widetilde{\Sigma}_{P}\right\|_{2}$
$\displaystyle=\left\|\widehat{Z}_{+}^{T}\widetilde{Z}_{P}-\widetilde{Z}_{P}^{T}\widetilde{Z}_{P}\right\|_{2}=\left\|\widehat{Z}_{+}-\widetilde{Z}_{P}\right\|_{2}\left\|\widetilde{Z}_{P}\right\|_{2}$
$\displaystyle\leq\sqrt{n}\left\|\widehat{Z}_{+}-\widetilde{Z}_{P}\right\|_{2\rightarrow\infty}\left\|\widetilde{Z}_{P}\right\|_{2}$
$\displaystyle=O_{p}(n^{.5}e_{n})O_{p}(n^{.5})$ $\displaystyle=O_{p}(ne_{n}).$

###  I.4 Stableness of NJ

To discuss the performance of NJ, we remove the identifiability assumption in
Remark 2.3, which constrains all internal nodes to have degree $\geq 3$, and
consider ${\mathbb{T}}$ as any general tree graph. Given ${\mathbb{T}}=(V,E)$,
distance-based recovery methods take the pairwise distances $\widehat{D}$
between a subset of nodes $V_{o}\subseteq V$ as input, and reconstruct a tree
structure $\widehat{\mathbb{T}}=\left(\widehat{V},\widehat{E}\right)$. We
refer to nodes in $V_{o}$ as “observed nodes” since the distance information
between them is observed. The reconstructed tree $\widehat{\mathbb{T}}$ should
always contain all the observed nodes, i.e., $V_{o}\subseteq\widehat{V}$. We
say two trees ${\mathbb{T}}=(V,E)$ and
$\widehat{\mathbb{T}}=\left(\widehat{V},\widehat{E}\right)$ are equivalent,
written as ${\mathbb{T}}\sim\widehat{\mathbb{T}}$, if there exists an
isomorphism mapping $f:V\rightarrow\widehat{V}$ that preserves adjacency
structure, that is, $\widehat{E}=\left\\{(f(u),f(v)):(u,v)\in E\right\\}$, and
the observed nodes, that is, $f(u)=u$ for any $u\in V_{o}$.

When ${\mathbb{T}}$ and $\widehat{\mathbb{T}}$ are not equivalent, it is
important to have a measure of the proximity between them. To this end, we
introduce the definition of “split” following [Bandelt and Dress, 1986,
Atteson, 1997]. This definition is formulated with respect to the observed set
$V_{o}$.

######  Definition 26.

Let ${\mathbb{T}}=(V,E)$ be a tree with an observed set $V_{o}$. Removing an
edge $e\in E$ from ${\mathbb{T}}$ splits it into two components. Denote
$s({\mathbb{T}}-e,V_{o})$ as how nodes in $V_{o}$ are distributed between
these two components, then $s({\mathbb{T}}-e,V_{o})$ is the split of edge $e$.
Let $S({\mathbb{T}},V_{o})$ be the set of all the splits in tree
${\mathbb{T}}$, i.e., $S({\mathbb{T}},V_{o})=\\{s({\mathbb{T}}-e,V_{o}):e\in
E\\}$.

######  Proposition I.4.

(Bandelt and Dress [1986]) If $\\{v\in V:deg(v)<3\\}\subseteq V_{o}$ and
$\left\\{v\in\widehat{V}:deg(v)<3\right\\}\subseteq V_{o}$, then
$S\left({\mathbb{T}},V_{o}\right)=S\left(\widehat{\mathbb{T}},V_{o}\right)\text{
if and only if }\ {\mathbb{T}}\sim\widehat{\mathbb{T}}.$

When $V_{o}$ contains all the nodes with degree smaller than three, the splits
of a tree ${\mathbb{T}}$ completely parametrize its topology. When
$S({\mathbb{T}},V_{o})=S\left(\widehat{\mathbb{T}},V_{o}\right)$, two trees
are equivalent; when $S({\mathbb{T}},V_{o})\neq
S\left(\widehat{\mathbb{T}},V_{o}\right)$, the cardinality of their
interaction set provides reasonable measure about how close
$\widehat{\mathbb{T}}$ and ${\mathbb{T}}$ are to each other. For example, the
popular Robinson-Foulds distance [Robinson and Foulds, 1981] calculates the
number of splits that differ in $S({\mathbb{T}},V_{o})$ and
$S\left(\widehat{\mathbb{T}},V_{o}\right)$.

######  Definition 27.

For a tree ${\mathbb{T}}=(V,E)$ and an estimation
$\widehat{\mathbb{T}}=\left(\widehat{V},\widehat{E}\right)$. We say
$\widehat{\mathbb{T}}$ correctly reconstruct edge $e\in E$ if there exists an
edge $e^{\prime}\in\widehat{E}$ such that
$s({\mathbb{T}}-e,V_{o})=s\left(\widehat{\mathbb{T}}-e^{\prime},V_{o}\right)$.

####  I.4.1 Proof for Theorem 4.2

The proof of Theorem 4.2 is established using Lemma I.10, which is an
extension of Theorem 23 in [Mihaescu et al., 2009] to allow $V_{o}$ to contain
non-leaf nodes.

######  Lemma I.10.

Given any tree ${\mathbb{T}}=(V,E)$ and the estimated pairwise distances
$\widehat{D}$ between nodes in $V_{o}\subseteq V$, let
$\delta=\max_{u,v}\left|\widehat{D}_{uv}-D_{uv}\right|$. If $\\{i\in
V:deg(i)<3\\}\subseteq V_{o}$, then NJ correctly reconstruct any edge
$e=(u,v)$ with

$d(u,v)>4\delta,$

where $d(\cdot,\cdot)$ is the true edge distances in ${\mathbb{T}}$.

###### Proof.

According to Theorem 23 in [Mihaescu et al., 2009], Lemma I.10 is valid when
$V_{o}=V_{\ell}$, and all internal nodes in ${\mathbb{T}}$ have degrees $\geq
3$. To remove these restrictions, we introduce another tree
$\widetilde{\mathbb{T}}=\left(\widetilde{V},\widetilde{E}\right)$ and its
corresponding true distance $\widetilde{d}(\cdot,\cdot)$ by converting all
internal nodes in $V_{o}$ to leaf nodes with zero edge weights. Initially, we
set $\widetilde{\mathbb{T}}={\mathbb{T}}$, and
$\widetilde{d}(\cdot,\cdot)=d(\cdot,\cdot)$. Then, we remove all nodes $u\in
V_{o}\setminus V_{\ell}$ by relabeling them as $\widetilde{u}$ in
$\widetilde{\mathbb{T}}$ and $\widetilde{d}(\cdot,\cdot)$. Subsequently, we
add all $u\in V_{o}\setminus V_{\ell}$ back as leaf nodes by updating

$\widetilde{V}\leftarrow\widetilde{V}\cup\\{u:u\in V_{o}\setminus
V_{\ell}\\},\quad\widetilde{E}=E\cup\\{(\widetilde{u},u):u\in V_{o}\setminus
V_{\ell}\\},\quad\text{and
}\widetilde{d}\left(\widetilde{u},u\right)=0,\,\text{for }\forall u\in
V_{o}\setminus V_{\ell}.$

After this process, all internal nodes in $\widetilde{\mathbb{T}}$ have degree
$\geq 3$, and the set of leaf nodes in $\widetilde{\mathbb{T}}$ is identical
to the set of observed nodes in ${\mathbb{T}}$.

∎

Let $\widehat{\mathbb{T}}_{nj}=\left(\widehat{V}_{nj},\widehat{E}_{nj}\right)$
with $\left\\{\widehat{d}(u,v):(u,v)\in\widehat{E}_{nj}\right\\}$ be the
output of the NJ algorithm. By Lemma I.10, for any edge $e\in E$, there exists
an edge $e^{\prime}\in\widehat{E}_{nj}$ such that

$S({\mathbb{T}}-e,V_{o})=S\left(\widehat{\mathbb{T}}_{nj}-e^{\prime},V_{o}\right).$

To better analyze the performance of NJ, it is essential to gain an intuitive
understanding of the structure of $\widehat{\mathbb{T}}_{nj}$. Firstly,
$\widehat{\mathbb{T}}_{nj}$ is a binary tree where all nodes in $V_{o}$ are
labeled as leaf nodes, resulting in $\widehat{E}_{nj}$ typically containing
more edges than $E$. We can classify edges in $\widehat{E}_{nj}$ into two
types. The first type is those correctly reconstructed edges, they create the
same splits as some edge in $E$; the second type is the wrongly reconstructed
edges, they create splits that differ from all edges in $E$. In the following
paragraphs, we abuse the notation a little bit, for two edges $e\in E$ and
$e^{\prime}\in\widehat{E}_{nj}$ that create the same splits, we denote both of
them as $e$. In other word, for any edge $e\in\widehat{E}_{nj}$, if we say
$e\in E$, that means $e$ is corrected reconstructed.

While Lemma I.10 implies that all edges in $E$ can be correctly reconstructed
by NJ, we want to further study the estimated edge distances $\widehat{d}$.
However, the topology structure of ${\mathbb{T}}$ and
$\widehat{\mathbb{T}}_{nj}$ are different, creating difficulties to compare
$\widehat{d}$ and $d$. To this end, we construct a set of edge distances
$\left\\{\widetilde{d}(e):e\in\widehat{E}_{nj}\right\\}$ for tree
$\widehat{\mathbb{T}}_{nj}$ to serve as a bridge between $\widehat{d}$ and
$d$. Specifically,

$\widetilde{d}(e)\begin{dcases}d(e)&\text{ if $e\in E$ ($e$ is correctly
reconstructed), }\\\ 0&\text{ otherwise.}\end{dcases}$ (76)

Then $\widetilde{d}(u,v)=d(u,v)$ for any pair of nodes $(u,v)\in V_{o}$. Now,
we can consider $\widehat{\mathbb{T}}_{nj}$ and $\widetilde{d}$ (instead of
${\mathbb{T}}$ and $d$) as the underlying truth and study how $\widehat{d}$
differs from $\widetilde{d}$.

To analyze how errors propagate at each step, we follow the procedure in
[Atteson, 1997] to create a series of ground truth trees
$\left\\{{\mathbb{T}}^{(t)}\right\\}_{t=1}^{k-2}$ and their corresponding
distances $\left\\{d^{(t)}\right\\}_{t=1}^{k-2}$. To accommodate cases where
${\mathbb{T}}$ is not binary and $V_{o}$ may contain non-leaf nodes, we set
${\mathbb{T}}^{(1)}$ to be $\widehat{\mathbb{T}}_{nj}$ and $d^{(1)}$ to be
$\widetilde{d}$. Further details can be found in Lemma 6 of [Atteson, 1997].
Lemma I.11 below shows that the errors in the estimated distances do not
accumulate through iterations.

######  Lemma I.11.

(Lemma 7 in Atteson [1997]) Estimation error of pairwise distance doesn’t
accumulate through iteration

$\max_{i^{\prime},j^{\prime}}\left|\widehat{d}^{(t)}(i^{\prime},j^{\prime})-d^{(t)}(i^{\prime},j^{\prime})\right|\leq\max_{i,j}\left|\widehat{d}^{(1)}(i,j)-d^{(1)}(i,j)\right|=\delta,\
\forall t\geq 1$

Now we can assess the error in the estimated distances. Since the edge lengths
in $\widehat{\mathbb{T}}_{nj}$ are estimated using Equation (63) or (64), we
only need to focus on these two equations. For Equation (63), it’s important
to note that $x^{(t)}$ are different for each iterations $t$, thus the last
summation term can have at most one non-zero entry. Assuming the $h$th term is
non-zero, then the estimated distance becomes:

$\widehat{d}\left(i^{(t)},x^{(t)}\right)=\frac{1}{2}\,\left(\widehat{d}^{(t)}\left(i^{(t)},j^{(t)}\right)+\,\widehat{d}^{(t)}_{-j}\left(i^{(t)}\right)-\,\widehat{d}^{(t)}_{-i}\left(j^{(t)}\right)-\,\widehat{d}^{(h)}\left(i^{(h)},j^{(h)}\right)\right),$

Then the error term

$\displaystyle\left|\widehat{d}\left(i^{(t)},x^{(t)}\right)-\widetilde{d}\left(i^{(t)},x^{(t)}\right)\right|$
$\displaystyle=\frac{1}{2}\left|\left(\widehat{d}^{(t)}\left(i^{(t)},j^{(t)}\right)+\,\widehat{d}^{(t)}_{-j}\left(i^{(t)}\right)-\,\widehat{d}^{(t)}_{-i}\left(j^{(t)}\right)-\,\widehat{d}^{(h)}\left(i^{(h)},j^{(h)}\right)\right)\right.$
$\displaystyle\qquad\left.-\left(d^{(t)}\left(i^{(t)},j^{(t)}\right)+\,d^{(t)}_{-j}\left(i^{(t)}\right)-\,d^{(t)}_{-i}\left(j^{(t)}\right)-\,d^{(h)}\left(i^{(h)},j^{(h)}\right)\right)\right|$
$\displaystyle\leq\frac{1}{2}\left\\{\left|\widehat{d}\left(i^{(t)},x^{(t)}\right)-d\left(i^{(t)},x^{(t)}\right)\right|+\left|\widehat{d}^{(t)}_{-j}\left(i^{(t)}\right)-d^{(t)}_{-j}\left(i^{(t)}\right)\right|\right.$
$\displaystyle\qquad\left.+\left|\widehat{d}^{(t)}_{-i}\left(j^{(t)}\right)-d^{(t)}_{-i}\left(j^{(t)}\right)\right|+\left|\widehat{d}^{(h)}\left(i^{(h)},j^{(h)}\right)-d^{(h)}\left(i^{(h)},j^{(h)}\right)\right|\right\\}$
$\displaystyle\leq 2\delta\text{ (by lemma
\ref{lemma:error_not_accumulate})},$

where $d^{(t)}_{-j}\left(i^{(t)}\right)$ is the corresponding mean for the
true distances, that is,

$d^{(t)}_{-j}\left(i^{(t)}\right)=\frac{1}{k-t-1}\sum_{\scaleto{u\,\in\,\left.V^{(t)}_{o}\middle\backslash\left\\{i^{(t)},j^{(t)}\right\\}\right.}{18pt}}d^{(t)}\left(i^{(t)},u\right).$

By similar steps, we can show
$\left|\widehat{d}\left(i^{(t)},x^{(t)}\right)-\widetilde{d}\left(i^{(t)},x^{(t)}\right)\right|\leq
3/2\delta$ for Equation (64). Therefore,
$\left|\widehat{d}(e)-\widetilde{d}(e)\right|\leq 2\delta$ holds for any edge
$e\in\widehat{E}_{nj}$.

For any edge $e\in E$, $\widetilde{d}(e)=d(e)>4\delta$, by triangle
inequality,

$\widehat{d}(e)\geq\widetilde{d}(e)-\left|\widehat{d}(e)-\widetilde{d}(e)\right|>4\delta-2\delta=2\delta.$

Similarly, for any $e_{0}\notin E$ but $e_{0}\in\widehat{\mathbb{T}}_{nj}$,
then $\widetilde{d}(e_{0})=0$,

$\widehat{d}(e_{0})\leq\widetilde{d}(e_{0})+\left|\widehat{d}(e)-\widetilde{d}(e)\right|\leq
0+2\delta=2\delta.$

####  I.4.2 Proof for Corollary 4.2.1

This is a direct result of Theorem 4.2 and Proposition I.4.

###  I.5 Proof of Theorem 4.3

The proof mainly relies on the consistency result in Theorem 4.1 and Theorem
4.2. The major component of the proof is showing that conditions in these two
theorems are satisfied in the context of Theorem 4.3.

The convergence of $\widehat{D}$ is a direct result of Lemma I.12, I.13, and
Theorem 4.1 (with $e_{n}=\Delta_{n}^{-.24}\log^{2.75}n$).

######  Lemma I.12.

Consider $\widehat{Z}$ being the output of Algorithm 5, then there exists a
series of reordering matrix $P_{n}\in\mathscr{P}(k)$ and a fixed diagonal
matrix $C$ such that

$\left\|\widehat{Z}-\widetilde{Z}CP_{n}\right\|_{2\rightarrow\infty}=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n).$

######  Lemma I.13.

$\left\|A-\mathscr{A}\right\|_{2}=O_{p}(n\rho_{n}\Delta_{n}^{-.24}\log^{2.75}n)$.

To demonstrate the consistency of $\widehat{\mathbb{T}}_{z}$, we apply Theorem
4.2 to tree ${\mathbb{T}}_{z}$ with the observed set being $V_{z}$. We would
like to verify that the two conditions in Theorem 4.2 are satisfied.

The first condition requires $V_{z}$ to contain all nodes with degree $<3$ in
${\mathbb{T}}_{z}$. If $u$ is a node in ${\mathbb{T}}_{z}$ such that $u\notin
V_{z}$ and $deg(u)<3$, then $u$ is also an internal node of ${\mathbb{T}}$
such that $deg(u)<3$, as the creation of ${\mathbb{T}}_{z}$ from
${\mathbb{T}}$ only affects nodes in $V_{\ell}\cup V_{z}$. This contradicts
our assumption that all internal nodes in ${\mathbb{T}}$ are of degree $>3$.
The second condition requires $\min_{e}d(e)>4\delta$. By the convergence of
$\widehat{D}$, this condition holds with a probability that goes to one.

Now we want to show that the cutoff value is chosen properly. For any cutoff
value $\varphi$ that grows faster than the convergence rate of $\widehat{D}$,

${\mathbb{P}}\left(\varphi>2\delta\right)\xrightarrow{n\rightarrow\infty}1.$
(77)

Since $d(e)>0$ for any edges $e\in E$, by the convergence of $\widehat{D}$ and
the fact that $\varphi\rightarrow 0$,

${\mathbb{P}}\left(\min_{e\in
E}\widehat{d}(e)>\varphi\right)\xrightarrow{n\rightarrow\infty}1$ (78)

Notice that $2\delta\geq\max_{e_{0}\in\widehat{E}\setminus
E}\widehat{d}(e_{0})$. Together Equation (77) and (78) implies that

${\mathbb{P}}\left(\min_{e\in
E}\widehat{d}(e)>\varphi>\max_{e_{0}\in\widehat{E}\setminus
E}\widehat{d}(e_{0})\right)\xrightarrow{n\rightarrow\infty}1.$

This means by applying the shrinking step in the SparseNJ algorithm, all
wrongly recovered edges are deleted with a probability that goes to one. Then
by Proposition I.4, we have

${\mathbb{P}}\left(\widehat{\mathbb{T}}_{z}\sim{\mathbb{T}}_{z}\right)\xrightarrow{n\rightarrow\infty}1.$

The consistency of $\widehat{\mathbb{T}}_{z}$, together with Lemma I.12,
implies the consistency of $\widehat{\mathbb{T}}$.

####  I.5.1 Proof of Lemma I.12 (Consistency of $\widehat{Z}$ after the Sign
Flipping Step)

In this proof, we use $\widehat{Z}$ to denote $UR_{U}$ (without sign flip) and
$\widehat{Z}_{D}$ to denote $\widehat{Z}\widehat{D}$ (with sign flip) in
Algorithm 5. We would like to show

$\left\|\widehat{Z}_{D}-\widetilde{Z}P_{n}\right\|_{2\rightarrow\infty}=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n).$

By Corollary C.1 in [Rohe and Zeng, 2022],

$\left\|\widehat{Z}-\widetilde{Z}P_{n}^{sign}\right\|_{2\rightarrow\infty}=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n)$
(79)

where $P^{sign}_{n}$ is a series of permutation matrix that allows sign flip,
i.e., $P^{sign}_{n}\in\mathscr{P}^{sign}(k)=\\{P\in{\mathbb{R}}^{k\times
k}:P^{T}P=PP^{T}=I_{k\times k},\ P_{ij}\in\\{0,-1,1\\}\\}$. Therefore we only
need to deal with the fluctuation caused by the sign adjustment in Algorithm
5.

Decompose $P_{n}^{sign}=P_{n}D_{n}$, where $D_{n}$ is a series of diagonal
matrix with elements in $\\{-1,1\\}$ and $P_{n}\in\mathcal{P}(k)$. Then
$D_{n}$ performs the sign flip and $P_{n}$ reorders the columns, by Equation
(79),

$\left\|\widehat{Z}D_{n}-\widetilde{Z}P_{n}\right\|_{2\rightarrow\infty}=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n).$

Let $\widehat{\mu}_{j}=\sum_{j}\widehat{Z}_{ij}/n$,
$\mu_{j}=\sum_{j}\left[\widetilde{Z}P_{n}\right]_{ij}/n$,
$\widehat{d}_{j}=\text{sgn}(\widehat{\mu}_{j})$,
$d_{j}=\left[D_{n}\right]_{jj}$. We drop the subscript $n$ for simplicity
here.

Since $\|\cdot\|_{2\rightarrow\infty}$ corresponds to the maximum row-wise
Euclidean norm,

$\left|\widehat{\mu}_{j}d_{j}-\mu_{j}\right|=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n).$
(80)

Notice that $\mu_{j}\geq 0$ by definition, and
$\widehat{\mu}_{j}\widehat{d}_{j}\geq 0$,

$\left|\widehat{\mu}_{j}\widehat{d}_{j}-\mu_{j}\right|\leq\left|\widehat{\mu}_{j}d_{j}-\mu_{j}\right|=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n).$
(81)

By Equation (80) and (81),

$\left|\widehat{\mu}_{j}\widehat{d}_{j}-\widehat{\mu}_{j}d_{j}\right|=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n).$
(82)

Since $\widetilde{Z}_{ij}$ are bounded, $|\mu_{j}d_{j}|=O_{p}(1)$. By Equation
(80),
$\left|\widehat{\mu}_{j}-\mu_{j}d_{j}\right|=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n)$.
These imply $|\widehat{\mu}_{j}|=O_{p}(1)$. Then by Equation (82),

$\left|\widehat{d}_{j}-d_{j}\right|=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n).$
(83)

Define $\widehat{D}_{n}$ to be a series of diagonal matrix with
$[\widehat{D}_{n}]_{jj}=\widehat{d}_{j}$, this implies

$\left\|\widehat{D}_{n}-D\right\|_{2}=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n).$
(84)

Now we can show

$\displaystyle\left\|\widehat{Z}\widehat{D}_{n}-\widetilde{Z}P_{n}\right\|_{2\rightarrow\infty}$
$\displaystyle\leq\left\|\widehat{Z}\widehat{D}_{n}-\widehat{Z}D_{n}\right\|_{2\rightarrow\infty}+\left\|\widehat{Z}D_{n}-\widetilde{Z}P_{n}\right\|_{2\rightarrow\infty}$
(85)
$\displaystyle\leq\left\|\widehat{Z}\right\|_{2\rightarrow\infty}\left\|\widehat{D}_{n}-D\right\|_{2}+O_{p}(\Delta^{-.24}\log^{2.75}n)$
(86)
$\displaystyle=O_{p}(1)O_{p}(\Delta_{n}^{-.24}\log^{2.75}n)+O_{p}(\Delta_{n}^{-.24}\log^{2.75}n)$
(87) $\displaystyle=O_{p}(\Delta_{n}^{-.24}\log^{2.75}n).$ (88)

$\left\|\widehat{Z}\right\|_{2\rightarrow\infty}=O_{p}(1)$ because
$\left\|\widetilde{Z}P_{n}^{sign}\right\|_{2\rightarrow\infty}=O_{p}(1)$ and
Equation (79), the second step follows from a basic property of
$\|\cdot\|_{2\rightarrow\infty}$. (see Proposition 6.5. in [Cape et al.,
2019])

This shows that the sign adjustment step does not affect the asymptotic
behavior of $\widehat{Z}$. The result for $\widehat{Z}_{+}$ follows from
Proposition I.3.

####  I.5.2 Proof of Lemma I.13

By Lemma G.4 in Rohe and Zeng [2022],