
\chapter{Graph Structured Data Objects\label{chapI:Tree-Structured-Data}}

In the mathematical field of graph theory a \emph{\index{graph|(}graph}
is defined as $G=\left(V,E\right)$, where $V$ is a set of \emph{vertices\index{graph!vertices}}
(also known as \emph{nodes}) and where $E$ is a set of \emph{\index{graph!edges}edges}
(that connect the vertices), i.e. $E=\left\{ [v,w]:v\neq w\in V\right\} $.
In a \emph{directed} graph\index{graph!directed}, the edges are thought
of as pointing from say $v$ to $w$, so $[v,w]$ is taken to be an
ordered pair $(v,w)$. Edges in \emph{\index{graph!undirected}undirected
graphs }ignore directions, and so $[v,w]=\{v,w\}$, just an unordered
set. In some situations, it useful to add \emph{\index{graph!attributes}attributes}
to the graph structure, which are numbers or vectors (or even more
general objects) assigned to each vertex and/or to each edge. An example
of vertex attributes are the centers and radii of the spheres that
compose the artery trees shown in Figures \ref{fig:ArtTree-3views}
and \ref{fig:3ArtTrees}.

Directed graphs are natural when tabulating ancestry, yielding the
terminology $w$ is a \emph{\index{tree!child}child} of $v$ when
$(v,w)\in E$, and $v$ is similarly a \emph{\index{tree!parent}parent}
of $w$. A \emph{tree\index{tree|(}} is a special case of a graph,
which is directed, has a starting vertex called the \emph{\index{tree!root}root}
which has no parent, and is \emph{acyclic\index{graph!acyclic}} in
the sense that every other vertex has exactly one parent and is a
descendant of the root. A vertex with no child is called a \emph{\index{tree!leaf}leaf}.
Brain artery systems as introduced in Section \ref{sec:Tree-Structured-Data}
and studied further in Section \ref{secI-A:ArterialTrees} are nearly
trees, except for an anatomical structure called the \index{Circle of Willis|(}Circle
of Willis (which seems to ensure that blockage of a carotid artery
will not result in loss of half the brain). To give reasonable correspondence\index{correspondence|(},
the data objects studied here are unions of the 3, 4 or 5 (depending
on the subject) actual trees which flow out of the Circle of Willis.
The leaves in the Brain Artery data occur when each artery becomes
too small to appear in the MRA images discussed in Section \ref{sec:Tree-Structured-Data}
(at about 1 mm in diameter). Hence, we do not consider the circulatory
system as the closed circuit that it actually is, because neither
the capillaries (between the arteries and the veins) nor the veins
themselves show up in the MRA. Thus the Brain Artery data is treated
here as a set of trees.

There is a large literature on network (i.e. graph) analysis from
various viewpoints. See \citet{West1996GraphTheory}, \citet{Kolaczyk2009Networks}
and \citet{Harary2015GraphTheory} for much more introductory material.
Much of the intersection with statistics is about the variation involved
in constructing a single graph. Here we take a different approach
by thinking of graphs as data objects and studying sample / population
properties. Section \ref{secI-A:ArterialTrees} gives an overview
of the literature on the arterial trees. Other examples of the analysis
of tree structured data objects in biomedical applications include
airways as data objects in \citet{Feragen2011geometries,Feragen2013tree,Feragen2015Amenta}.
Other approaches to data sets of tree structured objects include the
\emph{\index{tree kernel}tree kernel} idea discussed in \citet{VertTreeKernels2002}
and \citet{YamanishiVert2007}. Early work in this area was done in
\citet{BanksConst1998Trees}.

Section \ref{secI-B:NetworkData} studies the analysis of samples
of networks as data objects using \emph{graph Laplacian} representations,
which are a subset of the space of covariance matrices.

\section{Arterial Trees as Data Objects\label{secI-A:ArterialTrees}}

A\index{data objects!tree structured|(} deep and challenging set
of tree structured data\index{tree structured data|(} objects is
the Brain Artery data\index{Brain Artery data|(} introduced in Section
\ref{sec:Tree-Structured-Data}. A number of quite different approaches
have been taken to quantifying the variation in that data set, including
\emph{combinatoric} approaches overviewed in Section \ref{subsecI-A-A:Combinatorics},
a \emph{phylogenetic} point of view as taken in Section \ref{subsecI-A-C:Phylogenetics},
the \emph{Dyck Path} approach studied in Section \ref{subsecI-A-B:Dyck-Path},
and a representation using \emph{persistent homologies} in Section
\ref{subsecI-A-D:Persistent-Homology}. These methods are compared
in terms of performance on the Brain Artery data in Section \ref{subsecI-A-E:Comparison}.

\subsection{Combinatoric Approaches\label{subsecI-A-A:Combinatorics} }

The first versions of PCA-like visualization\index{visualization}s
of these data objects are called combinatoric\emph{\index{combinatoric analysis|(}}.
In particular, they ignore all attributes such as branch length, thickness
and physical location, and instead only take into account the tree
topology (the original nodes and edges). These analyses are in \citet{WangMarron2007}
and \citet{Aydin2009}, which were also the first studies to explicitly
use the terminology OODA. Those early analyses involved embedding
the trees which naturally lie in a three dimensional ambient space,
into a binary two dimensional data object representation, as shown
in Figure \ref{fig:2d-Tree-Reps}. Two arbitrary choices of branch
location involving either branch thickness or number of descendant
branches (called \emph{descendant \index{correspondence!descendant}correspondence}
in Section \ref{subsecI-A-B:Dyck-Path}), were considered and gave
different results. The most statistically significant results from
\citet{Aydin2009} appear in the top row of Table \ref{tabIA:BrainArtSummary}
in Section \ref{subsecI-A-E:Comparison}, suggesting that the tree
topology alone does not provide enough information. Instead it is
important to consider at least some tree attributes, as done in the
following sections.

\begin{figure}[H]
\includegraphics[scale=0.6]{Chapter1/OODAbookChp1FigJ}

\caption{Examples of 2-d embeddings as data objects, for 3 different subjects.\label{fig:2d-Tree-Reps}}
\end{figure}
Two challenges with early versions of the brain artery tree data were
the linking of tree branches into a tree structure and the starting
point of each tree. These issues have been addressed through careful
data objects choices. Linking was initially done in \citet{AylwardBullitt2002}
using a thresholding operation combined with manual intervention,
and the starting point was arbitrarily chosen by the MR operator.
In subsequent analyses, arteries were more accurately linked using
a visualization device invented in \citet{Aydin2011}. As noted above,
the starting point issue has been addressed by only including arteries
flowing out of the Circle of Willis\index{Circle of Willis|)} (a
readily identifiable anatomical feature).

\citet{WangWang2012} deeply investigated the relationship between
age and artery tree structure and found some unexpected age behavior,
by inventing an analog of kernel smoothing\index{smoothing} with
a tree structured response variable. See \citet{AlfaroAydin2014}
for another combinatoric approach to PCA of the Brain Artery data.\index{combinatoric analysis|)}

\subsection{Phylogenetics\label{subsecI-A-C:Phylogenetics}}

Another approach to the Brain Artery data, based on phylogenetic tree
representations as data objects, can be found in \citet{SkwererPhylo2014}.
\index{phylogenetic analysis}\index{phylogenetic tree|(}Phylogenetic
trees are a model for evolution of species (or other biological units)
over time. In addition to the branching structure of the combinatorial
trees in Section \ref{subsecI-A-A:Combinatorics}, the branches of
phylogenetic trees have the attribute of length representing the time
between species splits and/or the present. The motivation for addressing
the artery data using phylogenetic tree methods is that the latter
have been studied for a very long time. In particular, the ideas go
back to \citet{darwin1872origin} with interesting early graphical
representations already in \citet{Haeckel1866}, so much is known
about them which should be useful for the study of trees as data objects.
The main challenge is that in a typical phylogenetic setting, one
works with a common set of species (i.e. leaf set), and the goal is
to explore (often to choose between) various ways in which the species
could be reasonably organized into an ancestral tree. The main challenge
to adapting this idea to the case of the brain artery trees is that
the latter do not have a common leaf set. Instead, as noted above,
arteries are collected only until they become too thin to show up
reliably in the MRA (about 1 mm resolution). Hence each subject has
a different number of arterial endpoints, none of which correspond
across individuals in a meaningful way. To create a set of data objects
appropriate for a phylogenetic type of analysis, common leaves were
artificially generated as a set of corresponding landmarks, based
upon the brain cortical surfaces of each subject (also collected in
the original study), using an elegant algorithm of \citet{OguzStyner2008}.
An example of this for one subject appears in Figure \ref{figI.B:BrainLandmarks},
which is Figure 2.6 of the PhD dissertation \citet{Zhai2016PCAphylo}.
In the left panel the blue curves are the original arteries and the
red dots are landmarks on the cortical surface that correspond (with
respect to shape of the surface) across all subjects in the sample.
The red lines in the center panel show the projections of each landmark
onto the arteries. The cyan part of the artery curves in the center
panel show \emph{orphans}, which are arterial portions that are beyond
(with respect to arterial flow) the last such projection. The right
panel shows the result of trimming those orphans which leaves the
remaining parts as the blue tree representation. This representation
is ideal for phylogenetic analysis, because all leaves now correspond
across subjects.

\begin{figure}[H]
\includegraphics[scale=0.3]{ChapterI/OODAbookChpIFigBBrainLandmarks}

\caption{Illustration of common leaf set construction for use of phylogenetic
tree methods on the Brain Artery data. Dots are landmarks corresponding
across all subjects. These are connected by projection to the artery
tree shown as blue curves. Orphan curve segments, shown as cyan in
the center panel, are trimmed to give the final tree in the right
panel. \label{figI.B:BrainLandmarks}}
\end{figure}
\citet{SkwererPhylo2014} go on to show that this approach gives some
improved statistical inference (about age and sex) as summarized in
Table \ref{tabIA:BrainArtSummary} in Section \ref{subsecI-A-E:Comparison}. 

Phylogenetic tree space is another example of \index{stratified space|(}
stratified spaces, as discussed at the end of Section \ref{sec:Sounds-as-Data}
and in Section \ref{secG-B:CovMatDataObjects} (both about covariance
matrices as data objects\index{data objects!covariance matrices}).
The particular geometry of the space creates a number of surprises,
because it is locally flat (in fact exactly Euclidean on neighborhoods)
almost everywhere, with a very notable exception being the origin.
The singularity at that point results in the whole space having very
strong \index{non-positive curvature}non-positive curvature. This
has some good consequences such as uniqueness of the \index{Fréchet mean|(}Fréchet
mean. However as discussed in \citet{Skwerer2018TreeMeans}, even
calculation of the Fréchet mean is quite challenging. For example
the iterated pairwise weighted average algorithm of \citet{Sturm2002}
did not converge after 10,000 steps, and had a larger Fréchet variance\index{Fréchet variance}
than the origin at each of those steps. This motivated \citet{Skwerer2018TreeMeans}
to develop a more sophisticated optimization approach to calculation
of the Fréchet mean in phylogenetic tree space, which ultimately showed
that the origin is the Fréchet mean of this data set. See \citet{MilleOwenProvan2015}
for interesting related work.

Some interesting views of the strong curvature of phylogenetic tree
space have been provided using MDS (recall Multi-Dimensional Scaling\index{Multi-Dimensional Scaling}
from Section \ref{secE.2:Multi-dimensional-scaling}), in the PhD
dissertation \citet{Zhai2016PCAphylo}, as shown in Figure \ref{figI.D:MDSgeodesics}.
Demonstration of curvature effects in these examples has been enabled
by the ability to quickly compute \index{phylogenetic trees!geodesic|(}geodesics
using a clever algorithm invented by \citet{OwenProvan2011FastGeod}.
The data objects are the $n=67$ trees for which corresponding landmarks
were found using the method of \citet{OguzStyner2008}, represented
as blue dots (with a few as blue squares) in each panel. In each case
the Fréchet mean is shown as a red plus sign. The blue points in the
left panel show the MDS distribution of the original data, suggesting
an approximately Gaussian distribution with perhaps an outlier. The
center panel shows a much different MDS distribution of the same data
set. The green dots are additional data included in the MDS, which
are chosen as lying along equally spaced grids connecting three of
the data points. Note the addition of the green points gives a completely
different MDS view, because the additional points result in more overall
variation in their direction. A triangle is used here, because one
characterization of non-positive curvature is that triangles (connecting
three points with geodesics) ``bend inwards'' in the sense of having
angle sums much less than the usual $180^{\circ}$ of triangles in
Euclidean space. This particular triangle is representative in the
sense of having the median angle sum over all triples of data points.
Those angles are between geodesics in the local Euclidean plane containing
each vertex point.

\begin{figure}[H]
\includegraphics[scale=0.25]{ChapterI/OODAbookChpIFigD1geodMDS}\includegraphics[scale=0.25]{ChapterI/OODAbookChpIFigD2geodMDS}\includegraphics[scale=0.25]{ChapterI/OODAbookChpIFigD3geodMDS}

\caption{MDS views of Brain Artery data (blue symbols), together with the Fréchet
mean (red plus sign). The standard MDS is in the left panel. The MDS
in the other two panels are based on all of the blue data, the red
mean, and the green points, which are sampled along geodesics between
a few data points. Inclusion of the green points shows how the strong
curvature of the space introduces huge distortions in the MDS view.
The left panel shows how the out of sample MDS can address this distortion
by showing the same green points from the right panel embedded in
the original MDS \label{figI.D:MDSgeodesics}}
\end{figure}
A related distortion is shown in the right panel of Figure \ref{figI.D:MDSgeodesics}.
This time the MDS was based upon the union of the data together with
only one geodesic (chosen to have the median pairwise distance\index{distance!median pairwise}),
where the addition of the additional points again creates a very large
distortion of the view. Another viewpoint on this is provided in Figure
8 of \citet{SkwererPhylo2014}, which shows a great deal of shrinkage
in branch lengths as one follows such geodesics. Note that this time
the distortion is so strong that the Fréchet mean actually lies outside
the apparent convex hull (with respect to this embedding) of the data.
This distortion can be effectively dealt with using the out of sample
MDS\index{out of sample MDS} approach (invented by \citet{TrossetPriebe2008OutSampMDS}
and refined in Chapter 3 of \citet{Zhai2016PCAphylo}) that was discussed
in Section \ref{secE.2:Multi-dimensional-scaling}. The result of
this is shown in the left panel of Figure \ref{figI.D:MDSgeodesics},
where the blue dots have their original MDS configuration. The green
points are the same as in the right panel, but do not influence the
embedding because of the out of sample calculation. These points now
approximately lie along a line and the Fréchet mean\index{Fréchet mean|)}
seems to be near the center.

See \citet{Nye2011} for an early approach to PCA of phylogenetic
tree data objects, and \citet{Nye2017} for updated ideas. Other approaches
to PCA, based on \emph{tree lines}\index{tree lines}, \emph{sample
limited geodesics\index{sample limited geodesics}} and \emph{principal
rays\index{principal rays}} (making repeated use of the \citet{OwenProvan2011FastGeod}
fast geodesic\index{phylogenetic trees!geodesic|)} algorithm) were
proposed by \citet{Zhai2016PCAphylo}. These unfortunately did not
give reasonable insights into the population structure of the Brain
Artery data, apparently because of the strong curvature of the space,
and the broad spread of the artery data around the space. An interesting
open problem is to address these challenges by modifying MDS to target
data representation\index{data representation}s in a negatively curved
space, instead of the traditional Euclidean representations discussed
in Section \ref{secE.2:Multi-dimensional-scaling}.

Asymptotic results have been established by \citet{BardenLe2018PhylTrees,BardenLeOwen2018PhylTrees}.
An interesting way to quantify uncertainty in phylogenetic tree space
can be found in \citet{WillisBell2018UncertaintyPhylo}, which was
used to develop a notion of Confidence Sets in \citet{Willis2018PhyloConfidenceSets}.
An important point of the overview of \citet{FeragenNye2020StratSpaces}
is that phylogenetic tree space is another example of a \index{stratified space|)}
stratified space as discussed in Section \ref{secG-B:CovMatDataObjects}.
This viewpoint is the key to the discovery of \emph{stickiness\index{stickiness}}
in \citet{HotzEtal2013StickyMeans} that seems to occur generally
when studying limit behavior of sample means in phylogenetic tree\index{phylogenetic tree}
space.

\subsection{Dyck Path\label{subsecI-A-B:Dyck-Path}}

A quite different choice of data objects was made in \citet{ShenTrees2014}.
The key idea there was to use the \index{Dyck Path analysis}Dyck
Path idea of \citet{Harris1952} (invented as a tool in the stochastic
processes literature for the asymptotic analysis\index{asymptotic analysis}
of branching processes) to represent\index{represent} each data tree
as a curve, followed by the use of FDA\index{functional data analysis}
techniques for the resulting statistical analysis. 

The Dyck path analysis uses more tree information than the combinatorial
approach of Section \ref{subsecI-A-A:Combinatorics}, including length
of each branch as an edge attribute. As illustrated in the left panel
of Figure \ref{figI.A:DecCorrDyckPath}, a challenge to that old approach
was the correspondence issue caused by the arbitrariness of the embedding
of the 3-d arterial trees into the plane. Different representations
of the same tree can be obtained by \emph{\index{flipping vertices}flipping
vertices} as shown. The most compelling way to handle this ambiguity
is through the concept of \emph{invariance} discussed in Chapter 4
of \citet{DrydenMardia2016}. Proceeding as in Sections \ref{sec:Shapes-as-Data}
and \ref{secG-A:ShapeDataObjects} (recall their context was shape
analysis), the main idea is to call trees that can reached from each
other by vertex flips \emph{equivalent}, and then to work with the
equivalence class\index{equivalence class}es (\emph{orbit\index{orbit}s}
with respect to the group of flipping operations) as the data objects.
Note the strong parallel to the Fisher-Rao approach to curve registration
taken in Section \ref{secH.A:Fisher-Rao-Reg}. Pursuing such an approach
to this analysis is an interesting open problem. This was not done
in \citet{ShenTrees2014}, who instead used the descendant correspondence
idea of Section \ref{subsecI-A-A:Combinatorics}, where each equivalence
class was represented by its member with most descendants on the left
at each vertex.

\begin{figure}[H]
\includegraphics[scale=0.3]{ChapterI/OODAbookChpIFigA1DecCorr}\includegraphics[scale=0.4]{ChapterI/OODAbookChpIFigA2DyckPath}

\caption{Illustration of vertex flipping as an equivalence relation (left panel)
and Dyck Path interpretation as an ant walking around a tree (right
panel). \label{figI.A:DecCorrDyckPath}}
\end{figure}
The Dyck Path is intuitively expressed in terms of ``an ant walking
around a tree'' in a two dimensional embedding, as illustrated in
the right panel of Figure \ref{figI.A:DecCorrDyckPath}. The tree
is shown near the top in blue with the path of the ant shown in red.
The lower plot shows the corresponding trace of the ant's distance
from the root as a function of time (assuming uniform velocity). Such
resulting red curves (hence amenable to classical Euclidean FDA) are
the representations of the tree data objects. For better correspondence\index{correspondence|)}
across data objects, \citet{ShenTrees2014} also incorporate the idea
of \emph{\index{support tree}support tree}, essentially the union
of all the trees in the data set.

While the combinatorial approaches in Section \ref{subsecI-A-A:Combinatorics}
mostly focused on exploratory\index{exploratory analysis} analyses,
\citet{ShenTrees2014} went on to do deeper confirmatory\index{confirmatory analysis!brain artery trees}
analyses. These motivated the new idea of \emph{branch length representation}\index{branch length representation},
which resulted in statistically significant correlations with age.
This was not surprising as that connection was also found in the simple
summary based analysis of \citet{BullittSummaries2005}. However,
a deeper analysis, based on \emph{tree pruning\index{tree pruning}}
ideas found the first statistically significant connection of gender
with tree structure. Actual p-values are summarized in Table \ref{tabIA:BrainArtSummary}. 

\subsection{Persistent Homology\label{subsecI-A-D:Persistent-Homology}}

A \emph{\index{Topological Data Analysis|(}Topological Data Analysis}
(TDA) of the brain artery has been done by \citet{Bendich2016TDA}.
That paper uses various \emph{persistent homology} representations
as data objects. In confirmatory analysis, these coordinate free representations
have given the strongest statistical significance found to date for
both age and gender.

The basis of TDA is a \emph{filtration\index{filtration|(}} that
can be viewed as extracting a topological representation of the data.
An example of a filtration is shown in Figure \ref{figI.E:ToyFiltration}.
The input data points are the $n=13$ plus signs in $\mathbb{R}^{2}$
shown in each panel. The filtration records how topological properties
of the union of discs centered at the data points change as a function
of disc radius (which is the \emph{filtration index}\index{filtration!index}).
The process starts with $0$ length radii, where there are $13$ disconnected
components represented as solid vertical bars in the right subplot
of each panel (the dotted bars are explained below). In the top panel
the radius is large enough that the eight points on the left now lie
in a single connected region. Thus at this radius, represented by
the horizontal line in the subplot, there are 6 bars that touch. There
are 7 shorter bars, that ended at the radius where the circles became
tangent, resulting in fewer connected components. The middle panel
of Figure \ref{figI.E:ToyFiltration} shows a larger disc radius (represented
as a higher horizontal line in the subplot), where only two connected
components remain, since the 5 points on the left were connected up
at the radius shown as the top of the 5 bars in the middle. In the
bottom panel only one bar is still going, because the two circles
of data have now been merged into a single connected component. As
the radius continues to grow this single bar grows to infinite length. 

\begin{figure}[H]
\includegraphics{ChapterI/OODAbookChpIFigE1ToyFiltration}

\includegraphics{ChapterI/OODAbookChpIFigE2ToyFiltration}

\includegraphics{ChapterI/OODAbookChpIFigE3ToyFiltration}

\caption{Demonstration of a TDA filtration, based on plus signs as data objects
in $\mathbb{R}^{2}$. Rows show different disc radii, i.e. filtration
levels. Left panels show construction of bar code representation of
data. Homological properties (before and at each filtration level)
are displayed in the right panels: $H_{0}$ bars are solid and $H_{1}$
are dotted. \label{figI.E:ToyFiltration}}
\end{figure}
The above discussed TDA representation of the data is based solely
on connected components, which in topological terms are called $H_{0}$
(0-th order) \emph{homological properties}. Also of use in TDA are
higher order homologies, such as the first order $H_{1}$ (based on
loops), the second order $H_{2}$ (focusing on cavities in 3 and higher
dimensions) and also higher orders. In addition to demonstrating $H_{0}$
as solid bars, Figure \ref{figI.E:ToyFiltration} also shows an $H_{1}$
filtration, using dotted bars. Because there are no loops when the
discs are disjoint the dotted bars do not start at the bottom. The
first one starts when the right circle of data points first merges,
just before the radius in the top panel. The middle row shows two
dotted $H_{1}$ bars reflecting the two loops present at that radius.
One bar has ended before the radius shown in the bottom panel as the
right hand loop disappeared. When a feature disappears, the convention
is to end the shorter bar. Both loops disappear for large enough radii. 

The classical use of TDA, as discussed by \citet{BubenikKim2007TDA},
\citet{Carlsson2009TDA}, \citet{Zomorodian2012TDA} and \citet{Wasserman2018TDA},
focuses on understanding the relationships between\index{data objects!relationships between}
data objects. 

However, TDA filtrations are also very useful for data object representations,
as shown by \citet{Bendich2016TDA}, in an analysis of the Brain Artery
data. The filtration proposed in that paper is quite different from
the growing balls illustrated in Figure \ref{figI.E:ToyFiltration}.
It is instead based on the idea of filling a tank holding the arterial
system, as demonstrated in Figure \ref{figI.C:BrainTDAFiltration}.
An $H_{0}$ (connected component) filtration is indexed by the level
of the water. Bars start when the water level touches new parts of
the tree, and end when components merge together. Three such water
levels for the same data tree are shown in Figure \ref{figI.C:BrainTDAFiltration}.

\begin{figure}[H]
\includegraphics[scale=0.35]{ChapterI/OODAbookChpIFigCTDABrain}

\caption{Three water levels (submerged parts shown in red) of the $H_{0}$
TDA filtration for one brain artery system. \label{figI.C:BrainTDAFiltration}}
\end{figure}
\citet{Bendich2016TDA} used this and related object representations
to explore age and gender for the artery data. A challenge was finding
a Euclidean representation of the resulting bar graphs. A number of
things were tried including various summaries of the bar lengths,
together with the bar start times. The best of these gave results,
using $H_{1}$, quite competitive with other analyses, as shown in
Table \ref{tabIA:BrainArtSummary} of Section \ref{subsecI-A-E:Comparison}.

More sophisticated Euclidean summaries of the bar graphs are the \emph{\index{persistence landscapes}persistence
landscapes} studied in \citet{Bubenik2015PersLand}. A different approach
to Euclidean representation of bar graphs are the \emph{rank functions\index{rank functions}}
of \citet{RobinsTurner2016RankFuncTDA}. An interesting type of filtration\index{filtration|)}
with some inversion properties (not usual in topological data analysis
contexts) is the \emph{\index{persistent homology transformation}persistent
homology transformation\index{transformation!persistent homology}}
of \citet{Turner2014PersHomTrans}.

\subsection{Comparison of Tree Analysis Methods\label{subsecI-A-E:Comparison}}

An interesting question is how to compare these quite diverse ways
of understanding the variation in the Brain Artery data set that were
discussed in Sections \ref{subsecI-A-A:Combinatorics} - \ref{subsecI-A-D:Persistent-Homology}.
As noted in Section \ref{sec:Tree-Structured-Data} it would be medically
interesting to study effectiveness at finding early cancer or quantifying
stroke tendency, but that information is not available here. So instead
we work with the given covariates of age, sex and handedness. Handedness
has around 95\% right handed subjects, so that is not studied further.
However, it is interesting to investigate any brain arterial structure
associations with age and sex. To study age the first and third studies
used slope of a regression line (not reported here), while the others
reported correlations as shown in Table \ref{tabIA:BrainArtSummary}
(with blanks in cases where the correlation was not reported). Another
approach to comparison is based on the p-values of hypothesis tests
for a significant age effect, and also of significant sex effect.
The sex data include two trans-sexuals that were not included in the
sex based calculations, and no p-value was given in the first two
studies (hence the blanks in the table). Note that there is a general
trend towards stronger statistical inference for more sophisticated
representations of the Brain Artery data objects.

\begin{table}[H]
\begin{tabular}{|c|c|c|c|c|}
\hline 
 & Section & Age $\rho$ & Age p-val & Sex p-val\tabularnewline
\hline 
\hline 
Comb. & \ref{subsecI-A-A:Combinatorics} & - & $0.0025$ & -\tabularnewline
\hline 
Phylo. & \ref{subsecI-A-C:Phylogenetics} & $0.43$ & $10^{-5}$ & -\tabularnewline
\hline 
Dyck & \ref{subsecI-A-B:Dyck-Path} & - & $10^{-6}$ & $0.033$\tabularnewline
\hline 
TDA $H_{0}$ & \ref{subsecI-A-D:Persistent-Homology} & $0.53$ & $10^{-7}$ & $0.11$\tabularnewline
\hline 
TDA $H_{1}$ & \ref{subsecI-A-D:Persistent-Homology} & $0.61$ & $10^{-10}$ & $0.031$\tabularnewline
\hline 
\end{tabular}

\caption{Summary of results from various studies of the Brain Artery data\index{Brain Artery data|)}.
Shows improvement using more sophisticated methods. \label{tabIA:BrainArtSummary}}
\end{table}
A\index{Topological Data Analysis|)} mathematically compelling approach
to statistical analysis of \index{tree|)}tree structured data objects
can be found in \citet{GuoSrivastava2020ElasticGraphs}. This uses
equivalence class\index{equivalence class}es as data objects ideas
(discussed in Sections \ref{sec:Shapes-as-Data} and \ref{secG-A:ShapeDataObjects})
to simultaneously summarize both the topological structure as well
as the individual branch shapes. The latter is elegantly represented
using the Fisher-Rao elastic registration ideas discussed in Section
\ref{secH.B:PNSonFisherRao}. Direct comparison with the other approaches
summarized in Table \ref{tabIA:BrainArtSummary} is unfortunately
not possible, as that paper made a different choice of data objects
(sub-trees as opposed to the full arterial system),\index{tree structured data}
but the results appear to be fairly similar.\index{data objects!tree structured|)}
\index{confirmatory analysis!brain artery trees}

\section{Networks as Data Objects \label{secI-B:NetworkData}}

\index{data objects!networks|(}

Networks are of wide interest and able to represent many different phenomena, for example social interactions between individuals and white matter fiber connections between regions in the brain, e.g. see \cite{Kolaczyk2009Networks} and  \cite{Ginestetetal17}.  If a sample of networks is available then it is natural to carry out OODA and, following the main theme of this book, important considerations are to decide what are the data objects and how they are represented.  

\subsection{Graph Laplacians}
Consider a dataset where each data object is an undirected graph (as introduced at the beginning of this chapter) comprising a set of $m$ nodes (i.e. vertices), $V=\lbrace v_1, v_2,\ldots, v_m\rbrace$, and a set of edge attributes which are called {\it weights}, $\lbrace w_{ij} : w_{ij}\geq 0, 1\leq i,j \leq m\rbrace$, indicating nodes $v_i$ and $v_j$ are either connected by an edge of weight $w_{ij}>0$, or else unconnected (if $w_{ij}=0$). We call this type of graph a {\it weighted network}. 
An {\it unweighted network} is the special case with $w_{ij}\in\lbrace 0,1\rbrace$.  Following  \cite{Severnetal19} we restrict attention to networks that are undirected and without loops, so that $w_{ij}=w_{ji}$ and $w_{ii}=0$. \index{Graph Laplacian} \index{matrix!Graph Laplacian}

There are several representations of weighted networks that are very useful. These include the 
weighted {\it adjacency matrix} \index{matrix!adjacency}  $\mathbf{A} = \{ w_{ij} \}$, which is the matrix of edge weights. In the unweighted case, $\mathbf{A}$ is the indicator matrix of edges.  The {\it weighted degree} of a node is the sum of all edge weights associated with it.  These are summarized on the diagonals of 
the {\it degree matrix} \index{matrix!degree} 
$$\mathbf{D}=\text{diag}(\sum_{j=1}^mw_{1j},\ldots,\sum_{j=1}^mw_{mj})=\text{diag}(\mathbf{A}\mathbf{1}_{m,1}) $$
where $\mathbf{1}_{m,1}$ is the $m$-vector of ones. Throughout this book, we will denote the matrix of ones as   
\begin{equation} \boldsymbol{1}_{d,n}=\left[\begin{array}{ccc} 1 & \cdots & 1\\ \vdots & \ddots & \vdots\\ 1 & \cdots & 1 \end{array}\right] \label{eq:ones matrix} \end{equation}
The degree matrix contains useful information about the importance of each node, but it only contains partial information about the network. The weighted adjacency matrix does contain all the information about the network, but the degree information is only indirectly available. 
A representation
that combines both adjacency and degree is the graph Laplacian matrix 
$\mathbf{L}=(l_{ij})$, defined as \begin{align*}    l_{ij} =  \begin{cases}     -w_{ij}, & \text{if } i\neq j\\     \sum_{k\neq i}w_{ik},& \text{if } i=j \end{cases} \end{align*}   for $1\leq i,j \leq m$.  The graph Laplacian matrix can be written as 
$$\mathbf{L}=\mathbf{D}-\mathbf{A},$$ in terms of the adjacency matrix, $\mathbf{A}$, and the degree matrix  $\mathbf{D}$.   An advantage of using the graph Laplacian matrix representation is
that it explicitly includes both the degree information on the diagonal and the edge weight
adjacency terms (as negative off-diagonal elements). Also, a graph Laplacian is a square symmetric positive semi-definite matrix, and so we have methods available to deal with such data objects as given in 
Section \ref{subsec:Covariance-matrix-distances}.


In more detail, the space of $m \times m$ graph Laplacian matrices is of dimension $m(m-1)/2$ and is \begin{align}\label{eq:lapl space} \mathcal{L}_m=\lbrace \mathbf{L}=(l_{ij}):\mathbf{L}=\mathbf{L}^t ;\, l_{ij}\leq 0 \, \forall i\neq j ;\, \mathbf{L} {\mathbf{1}_{m,1}}={\mathbf{0}_{m,1}} \rbrace, \end{align} using the notation $\mathbf{0}_{d,n}$ for the matrix of zeroes from (\ref{eqB.G:0sMatrix}).  In fact the space $\mathcal{L}_m$ is a closed convex subset of the cone of centered (meaning rows and columns sum to 0) symmetric  positive semi-definite $m\times m$ matrices and $\mathcal{L}_m$ is a manifold with corners \citep{Ginestetetal17}.

\begin{figure}[H] \begin{center} \includegraphics[height=6cm]{./ChapterI/view-2x2.png} \end{center} \caption{Red: Illustration of the cone structure of the space $PSD_2$, using simulated members plotted as red dots.  Various rank 1 subcones are shown using colors. Blue dots highlight the graph Laplacians $\mathcal{L}_2$. This shows this space (and hence that of the graph Laplacians) is naturally non-Euclidean.}\label{SPD2}  \end{figure}

Figure \ref{SPD2} gives an indication of where the graph Laplacians, $\mathcal{L}_m$, lie within the space $PSD_m$ (positive semi-definite matrices, from Section \ref{secBA.2:OverviewObjFeat}) in the case $m=2$. The cone structure of $PSD_m$ is highlighted by plotting $10,000$ realizations of $2\times2$ positive semi-definite matrices constructed as $\mathbf{X}\mathbf{X}^t$, where the entries $x_{ij}$ of the $2\times2$  matrix $\mathbf{X}$ were generated as independent $N(0,1)$. The graphic is a 3-d plot of each realization as a red dot, of the form $\left(\begin{array}{ccc}y_{11} & y_{12} & y_{22}\end{array}\right)^{t}$,  where
$$ \mathbf{X}\mathbf{X}^t=\left[\begin{array}{cc}y_{11} & y_{12}\\y_{21} & y_{22}\end{array}\right], $$ 
recalling that $\mathbf{X}\mathbf{X}^t$ is symmetric.
Important subcones of $PSD_m$ are revealed by also plotting various rank 1 modifications of the coordinates of the red dots.  Edges of the cone are explored using 
green points  $\left(\begin{array}{ccc}0 & 0 & y_{11}\end{array}\right)^{t}$, 
yellow points  $\left(\begin{array}{ccc}y_{11} & 0 & 0\end{array}\right)^{t}$ 
and cyan points  $\left(\begin{array}{ccc}y_{11} & y_{11} & y_{11}\end{array}\right)^{t}$.
A more central subcone is multiples of the identity matrix shown as gray points  $\left(\begin{array}{ccc}y_{11} & 0 & y_{11}\end{array}\right)^{t}$.
Graph Laplacian matrices, i.e. members of $\mathcal{L}_2$, are shown as blue dots of the form 
$\left(\begin{array}{ccc}y_{11} & -y_{11} & y_{11}\end{array}\right)^{t}$.


\subsection{Example: A Tale of Two Cities}
An example of a type of network is where the language structure of phrases of text or whole novels are studied using a network.  In {\it corpus linguistics}, also called {\it natural language processing}, it is common to record word co-occurrences, where pairs of words occur within a scan of a number of neighboring words. Each distinct word is a node in the network, and the edges of the network between two nodes (words) have
weights proportional to the number of co-occurences of that pair of words.
In Figure \ref{TTC} we provide a network representation of the phrase {\it It was the best of times, it was the worst of times} that opens the Charles Dickens novel `A Tale of Two Cities'.  Here the thickness of the line denotes the weight $w_{ij}$ which is the number of times the neighboring pair occurred. A  neighbor pair is counted as occurring when they are within a scan window of just one word here. 

\begin{figure}[H] \begin{center} \includegraphics[height=8cm]{./ChapterI/weightedTTC.png} \end{center} \caption{A network representation of  the phrase {\it It was the best of times, it was the worst of times}. An edge occurs when words are neighbors in the phrase, and the thickness of the edge is proportional to the weight. }\label{TTC} \end{figure} 



The weighted adjacency matrix is given by: 
\begin{equation*} \mathbf{A} = \begin{bmatrix} & \color{red} { it}&\color{red} { was}&\color{red} { the}&\color{red} { best}&\color{red} { worst}&\color{red} { of}&\color{red} { times}\\  \color{red} { it}    &        0&2&0&0&0&0&1\\ \color{red} { was}     &        2&0&2&0&0&0&0\\  \color{red} { the}&             0&2&0&1&1&0&0\\  \color{red} { best}&             0&0&1&0&0&1&0\\ \color{red} { worst}&             0&0&1&0&0&1&0\\  \color{red} { of}      &    0&0&0&1&1&0&2\\  \color{red} { times} &            1&0&0&0&0&2&0               \end{bmatrix}               \end{equation*}  
The degree matrix is: 
\begin{equation*} \mathbf{D} = \begin{bmatrix} & \color{red} { it}&\color{red} { was}&\color{red} { the}&\color{red} { best}&\color{red} { worst}&\color{red} { of}&\color{red} { times}\\  \color{red} { it}    &        3&0&0&0&0&0&0\\ \color{red} { was}     &        0&4&0&0&0&0&0\\  \color{red} { the}&             0&0&4&0&0&0&0\\  \color{red} { best}&             0&0&0&2&0&0&0\\ \color{red} { worst}&             0&0&0&0&2&0&0\\  \color{red} { of}      &    0&0&0&0&0&4&0\\  \color{red} { times} &            0&0&0&0&0&0&3               \end{bmatrix}               \end{equation*}   
Hence the graph Laplacian matrix is:  \begin{equation*} \mathbf{L} = \mathbf{D} - \mathbf{A} = \begin{bmatrix} & \color{red} { it}&\color{red} { was}&\color{red} { the}&\color{red} { best}&\color{red} { worst}&\color{red} { of}&\color{red} { times}\\  \color{red} { it}    &        3&-2&0&0&0&0&-1\\ \color{red} { was}     &        -2&4&-2&0&0&0&0\\  \color{red} { the}&             0&-2&4&-1&-1&0&0\\  \color{red} { best}&             0&0&-1&2&0&-1&0\\ \color{red} { worst}&             0&0&-1&0&2&-1&0\\  \color{red} { of}      &    0&0&0&-1&-1&4&-2\\  \color{red} { times} &            -1&0&0&0&0&-2&3               \end{bmatrix}               \end{equation*}              

Using such a representation with all the words in a novel provides a way of representing a novel 
as a graph Laplacian matrix, and we provide an example of analyzing the novels of Jane Austen and Charles Dickens in Section \ref{subsec:corpuslingustics}.  


\subsection{Extrinsic and Intrinsic Analysis}
Since the sample space $\mathcal{L}_m$ for graph Laplacian data is non-Euclidean, as seen in Figure \ref{SPD2}, standard approaches to statistical analysis  cannot be applied directly.  \cite{Severnetal19} introduced a framework for extrinsic analysis of graph Laplacian data, in which ``extrinsic'' refers to the strategy of embedding the data into a Euclidean space, where analysis is performed, before mapping back to $\mathcal{L}_m$. An intrinsic distance for this manifold is the Euclidean distance restricted to the space of graph Laplacians. 
Discussion of extrinsic versus intrinsic distances was given in 
Section \ref{subsecI-C-C:Procrustes} (for shapes) and \ref{secG.E:DirectionalData} (for directional data). 
Some advantages of an extrinsic approach on a manifold 
were given in Section \ref{secG.E:DirectionalData}.  
The choice of embedding enables freedom in the choice of metric used for the statistical analysis, and in various applications with manifold-valued data analysis there is evidence of the advantage in using non-Euclidean metrics, as discussed in Section \ref{subsec:Covariance-matrix-distances}.
\index{extrinsic} \index{intrinsic} \index{Graph Laplacian}


\subsection{Case Study: Corpus Linguistics \label{subsec:corpuslingustics}}

 \cite{Severnetal19}  focussed on comparison of the novels of Jane Austen and Charles Dickens, as represented by  networks with edges based on a scan of 5 words. In that paper the top 1000 words were chosen and compared using several of the distances that have been used for covariance matrices, that we described in 
Section \ref{subsec:Covariance-matrix-distances}. Interesting distinctions were made between the authors' styles. This approach takes advantage of the fact that the graph Laplacians are a convex subset of the space of covariance matrices.  The data are from \cite{Mahlberg2016}. 


\begin{figure}[htbp] \begin{center} \includegraphics[width=12cm]{./ChapterI/MDSnorms-big.pdf} \end{center} \caption{MDS and cluster analysis for the Jane Austen (Blue, lower case) and Charles Dickens (Red, upper case) novels.  The sparse norms that are used are: a) Frobenius of (\ref{eq:Frobeniusnorm}); b)-e)  Entrywise norms of (\ref{eq:EWnorm}) for $p = 1,0.5,0.75,3$; f) one norm (O) (maximum absolute column sum); g)  the infinity norm (I) (maximum absolute row sum); h) the max norm (maximum modulus of all elements) (M). It can be see from the various MDS plots that there is generally good separation between the Austen and Dickens novels. However, on inspection of the clusters for some metrics (entrywise $p=3$, O, I, M) the Dickens novels Great Expectations (GE) and David Copperfield (DC) have been put in the same cluster as the Jane Austen novels.} \label{BigMDS}   \end{figure}

Here\index{data objects!covariance matrices} we consider some additional
comparisons of the novels of Austen and Dickens as data objects, using
all the $m=48,385$ different words, as opposed to the top 1000 words
used by \citet{Severnetal19}. We  use MDS (Multi-Dimensional Scaling\index{Multi-Dimensional Scaling},
Section \ref{secE.2:Multi-dimensional-scaling}) and  \index{hierarchical clustering}hierarchical
cluster analysis\index{cluster analysis} using Ward's linkage\index{linkage!Ward's}
(described in Section \ref{secK-B:HierarchicalClust}) for different
choices of metric\index{metric|(}, listed in Table \ref{tabI.B:Metrics4Novels}.
The graph Laplacians are very high dimensional $m\times m$ matrices
here, although they are very sparse. Hence these norms can all be
efficiently computed using sparse matrix arithmetic in R. The results
of clustering\index{clustering!in linguistics} these very high dimensional
sparse graph Laplacians appear in the indicated panels of Figure \ref{BigMDS}.
For each metric, the left panel is a dendrogram (also described in
Section \ref{secK-B:HierarchicalClust}) showing exactly now the Austen
(represented using lower case abbreviations of the titles) and the
Dickens (upper case abbreviations) novels cluster. The left panel
provides another view of the impact of each metric, as a scatterplot
of the MDS scores with the Austen (Dickens) novels using the same
abbreviated titles, colored blue (red respectively).
\begin{table}
\begin{tabular}{|c|c|c|}
\hline 
Panel Index & Symbol & Description\tabularnewline
\hline 
\hline 
(a) & F & Frobenius norm\index{Frobenius norm}, from (\ref{eq:Frobeniusnorm})\tabularnewline
\hline 
(b)-(e) & E(p) & Entrywise norms, from (\ref{eq:EWnorm}), for $p=1,\;0.5,\;0.75,\;3$\tabularnewline
\hline 
(f) & O & One norm\index{one norm}, maximum absolute column sum\tabularnewline
\hline 
(g) & I & Infinity norm, maximum absolute row sum\tabularnewline
\hline 
(h) & M & Maximum modulus of all elements\tabularnewline
\hline 
\end{tabular}

\caption{List of metrics, and indices, studied in Figure \ref{BigMDS}. \label{tabI.B:Metrics4Novels} }
\end{table}
It is clear in Figure \ref{BigMDS} that the MDS results vary widely
using these choices of distance\index{distance!choice in MDS}s.  Most
choices of metric separate the Austen and Dickens novels (colors)
in the two dimensional MDS plot. However, careful inspection of the
dendrograms shows that the only methods that put all the Austen and
Dickens novels  in separate clusters are the Frobenius (F), and entrywise
E(1), E(0.75) metrics, so these would be preferred here. For the sparse
norms (O, I and M) and entrywise E(3) the Dickens novels Great Expectations
(GE) and David Copperfield (DC) have been put in the same cluster
as Jane Austen's novels. This makes grammatical sense, because those
Dickens novels were written in the first person, which is not inconsistent
with some aspects of Austen\textquoteright s style. In the earlier
analysis of \citet{Severnetal19} based on the top $1000$ words,
the square root and Procrustes distance\index{distance!Procrustes}s
from Section \ref{subsec:Covariance-matrix-distances} gave preferable
clustering compared to the Frobenius \index{distance!Frobenius}distance
(which again clustered GE and DC with Jane Austen's novels). These
examples all show that the data object choice of metric\index{metric|)}
is very important in such analyses.

Further extensions of regression models for network object data include
the local Fr\'echet regression of \citet{PetersenMueller19}; functional
models for time-varing networks of \citet{DubeyMueller20}; and non-parametric
regression in \citet{Severnetal21} investigating changes in writing
style in the Austen and Dickens novels.

\subsection{Labeled versus unlabeled nodes\label{subsec:Labeled-versus-unlabeled}}

In the above applications we have considered the nodes to be labeled,
and the role of each node (e.g. a word in corpus linguistics) is the
same for each data object. In some applications it may be appropriate
to compare networks where the labeling of the nodes is also not of
relevance. The network distance\index{distance!network}s are then
obtained by minimizing over all permutations of the labels. Such optimization
is an NP-complete problem, although there are approximate algorithms
available for such graph matching. As the set of permutations is a
subset of the space of rotations the Procrustes distance provides
another alternative approach. Statistical analysis of unlabeled graph\index{graph|)}s
has been considered by \citet{Kolaczyk2020unlabeled}, \citet{GuoSrivastava2020ElasticGraphs}
and \citet{Calissanoetal20}.\index{data objects!networks|)} 
