# Generation Matrix: An Embeddable Matrix Representation for Hierarchical
Trees

Jianping Cai<EMAIL_ADDRESS>Ximeng Liu<EMAIL_ADDRESS>Jiayin Li
<EMAIL_ADDRESS>Shuangyue Zhang<EMAIL_ADDRESS>College of
Computer and Data Science, Fuzhou University, Fuzhou 350108, China  College of
information and Smart Electromechanical Engineering, Xiamen Huaxia University,
Xiamen 361024, China

###### Abstract

Starting from the local structures to study hierarchical trees is a common
research method. However, the cumbersome analysis and description make the
naive method challenging to adapt to the increasingly complex hierarchical
tree problems. To improve the efficiency of hierarchical tree research, we
propose an embeddable matrix representation for hierarchical trees, called
Generation Matrix. It can transform the abstract hierarchical tree into a
concrete matrix representation and then take the hierarchical tree as a whole
to study, which dramatically reduces the complexity of research. Mathematical
analysis shows that Generation Matrix can simulate various recursive
algorithms without accessing local structures and provides a variety of
interpretable matrix operations to support the research of hierarchical trees.
Applying Generation Matrix to differential privacy hierarchical tree release,
we propose a Generation Matrix-based optimally consistent release algorithm
(GMC). It provides an exceptionally concise process description so that we can
describe its core steps as a simple matrix expression rather than multiple
complicated recursive processes like existing algorithms. Our experiments show
that GMC takes only a few seconds to complete a release for large-scale
datasets with more than $10$ million nodes. The calculation efficiency is
increased by up to $100$ times compared with the state-of-the-art schemes.

###### keywords:

Generation Matrix, Matrix Representation, Hierarchical Tree, Differential
Privacy, Consistency

###### MSC:

[2020] 05C62 , 05C05

label3label3footnotetext: This work was supported in part by the National
Natural Science Foundation of China (project numbers 62072109 and U1804263).

##  1 Introduction

As a fundamental data structure, hierarchical trees are widely used in
different areas, including file systems [1], census [2], evolution [3], etc.
For example, in the U.S. Census Bureau’s plan to apply differential privacy to
protect privacy[2], designing a novel hierarchical tree releasing algorithm is
one of the important challenges[4]. The scale of the census data is so large
that we can organize them into a hierarchical tree with more than 10 million
nodes. Hence, the hierarchical tree release algorithms must be specially
designed and highly efficient to ensure the timely release of such large-scale
data. However, the design of efficient algorithms usually requires a large
amount of hierarchical tree research as a theoretical basis.

Most hierarchical tree research works naturally regard the hierarchical tree
as a collection of nodes and relationships. Starting from the perspective of
individual nodes and local relationships to study hierarchical trees is a
common research method, called Naive Research Method. Empirically, Naive
Research Method often leads to overly cumbersome analysis and abstract
algorithm descriptions, mainly reflected in two aspects. On the one hand,
hierarchical trees contain rich relationships, such as father, son, ancestor,
descendant, sibling, or cousin, but these relationships usually lack a
concrete enough description. When multiple node relationships occur in an
algorithm simultaneously, the intricate node relationships will make the
algorithm challenging to understand. On the other hand, Naive Research Method
focuses on the local structure of hierarchical trees rather than the overall
structure. The local structure is part of the overall structure, but the
studies falling into local structures may prevent researchers from solving
problems from a macro perspective. Worse, the additional auxiliary symbols or
indexes for describing relationships and local structures pose a significant
challenge to the researchers’ data analysis capabilities. Imagine a researcher
facing a half-page expression with various randomly labeled symbols and
subscripts; how should the next step go? Therefore, Naive Research Method is
too cumbersome to solve the increasingly complex hierarchical tree problems
effectively.

Considering the complexity of Naive Research Method, we adopted a Matrixing
Research Method for hierarchical tree problems. Its core idea is to transform
the hierarchical tree into a specific matrix representation and then embed it
into the research works or algorithm designs, making the initially abstract
and indescribable hierarchical tree concrete and analyzable. As a more
advanced research method, similar ideas widely exist in many fields such as
graph theory [5, 6, 7, 8], group theory [9], and deep learning[10, 11]. Unlike
Naive Research Method, the research object of Matrixing Research Method is the
hierarchical tree itself rather than the local structure. It emphasizes
avoiding visiting individual nodes as much as possible but implementing
operations of the hierarchical tree by the matrix representation. Therefore,
the matrix representation design is critical and directly determines whether
the research can proceed smoothly. The challenges of matrix representation
design are as follows.

  * 1)

A non-negligible problem is the universality of recursion in hierarchical tree
algorithms, while the access of individual nodes and the description of local
relationships are almost inevitable in recursion. It violates the core idea of
the Matrixing Research Method. Some matrix representations [5, 6, 7, 8] have
been used in the spectral theory of trees, but there is no achievement to show
that the existing matrix representations can implement recursion without
accessing local structures. So that whether supporting recursion is critical
to the matrix representation.

  * 2)

We hope that the matrix representation can directly serve algorithm designs,
not just a theoretical analysis tool. Therefore, the matrix representation
should be succinct to ensure the efficiency of algorithms. Specifically, the
space overhead of each hierarchical tree node should be constant rather than
the dense matrices like Distance Matrix [7] or Ancestral Matrix [8].

###  1.1 Our contributions

Considering the challenges above, we propose an embeddable matrix
representation called Generation Matrix. Generation Matrix is a lower
triangular matrix containing only $2n-1$ non-zero elements (i.e., the weights
of nodes and edges). Applying sparse storage technologies[12], we only need to
store non-zero elements, satisfying the succinctness. Compared with others [5,
6, 7, 8], Generation Matrix emphasizes the application in the hierarchical
tree algorithms. Our analysis of properties shows that many calculations on
Generation Matrix have specific mathematical meanings. We can explain them and
combine them to design complex hierarchical tree algorithms. More importantly,
we demonstrate that the inverse of the Generation Matrix contains the inherent
logic of recursion. Therefore, we can use Generation Matrix to simulate the
top-down and bottom-up recursions without accessing the local structures.
Besides, we study the relationship between Generation Matrix and some existing
matrix representations and find it can be easily converted to others. It
implies that Generation Matrix can be combined with the theories from other
matrix representations to solve hierarchical tree problems.

To demonstrate the practicability of Generation Matrix, we introduce an
application on the differentially private hierarchical tree release above.
Considering the consistency problem[13, 14], we design a Generation Matrix-
based optimally consistent release algorithm (GMC) for differentially private
hierarchical trees. To our knowledge, GMC is the first solution to the problem
by using matrix theory. It has an exceptionally concise process description so
that just a simple matrix expression can summarize the core process. GMC
embodies the advantages of Generation Matrix in solving problems in cross-
domain. Therefore, Generation Matrix has positive significance for promoting
the development of hierarchical tree-related research and applying matrix
theories to solve hierarchical tree problems.

###  1.2 Organization of paper

The rest of the paper is organized as follows. Section 2 reviews the related
works of existing hierarchical tree representations and differentially private
hierarchical tree release. Section 3 introduces the preliminaries of
hierarchical trees and the optimally consistent release of differentially
private hierarchical trees. Section 4 defines Generation Matrix, then analyzes
its mathematical properties and the conversion relationship with other matrix
representations. In Section 5, we show the application of Generation Matrix on
differentially private hierarchical tree release and design GMC. Finally,
Section 6 compares GMC with the existing technology through experiments and
demonstrates its efficiency.

##  2 Related Works

The research on the hierarchical tree representations mainly concentrates on
data structure and graph theory fields. In the data structure field,
researchers have achieved better performance in storage [15], query [16], or
structure updating [17]. However, these representations are mainly for storage
in computers but do not support mathematical analysis. We can not symbolize
them and use them as tools for hierarchical tree researches. In the graph
theory field, many works adopt matrix representations to represent trees,
including Adjacency Matrix [5], Laplacian Matrix [3, 6], Distance Matrix [7],
etc. Among them, Adjacency Matrix only describes the edge information, so that
it is challenging to undertake the complex model analysis. Laplacian matrix
and Distance matrix are two meaningful matrix representations widely used in
spectral graph theory. However, they are for undirected graphs or trees but
not suitable for representing rooted hierarchical trees. To summarize, none of
the three matrix representations is the best choice for representing
hierarchical trees. Subsequently, Eric et al. [8] proposed a new matrix
representation for rooted trees (i.e., hierarchical trees), named Ancestor
Matrix. It represents the structure of a hierarchical tree by describing the
number of overlapping edges on the path from any two leaves to the root.
Studying Ancestral Matrix, Eric et al. [8] obtained many essential
conclusions, such as the maximum spectrum radius and the determinants of the
characteristic polynomial. However, it is also not the best choice for the
calculations of hierarchical trees. First, the dense Ancestral Matrix is not
succinct enough. Secondly, Ancestral Matrix is a kind of matrix with a high
degree of feature summary. Although it can deterministically express the
structure of a hierarchical tree only by describing the leaves, it is very
unintuitive and cannot simulate the operations of hierarchical trees.
Therefore, the existing matrix representations are not suitable for the
analysis and calculation of hierarchical tree models. Significantly, the broad
application of the Laplacian matrix in deep learning[10, 11] in recent years
implies that matrix representation has essential value for solving complex
scientific problems. It motivates us to design a new matrix representation to
solve hierarchical tree problems and design algorithms.

Differentially private hierarchical tree release is a data releasing
technology that organizes the data into a hierarchical tree and applies
differential privacy (DP) [18] to protect individual privacy. It is widely
used in many scenarios, such as histogram publishing [13, 19], location
privacy release based on spatial partitioning [20], trajectory data publishing
[21], frequent term discovery [14]. By adding random noise to the data, DP
provides a provable and quantifiable guarantee of individual privacy. However,
the random noise will destroy the consistency that the hierarchical tree
should satisfy, i.e., “the sum of the children’s values equals the value at
the parent”[13]. Therefore, ensuring that the released results meet
consistency and obtain a higher accuracy is one of the leading research goals.
Hay et al. [13] first applied a hierarchical tree to improve the accuracy of
range query and designed Boosting for the consistency of histogram release.
However, Boosting can only support complete $k-$ary trees, which significantly
limits its application. Moreover, Hay et al.’s error analysis [13] of the
released results is rough, and only qualitative error results are obtained.
Subsequently, Wahlbeh et al. analyzed the error of Boosting and designed an
algorithm to calculate the error. However, it also can only support complete
$k-$ary trees. In the differentially private frequent term discovery problem
studied by Ning et al. [14], the hierarchical tree is arbitrary. Therefore, it
is impossible to apply Boosting. For this reason, Ning et al. designed an
optimally consistent release algorithm for arbitrary hierarchical trees in
their proposed algorithms PrivTrie [14]. Its implementation is based on
multiple complex recursions, which is not easy to understand and a large
number of function calls result in significant additional computational
overhead. Applying the idea of maximum likelihood estimation, Lee et al. [22]
proposed a general solution for differentially private optimally consistent
release. It solves the optimally consistent release by establishing a
quadratic programming equation and has a closed-form matrix expression.
Theoretically, it can apply to arbitrary optimally consistent release, but the
computational overhead is so significant that it can only be processed for
small-scale releases. However, Lee et al.’s research work [22] is inspiring.
It motivates us to try to analyze the issues of differentially private
hierarchical tree release from matrix analysis.

Under the representation of Generation Matrix, we can introduce many matrix
analysis methods to solve hierarchical tree problems. One of them is QR
decomposition [23]. In QR decomposition, we can transform any matrix into a
triangular matrix by orthogonal transformation. Compared with the original
form, the triangular matrix is simpler, has many exciting properties [24]. The
orthogonal transformation methods commonly used for QR decomposition include
Householder transformation [25], Gram-Schmidt orthogonalization [26], Givens
rotation [27], etc. Among them, Householder transformation is the simplest and
more suitable for sparse matrices.

##  3 Preliminaries

In this section, we describe some preliminaries of our work. Before formally
describing, we first introduce some of the main notation definitions shown in
Tab 1.

Table 1: Notations Descriptions in Our Work Notations |  Descriptions
---|---
$\mathcal{T}$ |  Hierarchical tree with arbitrary structure
${{\mathcal{T}}^{\left(k\right)}}$ |  $k-$order subtree of $\mathcal{T}$
${{f}_{i}}$, ${{\mathcal{C}}_{i}}$ |  Parent of node $i$; the set of children of node $i$
$n$, ${{n}_{k}}$ |  The number of nodes of the hierarchical tree; the $k-$order subtree
$h$, ${{h}_{i}}$ |  The height of the hierarchy tree; The height of node $i$
$m$ |  The number of unit counts
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}\in{{\mathbb{R}}^{n\times m}}$ |  The Generation Matrix defined by a $\mathcal{T}$ with the node weights ${{\mathbf{w}}_{node}}$ and the edge weights ${{\mathbf{w}}_{edge}}$
${{\mathbf{G}}_{\mathcal{T}}}\in{{\mathbb{R}}^{n\times n}}$ |  The structure matrix of $\mathcal{T}$
${{\mathbf{M}}_{\mathcal{T}}}\in{{\mathbb{R}}^{n\times m}}$ |  The consistency constraint matrix of $\mathcal{T}$
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}\in{{\mathbb{R}}^{{n}_{1}\times{n}_{1}}}$ |  The Generation Matrix inner-product equivalent to ${{\mathbf{M}}_{\mathcal{T}}}$
${{\mathbf{A}}_{\mathcal{T}}},{{\mathbf{L}}_{\mathcal{T}}},{{\mathbf{D}}_{\mathcal{T}}}\in{{\mathbb{R}}^{n\times n}}$, ${{\mathbf{C}}_{\mathcal{T}}}\in{{\mathbb{R}}^{m\times m}}$ |  The Adjacency Matrix, Laplacian Matrix, Distance Matrix and Ancestral Matrix of $\mathcal{T}$
$\mathbf{x}\in{{\mathbb{R}}^{m\times 1}}$ |  The vector composed of unit counts ${{x}_{i}}$
$\mathbf{v}\in{{\mathbb{R}}^{n\times 1}}$ |  The vector composed of the values of nodes of the hierarchical tree arranged in order
$\widetilde{\mathbf{v}}\in{{\mathbb{R}}^{n\times 1}}$, $\widetilde{\mathbf{x}}\in{{\mathbb{R}}^{m\times 1}}$ |  The noisy $\mathbf{v}$ and $\mathbf{x}$ satisfying DP
$\overline{\mathbf{v}}\in{{\mathbb{R}}^{n\times 1}}$, $\overline{\mathbf{x}}\in{{\mathbb{R}}^{m\times 1}}$ |  Optimally consistent release after post-processing and the vector restored from $\overline{\mathbf{v}}$
${{\mathbf{H}}_{\hbar}}\in{{\left\\{0,1\right\\}}^{m\times n}}$ |  The mapping matrix representing the mapping relationship between ${{x}_{i}}$ and ${{v}_{i}}$

###  3.1 Hierarchical Tree

Figure 1: Hierarchical Tree and Its $k-$Order Subtree

We first recall the definition of the hierarchical tree.

######  Definition 1 (Hierarchical Tree[28]).

The hierarchical tree $\mathcal{T}$ is a collection of nodes numbered
$1,2,\ldots,n$, which satisfies

  * 1)

$\mathcal{T}$ contains a specially designated node called the root.

  * 2)

The remaining nodes are divided into several non-empty collections called the
subtrees of the root.

In the hierarchical tree, we denote the relationships between the nodes as
$i\to j$, indicating node $j$ is the parent of node $i$. Fig. 1 shows a
weighted hierarchical tree with $10$ nodes. The node weights and edge weights
are denoted as ${{w}_{i}}$ and ${{w}_{i\to j}}$, respectively. By the height
of each node, we can obtain a good quasi-ranking, which is defined as follows.

######  Definition 2 (Node Height).

The node height of a hierarchical tree refers to the height of the subtree
rooted at the current node. Let the height of node $i$ be denoted as
${{h}_{i}}$, then ${{h}_{i}}$ can be calculated by the following recursive
expression.

${{h}_{i}}=\left\\{\begin{array}[]{*{35}{l}}1&,\text{node }i\text{ is leaf}\\\
\underset{j\in{{\mathcal{C}}_{i}}}{\mathop{\max}}\,{{h}_{j}}+1&,\text{otherwise}\\\
\end{array}\right..$ (1)

By the height of the nodes, we define a kind of induced subtree of
hierarchical trees, called $k-$Order Subtree.

######  Definition 3 ($k-$Order Subtree).

For a hierarchical tree $\mathcal{T}$ under the descending order of height,
the $k-$Order Subtree ${{\mathcal{T}}^{\left(k\right)}}$ is defined as an
induced subtree retained after $\mathcal{T}$ deletes all leaves $k$ times.
${{\mathcal{T}}^{\left(k\right)}}$ satisfies

${{\mathcal{T}}^{\left(k\right)}}=\left\\{i\left|i\in\mathcal{T}\wedge{{h}_{i}}>k\right.\right\\}.$
(2)

As a bottom-up induced subtree, ${{\mathcal{T}}^{\left(k\right)}}$ satisfies
transitive, i.e.,
${{\mathcal{T}}^{\left(a\right)\left(b\right)}}={{\mathcal{T}}^{\left(a+b\right)}}$.
It can help us determine whether the subtrees obtained in different ways are
equivalent. In subsequent applications, we use the concept of $k-$Order
Subtree to simplify the description of the tree structure. In Fig. 1, we use
dotted circles to mark the subtrees of $\mathcal{T}$ from $0$ to $2$ orders.
It can be seen that the $0-$Order Subtree is $\mathcal{T}$ itself actually;
${{\mathcal{T}}^{\left(1\right)}}$ is a subtree composed of non-leaf nodes of
$\mathcal{T}$. Let ${{n}_{k}}$ denote the number of nodes contained in
${{\mathcal{T}}^{\left(k\right)}}$, then there are ${{n}_{0}}\equiv n$ and
${{n}_{1}}$ equal to the number of non-leaf nodes of $\mathcal{T}$.

###  3.2 Optimally Consistent Release of Differentially Private Hierarchical
Tree

Before describing the optimally consistent releasing of the differentially
private hierarchical tree, we first recall the hierarchical tree releasing
model. Consider a set of unit counts
${{x}_{i}}:\mathcal{D}\to\mathbb{N}$$\left(1\leq i\leq m\right)$ for private
dataset $\mathcal{D}$, where ${{x}_{i}}$ indicates the number of records in
$\mathcal{D}$ that satisfies the mutually exclusive unit condition
${{\varphi}_{i}}$. The unit count ${{x}_{i}}$ satisfies

${{x}_{i}}=\left|\left\\{t\in\mathbf{D}\left|{{\varphi}_{i}}\left(t\right)=True\right.\right\\}\right|.$
(3)

Since ${{\varphi}_{i}}$ is mutually exclusive, any $t\in\mathcal{D}$ satisfies
and only satisfies one ${{\varphi}_{i}}$. Therefore, organizing ${{x}_{i}}$
into the form of a vector, we will get
$\mathbf{x}={{\left[{{x}_{1}},{{x}_{2}},\ldots,{{x}_{m}}\right]}^{T}}$.

Figure 2: The Process of Hierarchical Tree Release

As shown in Fig. 2, each leaf corresponds to a ${{x}_{i}}$. The non-leaf
node’s value equals the sum of the leaves’ value of the subtree rooted at that
node. Therefore, the results of the hierarchical tree meet the consistency,
i.e., “the sum of the values of the child nodes is equal to the value of the
parent node”. In Fig. 2, we denote the value of the $i$-th node as
${{v}_{i}}$. Then, organizing ${{v}_{i}}$ into the form of
$\mathbf{v}={{\left[{{v}_{1}},{{v}_{2}},\ldots,{{v}_{n}}\right]}^{\operatorname{T}}}$
in turn, we can get the to-be-released data $\mathbf{v}$.

However, several works[13, 19, 20, 21, 14] have demonstrated that releasing an
unprotected hierarchical tree will result in privacy disclosure. To protect
individual privacy, DWork et al. [18] proposed differential privacy, defined
as follows.

######  Definition 4 ($\varepsilon-$Differential Privacy[18]).

If a random algorithm $\mathcal{M}$ satisfies $\varepsilon-$difference
privacy, then for any two neighboring datasets $\mathcal{D}$ and
$\mathcal{D}^{\prime}$, all outputs
$O\in\operatorname{Range}\left(\mathcal{M}\right)$ satisfies

$\Pr\left(\mathcal{M}\left(\mathcal{D}\right)=O\right)\leq{{e}^{\varepsilon}}\Pr\left(\mathcal{M}\left(\mathcal{D}^{\prime}\right)=O\right).$
(4)

Under differential privacy, the process of hierarchical tree releasing can be
described as

$\widetilde{\mathbf{v}}=\mathbf{v}+\mathbf{\xi},$ (5)

where $\widetilde{\mathbf{v}}$ is the $\mathbf{v}$ after noise addition, which
satisfies differential privacy. $\mathbf{\xi}$ is the random vector for the
noise addition. Each element ${{\xi}_{i}}$ is i.i.d and satisfies
${{\xi}_{i}}\sim\operatorname{Lap}\left({\Delta}/{\varepsilon}\;\right)$,
where $\operatorname{Lap}$ represents a Laplacian distribution and $\Delta$ is
data sensitivity. In hierarchical tree releasing, $\Delta$ equals the height
of $\mathcal{T}$[13].

To keep the consistency of the hierarchical tree after adding noise, we can
get the optimally consistent release $\overline{\mathbf{v}}$ by following the
optimization equation according to maximum likelihood post-processing proposed
by Lee et al. [22].

$\begin{array}[]{*{35}{l}}\underset{\overline{\mathbf{v}}}{\mathop{\min}}&\left\|\overline{\mathbf{v}}-\widetilde{\mathbf{v}}\right\|\\\
s.t.&{{\mathbf{M}}_{\mathcal{T}}}^{T}\overline{\mathbf{v}}=\mathbf{0}\\\
\end{array},$ (6)

where ${{\mathbf{M}}_{\mathcal{T}}}$ is the consistency constraint matrix of a
hierarchical tree, defined as follows.

######  Definition 5 (Consistency Constraint Matrix of Hierarchical Tree).

Given a hierarchical tree $\mathcal{T}$ containing $n$ nodes. Let ${{n}_{1}}$
denote the number of non-leaf nodes in $\mathcal{T}$. The value ${{m}_{ij}}$
in row $i$ and column $j$ of the consistency constraint matrix
${{\mathbf{M}}_{\mathcal{T}}}\in{{\mathbb{R}}^{n\times{{n}_{1}}}}$ is defined
as follows:

${{m}_{ij}}=\left\\{\begin{array}[]{*{35}{l}}1&,i=j\\\ -1&,j={{f}_{i}}\\\
0&,\text{otherwise}\\\ \end{array}\right.,$ (7)

where ${{f}_{i}}$ is the parent of node $i$.

The optimization equation (6) has the following closed-form expression:

$\overline{\mathbf{v}}=\widetilde{\mathbf{v}}-{{\mathbf{M}}_{\mathcal{T}}}{{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}{{\mathbf{M}}_{\mathcal{T}}}^{T}\widetilde{\mathbf{v}}.$
(8)

Since Formula (8) involves the inner product and inverse operations of the
matrix, the time complexity of the direct solution is as high as
$O\left({{n}^{3}}\right)$. The amount of calculation is too large to obtain an
efficient enough algorithm directly by the expressions. On the surface,
Formula (8) is not a good choice for solving optimally consistent releases,
but under the theories of Generation Matrix, we can convert it into another
form and apply the properties of Generation Matrix to obtain an efficient
algorithm.

##  4 Generation Matrix Model for Hierarchical Tree

###  4.1 Generation Matrix

Before defining Generation Matrix, we number the nodes of $\mathcal{T}$ by
descending order of height firstly.

######  Definition 6 (Descending Order of Height).

Let ${{h}_{i}}$ denote the height of node $i$ defined by Def. 1. If any two
nodes $i$ and $j$ in $\mathcal{T}$ satisfy

$i<j\Rightarrow{{l}_{i}}\geq{{l}_{j}},$ (9)

we say that $\mathcal{T}$ satisfies Descending Order of Height.

Under the descending order of height, we define Generation Matrix for
$\mathcal{T}$.

Figure 3: Generation Matrix and Its $k-$Order Submatrix

######  Definition 7 (Generation Matrix).

Considering a non-zero weighted hierarchical tree $\mathcal{T}$ under
descending order of height, let ${{w}_{i}}$ and
${{w}_{i\to{{f}_{i}}}}$$\left({{w}_{i}},{{w}_{i\to{{f}_{i}}}}\neq 0\right)$
denote the weight values of the node $i$ and the edge $i\to{{f}_{i}}$.
Organizing them into a vector, denoted as ${{\mathbf{w}}_{node}}$ and
${{\mathbf{w}}_{edge}}$, the generation matrix is denoted as
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}\in{{\mathbb{R}}^{n\times
n}}$, whose element ${{g}_{i,j}}$ in row $i$ and column $j$ is defined as
follows,

${{g}_{i,j}}=\left\\{\begin{array}[]{*{35}{l}}{{w}_{i}}&,i=j\\\
-{{w}_{i\to{{f}_{i}}}}&,i\to{{f}_{i}}\\\ 0&,\text{otherwise}\\\
\end{array}\right..$ (10)

As shown in Fig. 3, since $\mathcal{T}$ satisfies Descending Order of Height,
the number of any non-root node $i$ in $\mathcal{T}$ is always bigger than its
parent. It ensures Generation Matrix is always a lower triangular matrix.
According to Def. 10, there is a one-to-one mapping between arbitrary non-zero
weighted hierarchical tree and
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}\in{{\mathbb{R}}^{n\times
n}}$, i.e., the matrix representation of the non-zero weighted hierarchical
tree is unique. When we only need to describe the structure of the
hierarchical tree, we can use a Generation Matrix with all weights of $1$ to
represent it, i.e.,
$\mathbf{G}_{\mathcal{T}}^{\left(\mathbf{1},\mathbf{1}\right)}$. We call
$\mathbf{G}_{\mathcal{T}}^{\left(\mathbf{1},\mathbf{1}\right)}$ Structure
Matrix, which is abbreviated as ${{\mathbf{G}}_{\mathcal{T}}}$. If two
hierarchical trees have the same structure and arrangement, the positions of
non-zero elements in their Generation Matrices are always the same, which we
call Similar Generation Matrices.

######  Definition 8 (Similar Generation Matrices).

If ${{\mathbf{G}}_{1}}$ and ${{\mathbf{G}}_{2}}$ are two Generation Matrices
defined by the hierarchical trees with the same structure and arrangement (or
the same tree), we call them similar Generation Matrices, which are denoted as
${{\mathbf{G}}_{1}}\sim{{\mathbf{G}}_{2}}$.

Every Generation Matrix from the same hierarchical tree is always similar. We
can use $\mathbf{G}\sim{{\mathbf{G}}_{\mathcal{T}}}$ as sufficient to judge
whether the hierarchical tree represented by $\mathbf{G}$ has the same
structure as $\mathcal{T}$.

According to Def. 2, ${{\mathcal{T}}^{\left(k\right)}}$ is an induced subtree
composed of nodes $i$ with ${{h}_{i}}\geq k$ in $\mathcal{T}$. Under
Descending Order of Height, these nodes are always ranked first. In Fig. 3,
$k-$Order Submatrix that represents the $k-$Order Subtree is denoted as
$\mathbf{G}_{{{\mathcal{T}}^{\left(k\right)}}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$.
We can obtain it by taking the ${{n}_{k}}-$order leading principal minor of
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
(i.e., the elements in rows and columns from $1$ to ${{n}_{k}}$). In
particular,
$\mathbf{G}_{{{\mathcal{T}}^{\left(1\right)}}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
represents the sub-tree composed of non-leaf nodes of $\mathcal{T}$.

Considering a specific application, one problem we may encounter is that the
nodes of the hierarchical tree are numbered but not in Descending Order of
Height. Under the matrix representation, the problem is elementary to solve.
We can adopt a sparse mapping matrix to convert the original number into
Descending Order of Height.

######  Definition 9 (Mapping Matrix).

Given an ordered set
$\mathcal{S}=\left\langle{{s}_{1}},{{s}_{2}},\ldots,{{s}_{m}}\right\rangle$
represents the mapping relationship between integers, satisfying
${{s}_{i}}\in{{\mathbb{N}}^{+}}\wedge{{s}_{i}}\leq n$, the mapping matrix
defined by $\mathcal{S}$ is denoted as
${{\mathbf{H}}_{\mathcal{S}}}\in{{\left\\{0,1\right\\}}^{m\times n}}$. The
value ${{h}_{i,j}}$ in row $i$ and column $j$ of
${{\mathbf{H}}_{\mathcal{S}}}$ satisfies

${{h}_{i,j}}=\left\\{\begin{array}[]{*{35}{l}}1&,{{s}_{i}}=j\\\
0&,\text{otherwise}\\\ \end{array}\right..$ (11)

By the definition of the mapping matrix, $\mathcal{S}$ always represents an
injection and satisfies
${{\mathbf{H}}_{\mathcal{S}}}{{\mathbf{H}}_{\mathcal{S}}}^{T}=\mathbf{I}$. If
$\mathcal{S}$ represents a bijection, ${{\mathbf{H}}_{\mathcal{S}}}$ will be a
permutation matrix. When the basis vector ${{\mathbf{e}}_{i}}$ acts on
${{\mathbf{H}}_{\mathcal{S}}}$, the following equations holds.

${{\mathbf{H}}_{\mathcal{S}}}^{T}{{\mathbf{e}}_{i}}={{\mathbf{e}}_{{{s}_{i}}}},$
(12)
${{\mathbf{H}}_{\mathcal{S}}}{{\mathbf{e}}_{i}}=\left\\{\begin{array}[]{*{35}{l}}{{\mathbf{e}}_{s_{i}^{-1}}}&,i\in\mathcal{S}\\\
\mathbf{0}&,i\notin\mathcal{S}\\\ \end{array}\right.,$ (13)

where $s_{i}^{-1}$ represents the inverse mapping of ${{s}_{i}}$, which
satisfies $s_{{{s}_{i}}}^{-1}=i$.

To describe the mapping relationship between the nodes before and after
sorting by Descending Order of Height, we only need to define the ordered set
$\mathcal{S}=\left\langle{{s}_{1}},{{s}_{2}},\ldots,{{s}_{n}}\right\rangle$,
where ${{s}_{i}}$ represents the sorted number of the node initially numbered
$i$. Then, we can use ${{\mathbf{H}}_{\mathcal{S}}}\mathbf{v}$ to get the
vector before sorting from $\mathbf{v}$ after sorting.

In addition, the mapping matrix can be used to represent other mapping
relationships, such as the mapping of ${{v}_{i}}$ to ${{x}_{i}}$. For example,
in Fig. 1, if we use an ordered set
$\mathcal{H}=\left\langle{{\hbar}_{1}},{{\hbar}_{2}},\ldots,{{\hbar}_{m}}\right\rangle$
to represent the mapping relationship between ${{v}_{i}}$ and ${{x}_{i}}$,
then ${{\hbar}_{i}}=i+5$, and we have the mapping matrix
${{\mathbf{H}}_{\hbar}}$ to represent their mapping relationship.

###  4.2 Properties of Generation Matrix

Our research shows that Generation Matrix has many mathematical properties
that deserve attention. These properties can help us solve various problems
about the analysis and calculation of hierarchical trees. According to Def.
10, it is not difficult to find that Generation Matrix satisfies sparsity.

######  Property 1 (Sparsity).

Considering a hierarchical tree $\mathcal{T}$ consists of $n$ nodes,
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
is has and only has $2n-1$ non-zero elements. Its first row has only $1$ non-
zero element, and the remaining $n-1$ rows have $2$ non-zero elements.

Due to the sparsity of Generation Matrix, we can apply various sparse matrix
technologies such as COO (Coordinate Format) and CSR (Compressed Sparse Row)
to calculate hierarchical tree models efficiently. Under the sparse
representations, the storage and calculation of Generation Matrix are both
only $O\left(n\right)$. Therefore, the application based on Generation Matrix
does not cause more computational overhead. Currently, the computing
technologies of sparse matrices are very mature and widely used in various
high-performance platforms [29, 30, 31].

One of the fundamental properties of Generation Matrices is invertibility. By
solving the equations
$\mathbf{G}{{{}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}}^{T}}\mathbf{z}=\mathbf{v}$
and
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}\mathbf{z}=\mathbf{v}$
about $\mathbf{z}$, we find two interesting and important mathematical
properties of Generation Matrices. We collectively call them the propagation
of Generation Matrix.

######  Property 2 (Upward Propagation).

Let ${{g}_{i,j}}$ denotes the element in row $i$ and column $j$ of
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$,
and ${{v}_{i}}$ is the value of node $i$ of $\mathcal{T}$. Organize
${{v}_{i}}$ into vector
$\mathbf{v}={{\left[{{v}_{1}},{{v}_{2}},\ldots,{{v}_{n}}\right]}^{T}}$, then
$\mathbf{z}=\mathbf{G}{{{}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}}^{-T}}\mathbf{v}$
is an upward propagation on $\mathbf{v}$. The value ${{z}_{i}}$ of
$\mathbf{z}$ satisfies

${{z}_{i}}=\left\\{\begin{array}[]{*{35}{l}}{{{v}_{i}}}/{{{g}_{i,i}}}&,\text{node
}i\text{ is leaf}\\\
{\left({{v}_{i}}-\sum\limits_{j\in{{\mathcal{C}}_{i}}}{{{g}_{j,i}}{{z}_{j}}}\right)}/{{{g}_{i,i}}}&,\text{otherwise}\\\
\end{array}\right..$ (14)

######  Property 3 (Downward Propagation).

If
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
and $\mathbf{v}$ have the exact definition as Prop. 14, then
$\mathbf{z}=\mathbf{G}{{{}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}}}^{-1}\mathbf{v}$
is a downward propagation on $\mathbf{v}$. The value ${{z}_{i}}$ of
$\mathbf{z}$ satisfies

${{z}_{i}}=\left\\{\begin{array}[]{*{35}{l}}{{{v}_{i}}}/{{{g}_{i,i}}}&,\text{node
}i\text{ is root}\\\
{\left({{v}_{i}}-{{g}_{i,{{f}_{i}}}}{{z}_{{{f}_{i}}}}\right)}/{{{g}_{i,i}}}&,\text{otherwise}\\\
\end{array}\right..$ (15)

Prop. 14 and Prop. 15 show that Generation Matrix can simulate multiple
recursive operations of hierarchical trees. According them, Cor. 1 analyzes
the elements affected by the propagations of Generation Matrix.

######  Corollary 1.

For the upward propagation, affected ${{z}_{j}}$ by ${{v}_{i}}$ satisfies
$j=i$, or $j$ is the ancestor of $i$ in $\mathcal{T}$; for the downward
propagation, affected ${{z}_{j}}$ by ${{v}_{i}}$ satisfies $j=i$, or $j$ is a
descendant of $i$ in $\mathcal{T}$.

Combining the propagations, we further study a variety of matrix operations of
Generation Matrices. They have strong interpretability and provide crucial
theoretical support for the research of hierarchical trees.

######  Property 4.

Let the vector
$\mathbf{z}=\left(\mathbf{I}-{{\mathbf{G}}_{\mathcal{T}}}^{T}\right)\mathbf{1}$,
then the $i$-th element ${{z}_{i}}$ of $\mathbf{z}$ represents the number of
children of the node $i$, i.e., ${{z}_{i}}=\left|{{\mathcal{C}}_{i}}\right|$.

######  Property 5.

If the vector $\mathbf{z}={{\mathbf{G}}_{\mathcal{T}}}^{-T}\mathbf{1}$, the
$i$-th element ${{z}_{i}}$ of $\mathbf{z}$ represents the number of nodes
contained in the subtree rooted at node $i$.

######  Property 6.

Let the vector $\mathbf{z}={{\mathbf{G}}_{\mathcal{T}}}^{-1}\mathbf{1}$, then
the $i$-th element ${{z}_{i}}$ of $\mathbf{z}$ represents the depth of node
$i$, where the depth of the root is $1$.

The properties above indicate that Generation Matrix is an effective and easy-
to-use tool for various hierarchical tree analyses. In addition to the
conclusions about vectors discussed above, there are some conclusions about
matrices as follows. Compared with conclusions about vectors, they focus on
describing the characteristics between nodes.

######  Property 7.

Let $g_{ij}^{\left(-1\right)}$ denote the element in row $i$ and column $j$ of
${{\mathbf{G}}_{\mathcal{T}}}^{-1}$, then $g_{ij}^{\left(-1\right)}$ satisfies

$g_{ij}^{\left(-1\right)}=\left\\{\begin{array}[]{*{35}{l}}1&,i=j\vee j\text{
is an ancestor of }i\\\ 0&,\text{otherwise}\\\ \end{array}\right..$ (16)

###### Proof.

See Appendix A.1. ∎

Prop. 16 shows that ${{\mathbf{G}}_{\mathcal{T}}}^{-1}$ is a matrix indicating
the relationship between ancestors and descendants. Although
${{\mathbf{G}}_{\mathcal{T}}}^{-1}$ is denser than
${{\mathbf{G}}_{\mathcal{T}}}$, in most cases,
${{\mathbf{G}}_{\mathcal{T}}}^{-1}$ is still sparse.

######  Property 8.

Let $\mathbf{M}={{\mathbf{G}}_{\mathcal{T}}}{{\mathbf{G}}_{\mathcal{T}}}^{T}$
and ${{m}_{i,j}}$ denote the element in row $i$ and column $j$ of
$\mathbf{M}$. Except for ${{m}_{11}}=1$, other elements satisfy
“${{m}_{ij}}=1$ $\Leftrightarrow$ $i$ and $j$ are sibling nodes”.

######  Property 9.

Let
$\mathbf{M}={{\left({{\mathbf{G}}_{\mathcal{T}}}^{T}{{\mathbf{G}}_{\mathcal{T}}}\right)}^{-1}}$
and ${{m}_{ij}}$ is the element in row $i$ and column $j$ of $\mathbf{M}$,
then the value of ${{m}_{ij}}$ represents the number of common ancestors of
the node pair $i$ and $j$, and ${{m}_{ii}}$ represents the depth of $i$.

###### Proof.

See Appendix A.2. ∎

Similar to Prop. 16, Prop. 8 can also be used as an indicator matrix to
describe the relationship between nodes. Prop. 9 is an important property,
which describes an effective method of calculating common ancestors. As an
essential feature to describe the correlation between nodes, the number of
common ancestors has an important application value for hierarchical tree
analyses[8].

In the study of spectral graph theory, feature analysis is usually
indispensable. Our research shows that the eigenvalues and eigenvectors of a
Generation Matrix satisfy the following properties.

######  Property 10 (Eigenvalues and Eigenvectors).

Let
$\boldsymbol{\lambda}={{\left[{{\lambda}_{1}},{{\lambda}_{2}},\ldots,{{\lambda}_{n}}\right]}^{T}}$
denote the eigenvalues of
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$,
then the $i$-th eigenvalue${{\lambda}_{i}}$ is $w_{i}$.

Let the left eigenvector and the right eigenvector corresponding to the $i$-th
eigenvalue denote as ${{\mathbf{u}}_{i}}$ and ${{\mathbf{v}}_{i}}$,
respectively. The premise of the existence of ${{\mathbf{u}}_{i}}$ is that
each ancestor $j$ of $i$ satisfies $w_{i}\neq w_{j}$, and the premise of the
existence of ${{\mathbf{v}}_{i}}$ is that each descendant $j$ of $i$ satisfies
$w_{i}\neq w_{j}$.

Let the $j$-th element of ${{\mathbf{u}}_{i}}$ and ${{\mathbf{v}}_{i}}$ denote
as $u_{j}^{\left(i\right)}$ and $v_{j}^{\left(i\right)}$, respectively. If
${{\mathbf{u}}_{i}}$ exists, then $u_{j}^{\left(i\right)}=0$ for any $j>i$.
Let $u_{i}^{\left(i\right)}=1$. The remaining elements
$u_{j}^{\left(i\right)}\left(j<i\right)$ can be obtained by

$u_{j}^{\left(i\right)}=\left\\{\begin{array}[]{*{35}{l}}\frac{\sum\nolimits_{k\in{{\mathcal{C}}_{j}}}{w_{k\to
j}u_{k}^{\left(i\right)}}}{w_{j}-w_{i}}&,j\text{ is a ancestor of }i\\\
0&,\text{otherwise}\\\ \end{array}\right..$ (17)

If ${{\mathbf{v}}_{i}}$ exists, then $v_{j}^{\left(i\right)}=0$ for any $j<i$.
Let $v_{i}^{\left(i\right)}=1$. The remaining elements
$v_{j}^{\left(i\right)}\left(j>i\right)$ can be obtained by

$v_{j}^{\left(i\right)}=\left\\{\begin{array}[]{*{35}{l}}\frac{w_{j\to{{f}_{j}}}v_{{{f}_{j}}}^{\left(k\right)}}{w_{j}-w_{i}}&,j\text{
is a descendant of }i\\\ 0&,\text{otherwise}\\\ \end{array}\right..$ (18)

Prop. 10 shows that the eigenvalues and eigenvectors of the Generation Matrix
have many interesting properties. For example, the eigenvalue of Generation
Matrix is the weights of the nodes, which is much easier to solve than other
matrix representations; the eigenvectors also satisfy some propagation
properties similar to Prop. 14 and 15. Notably, the eigenvectors are
conditional, which means that Generation Matrix is not always diagonalizable.
Some Generation Matrices, especially the eigenvectors of
${{\mathbf{G}}_{\mathcal{T}}}$, still have many problems waiting to be
studied. Although feature analysis is not the main focus in this paper, Prop.
10 still provides some valuable references for the subsequent research works.

Considering the relationship between
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
and corresponding ${{\mathbf{G}}_{\mathcal{T}}}$, we find that
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
satisfies a particular decomposition form, which we call the diagonal
decomposition of Generation Matrix.

######  Property 11 (Diagonal Decomposition).

Given arbitrary
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$,
there is always a pair of vectors
$\boldsymbol{\alpha},\boldsymbol{\beta}\in{{\mathbb{R}}^{n}}$, making the
following decomposition hold for
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
and the structure matrix ${{\mathbf{G}}_{\mathcal{T}}}$.

$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}=\operatorname{diag}\left(\boldsymbol{\beta}\right){{\mathbf{G}}_{\mathcal{T}}}\operatorname{diag}\left(\boldsymbol{\alpha}\right)$
(19)

Let ${{\alpha}_{i}}$ and ${{\beta}_{i}}$ denote the $i$-th element of them,
respectively. Then a pair of legal $\boldsymbol{\alpha}$ and
$\boldsymbol{\beta}$ can be obtained by

$\left\\{\begin{aligned}
&\boldsymbol{\alpha}=\exp\left({{\mathbf{G}}_{\mathcal{T}}}^{-1}\left(\ln\left({{\mathbf{w}}_{node}}\right)-\ln\left({{\mathbf{w}}_{edge}}\right)\right)\right)\\\
&\boldsymbol{\beta}={{\mathbf{w}}_{node}}\oslash\boldsymbol{\alpha}\\\
\end{aligned}\right..$ (20)

Where “$\oslash$” denote the element-wise division of vectors. Note, since the
root numbered $1$ has no parent, we set ${{w}_{1\to\varnothing}}=1$ as the
first element of ${{\mathbf{w}}_{edge}}$, and ${{w}_{i\to{{f}_{i}}}}$ is the
$i$-th element of ${{\mathbf{w}}_{edge}}$ in the remaining elements.

###### Proof.

See Appendix A.3. ∎

By the diagonal decomposition of Generation Matrix, we can express arbitrary
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
as an expression with ${{\mathbf{G}}_{\mathcal{T}}}$. Using Prop. 11, we can
extend some mathematical properties of ${{\mathbf{G}}_{\mathcal{T}}}$ to
$\mathbf{G}_{\mathcal{T}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
to solve more problems effectively.

###  4.3 The Conversion between Generation Matrix and Other Matrix
Representations

Figure 4: Conversion Relationships from Generation Matrix to Other Matrix
Representations

Our research shows that Generation Matrix is not an isolated matrix
representation from others. Through proper operations, we can convert
Generation Matrix into other matrix representations. Fig. 4 shows the four
matrix representations that can be transformed by the Generation Matrix
constructed by the hierarchical tree in Fig. 1, including Adjacency Matrix,
Laplacian Matrix, Distance Matrix, and Ancestor Matrix.

######  Theorem 1.

Let ${{\mathbf{A}}_{\mathcal{T}}}$ be Adjacency Matrix of $\mathcal{T}$, then
${{\mathbf{A}}_{\mathcal{T}}}$ can be obtained by the following expression of
${{\mathbf{G}}_{\mathcal{T}}}$:

${{\mathbf{A}}_{\mathcal{T}}}=\mathbf{I}-{{\mathbf{G}}_{\mathcal{T}}}.$ (21)

######  Theorem 2.

Let ${{\mathbf{L}}_{\mathcal{T}}}$ be Laplacian Matrix of $\mathcal{T}$, then
${{\mathbf{L}}_{\mathcal{T}}}$ can be obtained by the following expression of
${{\mathbf{G}}_{\mathcal{T}}}$:

${{\mathbf{L}}_{\mathcal{T}}}={{\mathbf{G}}_{\mathcal{T}}}^{T}{{\mathbf{G}}_{\mathcal{T}}}-{{\mathbf{e}}_{1}}{{\mathbf{e}}_{1}}^{T}.$
(22)

######  Theorem 3.

Let ${{\mathbf{D}}_{\mathcal{T}}}$ be Distance Matrix of $\mathcal{T}$, then
${{\mathbf{D}}_{\mathcal{T}}}$ can be obtained by the following expression of
${{\mathbf{G}}_{\mathcal{T}}}$:

${{\mathbf{D}}_{\mathcal{T}}}={{\mathbf{G}}_{\mathcal{T}}}^{-1}\mathbf{I}{{\mathbf{I}}^{T}}+\mathbf{I}{{\mathbf{I}}^{T}}{{\mathbf{G}}_{\mathcal{T}}}^{-T}-2{{\left({{\mathbf{G}}_{\mathcal{T}}}^{T}{{\mathbf{G}}_{\mathcal{T}}}\right)}^{-1}}.$
(23)

######  Theorem 4.

Let ${{\mathbf{C}}_{\mathcal{T}}}$ be Ancestral Matrix[8] of $\mathcal{T}$,
then ${{\mathbf{C}}_{\mathcal{T}}}$ can be obtained by the following
expression of ${{\mathbf{G}}_{\mathcal{T}}}$:

${{\mathbf{C}}_{\mathcal{T}}}={{\mathbf{H}}_{\mathcal{H}}}{{\left({{\mathbf{G}}_{\mathcal{T}}}^{T}{{\mathbf{G}}_{\mathcal{T}}}\right)}^{-1}}{{\mathbf{H}}_{\mathcal{H}}}^{T}-1.$
(24)

###### Proof.

The proofs of Thm. 2-4 in Appendix A.4 to A.6. ∎

It can be seen from the theorems above that we can convert Generation Matrix
into other matrix representations by simple matrix expressions. However, the
reverse is not easy. Except for Adjacency Matrix, other matrix representations
cannot be directly converted back to Generation Matrix. Therefore, we can use
Generation Matrix to construct other matrix representations. Besides, it also
implies that the theories of Generation Matrix have a particular internal
connection with the matrix represented. We can combine the theories of
Generation Matrix and other matrix representations to solve more problems
about hierarchical trees.

##  5 The Application on Differentially Private Hierarchical Tree Release

###  5.1 Hierarchical Tree Release Based on Generation Matrix

In this section, we introduce how to apply Generation Matrix to efficiently
and concisely achieve an optimally consistent release on differentially
private hierarchical tree release. Since each leaf of ${\mathcal{T}}$
corresponds to a ${{x}_{i}}$, we use the mapping matrix
${{\mathbf{H}}_{\mathcal{H}}}$ to represent the mapping relationship between
leaf nodes and hierarchical tree nodes. Using Prop. 14, the hierarchical tree
building process ${{\operatorname{BuildTree}}_{\mathcal{T}}}$ can be described
as

$\mathbf{v}={{\operatorname{BuildTree}}_{\mathcal{T}}}\left(\mathbf{x}\right)={{\mathbf{G}}_{\mathcal{T}}}^{-T}{{\mathbf{H}}_{\mathcal{H}}}^{T}\mathbf{x}.$
(25)

At the same time, we also define the inverse tree-building process
${{\operatorname{BuildTree}}_{\mathcal{T}}}^{-1}$ as the following expression,
which is taking the leaves of $\mathcal{T}$ and restoring them to
$\mathbf{x}$.

$\mathbf{x}={{\operatorname{BuildTree}}_{\mathcal{T}}}^{-1}\left(\mathbf{v}\right)={{\mathbf{H}}_{\mathcal{H}}}\mathbf{v}.$
(26)

Although most works[13, 19, 20, 21, 14] do not take matrix analysis as the
theoretical basis for optimally consistent release, there are many advantages
to applying matrix analysis. One of them is error analysis. Using matrix
analysis, we can quickly calculate the overall mean square error of the “Node
Query” after the post-processing for optimally consistent release.

######  Theorem 5.

Given the privacy budget $\varepsilon$ and the to-be-released hierarchical
tree $\mathcal{T}$ containing $n$ nodes and $m$ leaves, whose height is $h$,
the overall mean square error before and after post-processing
$mse\left(\widetilde{\mathbf{v}}\right)$ and
$mse\left(\overline{\mathbf{v}}\right)$ satisfy

$\operatorname{mse}\left(\widetilde{\mathbf{v}}\right)=\sum\nolimits_{i=1}^{n}{\mathbb{E}\left({{\left({{\widetilde{v}}_{i}}-{{v}_{i}}\right)}^{2}}\right)}={2n{{h}^{2}}}/{{{\varepsilon}^{2}}}\;,$
(27)
$\operatorname{mse}\left(\overline{\mathbf{v}}\right)=\sum\nolimits_{i=1}^{n}{\mathbb{E}\left({{\left({{\overline{v}}_{i}}-{{v}_{i}}\right)}^{2}}\right)}={2m{{h}^{2}}}/{{{\varepsilon}^{2}}}\;.$
(28)

###### Proof.

See Appendix A.7. ∎

According to Thm. 28, the overall mean square error depends on the number of
leaves after post-processing. Generally, $n$ is much less than the number of
leaves $m$, so post-processing will significantly reduce the error. As the
proof shown in Appendix A.7, We applied the property of the trace of the
matrix to obtain a concrete and concise demonstration, which embodies matrix
analysis’s great potential for solving problems.

Next, we will introduce how to apply Generation Matrix to achieve an efficient
enough algorithm.

###  5.2 $\text{``LO''}-$QR Decomposition on ${{\mathbf{M}}_{\mathcal{T}}}$

To obtain an efficient release algorithm, we apply QR decomposition to analyze
Formula (8). Unfortunately, the traditional QR decomposition[23] cannot meet
our analysis requirements, so we propose another QR decomposition form, namely
the $\text{``LO''}-$QR decomposition.

######  Definition 10 ($\text{``LO''}-$QR Decomposition).

For matrix $\mathbf{M}\in{{\mathbb{R}}^{n\times m}}\left(n\geq m\right)$, QR
decomposition looks for an orthogonal matrix $\mathbf{Q}$, which converts
$\mathbf{M}$ into a form composed of lower triangular matrix $\mathbf{L}$ and
zero matrix. i.e.,

$\mathbf{M}=\mathbf{Q}\left[\begin{matrix}\mathbf{L}\\\ \mathbf{O}\\\
\end{matrix}\right].$ (29)

Correspondingly, we call the traditional QR decomposition the
$\text{``UO''}-$QR decomposition, which decomposes a matrix into an upper
triangular matrix. Although the two have different forms, they both achieve
decomposition through a series of basic orthogonal transformations.
Householder transformation is the most widely used among various orthogonal
transformation techniques because of its high efficiency, easy implementation,
and applicability to sparse matrices. Completing QR decomposition once
requires $m$ householder transformations. To describe the QR decomposition
process in more detail, we define $\left(\mathcal{S},j\right)-$Householder
transformation to describe each transformation.

######  Definition 11 ($\left(\mathcal{S},j\right)-$Householder
Transformation).

For matrix $\mathbf{M}$, given an ordered set
$\mathcal{S}=\left\langle{{s}_{1}},{{s}_{2}},\ldots,{{s}_{r}}\right\rangle$
and column number $j$, $\left(\mathcal{S},j\right)-$Householder Transformation
selects the rows ${{s}_{1}},{{s}_{2}},\ldots,{{s}_{r}}$ and column $j$ of
$\mathbf{M}$ as the reference for householder transformation,
$\mathbf{Y}=\mathbf{QM}$. The transformation result will make $\mathbf{Y}$
satisfy
${{y}_{{{s}_{1}},j}}=\sqrt{\sum\nolimits_{s\in\mathcal{S}}{{{m}_{s,j}}^{2}}}$
and ${{y}_{{{s}_{i}},j}}=0,2\leq i\leq r$, where $\mathbf{Q}$ satisfies the
following expression:

$\left\\{\begin{aligned}
&\mathbf{m}={{\mathbf{H}}_{\mathcal{S}}}\mathbf{M}{{\mathbf{e}}_{j}}\\\
&\boldsymbol{\omega}=\mathbf{m}-\left\|\mathbf{m}\right\|{{\mathbf{e}}_{1}}\\\
&\mathbf{Q}=\mathbf{I}-2{{\mathbf{H}}_{\mathcal{S}}}^{T}\frac{\boldsymbol{\omega}{{\boldsymbol{\omega}}^{T}}}{{{\boldsymbol{\omega}}^{T}}\boldsymbol{\omega}}{{\mathbf{H}}_{\mathcal{S}}}\\\
\end{aligned}\right..$ (30)

For $\mathbf{M}$, we denote $\left(\mathcal{S},j\right)-$Householder
transformation as
$\mathbf{Y}={{\operatorname{House}}_{\mathcal{S},j}}\left(\mathbf{M}\right)$.
The QR decomposition based on the Householder transformation can be expressed
as

$\mathbf{R}={{\operatorname{House}}_{{{\varsigma}_{m}}}}\centerdot\cdots\centerdot{{\operatorname{House}}_{{{\varsigma}_{2}}}}\centerdot{{\operatorname{House}}_{{{\varsigma}_{1}}}}\left(\mathbf{M}\right),$
(31)

where $\mathbf{R}$ is the result of QR decomposition and “$\centerdot$”
represents the operation of function composition such as
${{f}_{2}}\centerdot{{f}_{1}}\left(x\right)={{f}_{2}}\left({{f}_{1}}\left(x\right)\right)$.
For $\text{``UO''}-$QR decomposition, the parameter
${{\varsigma}_{i}}=\left(\left\langle i,\cdots,n\right\rangle,i\right)$; for
$\text{``LO''}-$QR decomposition, the parameter
${{\varsigma}_{i}}=\left(\left\langle
m-i+1,1,\cdots,m-i,m+1,\cdots,n\right\rangle,m-i+1\right)$.

Next, we apply the $\text{``LO''}-$QR decomposition on
${{\mathbf{M}}_{\mathcal{T}}}$. To understand how $\text{``LO''}-$QR
decomposition affects ${{\mathbf{M}}_{\mathcal{T}}}$, we divide
${{\mathbf{M}}_{\mathcal{T}}}$ into the following forms,

${{\mathbf{M}}_{\mathcal{T}}}\equiv\left[\begin{matrix}{{\mathbf{M}}_{\uparrow}}\\\
{{\mathbf{M}}_{\downarrow}}\\\ \end{matrix}\right].$ (32)

The upper half
${{\mathbf{M}}_{\uparrow}}\in{{\mathbb{R}}^{{{n}_{1}}\times{{n}_{1}}}}$ of
${{\mathbf{M}}_{\mathcal{T}}}$ consists of the first ${{n}_{1}}$ rows; The
second half ${{\mathbf{M}}_{\downarrow}}\in{{\mathbb{R}}^{m\times{{n}_{1}}}}$
consists of the remaining $m$ rows. According to Def. 5, we have
${{\mathbf{M}}_{\uparrow}}={{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}}}$
and
${{\mathbf{M}}_{\downarrow}}=-{{\mathbf{H}}_{{{\mathcal{S}}^{\left(f\right)}}}}$,
where the $i$-th element of ordered set ${{\mathcal{S}}^{\left(f\right)}}$
satisfies $s_{i}^{\left(f\right)}=\text{ }{{f}_{i+{{n}_{1}}}}$. Considering
the effects of Householder transformation on ${{\mathbf{M}}_{\mathcal{T}}}$,
we denote the matrix obtained after the $k$-th Householder transformation as
$\mathbf{M}_{\mathcal{T}}^{\left(k\right)}\left(0\leq k\leq{{n}_{1}}\right)$,
whose upper half and second half are denoted as
$\mathbf{M}_{\uparrow}^{\left(k\right)}$ and
$\mathbf{M}_{\downarrow}^{\left(k\right)}$.
$\mathbf{M}_{\mathcal{T}}^{\left(0\right)}$ is the form before Householder
transformation, satisfying
$\mathbf{M}_{\mathcal{T}}^{\left(0\right)}={{\mathbf{M}}_{\mathcal{T}}}$;
$\mathbf{M}_{\mathcal{T}}^{\left({{n}_{1}}\right)}$ is the result after
$\text{``LO''}-$QR decomposition. Thm. 6 demonstrates that, in the process of
Householder transformation, $\mathbf{M}_{\mathcal{T}}^{\left(k\right)}$
satisfies some invariant properties.

Figure 5: Householder Transformations in $\text{``LO''}-$QR Decomposition on
${{\mathbf{M}}_{\mathcal{T}}}$

######  Theorem 6.

For the $\text{``LO''}-$QR decomposition on ${{\mathbf{M}}_{\mathcal{T}}}$,
after $k$ $\left(0\leq k\leq{{n}_{1}}-1\right)$ times of Householder
transformation, $\mathbf{M}_{\mathcal{T}}^{\left(k\right)}$ always keeps the
following three properties unchanged:

  * a)

$\mathbf{M}_{\uparrow}^{\left(k\right)}\sim{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}}}$;

  * b)

Each line of $\mathbf{M}_{\downarrow}^{\left(k\right)}$ has one and only one
non-zero value;

  * c)

The last $k$ columns of $\mathbf{M}_{\downarrow}^{\left(k\right)}$ (i.e., the
columns from ${{n}_{1}}-k+1$ to ${{n}_{1}}$) are all $0$.

###### Proof.

See Appendix A.8. ∎

As shown in Fig. 5, with the Householder transformation proceeds, the non-zero
elements in $\mathbf{M}_{\downarrow}^{\left(k\right)}$ shift from right to
left, and the position of the non-zero elements of
$\mathbf{M}_{\uparrow}^{\left(k\right)}$ remains unchanged. Specifically, in
the $k$-th Householder transformation, all non-zero elements in the
$\left({{n}_{1}}-k+1\right)$-th column of
$\mathbf{M}_{\downarrow}^{\left(k\right)}$ are transferred to the
${{f}_{{{n}_{1}}-k+1}}$-th column. Combining Thm. 6, we can infer the specific
form of $\mathbf{M}_{\mathcal{T}}^{\left({{n}_{1}}-1\right)}$ after
${{n}_{1}}-1$ times of Householder transformation. After the last householder
transformation, the result satisfies the following theorem.

######  Theorem 7.

After $\text{``LO''}-$QR decomposition, there is a
$\mathbf{G}_{{{\mathcal{T}}^{\left(1\right)}}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
and an orthogonal matrix $\mathbf{Q}$, which let
${{\mathbf{M}}_{\mathcal{T}}}$ satisfies:

${{\mathbf{M}}_{\mathcal{T}}}=\mathbf{Q}\left[\begin{matrix}\mathbf{G}_{{{\mathcal{T}}^{\left(1\right)}}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}\\\
\mathbf{O}\\\ \end{matrix}\right].$ (33)

###### Proof.

See Appendix A.9. ∎

Thm. 33 implies that the calculation
${{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}$
about ${{\mathbf{M}}_{\mathcal{T}}}$ in expression (8) can be replaced by
${{\mathcal{T}}^{\left(1\right)}}$. Since it is related to $\mathcal{T}$ and
${{\mathcal{T}}^{\left(1\right)}}$ simultaneously, we denote it as
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$. Thm.
8 shows that
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$ and
${{\mathbf{M}}_{\mathcal{T}}}$ are inner-product-equivalent.

######  Theorem 8.

For arbitrary ${{\mathbf{M}}_{\mathcal{T}}}$, there is a
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$
inner-product-equivalent to it, which satisfies

${{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}={{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{T}{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}},$
(34)

where ${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$
is the upper half $\mathbf{M}_{\downarrow}^{\left({{n}_{1}}\right)}$ of
${{\mathbf{M}}_{\mathcal{T}}}$ after $\text{``LO''}-$QR decomposition.

###### Proof.

See Appendix A.10. ∎

###  5.3 Generation Matrix-based Optimally Consistent Release Algorithm

The property of inner product equivalence provides us with a vital
optimization idea for an optimal release, as shown in Cor. 35. Using matrix
analysis, we convert the expression (8) into an expression about
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$ and
then use the mathematical properties of Generation Matrix to improve the
efficiency of optimal release.

######  Corollary 2.

The expression
$\mathbf{y}={{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}\mathbf{x}$
can be obtained by performing an upward propagation and a downward propagation
successively about
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$. That
is

$\mathbf{y}={{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}\mathbf{x}={{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{-1}\left({{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{-T}\mathbf{x}\right).$
(35)

###### Proof.

See Appendix A.11. ∎

According to Cor. 35, we get another optimal release form as follows.

$\overline{\mathbf{v}}=\widetilde{\mathbf{v}}-{{\mathbf{M}}_{\mathcal{T}}}\left({{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{-1}\left({{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{-T}\left({{\mathbf{M}}_{\mathcal{T}}}^{T}\widetilde{\mathbf{v}}\right)\right)\right).$
(36)

We illustrate with parentheses that Formula (36) is calculated from right to
left, ensuring that all multiplication and solution equations are for matrices
and vectors. According to the sparsity of ${{\mathbf{M}}_{\mathcal{T}}}$, the
time complexity of ${{\mathbf{M}}_{\mathcal{T}}}$-related multiplication
calculation in Formula (36) is $O\left(n\right)$. Besides, according to Prop.
14 and Prop. 15, the time complexity of solving the linear equation of
Generation Matrix is also $O\left({{n}_{1}}\right)$. Therefore, the overall
time complexity of Formula (36) is $O\left(n\right)$. Formula (36) has
completely summarized the core process of optimally consistent release. So
long as we execute the formula directly after constructing
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$, we
can efficiently obtain the optimal consistent release. The algorithm
description with Generation Matrices is very concise and easy to implement.

However, only ensuring that the calculation of
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$ is
also highly efficient, the whole process is efficient. So, we further proposed
Thm. 38 to calculate it.

######  Theorem 9.

Let ${{w}_{i}}$$\left(1\leq i\leq{{n}_{1}}\right)$ and
${{w}_{i\to{{f}_{i}}}}$$\left(2\leq i\leq{{n}_{1}}\right)$ as the weights of
the nodes and edges in
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$,
respectively. They satisfy

$\left\\{\begin{aligned} &{{w}_{i}}=\sqrt{1+{{\theta}_{i}}}\\\
&{{w}_{i\to{{f}_{i}}}}={{w}_{i}}^{-1}\\\ \end{aligned}\right.,$ (37)

where ${{\theta}_{i}}\left(1\leq i\leq{{n}_{1}}\right)$ satisfies

${{\theta}_{i}}=\left|{{\mathcal{C}}_{i}}\right|-\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{{\left(1+{{\theta}_{j}}\right)}^{-1}}}.$ (38)

###### Proof.

See Appendix A.12. ∎

Thm. 38 shows that ${{w}_{i}}$ and ${{w}_{i\to{{f}_{i}}}}$ can be directly
calculated by only requiring ${{\theta}_{i}}$, and the calculation of
${{\theta}_{i}}$ only needs to traverse from ${{n}_{1}}$ to $1$ once. Since
this process involves the calculation of $\left|{{\mathcal{C}}_{i}}\right|$,
the overall time complexity of constructing
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$ is
$O\left(n\right)$. The specific construction process is shown in Alg. 1.

Algorithm 1 Construct
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$ from
${{\mathbf{M}}_{\mathcal{T}}}$

0: Consistency Constraint Matrix ${{\mathbf{M}}_{\mathcal{T}}}$

0: the inner-product-equivalent
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$

1: Initialize $\boldsymbol{\theta}\in{{\mathbb{R}}^{{{n}_{1}}\times 1}}$,
satisfying ${{\theta}_{i}}=\left|{\mathcal{C}}_{i}\right|$.

2: for $i={{n}_{1}}\text{ to 2}$ do
${{\theta}_{{{f}_{i}}}}\leftarrow{{\theta}_{{{f}_{i}}}}-{{\left(1+{{\theta}_{i}}\right)}^{-1}}$;

3: for $i=1\text{ to }{{n}_{1}}$ do Let ${{w}_{i}}=\sqrt{1+{{\theta}_{i}}}$;

4: for $i=2\text{ to }{{n}_{1}}$ do Let
${{w}_{i\to{{f}_{i}}}}={{w}_{i}}^{-1}$;

5: Construct
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$ by
${{w}_{i}}$ and ${{w}_{i\to{{f}_{i}}}}$;

6: return
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$;

In summary, we propose a Generation Matrix-based optimally consistent release
algorithm (GMC) for differentially private hierarchical trees, described as
Alg. 2. Note that Step 1 to Step 3 in Alg. 2 are the normal hierarchical tree
release process, and Step 4 is the call of Alg. 1. Only step 5 is the core
step, which uses formula (36) to achieve optimally consistent release. In the
previous, the time complexity of formula (36) has been proved as
$O\left(n\right)$. Therefore, the overall time complexity of GMC is also
$O\left(n\right)$. Besides, it can be seen that GMC is a two-stage algorithm,
i.e., the construction of
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$ and
post-processing. If the same hierarchical tree is used for multiple releases,
we only need to construct
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$ once.

Algorithm 2 Generation Matrix-based Optimally Consistent Release Algorithm

0: hierarchical tree $\mathcal{T}$, dataset $\mathcal{D}$, privacy parameters
$\varepsilon$

0: the optimally consistent release $\overline{\mathbf{v}}$

1: Construct a vector $\mathbf{x}$ from $\mathcal{D}$, which satisfies
${{x}_{i}}={{\phi}_{i}}\left(\mathbf{D}\right)$.

2: Build a hierarchical tree with
$\mathbf{v}={{\mathbf{G}}_{\mathcal{T}}}^{-T}{{\mathbf{H}}_{\mathcal{H}}}^{T}\mathbf{x}$;

3: Calculate the height of $\mathcal{T}$, then get $\widetilde{\mathbf{v}}$ by
adding noise to $\mathbf{v}$, where
${{\widetilde{v}}_{i}}={{v}_{i}}+{{\xi}_{i}},{{\xi}_{i}}\sim\operatorname{Lap}\left({h}/{\varepsilon}\;\right)$.

4: Construct ${{\mathbf{M}}_{\mathcal{T}}}$, then substitute it into Alg. 1 to
obtain
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$;

5: Calculate
$\overline{\mathbf{v}}=\widetilde{\mathbf{v}}-{{\mathbf{M}}_{\mathcal{T}}}\left({{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{-1}\left({{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{-T}\left({{\mathbf{M}}_{\mathcal{T}}}^{T}\widetilde{\mathbf{v}}\right)\right)\right)$;

6: return $\overline{\mathbf{v}}$;

In addition, we can further optimize the algorithm. Considering that the
construction of
${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$
involves square root extraction, which may cause more calculation overhead, we
propose an improved version of Alg. 2 to avoid any square root. The main idea
is shown as follows.

$\overline{\mathbf{v}}=\widetilde{\mathbf{v}}-{{\mathbf{M}}_{\mathcal{T}}}\left(\mathbf{G}{{{}_{{{\mathcal{T}}^{\left(1\right)}}}^{\left(\boldsymbol{\theta}^{\prime},\mathbf{1}\right)}}^{-1}}\left(\boldsymbol{\theta}^{\prime}*\left(\mathbf{G}{{{}_{{{\mathcal{T}}^{\left(1\right)}}}^{\left(\boldsymbol{\theta}^{\prime},\mathbf{1}\right)}}^{-T}}\left({{\mathbf{M}}_{\mathcal{T}}}^{T}\widetilde{\mathbf{v}}\right)\right)\right)\right).$
(39)

Where the vector
$\boldsymbol{\theta}^{\prime}={{\left[{{\theta}_{1}},{{\theta}_{2}},\ldots,{{\theta}_{{{n}_{1}}}}\right]}^{T}}+1$,
and “$*$” is Hadamard product [32]. The new version without square root
extraction can slightly improve the calculation efficiency, which shows that
the algorithm under the matrix description has high scalability. The
improvement of the algorithm only needs to make some slight modifications on
Formula (36). Furthermore, we can directly extend the existing model to solve
other hierarchical tree problems, such as the hierarchical tree release with
the non-uniform privacy budget.

##  6 Experiment

We conducted experiments to verify the performance of GMC our proposed for
differentially private hierarchical tree release. All our experiments are run
on a computer with Dual $4$ Core $3.9$ GHz AMD Ryzen CPUs, $32$GB RAM, and
MATLAB’s development software. To improve the reliability of our experimental
results, we repeatedly run the same experimental setup $100$ times and then
take the average of multiple experimental results as the final results. In
addition, we denote the output of our algorithm by
${{\mathbf{v}}^{\left(out\right)}}$ or ${{\mathbf{x}}^{\left(out\right)}}$,
$v_{i}^{\left(out\right)}$, and their $i$-th outputs are denoted as
$v_{i}^{\left(out\right)}$ and $x_{i}^{\left(out\right)}$, respectively.

###  6.1 Datasets and Comparison Algorithms

Our experiments run on $3$ large datasets with more than $10$ million nodes.
They are Census2010, NYCTaxi, and SynData, with the following details.

Census2010[33]: Due to the plan that the U.S. Census Bureau announced using
differential privacy[2], we adopt the 2010 U.S. Census dataset as our first
dataset, which contains demographic information of all Americans. The
statistical results are divided into $8$ levels by the geographic components,
i.e., “United States - State - County - County Subdivision - Place/Remainder -
Census Tract - Block Group - Block”. The dataset contains $312,471,327$
individuals, which construct a hierarchical tree containing $11,802,162$
nodes. One of its typical applications is to provide users with queries on the
population of the area of interest, called “Node Query”. For example, a user
submits a query request “What is the population of Albany County in New York,
USA?”. The system will return the value at the node “USA - New York - Albany
County”. After verification, we ensured that the data before adding noise
satisfies consistency.

NYCTaxi[34]: This data set comes from car ride records in New York City in
2013. In order to ensure the uniqueness of the data, we selected the data
provided by Creative Mobile Technologies. According to the start time of the
taxi, we constructed a statistical histogram of the frequency of people taking
a taxi in seconds and provided a range query. The process of building a
hierarchical tree is random, which ensures that our algorithm can handle any
hierarchical tree structure. The data contains $86,687,775$ individuals. Since
we count the ride frequency by seconds, the number of histograms (leaf nodes)
totals $31,536,000$. The fan-out of nodes is random. In our experiments, we
set the proportion of nodes with fan-outs of $2$, $3$, $4$ and $5$ to
$\left\\{40\%,30\%,20\%,10\%\right\\}$. In this way, the hierarchical tree we
build contains approximately $45$ to $50$ million nodes.

SynData: To test the hierarchical tree with special structures, we adopt a
randomly synthesized dataset for our experiments. In synthetic data, the
hierarchical tree structure is a complete binary, and the number of nodes $n$
is controlled by the tree height $h$, where $n={{2}^{h}}-1$. We generate
${{x}_{i}}$ by Poisson distribution, i.e.,
${{x}_{i}}\sim\operatorname{Poi}\left(\lambda\right)$. In our experiments, we
set $\lambda=100$ and take $h=24$ as the complete dataset, containing
$16,777,215$ nodes. Like NYCTaxi, we focus on the “Range Query” on SynData.

Table 2: Description of the Algorithms Name | Description
---|---
Processless | No processing after adding noise.
Boosting | Boosting[13], the classic post-processing of only for the complete trees. For arbitrary structure, we take the fan-out of root as the fan-out of the algorithm.
PrivTrie | The post-processing in PrivTrie[14], which has been proven to achieve the optimally consistent release for arbitrary hierarchical tree.
GMC | Our post-processing for arbitrary hierarchical tree, which achieve the optimally consistent release based on Generation Matrix.

Our experiments compare $4$ different algorithm settings. Their details are
shown in Tab. 2. Because our experiment is for large-scale hierarchical trees
with more than $10$ million nodes, the time complexity of the selected
algorithm settings is both $O\left(n\right)$.

###  6.2 Verifying the Effectiveness for GMC

In the first experiment, we verify the effectiveness of GMC with two main
aspects, i.e., error and consistency.

The error is measured by the root mean square error ($rmse$), whose
calculation methods are different for “Node Query” and “Range Query”. We
denote the $rmse$ of “Node Query” (For Census2010) by ${{rmse}_{NQ}}$, and its
formula is

${{rmse}_{NQ}}=\sqrt{\frac{1}{n}\sum\nolimits_{i=1}^{n}{{{\left(v_{i}^{\left(out\right)}-{{v}_{i}}\right)}^{2}}}}.$
(40)

And the $rmse$ of “Range Query” (For NYCTaxi and SynData) is denoted as
${{rmse}_{RQ}}$, calculated by

${{rmse}_{RQ}}=\sqrt{\frac{1}{q}\sum\nolimits_{i=1}^{q}{{{\left(\sum\nolimits_{j={{a}_{i}}}^{{{b}_{i}}}{x_{i}^{\left(out\right)}}-\sum\nolimits_{j={{a}_{i}}}^{{{b}_{i}}}{{{x}_{j}}}\right)}^{2}}}}.$
(41)

Where $q$ is the number of range queries selected randomly and without
repetition, and the range of the $i$-th query is recorded as
$\left[{{a}_{i}},{{b}_{i}}\right]$. The main reason for random sampling is
that all range queries are up to $C_{m}^{2}$ so that we cannot test all range
queries. In our experiment, we take $q={{10}^{5}}$.

The consistency of the outputs is measured by consistency bias. Let
$\mathbf{\Delta}={{\mathbf{M}}^{T}}{{\mathbf{v}}^{\left(out\right)}}$, and
${{\Delta}_{i}}$ as the $i$-th element of $\mathbf{\Delta}$, then $bias$
satisfies

$bias=\sqrt{{\sum\nolimits_{i=1}^{{{n}_{1}}}{{{\Delta}_{i}}^{2}}}/{{{n}_{1}}}\;}.$
(42)

Besides, we adopt the complete datasets in the experiment and take
$\varepsilon=1$.

Table 3: Experimental Results on Multiple Algorithm Settings and Large-scale Datasets | Census2010 | NYCTaxi | SynData
---|---|---|---
${{rmse}}$ | ${{bias}}$ | ${{rmse}}$ | ${{bias}}$ | ${{rmse}}$ | ${{bias}}$
Processless | 11.32 | 49.61 | 138.42 | 48.38 | 166.37 | 61.24
Boosting | 11.30 | 159.01 | 120.75 | 22.42 | 74.94 | 0.00
PrivTrie | 11.00 | 0.00 | 68.69 | 0.00 | 74.94 | 0.00
GMC | 11.00 | 0.00 | 68.69 | 0.00 | 74.94 | 0.00

Since the optimally consistent release problem of the differentially private
hierarchical tree is a convex optimization problem, its solution is unique. If
the outputs of GMC also satisfy optimally consistent, they should be the same
as PrivTrie. The results in Tab. 3 confirm this point. They show that GMC is
effective and correct. However, it does not mean that PrivTrie and GMC are
entirely equivalent. Their implementations are entirely different, so we need
further to analyze the algorithms’ performance in the subsequent experiments.

In addition, the results also show the major drawback of Boosting. i.e., it
can only guarantee the consistency of complete trees. If the fan-outs of nodes
are different, Boosting cannot guarantee that the results are consistent.
Especially for Census2010, where the fan-out of nodes is highly different,
Boosting results in more significant consistency bias after post-processing.

###  6.3 Performance Testing

In this section, we focus on the algorithms’ performance and test the running
time of the algorithms above from small-scale data to large-scale data. To
construct hierarchical trees with different scales, we adopted the following
different methods according to the characteristics of each dataset. For
Census2010, we obtain a smaller hierarchical tree by $k-$order subtree. For
example, in its $4-$order subtree, the leaves represent the “County
Subdivision” level. For NYC taxi, we divide the data of 2013 into $12$ months.
The data of the first $k$ months as the $k$-th subset. For SynData, we control
the data scale by directly setting the tree height. In the experiment, we used
the six different tree heights $\left\\{8,12,16,20,24\right\\}$ to generate
hierarchical trees with different scales. Since Processless does not perform
any processing for consistency, we omit it in the experiment.

(a) Census2010

(b) NYCTaxi

(c) SynData

Figure 6: The Comparison of Running Time for Various Different Data Scales

In Fig. 6, the experimental results show that all three algorithms can
complete the post-processing within some time, but their running times are
quite different. Boosting and PrivTrie need more than 200 seconds to process
the hierarchical trees with tens of millions of nodes, while GMC only needs
about $2$ seconds to process the same data (See Fig. 6a). Their performance
gap is up to $100$ times. It shows that even if Boosting and PrivTrie have
reached the lowest time complexity with $O\left(n\right)$, they still have
much space for performance improvement. In addition to the relatively
inefficient recursive algorithms, another important reason is that GMC uses
standard matrix operations to complete the post-processing after establishing
the matrix model. These standard matrix operations introduce many optimization
techniques in the underlying design, which can make full use of computer
resources and significantly improve computing efficiency. Although the results
above do not deny that Boosting and PrivTrie can handle large-scale
hierarchical trees, applying them to some scenarios, such as real-time data
updates or more complex models, may cause considerable challenges in
computational efficiency.

Figure 7: Running Time for Two Stages of GMC with Complete Datasets

Finally, we test the running time for the two stages of GMC, i.e., the
Generation Matrix construction (Stage 1) and the post-processing (Stage 2). In
Fig. 7, we can see that the time overhead in Stage 1 is much more significant
than in Stage 2. The reason is the Generation Matrix construction includes the
sorting by Descending Order of Height, counting the number of children, and
some high-cost operations such as division, square root (in the process of
calculating ${{\theta}_{i}}$). It is worth noting that the Generation Matrix
construction is independent of the data to be released and does not involve
individual privacy. When the same hierarchical tree structure is reused in
multiple releases, we only need to perform the construction process once,
further reducing the overall running time of the optimally consistent
releases.

##  7 Conclusions and Future Work

In the previous, we successfully defined Generation Matrix and demonstrated
many of its critical mathematical properties. Using Generation Matrix, we can
implement various hierarchical tree operations without accessing the local
structure, which provides crucial theoretical support for the Matrixing
Research Method of hierarchical trees. The application on the differentially
private hierarchical tree release reflects the Generation Matrix’s
practicability. The proposed GMC based on Generation Matrix provides a concise
algorithm for optimally consistent release. Our experiments show that GMC has
achieved a significant performance improvement of up to $100$ times compared
with the state-of-the-art schemes.

The scientific problem that we solve in this paper is not very complicated,
but it is classic and is suitable as an example to show the practicability of
the Generation Matrix. However, the hierarchical tree problems that Generation
Matrix can solve are far more than the application. We can use it to explore
more complex hierarchical tree release problems and even the problems that
have not been solved so far. For example, the issue of non-negative consistent
release of hierarchical trees currently does not exist any closed-form
solution with time complexity of $O\left(n\right)$, which makes it very
difficult to solve the optimal release satisfying both consistency and non-
negativity for large-scale data. Nonetheless, Generation Matrix provides us
with a critical analysis tool to challenge the problem.

##  Appendix A Partial Proofs

###  A.1 Proof of Property 16

###### Proof.

According to the basic properties of the lower triangular matrix[24], the
inverse ${{\mathbf{G}}_{\mathcal{T}}}^{-1}$ of the lower triangular matrix
${{\mathbf{G}}_{\mathcal{T}}}$ is also a lower triangular matrix.

Considering ${{\mathbf{G}}_{\mathcal{T}}}^{-1}$’s $j$-th column vector
$\mathbf{g}_{j}^{\left(-1\right)}={{\mathbf{G}}_{\mathcal{T}}}^{-1}{{\mathbf{e}}_{j}}$,
whose $i$-th element is denoted as $g_{ij}^{\left(-1\right)}$, we have
$g_{ij}^{\left(-1\right)}=0,i<j$. Since only the $j$-th element of
${{\mathbf{e}}_{j}}$ is $1$, but the rest are all $0$,
$g_{ij}^{\left(-1\right)}$, for $i\geq j$, satisfies

$g_{ij}^{\left(-1\right)}=\left\\{\begin{array}[]{*{35}{l}}1&,i=j\\\
g_{{{f}_{j}},j}^{\left(-1\right)}&,i>j\\\ \end{array}\right..$ (43)

Therefore, $g_{jj}^{\left(-1\right)}=1$. Next, we adopt the contradiction
method to prove. Suppose $j$ is the ancestor of $i$, but
$g_{ij}^{\left(-1\right)}\neq 1$.

Let
$t_{0}^{\left(i\right)},t_{1}^{\left(i\right)},\ldots,t_{p}^{\left(i\right)}$
denote the node $i$ and its $p$ ancestors respectively.

Since $j$ is an ancestor of $i$, there is a $q$ such that
$j=it_{q}^{\left(i\right)}$. Therefore, we have
$g_{jj}^{\left(-1\right)}=g_{t_{q}^{\left(i\right)}j}^{\left(-1\right)}=\cdots=g_{t_{1}^{\left(i\right)}j}^{\left(-1\right)}=g_{ij}^{\left(-1\right)}\neq
1$ according to the recurrence formula (43).

The conclusion contradicts $g_{jj}^{\left(-1\right)}=1$. Therefore, when $j$
is an ancestor of $i$, $g_{ij}^{\left(-1\right)}=1$.

If $j$ is not an ancestor of $i$, obviously $j$ is not the root, i.e., $j>1$.
According to the formula (43), we have
$g_{1,j}^{\left(-1\right)}=g_{t_{p}^{\left(i\right)}j}^{\left(-1\right)}=\cdots=g_{t_{1}^{\left(i\right)}j}^{\left(-1\right)}=g_{ij}^{\left(-1\right)}$.
Since $g_{1,j}^{\left(-1\right)},j>1$ has been proved to be $0$, thus
$g_{ij}^{\left(-1\right)}=0$. ∎

###  A.2 Proof of Property 9

###### Proof.

Considering the $i$-th row of ${{\mathbf{G}}_{\mathcal{T}}}^{-1}$, we denote
${{U}_{i}}=\left\\{k\left|g_{ik}^{\left(-1\right)}\neq 0\right.\right\\}$ as
the set formed by the column subscripts of the non-zero elements in the $i$-th
row. According to
$\mathbf{M}={{\left({{\mathbf{G}}_{\mathcal{T}}}^{T}{{\mathbf{G}}_{\mathcal{T}}}\right)}^{-1}}={{\mathbf{G}}_{\mathcal{T}}}^{-1}{{\mathbf{G}}_{\mathcal{T}}}^{-T}$,
we have ${{m}_{ij}}$ satisfied

${{m}_{ij}}=\sum\nolimits_{k=1}^{n}{g_{ik}^{\left(-1\right)}g_{jk}^{\left(-1\right)}}=\sum\nolimits_{k\in{{U}_{i}}\cap{{U}_{j}}}{g_{ik}^{\left(-1\right)}g_{jk}^{\left(-1\right)}}=\left|{{U}_{i}}\cap{{U}_{j}}\right|$
(44)

According to Prop. 16, ${{U}_{i}}=\left\\{k\left|k\text{ is an ancestor of
}i\right.\right\\}$. Therefore, ${{U}_{i}}\cap{{U}_{j}}$ is the common
ancestor of $i$ and $j$ and ${{m}_{ij}}$ records the number of their common
ancestors.

Specifically, if $i=j$, ${{m}_{ii}}=\left|{{U}_{i}}\right|$, i.e., the number
of ancestors of $i$ plus $1$ (itself). Let the depth of the root be 1,
${{m}_{ii}}$ is the depth of $i$. ∎

###  A.3 Proof of Property 11

###### Proof.

Let
$\boldsymbol{\alpha}={{\left[{{\alpha}_{1}},{{\alpha}_{2}},\ldots,{{\alpha}_{n}}\right]}^{T}}$,
$\boldsymbol{\beta}={{\left[{{\beta}_{1}},{{\beta}_{2}},\ldots,{{\beta}_{n}}\right]}^{T}}$.
According to Equation (19), we have ${{w}_{i}}={{\alpha}_{i}}{{\beta}_{i}}$,
${{w}_{i\to{{f}_{i}}}}={{\alpha}_{{{f}_{i}}}}{{\beta}_{i}}$. That is,
$\ln{{w}_{i}}=\ln{{\alpha}_{i}}+\ln{{\beta}_{i}}$,
$\ln{{w}_{i\to{{f}_{i}}}}={{\alpha}_{{{f}_{i}}}}+{{\beta}_{i}}$. Therefore, we
have the following matrix equation holds.

$\left[\begin{matrix}\mathbf{I}&\mathbf{I}\\\
\mathbf{I}-\mathbf{G}&\mathbf{I}\\\
\end{matrix}\right]\left[\begin{matrix}\ln\boldsymbol{\alpha}\\\
\ln\boldsymbol{\beta}\\\
\end{matrix}\right]=\left[\begin{matrix}\ln{{\mathbf{w}}_{node}}\\\
\ln{{\mathbf{w}}_{edge}}\\\ \end{matrix}\right].$ (45)

According to the property of Block Matrix Inversion, we have

${{\left[\begin{matrix}\mathbf{I}&\mathbf{I}\\\
\mathbf{I}-\mathbf{G}&\mathbf{I}\\\
\end{matrix}\right]}^{-1}}=\left[\begin{matrix}{{\mathbf{G}}^{-1}}&-{{\mathbf{G}}^{-1}}\\\
\mathbf{I}-{{\mathbf{G}}^{-1}}&{{\mathbf{G}}^{-1}}\\\ \end{matrix}\right].$
(46)

And then,

$\left[\begin{matrix}\ln\boldsymbol{\alpha}\\\ \ln\boldsymbol{\beta}\\\
\end{matrix}\right]=\left[\begin{matrix}{{\mathbf{G}}_{\mathcal{T}}}^{-1}\left(\ln{{\mathbf{w}}_{node}}-\ln{{\mathbf{w}}_{edge}}\right)\\\
\ln{{\mathbf{w}}_{node}}+{{\mathbf{G}}_{\mathcal{T}}}^{-1}\left(\ln{{\mathbf{w}}_{edge}}-\ln{{\mathbf{w}}_{node}}\right)\\\
\end{matrix}\right]=\left[\begin{matrix}\ln\boldsymbol{\alpha}\\\
\ln{{\mathbf{w}}_{node}}-\ln\boldsymbol{\alpha}\\\ \end{matrix}\right].$ (47)

Performing the exponential operations $\exp\left(*\right)$ on both sides of
the equation (47) at the same time, we have formula (20) holds. ∎

###  A.4 Proof of Theorem 22

###### Proof.

Let ${{l}_{ij}}$ denote the element in row $i$ and column $j$ of
${{\mathbf{L}}_{\mathcal{T}}}$. According to the definition of Laplacian
Matrix[6], we have the diagonal elements ${{l}_{ii}}$ representing the number
of adjacent nodes of $i$; and if $j$ is the adjacent node of $i$, i.e.,
$j={{f}_{i}}$ or $i={{f}_{j}}$, we have ${{l}_{ij}}=-1$; otherwise,
${{l}_{ij}}=0$.

According to the expression (22), we have

${{l}_{ij}}=\left\\{\begin{array}[]{*{35}{l}}\left(\sum\nolimits_{k\in{{U}_{1}}}{{{g}_{k1}}{{g}_{k1}}}\right)-1&,i=j=1\\\
\sum\nolimits_{k\in{{U}_{i}}\cap{{U}_{j}}}{{{g}_{ki}}{{g}_{kj}}}&,\text{otherwise}\\\
\end{array}\right.$ (48)

where ${{U}_{j}}=\left\\{k\left|{{g}_{kj}}\neq
0\right.\right\\}=\left\\{j\right\\}\cup{{\mathcal{C}}_{j}}$ denotes the set
formed by the row subscripts of non-zero elements in the $j$-th column of
${{\mathbf{G}}_{\mathcal{T}}}$.

Next, we discuss the following situations:

For $i=j=1$, under the definition of Laplacian Matrix, ${{l}_{11}}$ should be
equal to the number of children of the root, i.e.,
${{l}_{11}}=\left|{{\mathcal{C}}_{1}}\right|$. According to the expression
(22), there is $k\in\left\\{1\right\\}\cup{{\mathcal{C}}_{1}}$ and
${{l}_{11}}=\left|\left\\{1\right\\}\cup{{\mathcal{C}}_{1}}\right|-1=\left|{{\mathcal{C}}_{1}}\right|$.
It conforms to the definition of Laplacian Matrix.

For $i=j>1$, under the definition of Laplacian Matrix, ${{l}_{ii}}$ should be
equal to the number of $i$’s children and parent, i.e.,
${{l}_{ii}}=\left|{{\mathcal{C}}_{i}}\cup{{f}_{i}}\right|=\left|{{\mathcal{C}}_{i}}\right|+1$.
According to the expression (22),
${{l}_{ii}}=\sum\nolimits_{k\in{{U}_{i}}}{{{g}_{ki}}{{g}_{ki}}}=\left|\left\\{i\right\\}\cup{{\mathcal{C}}_{i}}\right|=\left|{{\mathcal{C}}_{i}}\right|+1$.
It conforms to the definition of Laplacian Matrix.

For $i\neq j$ but $i\in{{\mathcal{C}}_{j}}$, under the definition of Laplacian
Matrix, ${{l}_{ij}}=-1$. According to the expression (22),
$k\in{{U}_{i}}\cap{{U}_{j}}\text{=}\left(\left\\{i\right\\}\cup{{\mathcal{C}}_{i}}\right)\cap\left(\left\\{j\right\\}\cup{{\mathcal{C}}_{j}}\right)=\left\\{i\right\\}\cap{{\mathcal{C}}_{j}}=\left\\{i\right\\}$,
we have ${{l}_{ij}}={{g}_{ii}}{{g}_{ij}}=-1$. Again, It conforms to the
definition of Laplacian Matrix. Similarly, if $i\neq j$ and
$j\in{{\mathcal{C}}_{i}}$, ${{l}_{ij}}=-1$. Finally, when $i\neq j$ and $j$
and $i$ do not contain a parent-child relationship,
${{U}_{i}}\cap{{U}_{j}}=\varnothing$ , ${{L}_{ij}}=0$, which also conforms to
the definition of Laplacian Matrix.

Therefore, in any case, the expression(22) always conforms to the definition
of the Laplacian Matrix. ∎

###  A.5 Proof of Theorem 23

###### Proof.

Let ${{d}_{ij}}$ denote the element in row $i$ and column $j$ of
${{\mathbf{D}}_{\mathcal{T}}}$.

Figure 8: The Distance of Node $i$, $j$ and Their Nearest Common Ancestor

According to the definition of distance matrix[7], ${{d}_{ij}}$ is the
distance from node $i$ to $j$. As shown in Fig. 8, $c$ (red node) is the
nearest common ancestor of nodes $i$ and $j$. ${{d}_{c}}$ denotes the depth of
node $c$ (i.e., the distance from node C to the root (orange node) plus 1);
${{d}_{1}}$ denotes the distance from $c$ to $i$; ${{d}_{2}}$ denotes the
distance from $c$ to $j$. Obviously, the distance
${{d}_{ij}}={{d}_{1}}+{{d}_{2}}$.

Considering expression (23), let
${{\mathbf{M}}_{1}}={{\mathbf{G}}_{\mathcal{T}}}^{-1}\mathbf{I}{{\mathbf{I}}^{T}}$,
${{\mathbf{M}}_{2}}=\mathbf{I}{{\mathbf{I}}^{T}}{{\mathbf{G}}_{\mathcal{T}}}^{-T}$,
${{\mathbf{M}}_{2}}=\mathbf{I}{{\mathbf{I}}^{T}}{{\mathbf{G}}_{\mathcal{T}}}^{-T}$
and $m_{ij}^{\left(k\right)}$ denotes the element in the row $i$ and column
$j$ of ${{\mathbf{M}}_{k}}$. According to Prop. 6,
$m_{ij}^{\left(1\right)}=m_{ji}^{\left(2\right)}$ is the depth of the node
$i$, i.e., $m_{ij}^{\left(3\right)}={{d}_{c}}$. According to Prop. 9,
$m_{ij}^{\left(3\right)}$ is the number of common ancestors of $i$ and $j$
(the depth of $c$), i.e., $m_{ij}^{\left(3\right)}={{d}_{c}}$.

Substituting them into expression (23), we have

${{d}_{ij}}=m_{ij}^{\left(1\right)}+m_{ij}^{\left(2\right)}-2m_{ij}^{\left(3\right)}=\left({{d}_{1}}+{{d}_{c}}\right)+\left({{d}_{2}}+{{d}_{c}}\right)-2{{d}_{c}}={{d}_{1}}+{{d}_{2}}$
(49)

The expression (49) is consistent with the definition, so
${{\mathbf{D}}_{\mathcal{T}}}$ can be calculated by expression (23). ∎

###  A.6 Proof of Theorem 24

###### Proof.

Let ${{c}_{ij}}$ denote the element in row $i$ and column $j$ of
${{\mathbf{C}}_{\mathcal{T}}}$.

According to the definition of Ancestral Matrix[8], ${{c}_{ij}}$ represents
the distance from the nearest common ancestor of leaves $i$ and $j$ to the
root.

Note, Prop. 9 has been proved that the element of
${{\left({{\mathbf{G}}_{\mathcal{T}}}^{T}{{\mathbf{G}}_{\mathcal{T}}}\right)}^{-1}}$
is the number of the common nodes, i.e., the distance from the nearest common
ancestor to the root node plus $1$.

Therefore, we can get ${{\mathbf{C}}_{\mathcal{T}}}$ by taking the sub-matrix
corresponding to the leaves in
${{\left({{\mathbf{G}}_{\mathcal{T}}}^{T}{{\mathbf{G}}_{\mathcal{T}}}\right)}^{-1}}$
and then subtracting $1$. ∎

###  A.7 Proof of Theorem 28

###### Proof.

According to formula (5), the noise we add to each element in
$\widetilde{\mathbf{v}}$ is i.i.d, and satisfies
$\operatorname{Lap}\left({h}/{\varepsilon}\;\right)$. Since the variance of
$\operatorname{Lap}\left(b\right)$ is $2{{b}^{2}}$, the covariance matrix of
$\widetilde{\mathbf{v}}$ is
$D\left(\widetilde{\mathbf{v}}\right)=2\left({{{h}^{2}}}/{{{\varepsilon}^{2}}}\;\right)\mathbf{I}$.

According to the mean square error analysis of differential privacy, we have

$\operatorname{mse}\left(\widetilde{\mathbf{v}}\right)=\operatorname{trace}\left(D\left(\widetilde{\mathbf{v}}\right)\right)=2\left({{{h}^{2}}}/{{{\varepsilon}^{2}}}\;\right)\operatorname{trace}\left(\mathbf{I}\right)={2n{{h}^{2}}}/{{{\varepsilon}^{2}}}\;$
(50)

In addition, according to formula (8),

$D\left(\overline{\mathbf{v}}\right)=D\left(\left(\mathbf{I}-{{\mathbf{M}}_{\mathcal{T}}}{{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}{{\mathbf{M}}_{\mathcal{T}}}^{T}\right)\widetilde{\mathbf{v}}\right)=2\left({{{h}^{2}}}/{{{\varepsilon}^{2}}}\;\right)\left(\mathbf{I}-{{\mathbf{M}}_{\mathcal{T}}}{{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}{{\mathbf{M}}_{\mathcal{T}}}^{T}\right)$
(51)

Then,

$\begin{aligned}
\operatorname{mse}\left(\overline{\mathbf{v}}\right)=&\operatorname{trace}\left(D\left(\overline{\mathbf{v}}\right)\right)=2\left({{{h}^{2}}}/{{{\varepsilon}^{2}}}\;\right)\operatorname{trace}\left(\mathbf{I}-{{\mathbf{M}}_{\mathcal{T}}}{{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}{{\mathbf{M}}_{\mathcal{T}}}^{T}\right)\\\
=&2\left({{{h}^{2}}}/{{{\varepsilon}^{2}}}\;\right)\left(n-\operatorname{trace}\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}{{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}\right)\right)\\\
\end{aligned}.$ (52)

Since ${{\mathbf{M}}_{\mathcal{T}}}\in{{\mathbb{R}}^{n\times{{n}_{1}}}}$, we
have

$\operatorname{trace}\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}{{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}\right)=\operatorname{trace}\left(\mathbf{I}\right)={{n}_{1}}.$
(53)

Substituting it into (52), we have

$\operatorname{mse}\left(\overline{\mathbf{v}}\right)=2\left({{{h}^{2}}}/{{{\varepsilon}^{2}}}\;\right)\left(n-{{n}_{1}}\right)={2m{{h}^{2}}}/{{{\varepsilon}^{2}}}\;$
(54)

∎

###  A.8 Proof of Theorem 6

###### Proof.

By Def. 29, it is obvious that the process of Householder transformation
satisfies property c). Because the process of $\text{``LO''}-$QR decomposition
is the process of setting $0$ column by column from the last column to the
first column.

According to Def. 5, $\mathbf{M}_{\mathcal{T}}^{\left(0\right)}$ satisfies
both properties a),b) and c).

Assume that M satisfies both properties a), b) and c). By the formula (31),
the expression of the $k$-th Householder transformation is as follows:

$\mathbf{M}_{\mathcal{T}}^{\left(k\right)}={{\operatorname{House}}_{{{\mathcal{S}}_{k}},{{t}_{k}}}}\left(\mathbf{M}_{\mathcal{T}}^{\left(k-1\right)}\right),$
(55)

where ${{t}_{k}}={{n}_{1}}-k+1$. Considering that
$\mathbf{M}_{\mathcal{T}}^{\left(k-1\right)}$ satisfies the property a) and is
a lower triangular matrix, the values of ${{\mathcal{S}}_{k}}$ can be
simplified, taking
${{\mathcal{S}}_{k}}=\left\langle{{t}_{k}},{{n}_{1}}+1,\ldots,n\right\rangle$.

According to Def. 30 , during the transformation process, ${{\mathbf{m}}_{k}}$
and ${{\boldsymbol{\omega}}_{k}}$ satisfy

$\left\\{\begin{aligned}
&{{\mathbf{m}}_{k}}={{\left[m_{{{t}_{k}},{{t}_{k}}}^{\left(k-1\right)},m_{{{n}_{1}}+1,{{t}_{k}}}^{\left(k-1\right)},m_{{{n}_{1}}+2,{{t}_{k}}}^{\left(k-1\right)},\ldots,m_{n,{{t}_{k}}}^{\left(k-1\right)}\right]}^{T}}\\\
&{{\boldsymbol{\omega}}_{k}}={{\left[m_{{{t}_{k}},{{t}_{k}}}^{\left(k-1\right)}-\rho,m_{{{n}_{1}}+1,{{t}_{k}}}^{\left(k-1\right)},m_{{{n}_{1}}+2,{{t}_{k}}}^{\left(k-1\right)},\ldots,m_{n,{{t}_{k}}}^{\left(k-1\right)}\right]}^{T}}\\\
\end{aligned}\right.,$ (56)

where
${{\rho}_{k}}=\left\|{{\mathbf{m}}_{k}}\right\|=\sqrt{\sum\limits_{s\in{{\mathcal{S}}_{k}}}{m{{{}_{s,{{t}_{k}}}^{\left(k\right)}}^{2}}}}$.
By calculating ${{\boldsymbol{\omega}}_{k}}^{T}{{\mathbf{m}}_{k}}$, we have

${{\boldsymbol{\omega}}_{k}}^{T}{{\mathbf{m}}_{k}}=\left(m_{{{t}_{k}},{{t}_{k}}}^{\left(k-1\right)}-{{\rho}_{k}}\right)m_{{{t}_{k}},j}^{\left(k-1\right)}+\sum\limits_{s={{n}_{1}}+1}^{n}{m_{s,{{t}_{k}}}^{\left(k-1\right)}m_{s,j}^{\left(k-1\right)}}.$
(57)

Due to $\mathbf{M}_{\mathcal{T}}^{\left(k-1\right)}$ satisfies the property
b), for the same row $s>{{n}_{1}}$, at most only one of
$m_{s,{{t}_{k}}}^{\left(k-1\right)}$ and $m_{s,j}^{\left(k-1\right)}$ in
$\mathbf{M}_{\mathcal{T}}^{\left(k-1\right)}$ is non-zero. Therefore,

${{\boldsymbol{\omega}}_{k}}^{T}{{\mathbf{m}}_{k}}=\left(m_{{{t}_{k}},{{t}_{k}}}^{\left(k-1\right)}-{{\rho}_{k}}\right)m_{{{t}_{k}},j}^{\left(k-1\right)}.$
(58)

Simplifying according to formula (30), we can get
$\mathbf{M}_{\mathcal{T}}^{\left(k\right)}$ after $k$-th Householder
transformation, whose element $m_{i,j}^{\left(k\right)}$ in in row $i$ and
column $j$ satisfies

$m_{i,j}^{\left(k\right)}=\left\\{\begin{array}[]{*{35}{l}}{{\rho}_{k}}&,i={{t}_{k}},j={{t}_{k}}\\\
0&,{{n}_{1}}+1\leq i\leq n,j={{t}_{k}}\\\
{m_{{{t}_{k}},j}^{\left(k-1\right)}m_{{{t}_{k}},{{t}_{k}}}^{\left(k-1\right)}}/{{{\rho}_{k}}}&,i={{t}_{k}},j\neq{{t}_{k}}\\\
m_{i,j}^{\left(k-1\right)}+{m_{i,{{t}_{k}}}^{\left(k-1\right)}m_{{{t}_{k}},j}^{\left(k-1\right)}}/{{{\rho}_{k}}}&,{{n}_{1}}+1\leq
i\leq n,j\neq{{t}_{k}}\\\ m_{i,j}^{\left(k-1\right)}&,\text{otherwise}\\\
\end{array}\right.$ (59)

According to the recursive expression (59), consider the properties of
$\mathbf{M}_{\mathcal{T}}^{\left(k\right)}$. First, consider the property a).
Since
$\mathbf{M}_{\uparrow}^{\left(k-1\right)}\sim{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}}}$,
and only the row ${{t}_{k}}={{n}_{1}}-k+1$ in the first ${{n}_{1}}$ rows of
$\mathbf{M}_{\mathcal{T}}^{\left(k-1\right)}$ is affected, according to the
sparsity of GM, it can be known that the ${{t}_{k}}$-th row of
$\mathbf{M}_{\mathcal{T}}^{\left(k-1\right)}$ satisfies
$m_{{{t}_{k}},j}^{\left(k-1\right)}\neq 0$ if and only if
$j\in\left\\{{{t}_{k}},{{f}_{{{t}_{k}}}}\right\\}$.

Since ${m_{{{t}_{k}},{{t}_{k}}}^{\left(k-1\right)}}/{{{\rho}_{k}}}\;\neq 0$,
according to
$m_{{{t}_{k}},j}^{\left(k\right)}={m_{{{t}_{k}},j}^{\left(k-1\right)}m_{{{t}_{k}},{{t}_{k}}}^{\left(k-1\right)}}/{{{\rho}_{k}}}\;$
for $j\neq{{t}_{k}}$, we have $m_{{{t}_{k}},j}^{\left(k\right)}\neq
0\Leftrightarrow m_{{{t}_{k}},j}^{\left(k-1\right)}\neq 0$.

Therefore, there is no mutual conversion between non-zero elements and zero
elements in the only affected ${{t}_{k}}$-th row.
$\mathbf{M}_{\mathcal{T}}^{\left(k\right)}$ satisfies property a).

Next consider property b). For the rows ${{n}_{1}}+1\sim n$, according to the
property c), all the values of the ${{t}_{k}}$-th column of
$\mathbf{M}_{\downarrow}^{\left(k\right)}$ are $0$. Consider the $j$-th column
$\left(j\neq{{t}_{k}}\right)$ of $\mathbf{M}_{\downarrow}^{\left(k\right)}$,
we have

$m_{i,j}^{\left(k\right)}=m_{i,j}^{\left(k-1\right)}+{m_{i,{{t}_{k}}}^{\left(k-1\right)}m_{{{t}_{k}},j}^{\left(k-1\right)}}/{{{\rho}_{k}}}\;.$
(60)

If $j\neq{{f}_{{{t}_{k}}}}$, there is $m_{{{t}_{k}},j}^{\left(k-1\right)}=0$,
i.e., $m_{i,j}^{\left(k\right)}=m_{i,j}^{\left(k-1\right)}$; If
$j={{f}_{{{t}_{k}}}}$, there is $m_{{{t}_{k}},j}^{\left(k-1\right)}\neq 0$,
i.e., $m_{i,j}^{\left(k\right)}\neq 0\Leftrightarrow
m_{i,j}^{\left(k-1\right)}\neq 0\vee m_{i,{{t}_{k}}}^{\left(k-1\right)}\neq
0$.

Therefore, the $k$-th Householder transformation is equivalent to transferring
non-zero elements from the ${{t}_{k}}$-th column of
$\mathbf{M}_{\downarrow}^{\left(k-1\right)}$ to the ${{f}_{{{t}_{k}}}}$-th
column of $\mathbf{M}_{\downarrow}^{\left(k-1\right)}$. The process keeps the
property b) holds.

In summary, $\mathbf{M}_{\mathcal{T}}^{\left(k\right)}$ also satisfies the
properties a), b) and c). Since $\mathbf{M}_{\mathcal{T}}^{\left(0\right)}$
satisfies the properties a), b) and c), all
$\mathbf{M}_{\mathcal{T}}^{\left(k\right)}$$\left(0\leq
k\leq{{n}_{1}}-1\right)$ satisfy the properties a), b) and c). ∎

###  A.9 Proof of Theorem 33

###### Proof.

By Thm. 6, after ${{n}_{1}}-1$ Householder transformations,
$\mathbf{M}_{\mathcal{T}}^{\left({{n}_{1}}-1\right)}$ satisfies both the
properties a), b), and c).

Consider
$\mathbf{M}_{\mathcal{T}}^{\left({{n}_{1}}\right)}={{\operatorname{House}}_{{{\mathcal{S}}_{{{n}_{1}}}},1}}\left(\mathbf{M}_{\mathcal{T}}^{\left({{n}_{1}}-1\right)}\right)$
for the ${{n}_{1}}$-th Householder transformation. Due to
$\mathbf{M}_{\uparrow}^{\left({{n}_{1}}-1\right)}\sim{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}}}$
and only $m_{1,1}^{\left({{n}_{1}}-1\right)}$ in the first row of
$\mathbf{M}_{\uparrow}^{\left({{n}_{1}}-1\right)}$ is non-zero, which is the
only element of $\mathbf{M}_{\uparrow}^{\left({{n}_{1}}-1\right)}$ affected by
the last transformation. The transformed $m_{1,1}^{\left({{n}_{1}}\right)}$
satisfies

$m_{1,1}^{\left({{n}_{1}}\right)}=\sqrt{m{{{}_{1,1}^{\left({{n}_{1}}-1\right)}}^{2}}+\sum\limits_{s={{n}_{1}}+1}^{n}{m{{{}_{s,1}^{\left({{n}_{1}}-1\right)}}^{2}}}}.$
(61)

Therefore, there is still
$\mathbf{M}_{\uparrow}^{\left({{n}_{1}}\right)}\sim{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}}}$
after the last transformation, i.e., there is a
$\mathbf{G}_{{{\mathcal{T}}^{\left(1\right)}}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}$
satisfying
$\mathbf{G}_{{{\mathcal{T}}^{\left(1\right)}}}^{\left({{\mathbf{w}}_{node}},{{\mathbf{w}}_{edge}}\right)}=\mathbf{M}_{\uparrow}^{\left({{n}_{1}}\right)}$.
Besides, according to Def. 30 and property c), it can be known that
$\mathbf{M}_{\downarrow}^{\left({{n}_{1}}\right)}=\mathbf{O}$ after the last
transformation. ∎

###  A.10 Proof of Theorem 8

###### Proof.

Let ${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$
be the upper half of ${{\mathbf{M}}_{\mathcal{T}}}$ after the
$\text{``LO''}-$QR decomposition. According to Thm. 33, we have

${{\mathbf{M}}_{\mathcal{T}}}=\mathbf{Q}\left[\begin{matrix}{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}\\\
\mathbf{O}\\\ \end{matrix}\right].$ (62)

Substituting it into the expression
${{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}$, we have

${{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}=\left[\begin{matrix}{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{T}&\mathbf{O}\\\
\end{matrix}\right]{{\mathbf{Q}}^{T}}\mathbf{Q}\left[\begin{matrix}{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}\\\
\mathbf{O}\\\
\end{matrix}\right]=\left[\begin{matrix}{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{T}&\mathbf{O}\\\
\end{matrix}\right]\left[\begin{matrix}{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}\\\
\mathbf{O}\\\
\end{matrix}\right]={{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{T}{{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}.$
(63)

∎

###  A.11 Proof of Corollary 35

###### Proof.

Since ${{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}$
is reversible, according to Thm. 8, substituting formula (34) into
$\mathbf{y}={{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}\mathbf{x}$,
we have

$\mathbf{y}={{\left({{\mathbf{M}}_{\mathcal{T}}}^{T}{{\mathbf{M}}_{\mathcal{T}}}\right)}^{-1}}\mathbf{x}={{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{-1}\left({{\mathbf{G}}_{{{\mathcal{T}}^{\left(1\right)}}\leftarrow\mathcal{T}}}^{-T}\mathbf{x}\right).$
(64)

∎

###  A.12 Proof of Theorem 38

###### Proof.

Define a sequence ${{\theta}_{i}}\left(1\leq i\leq{{n}_{1}}\right)$ satisfies

${{\theta}_{i}}=\sum\limits_{s={{n}_{1}}+1}^{n}{m{{{}_{s,i}^{\left({{t}_{i}}\right)}}^{2}}},$
(65)

where ${{t}_{i}}={{n}_{1}}-i$. The $\left({{t}_{i}}+1\right)$-th Householder
transformation is the Householder transformation on the $i$-th column. And let
$j$ denote the child of $i$, i.e., $\left(j\in{{\mathcal{C}}_{i}}\right)$.

By recursive expression (59), in the first ${{t}_{i}}$ Householder
transformations, only the Householder transformation on the $j$-th column
(i.e., the $\left({{t}_{j}}+1\right)$-th transformation) will cause the value
of ${{m}_{s,i}}$$\left({{n}_{1}}+1\leq s\leq n\right)$ to change. Therefore,
$m_{s,i}^{\left({{t}_{i}}\right)}$ satisfies

$m_{s,i}^{\left({{t}_{i}}\right)}=m_{s,i}^{\left(0\right)}+\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{\left({m_{s,j}^{\left({{t}_{j}}\right)}m_{j,i}^{\left({{t}_{j}}\right)}}/{m_{j,j}^{\left({{t}_{j}}+1\right)}}\;\right)}.$
(66)

For a non-leaf node $i$, since the values of
$m_{j,i}^{\left({{t}_{j}}\right)}$ and $m_{j,j}^{\left({{t}_{j}}\right)}$
haven’t changed in the first ${{t}_{j}}$ Householder transformations, there
are $m_{j,j}^{\left({{t}_{j}}\right)}=1$ and
$m_{j,i}^{\left({{t}_{j}}\right)}=-1$. Therefore,
$m_{j,j}^{\left({{t}_{j}}+1\right)}$ satisfies

$m_{j,j}^{\left({{t}_{j}}+1\right)}=\sqrt{m{{{}_{j,j}^{\left({{t}_{j}}\right)}}^{2}}+\sum\limits_{s={{n}_{1}}+1}^{n}{m{{{}_{s,j}^{\left({{t}_{j}}\right)}}^{2}}}}=\sqrt{1+{{\theta}_{j}}}.$
(67)

Therefore, for ${{n}_{1}}+1\leq s\leq n$, we have

$m_{s,i}^{\left({{t}_{i}}\right)}=m_{s,i}^{\left(0\right)}-\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{m_{s,j}^{\left({{t}_{j}}\right)}}/{\sqrt{1+{{\theta}_{j}}}}\;}.$
(68)

According to formula (65), ${{\theta}_{i}}$ satisfies

${{\theta}_{i}}=\sum\limits_{s={{n}_{1}}+1}^{n}{m{{{}_{s,i}^{\left({{t}_{i}}\right)}}^{2}}}=\sum\limits_{s={{n}_{1}}+1}^{n}{{{\left(m_{s,i}^{\left(0\right)}-\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{m_{s,j}^{\left({{t}_{j}}\right)}}/{\sqrt{1+{{\theta}_{j}}}}\;}\right)}^{2}}}.$
(69)

According to Thm. 6, the process of $\text{``LO''}-$QR decomposition always
satisfies the property b), so at most only one item in
$m_{s,i}^{\left(0\right)}-\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{m_{s,j}^{\left({{t}_{j}}\right)}}/{\sqrt{1+{{\theta}_{j}}}}\;}$
is non-zero, and we have

${{\theta}_{i}}={{\left(m_{s,i}^{\left(0\right)}-\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{m_{s,j}^{\left({{t}_{j}}\right)}}/{\sqrt{1+{{\theta}_{j}}}}\;}\right)}^{2}}=m{{{}_{s,i}^{\left(0\right)}}^{2}}+\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{m{{{}_{s,j}^{\left({{t}_{j}}\right)}}^{2}}}/{\left(1+{{\theta}_{j}}\right)}\;}.$
(70)

Therefore,

$\displaystyle{{\theta}_{i}}=$
$\displaystyle\sum\limits_{s={{n}_{1}}+1}^{n}{{{\left(m_{s,i}^{\left(0\right)}-\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{m_{s,j}^{\left({{t}_{j}}\right)}}/{\sqrt{1+{{\theta}_{j}}}}\;}\right)}^{2}}}=\sum\limits_{s={{n}_{1}}+1}^{n}{m{{{}_{s,i}^{\left(0\right)}}^{2}}}+\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{\left({\sum\limits_{s={{n}_{1}}+1}^{n}{m{{{}_{s,j}^{\left({{t}_{j}}\right)}}^{2}}}}/{\left(1+{{\theta}_{j}}\right)}\;\right)}$
(71) $\displaystyle=$
$\displaystyle\sum\limits_{s={{n}_{1}}+1}^{n}{m{{{}_{s,i}^{\left(0\right)}}^{2}}}+\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{{{\theta}_{j}}}/{\left(1+{{\theta}_{j}}\right)}\;}=\sum\limits_{s={{n}_{1}}+1}^{n}{m{{{}_{s,i}^{\left(0\right)}}^{2}}}+\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{\left(1-{{\left(1+{{\theta}_{j}}\right)}^{-1}}\right)}.$

According to the definition of ${{\mathbf{M}}_{\downarrow}}$, for
${{n}_{1}}+1\leq s\leq n$, if $s\in{{\mathcal{C}}_{i}}$, then
$m_{s,i}^{\left(0\right)}=-1$, otherwise $m_{s,i}^{\left(0\right)}=0$.
Finally, ${{\theta}_{i}}$ is reduced to

${{\theta}_{i}}=\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j>{{n}_{1}}}{1}+\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{1}-\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{1}/{\left(1+{{\theta}_{j}}\right)}\;}=\sum\limits_{j\in{{\mathcal{C}}_{i}}}{1}-\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{1}/{\left(1+{{\theta}_{j}}\right)}\;}=\left|{{\mathcal{C}}_{i}}\right|-\sum\limits_{j\in{{\mathcal{C}}_{i}}\wedge
j\leq{{n}_{1}}}{{1}/{\left(1+{{\theta}_{j}}\right)}\;}.$ (72)

According to formula (67), we have

${{w}_{i}}=m_{i,i}^{\left({{t}_{i}}+1\right)}=\sqrt{1+{{\theta}_{i}}}.$ (73)

Then, according to formula (59), we have

${{w}_{i\to{{f}_{i}}}}=-m_{{{f}_{i}},i}^{\left({{t}_{i}}+1\right)}=-{m_{i,{{f}_{i}}}^{\left({{t}_{i}}\right)}m_{i,i}^{\left({{t}_{i}}\right)}}/{m_{i,i}^{\left({{t}_{i}}+1\right)}}\;=-{m_{i,{{f}_{i}}}^{\left(0\right)}m_{i,i}^{\left(0\right)}}/{m_{i,i}^{\left({{t}_{i}}+1\right)}}\;=-{\left(-1\times
1\right)}/{{{w}_{i}}}\;={{w}_{i}}^{-1}.$ (74)

∎

## References

  * [1] S. Niazi, M. Ismail, S. Grohsschmiedt, M. Ronstrm, S. Haridi, J. Dowling, Hopsfs: Scaling hierarchical file system metadata using newsql databases.
  * [2] J. Abowd, The u.s. census bureau adopts differential privacy, 2018, pp. 2867–2867.  doi:10.1145/3219819.3226070.
  * [3] T. Lima, M. de Aguiar, Laplacian matrices for extremely balanced and unbalanced phylogenetic trees (08 2020).
  * [4] S. Garfinkel, J. Abowd, S. Powazek, Issues encountered deploying differential privacy (09 2018).  doi:10.1145/3267323.3268949.
  * [5] X. Li, Z. Wang, Trees with extremal spectral radius of weighted adjacency matrices among trees weighted by degree-based indices, Linear Algebra and its Applications 620.  doi:10.1016/j.laa.2021.02.023.
  * [6] S. Ganesh, S. Mohanty, Trees with matrix weights: Laplacian matrix and characteristic-like vertices (09 2020).
  * [7] R. Bapat, S. Sivasubramanian, Squared distance matrix of a tree: Inverse and inertia, Linear Algebra and its Applications 491.  doi:10.1016/j.laa.2015.09.008.
  * [8] E. Andriantiana, K. Dadedzi, S. Wagner, The ancestral matrix of a rooted tree, Linear Algebra and Its Applications 575 (2019) 35–65.  doi:10.1016/j.laa.2019.04.004.
  * [9] W. Fulton, J. Harris, Graduate texts in mathematics, Representation Theory. A First Course, Readings in Mathematics 129.
  * [10] J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, M. Sun, Graph neural networks: A review of methods and applications, AI Open 1 (2020) 57–81.  doi:10.1016/j.aiopen.2021.01.001.
  * [11] X. A. Chen, Understanding spectral graph neural network.
  * [12] M. Deveci, C. Trott, S. Rajamanickam, Multi-threaded sparse matrix-matrix multiplication for many-core and gpu architectures, Parallel Computing 78.  doi:10.1016/j.parco.2018.06.009.
  * [13] M. Hay, V. Rastogi, G. Miklau, D. Suciu, Boosting the accuracy of differentially-private histograms through consistency, Proceedings of the VLDB Endowment 3.  doi:10.14778/1920841.1920970.
  * [14] N. Wang, X. Xiao, Y. Yang, T. Hoang, H. Shin, J. Shin, G. Yu, Privtrie: Effective frequent term discovery under local differential privacy, 2018, pp. 821–832.  doi:10.1109/ICDE.2018.00079.
  * [15] J. Jansson, K. Sadakane, W.-K. Sung, Ultra-succinct representation of ordered trees with applications, J. Comput. Syst. Sci. 78 (2012) 619–631.  doi:10.1016/j.jcss.2011.09.002.
  * [16] D. Tsur, Succinct representation of labeled trees, Theoretical Computer Science 562\.  doi:10.1016/j.tcs.2014.10.006.
  * [17] A. Farzan, J. Munro, Succinct representation of dynamic trees, Theor. Comput. Sci. 412 (2011) 2668–2678.  doi:10.1016/j.tcs.2010.10.030.
  * [18] C. Dwork, F. McSherry, K. Nissim, A. Smith, Calibrating noise to sensitivity in private data analysis, Journal of Privacy and Confidentiality 7 (2017) 17–51.  doi:10.29012/jpc.v7i3.405.
  * [19] W. Qardaji, W. Yang, N. Li, Understanding hierarchical methods for differentially private histograms, Proceedings of the VLDB Endowment 6 (2013) 1954–1965.  doi:10.14778/2556549.2556576.
  * [20] G. Cormode, M. Procopiuc, E. Shen, D. Srivastava, T. Yu, Differentially private spatial decompositions, Computing Research Repository - CORRdoi:10.1109/ICDE.2012.16.
  * [21] S. Yuan, D. Pi, X. Zhao, M. Xu, Differential privacy trajectory data protection scheme based on r-tree, Expert Systems with Applications 182 (2021) 115215.  doi:10.1016/j.eswa.2021.115215.
  * [22] J. Lee, Y. Wang, D. Kifer, Maximum likelihood postprocessing for differential privacy under consistency constraints, 2015, pp. 635–644.  doi:10.1145/2783258.2783366.
  * [23] G. Strang, Linear algebra and learning from data, Wellesley-Cambridge Press Cambridge, 2019.
  * [24] G. Birkenmeier, H. Heatherly, J. Kim, J. Park, Triangular matrix representations, Journal of Algebra 230 (2000) 558–595.  doi:10.1006/jabr.2000.8328.
  * [25] L. Minah, A. Fox, G. Sanders, Rounding error analysis of mixed precision block householder qr algorithms, SIAM Journal on Scientific Computing 43 (2021) A1723–A1753.  doi:10.1137/19M1296367.
  * [26] P. Desai, S. Aslan, J. Saniie, Fpga implementation of gram-schmidt qr decomposition using high level synthesis, 2017, pp. 482–487.  doi:10.1109/EIT.2017.8053410.
  * [27] W. Fam, A. Alimohammad, Givens rotation-based qr decomposition for mimo systems, IET Communications 11.  doi:10.1049/iet-com.2016.0789.
  * [28] R. Stanley, Enumerative combinatorics — volume 1.
  * [29] M. C. M. incorporates LAPACK, Increasing the speed and capabilities of matrix computation, [Online] (2000).
  * [30] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, L. Kaiser, M. Kudlur, J. Levenberg, X. Zheng, Tensorflow : Large-scale machine learning on heterogeneous distributed systems (01 2015).
  * [31] Y. Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, T. Darrell, Caffe: Convolutional architecture for fast feature embedding, MM 2014 - Proceedings of the 2014 ACM Conference on Multimediadoi:10.1145/2647868.2654889.
  * [32] J. Magnus, Matrix differential calculus with applications in statistics and econometricsdoi:10.1002/9781119541219.
  * [33] U. C. Bureau, 2010 census summary file 1, https://www.census.gov/prod/cen2010/doc/sf1.pdf (2012).
  * [34] New york city taxi data, http://www.nyc.gov/html/tlc/html/about/trip/record/data.shtml.