A Topological Approach to Spectral Clustering
Antonio Rieser
Antonio Rieser
Laplace-Beltrami_clustering_arxiv.tex
\documentclass[11pt,oneside,a4paper]{article}

%-----General packages----

%\usepackage{amsrefs}
\usepackage[backend=bibtex]{biblatex}
\usepackage[T1]{fontenc}
\usepackage{color}
%\usepackage[pdffitwindow=false,
 %  pdfview=FitH,
   %pdfstartview=FitH,
 %  plainpages=false]{hyperref}
\usepackage[utf8]{inputenc} % ------ Pour utiliser des fichiers UTF-8
\usepackage[pdftex]{thumbpdf}

%---------- Math related --------------------
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{paralist}
\usepackage{mathtools}
\usepackage{colonequals}
\usepackage{breqn}
\usepackage{amssymb}

%-----My packages----- 
\usepackage{graphicx}
\usepackage{caption}
\usepackage{verbatim}
%\usepackage[foot]{amsaddr}
\usepackage{setspace}
\usepackage{lipsum}
\usepackage{algorithm}
\usepackage{algpseudocode}

%-----Spacing--------
\singlespacing

%-----Textclass specific LaTeX commands-----
\numberwithin{equation}{section} %----------Comment out for sequentially-numbered
\numberwithin{figure}{section} %--------------Comment out for sequentially-numbered
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{plain}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
\newtheorem{example}[thm]{Example}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\theoremstyle{plain}
\newtheorem{prop}[thm]{Proposition}
\theoremstyle{plain}
\newtheorem{lem}[thm]{Lemma}
\theoremstyle{plain}
\newtheorem*{thm*}{Theorem}
\newtheorem*{lem*}{Lemma}
\newtheorem*{prop*}{Proposition}
\newtheorem*{cor*}{Corollary}
\newtheorem*{rem*}{Remark}
\newtheorem*{defn*}{Definition}

%-----New Commands-------
\newcommand{\Id}{\operatorname{Id}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\HR}[1]{H_{\R^n}^{#1}([0,1],\R^{2n})}
\newcommand{\e}{\operatorname{e}}
\newcommand{\defeq}{\buildrel\triangle\over =}
\newcommand{\ceq}{\colonequals}
\newcommand{\F}{\mathcal{F}}
\newcommand{\Ar}{\mathcal A}
\newcommand{\defin}[1]{\textbf{#1}}
\newcommand{\supp}{\operatorname{supp}}
\newcommand{\X}{\mathcal X}

\addbibresource{Mathematics.bib}

\title{A Topological Approach to Spectral Clustering }
\author{Antonio Rieser}
\date{}
%\author{Antonio Rieser}
%\address{Department of Electrical Engineering, Technion - Israel Institute for Technology, Haifa 32000, Israel}

\begin{document}
\maketitle
\abstract{We propose a clustering algorithm which, for input, takes data assumed to be sampled from a uniform distribution supported on a metric space $X$, and outputs a clustering of the data based on a topological estimate of the connected components of $X$. The algorithm works by choosing a weighted graph on the samples from a natural one-parameter family of graphs using an error based on the heat operator on the graphs. The estimated connected components of $X$ are identified as the support of the eigenfunctions of the heat operator with eigenvalue $1$, which allows the algorithm to work without requiring the number of expected clusters as input.}

\section{Introduction}

The analysis of complex, high-dimensional data is one of the major research challenges in contemporary computer science and statistics. In recent years, geometric and topological approaches to data analysis have begun to yield important insights into the structure of complex data sets (see, for instance, \cite{Belkin_Niyogi_2003} for an example of spectral geometry applied to dimension reduction, and \cite{Ghrist_2008}, \cite{Carlsson_2009} for surveys on homological methods of data analysis and visualization).  The common point of departure of these methods is the assumption that data in high-dimensional spaces is often concentrated around a low-dimensional manifold or other topological space. In this note, we begin from the assumption that the data comes from a uniform distribution supported on a topologically disconnected space, and that clusters in the data reflect this lack of topological connectivity.

Geometric techniques for data analysis have concentrated on approximating the geometry of the data as a step toward non-linear dimension reduction. Once the dimension is reduced, standard statistical techniques are then used to analyze the data in the lower-dimensional space. Methods in this class include ISOMAP \cite{Tenenbaum_de_Sliva_Langford_2000}, Locally Linear Embedding \cite{Roweis_Saul_2000}, Hessian Eigenmaps \cite{Donoho_Grimes_2003}, Laplacian Eigenmaps \cite{Belkin_Niyogi_2003}, and Diffusion Maps \cite{Coifman_Lafon_2006}.  Most of these techniques build a weighted graph to approximate the Laplace-Beltrami operator on a manifold, or else a related Markov chain on a graph, and then in practice use the eigenvalues and eigenvectors of an approximation to the Laplacian to reduce the dimension of the data and then use a $k$-means clustering algorithm to classify the data \cite{Shen_et_al_2014}, \cite{Sanchez-Garcia_et_al_2014}. In \cite{Chazal_Guibas_2013}, we find a more topologically-oriented approach, in which persistent homology is used to help identify high-density regions of a distribution function.



In this article, we give an algorithm that directly uses the topological information in the Laplacian and heat operator, and which also demonstrates the utility of considering clustering as a problem of estimating the number of connected components of a distribution whose support is disconnected. While the topological aspect of the clustering problem is generally acknowledged in the topological data analysis community, this is, to the best of our knowledge, the first completely data-driven clustering algorithm that explicitly exploits this point of view. Second, the algorithm produces both the number of clusters and the clusters themselves, unlike popular algorithms such as $k$-means clustering, in which the number of clusters is required as input. The algorithm we present also gives, we believe, the first use of cross-validation in a non-commutative context. While this appears formally like standard cross-validation, we find ourselves outside the standard context of commutative probability, and the usual proofs of convergence no longer apply. Rigorous justification of this cross-validation technique is an important topic for future study, but we do not address this here. Finally, we give the first algorithm for automatically choosing the bandwidth of the kernel function used in approximations to Laplace-Beltrami operators.


\section{The Heat Operator on a Family of Graphs}
We will see in Section \ref{sec:TopC} that, for data sampled from a uniform distribution supported on a disconnected manifold, the clustering problem reduces to identifying the $0$-eigenfunctions of a certain graph Laplacian $L$, or, equivalently, the $1$-eigenfunctions of the the heat operator $e^{-tL}$ at some $t>0$.

We now describe how to construct the family of graph Laplacians from which we will choose $L$. First, let $S = \{x_i\}_{i=1}^n \subset X$ be the points sampled from $X$.  Given a subset $S' \subseteq S$, We define the matrix $L_{r,S'}$ to be
\begin{equation*}
(L_{r,S'})_{(i,j)} =
\begin{cases}
K_r(x_i,x_j) &\begin{split}& i\neq j, \\ & x_i \in S' \end{split}\\
-\sum_{x_j \in S'} K_r(x_i,x_j) &  i = j, \\
0 & \text{otherwise}
\end{cases}
\end{equation*}
where $K_r: X \times X\to \R$ is a function which satisfies
\begin{enumerate}
\item $K_r(x,y) = f_r(d(x,y))$ for some non-negative function $f_r$
\item $K_r(x,\cdot) \to \delta_{x}(\cdot)$ as a distribution as $r\to 0$.
\item $\int_X K_r(x,y) \,d\mu(y) = 1 \;\forall r\in (0,\infty), x \in S$.
\end{enumerate}
In our applications, $K_r$ will also have compact support. We will sometimes use $L_{r,n}$ to denote $L_{r,S}$.

We likewise define the corresponding heat operators by
\begin{equation*}
e^{-tL_{r,S'}} = \sum_{k=1}^\infty \frac{(-tL_{r,S'})^k}{k!}.
\end{equation*}

\section{Topology and Clustering}
\label{sec:TopC}

We suppose that our data is sampled from a uniform distribution which is supported on a disconnected subspace $X$ embedded in a topological space $Y$. Our task is then to estimate the number of connected components of $X$ from the samples and to decide which points belong to which connected component.  Given the sample points $S$ from $X$,  we generate a one-parameter family of weighted graphs with vertices at $S$, with Laplace operator on $M$, and we appeal to several basic facts of Hodge theory (see, for instnace, \cite{Jost_2011}, Chapter 3). 

First, we recall that the Laplace-Beltrami operator $\Delta:L^2(M) \to L^2(M)$ may be defined by $\Delta = -d^*d$. We first recall that the dimension of the kernel of the Laplace-Beltrami operator $\Delta:L^2(M) \to L^2(M)$ is equal to the $0$-th real Betti number $\beta_0$ of $M$, which gives the number of connected components of $M$. Also, since $\Delta = -d^*d$, the functions in the kernel are constant on each connected component (also Lemma 3.3.5 in \cite{Jost_2011}). The following proposition now follows easily.

\begin{prop}
\label{prop:Image F}
Let $(M,g)$ be a smooth Riemannian manifold, and let $\beta_0$ denote the $0$-th Betti number of $M$. Let $\{f_i\}_{i=1}^{\beta_0(M)}$ be a basis of the kernel of the Laplace-Beltrami operator $\Delta$ of $M$, and define the map $F:M \to \R^{\beta_0(M)}$ by
\[F(x) \ceq (f_1(x),\dots,f_{\beta_0}(x)) \in \R^{\beta_0}.\]
Then the image of $F$ consists of exactly $\beta_0(M)$ points in $\R^{\beta_0(M)}$, and the image of each connected component of $M$ is a single point.
\end{prop} 
\begin{proof} First, we know from \cite{Jost_2011}, Section 3.3 that each basis function is constant on each connected component of $M$, and it follows that each connected component is sent to a single point. It only remains to show that no two connected components are sent to the same point. Consider the matrix $A$ defined by $a_{ij} = f_i(M_j)$. Since the $f_i$ are linearly independent, this is a $\beta_0(M) \times \beta_0(M)$ matrix of full rank. Suppose now that there are two connected components, $M_1$ and $M_2$, whose image under $F$ is the same point $x \in \R^{\beta_0(M)}$. Then two rows of $A$ are the same, and the $rank A < \beta_0(M)$, a contradiction. Therefore, all of the connected components of $M$ are sent to different points in $\R^{\beta_0(M)}$.
\end{proof}

We note, too, that Proposition \ref{prop:Image F} also hold for graphs and the graph Laplacian instead of manifolds, with a nearly identical proof. 

\section{Cross-Validation and Bandwidth Selection}

When working with approximations to the Laplace-Beltrami operator, the properties of the approximation depend on the particular choice of kernel $K_r$ and bandwidth $r$ used. In practice, this parameter is generally chosen on an ad hoc basis, or else based on an asymptotic formula with unknown constants, as, for instance, in \cite{Coifman_Lafon_2006}. In these methods, the resulting graphs are connected for any given bandwidth, and the exact dependence of the clustering on the bandwidth is unclear. In our case, we use a compactly supported kernel function, so the bandwidth directly dictates the connected components of the graph, and it becomes critical for us to have a systematic method for choosing this parameter. 

In this article, we make this choice using a variant of the so-called "elbow method", which is often used to estimate the number of clusters in k-means clustering
or the number of eigenvalues to use in principal component analysis. 
The idea in this method is the following. When $X$ is a manifold, would ideally like to choose a bandwidth which minimizes an error functional of the form $E(r) \colonequals \Vert e^{-L_{r,S_i}} - e^{-\Delta} \Vert_{HS}$, where $\Vert A \Vert_{HS}= (Tr(A^*A))^{1/2}$ denotes the Hilbert-Schmidt norm. Let the operator $L_r : L^2(X)\to L^2(X)$ be defined by
\[
(L_rf)(x) \colonequals \frac{1}{r}\left(\int_X K_r(x,y)f(x) \, d\mu(y) - \int_X K_r(x,y)f(y) \, d\mu(y)\right)
\]
where $\mu$ is a uniform measure on the manifold $X$. Let $V(r) \colonequals \Vert e^{-L_{r,n}} - e^{-L_{r}}\Vert_{HS}$, and let $B(r) \colonequals \Vert e^{-L_{r}} - e^{-\Delta}\Vert_{HS}$, and note the $B(r)$ and $V(r)$ are the natural bias and variance terms for this problem, respectively. Now, $E(r) \leq B(r) + V(r)$ by the triangle inequality, and we estimate $V(r)$ using the cross validation sum
\[
\hat{V}(r) = \frac{1}{N} \sum_{i=1}^N \Vert e^{-L_{r,S_i}} - e^{-L_{r,n}}\Vert_{HS}.
\] 
(As mentioned in the introduction, it is actually not obvious that this is an appropriate estimate for $V(r)$, given the norm and the non-commutativity in the problem. We do not discuss this further here, however, but we will return to this question in future work.) The bias $B(r)$ is difficult to estimate, but we may nonetheless attempt to choose the bandwidth $r_0$ such that  increasing $r$ beyond $r_0$ produces diminishing returns with respect to decreasing the variance, i.e. to find $r_0$ such that 
\[
\frac{dV}{dr}(r) < \frac{V(r_{max}) - V(r_{min})}{r_{max}-r_{min}}
\] 
for $r > r_0$. We further estimate this to be the value $\hat{r}_0$ which is the largest value of $r$ such that
\begin{equation*}
\frac{\hat{V}(r+1) - \hat{V}(r-1)}{2} < \frac{\hat{V}(r_{max})-\hat{V}(1)}{r_{max} -1},
\end{equation*}
where  $r_{max}$ is the diameter of the data set.


\section{Compensating for estimation error}

The results in Section \ref{sec:TopC} tell us that the points in each connected component of our graphs should be sent to exactly the same point in $\R^{\beta_0(X)}$ by the map $F$. In practice, however, there are small amounts of estimation error in the algorithms for computing eigenvalues and eigenvectors, and this must be accounted for when constructing the final clustering. We do this with a modified version of Gaussian elimination on the matrix formed by the eigenvectors, which we now describe.

First, note that the $j$-th entry in the eigenvector $f_i$ is the value of the eigenfunction $f_i$ evaluated on the point $x_j$. Let $\Psi$ be the matrix defined by
\begin{equation*}
(\Psi)_{(i,j)}  = (f_i)_j,
\end{equation*} 
We give a modified Gaussian elimination algorithm in Algorithm \ref{alg:Gauss}. For what follows, let $n$ denote the number of points in our sample.
\begin{algorithm}
\caption{Modified Gaussian elimination on $\Psi$}
\label{alg:Gauss}
\begin{algorithmic}[1]

\For{$i = 1$ to $\beta_0(X)$}
\State Reorder columns $i$ through $n$ of $\Psi$ so that $\vert \Psi_{(i,i)} \vert$ is the maximum of $\vert \Psi_{(i,j)} \vert$ in row $i$.
\State Divide row $i$ by $\Psi_{(i,i)}$
\State Using elementary row operations, make $\Psi_{(k,i)} = 0$ for $k\neq i$.
\EndFor
\State Let $f_i \ceq \Psi_i$, and (abusing notation) define the map $\Phi(x) \ceq (f_1,\dots,f_{\beta_0(X)})$
\end{algorithmic}
\end{algorithm}

Note that the algorithm, if there was no estimation error, would send each point in the sample to one of the vectors $e_i$ in the standard basis of $\R^{\beta_0(X)}$. Now, however, even given some numerical error, we are able to cluster the sample points according to how close $\Phi(x)$ are to each of the vectors $e_i$. 

\section{Algorithm and Experiments}

We now give the complete algorithm and the results of some numerical experiements.

\begin{algorithm}
\caption{Clustering algorithm}
\begin{algorithmic}[1]
\State Generate $N$ random subsamples $S_i$ of $S$
\State For each $r < Diam(S)$, compute $L_{r,n}$, $e^{-L_{r,n}}$, $L_{r,S_i}$ and $e^{-L_{r,S_i}}$
\State Find the max $\hat{r}$ of $\hat{V}(r)$
\State Compute the $1$-eigenvectors of $e^{-L_{\hat{r},n}}$, $\phi_i$, $i \in 1\dots k$
\State Using algorithm \ref{alg:Gauss}, create the map $\Phi: x \mapsto \Phi(x) = (\phi_1(x), \dots, \phi_k(x)) \in \R^k$
\State Compute the distances $d_i(x) = \Vert \Phi(x) - e_i \Vert$ for each point $x$ in the sample.
\State Put the point $x$ in the $i$-th cluster if $d_i(x) < d_j(x)$ for all $j \neq i$.
\end{algorithmic}
\end{algorithm}

For our experiments, the functions $K_r(x,y)$ used are
\begin{equation*}
K_r(x,y) = \begin{cases} \frac{1}{\int_{B(x,r)} d\mu}, & \text{if } d(x,y) \leq r \\
0 & \text{otherwise},
\end{cases}
\end{equation*}
where $B(x,r) \subset X$ are balls centered at $x$ of radius $r$, and $\mu$ is the standard Lebesgue measure in the ambient Euclidean space.

The following figures summarize the output of this algorithm on a data set of 500 points sampled with a small amount of Guassian noise from three circles embedded in $\R^3$. The horizontal circle has radius $1$, and the other two have radius $0.5$ and are centered on a random point of the horizontal circle. The standard deviation of the noise was taken to be $0.05$. The Figure \ref{fig:Variance} shows the curve giving the variance estimate, and figure \ref{fig:Phi} shows the image of the eigenfunctions, after passing through the modified Gaussian elimination procedure. Finally, Figure \ref{fig:Clustering} shows the clustering given by the algorithm, with the different clusters colored in red, green, and blue. 


\begin{figure}[H]
\includegraphics[width=\textwidth]{CirclesWithNoise41VariancePlot.png}
\caption{The Estimate of the Variance}
\label{fig:Variance}
\end{figure}
\begin{figure}[H]
\includegraphics[width=\textwidth]{CirclesWithNoise41PhiPlot.png}
\caption{The image of $\Phi$, centered around the points $(1,0,0), (0,1,0),$ and $(0,0,1)$}
\label{fig:Phi}
\end{figure}


\begin{figure}[h]
\includegraphics[width=\textwidth]{CirclesWithNoise41ClusterImage.png}
\caption{Clusters}
\label{fig:Clustering}
\end{figure}
\pagebreak

\thanks{We thank Robert Adler, Jacob Abernathy, and Bertrand Michel for many useful discussions and comments. We would additionally like to thank the organizers of the CIMAT Differential Geometry Seminar, the AUS-ICMS Meeting, the XXIst Oporto Meeting on Topology, Geometry, and Physics, and the Toposys Network for the opportunity to present early versions of this work in their conferences and seminars. This research was supported in part by FP7-ICT- 318493-STREP}
\printbibliography

\end{document}
Laplace-Beltrami_clustering_arxiv.bbl
% $ biblatex auxiliary file $
% $ biblatex version 2.3 $
% Do not modify the above lines!
%
% This is an auxiliary file used by the 'biblatex' package.
% This file may safely be deleted. It will be recreated as
% required.
%
\begingroup
\makeatletter
\@ifundefined{ver@biblatex.sty}
  {\@latex@error
     {Missing 'biblatex' package}
     {The bibliography requires the 'biblatex' package.}
      \aftergroup\endinput}
  {}
\endgroup

\entry{Belkin_Niyogi_2003}{article}{}
  \name{author}{2}{}{%
    {{}%
     {Belkin}{B.}%
     {Mikhail}{M.}%
     {}{}%
     {}{}}%
    {{}%
     {Niyogi}{N.}%
     {Partha}{P.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {MIT Press}%
  }
  \strng{namehash}{BMNP1}
  \strng{fullhash}{BMNP1}
  \field{sortinit}{B}
  \verb{doi}
  \verb 10.1162/089976603321780317
  \endverb
  \field{issn}{0899-7667}
  \field{number}{6}
  \field{pages}{1373\bibrangedash 1396}
  \field{title}{{Laplacian Eigenmaps for Dimensionality Reduction and Data
  Representation}}
  \verb{url}
  \verb http://dx.doi.org/10.1162/089976603321780317
  \endverb
  \field{volume}{15}
  \list{location}{1}{%
    {Cambridge, MA, USA}%
  }
  \field{journaltitle}{Neural Comput.}
  \field{month}{06}
  \field{year}{2003}
\endentry

\entry{Carlsson_2009}{article}{}
  \name{author}{1}{}{%
    {{}%
     {Carlsson}{C.}%
     {Gunnar}{G.}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{CG1}
  \strng{fullhash}{CG1}
  \field{sortinit}{C}
  \field{number}{2}
  \field{pages}{255\bibrangedash 308}
  \field{title}{{Topology and Data}}
  \field{volume}{46}
  \field{journaltitle}{Bulletin of the American Mathematical Society}
  \field{year}{2009}
\endentry

\entry{Chazal_Guibas_2013}{article}{}
  \name{author}{4}{}{%
    {{}%
     {Chazal}{C.}%
     {F.}{F.}%
     {}{}%
     {}{}}%
    {{}%
     {Guibas}{G.}%
     {L.~J.}{L.~J.}%
     {}{}%
     {}{}}%
    {{}%
     {Oudot}{O.}%
     {S.~Y.}{S.~Y.}%
     {}{}%
     {}{}}%
    {{}%
     {Skraba}{S.}%
     {P}{P}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{CF+1}
  \strng{fullhash}{CFGLJOSYSP1}
  \field{sortinit}{C}
  \field{number}{6}
  \field{title}{Persistence-based clustering in Riemannian manifolds}
  \field{volume}{60}
  \field{journaltitle}{Journal of the ACM}
  \field{year}{2013}
  \warn{\item Invalid format of field 'month'}
\endentry

\entry{Coifman_Lafon_2006}{article}{}
  \name{author}{2}{}{%
    {{}%
     {Coifman}{C.}%
     {Ronald~R.}{R.~R.}%
     {}{}%
     {}{}}%
    {{}%
     {Lafon}{L.}%
     {St{\'e}phane}{S.}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{CRRLS1}
  \strng{fullhash}{CRRLS1}
  \field{sortinit}{C}
  \verb{doi}
  \verb 10.1016/j.acha.2006.04.006
  \endverb
  \field{issn}{1063-5203}
  \field{number}{1}
  \field{pages}{5\bibrangedash 30}
  \field{title}{{Diffusion maps}}
  \verb{url}
  \verb http://dx.doi.org/10.1016/j.acha.2006.04.006
  \endverb
  \field{volume}{21}
  \field{journaltitle}{Appl. Comput. Harmon. Anal.}
  \field{year}{2006}
\endentry

\entry{Donoho_Grimes_2003}{article}{}
  \name{author}{2}{}{%
    {{}%
     {Donoho}{D.}%
     {David~L.}{D.~L.}%
     {}{}%
     {}{}}%
    {{}%
     {Grimes}{G.}%
     {Carrie}{C.}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{DDLGC1}
  \strng{fullhash}{DDLGC1}
  \field{sortinit}{D}
  \field{abstract}{%
  We describe a method for recovering the underlying parametrization of
  scattered data (mi) lying on a manifold M embedded in high-dimensional
  Euclidean space. The method, Hessian-based locally linear embedding, derives
  from a conceptual framework of local isometry in which the manifold M, viewed
  as a Riemannian submanifold of the ambient Euclidean space ?n, is locally
  isometric to an open, connected subset ? of Euclidean space ?d. Because ?
  does not have to be convex, this framework is able to handle a significantly
  wider class of situations than the original ISOMAP algorithm. The theoretical
  framework revolves around a quadratic form ?(f) = ?M??Hf(m)?dm defined on
  functions f : M ? ?. Here Hf denotes the Hessian of f, and ?(f) averages the
  Frobenius norm of the Hessian over M. To define the Hessian, we use
  orthogonal coordinates on the tangent planes of M. The key observation is
  that, if M truly is locally isometric to an open, connected subset of ?d,
  then ?(f) has a (d + 1)-dimensional null space consisting of the constant
  functions and a d-dimensional space of functions spanned by the original
  isometric coordinates. Hence, the isometric coordinates can be recovered up
  to a linear isometry. Our method may be viewed as a modification of locally
  linear embedding and our theoretical framework as a modification of the
  Laplacian eigenmaps framework, where we substitute a quadratic form based on
  the Hessian in place of one based on the Laplacian.%
  }
  \verb{doi}
  \verb 10.1073/pnas.1031596100
  \endverb
  \verb{eprint}
  \verb http://www.pnas.org/content/100/10/5591.full.pdf+html
  \endverb
  \field{number}{10}
  \field{pages}{5591\bibrangedash 5596}
  \field{title}{Hessian eigenmaps: Locally linear embedding techniques for
  high-dimensional data}
  \verb{url}
  \verb http://www.pnas.org/content/100/10/5591.abstract
  \endverb
  \field{volume}{100}
  \field{journaltitle}{Proceedings of the National Academy of Sciences}
  \field{year}{2003}
\endentry

\entry{Ghrist_2008}{article}{}
  \name{author}{1}{}{%
    {{}%
     {Ghrist}{G.}%
     {Robert}{R.}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{GR1}
  \strng{fullhash}{GR1}
  \field{sortinit}{G}
  \field{number}{1}
  \field{pages}{61\bibrangedash 75}
  \field{title}{{Barcodes: the persistent topology of data}}
  \verb{url}
  \verb http://www.ams.org/bull/2008-45-01/S0273-0979-07-01191-3/
  \endverb
  \field{volume}{45}
  \field{journaltitle}{Bulletin of the American Mathematical Society}
  \field{year}{2008}
\endentry

\entry{Tenenbaum_de_Sliva_Langford_2000}{article}{}
  \name{author}{1}{}{%
    {{}%
     {Joshua B.~Tenenbaum}{J.~B.~T.}%
     {Josh~Langford}{J.~L.}%
     {}{}%
     {Vin de~Silva}{V.~d.~S.}}%
  }
  \strng{namehash}{JBTVdSJL1}
  \strng{fullhash}{JBTVdSJL1}
  \field{sortinit}{J}
  \verb{doi}
  \verb 10.1126/science.290.5500.2319
  \endverb
  \field{pages}{2319}
  \field{title}{A Global Geometric Framework for Nonlinear Dimensionality
  Reduction}
  \field{volume}{290}
  \field{journaltitle}{Science}
  \field{year}{2000}
\endentry

\entry{Jost_2011}{book}{}
  \name{author}{1}{}{%
    {{}%
     {Jost}{J.}%
     {J{\"u}rgen}{J.}%
     {}{}%
     {}{}}%
  }
  \list{publisher}{1}{%
    {Springer, Heidelberg}%
  }
  \strng{namehash}{JJ1}
  \strng{fullhash}{JJ1}
  \field{sortinit}{J}
  \verb{doi}
  \verb 10.1007/978-3-642-21298-7
  \endverb
  \field{edition}{Sixth}
  \field{isbn}{978-3-642-21297-0}
  \field{pages}{xiv+611}
  \field{series}{Universitext}
  \field{title}{Riemannian geometry and geometric analysis}
  \verb{url}
  \verb http://dx.doi.org/10.1007/978-3-642-21298-7
  \endverb
  \field{year}{2011}
\endentry

\entry{Roweis_Saul_2000}{article}{}
  \name{author}{1}{}{%
    {{}%
     {Sam T.~Roweis}{S.~T.~R.}%
     {Lawrence K.~Saul}{L.~K.~S.}%
     {}{}%
     {}{}}%
  }
  \strng{namehash}{STRLKS1}
  \strng{fullhash}{STRLKS1}
  \field{sortinit}{S}
  \verb{doi}
  \verb 10.1126/science.290.5500.2323
  \endverb
  \field{pages}{2323}
  \field{title}{Nonlinear Dimensionality Reduction by Local Linear Embedding}
  \field{volume}{290}
  \field{journaltitle}{Science}
  \field{year}{2000}
\endentry

\entry{Sanchez-Garcia_et_al_2014}{article}{}
  \name{author}{7}{}{%
    {{}%
     {Sanchez-Garcia}{S.-G.}%
     {Ruben}{R.}%
     {}{}%
     {}{}}%
    {{}%
     {Fennelly}{F.}%
     {Max}{M.}%
     {}{}%
     {}{}}%
    {{}%
     {Norris}{N.}%
     {Sean}{S.}%
     {}{}%
     {}{}}%
    {{}%
     {Wright}{W.}%
     {Nick}{N.}%
     {}{}%
     {}{}}%
    {{}%
     {Niblo}{N.}%
     {Graham}{G.}%
     {}{}%
     {}{}}%
    {{}%
     {Brodzki}{B.}%
     {Jacek}{J.}%
     {}{}%
     {}{}}%
    {{}%
     {Bialek}{B.}%
     {Janusz}{J.}%
     {}{}%
     {}{}}%
  }
  \keyw{clustering, power system analysis computing}
  \strng{namehash}{SGR+1}
  \strng{fullhash}{SGRFMNSWNNGBJBJ1}
  \field{sortinit}{S}
  \field{abstract}{%
  A power transmission system can be represented by a network with nodes and
  links representing buses and electrical transmission lines, respectively.
  Each line can be given a weight, representing some electrical property of the
  line, such as line admittance or average power flow at a given time. We use a
  hierarchical spectral clustering methodology to reveal the internal
  connectivity structure of such a network. Spectral clustering uses the
  eigenvalues and eigenvectors of a matrix associated to the network, it is
  computationally very efficient, and it works for any choice of weights. When
  using line admittances, it reveals the static internal connectivity structure
  of the underlying network, while using power flows highlights islands with
  minimal power flow disruption, and thus it naturally relates to controlled
  islanding. Our methodology goes beyond the standard k-means algorithm by
  instead representing the complete network substructure as a dendrogram. We
  provide a thorough theoretical justification of the use of spectral
  clustering in power systems, and we include the results of our methodology
  for several test systems of small, medium and large size, including a model
  of the Great Britain transmission network.%
  }
  \field{pages}{1\bibrangedash 9}
  \field{title}{Hierarchical spectral clustering of power grids}
  \verb{url}
  \verb http://eprints.soton.ac.uk/363140/
  \endverb
  \field{journaltitle}{IEEE Transactions on Power Systems}
  \field{year}{2014}
  \warn{\item Invalid format of field 'month'}
\endentry

\entry{Shen_et_al_2014}{article}{}
  \name{author}{5}{}{%
    {{}%
     {Shen}{S.}%
     {Wen-Jun}{W.-J.}%
     {}{}%
     {}{}}%
    {{}%
     {Wong}{W.}%
     {Hau-San}{H.-S.}%
     {}{}%
     {}{}}%
    {{}%
     {Xiao}{X.}%
     {Quan-Wu}{Q.-W.}%
     {}{}%
     {}{}}%
    {{}%
     {Guo}{G.}%
     {Xin}{X.}%
     {}{}%
     {}{}}%
    {{}%
     {Smale}{S.}%
     {Stephen}{S.}%
     {}{}%
     {}{}}%
  }
  \list{language}{1}{%
    {English}%
  }
  \list{publisher}{1}{%
    {Springer US}%
  }
  \keyw{String kernel; Peptide binding prediction; Reproducing kernel Hilbert
  space; Major histocompatibility complex; HLA DRB allele classification;
  62P10; 68T05; 92B15; 92C40}
  \strng{namehash}{SWJ+1}
  \strng{fullhash}{SWJWHSXQWGXSS1}
  \field{sortinit}{S}
  \verb{doi}
  \verb 10.1007/s10208-013-9173-9
  \endverb
  \field{issn}{1615-3375}
  \field{number}{5}
  \field{pages}{951\bibrangedash 984}
  \field{title}{Introduction to the Peptide Binding Problem of Computational
  Immunology: New Results}
  \verb{url}
  \verb http://dx.doi.org/10.1007/s10208-013-9173-9
  \endverb
  \field{volume}{14}
  \field{journaltitle}{Foundations of Computational Mathematics}
  \field{year}{2014}
\endentry

\lossort
\endlossort

\endinput
