Consider a weighted or unweighted $k$-nearest neighbor graph that has been built on $n$ data points drawn randomly according to some density $p$ on $\R^d$. We study the convergence of the shortest path distance in such graphs as the sample size tends to infinity. We prove that for unweighted $\knn$ graphs, this distance converges to an unpleasant distance function on the underlying space whose properties are detrimental to machine learning. We also study the behavior of the shortest path distance in weighted $\knn$ graphs.
knn_icml2012.tex
\documentclass{article}

% For figures
%\usepackage[belowskip=-15pt]{caption}
\usepackage{graphicx,amssymb} % more modern
\usepackage{subfigure} 
%\usepackage[caption=false,font=footnotesize]{subfig}
% For citations
\usepackage{natbib}

% For algorithms
\usepackage{algorithm}
%\usepackage{algorithmic}

% As of 2011, we use the hyperref package to produce hyperlinks in the
% resulting PDF.  If this breaks your system, please commend out the
% following usepackage line and replace \usepackage{icml2012} with
% \usepackage[nohyperref]{icml2012} above.
%\usepackage{hyperref}

% Packages hyperref and algorithmic misbehave sometimes.  We can fix
% this with the following command.
%\newcommand{\theHalgorithm}{\arabic{algorithm}}

% Employ the following version of the ``usepackage'' statement for
% submitting the draft version of the paper for review.  This will set
% the note in the first column to ``Under review.  Do not distribute.''
%\usepackage[nohyperref]{icml2012} 
% Employ this version of the ``usepackage'' statement after the paper has
% been accepted, when creating the final version.  This will set the
% note in the first column to ``Appearing in''
\usepackage[accepted]{icml2012}


% The \icmltitle you define below is probably too long as a header.
% Therefore, a short form for the running title is supplied here:
%\icmltitlerunning{Submission and Formatting Instructions for ICML 2012}

\input{ules_latex_defaults.tex}

\renewcommand{\ulesqed}{\mbox{}\hfill$\Box$}
\newcommand{\SP}{\mathcal{SP}}
%\addtolength{\belowcaptionskip}{-15pt}

\begin{document} 

\twocolumn[
\icmltitle{Shortest path distance in random $k$-nearest neighbor graphs}
\icmlauthor{Morteza Alamgir$^{1}$}{morteza@tuebingen.mpg.de}
\icmlauthor{Ulrike von Luxburg$^{1,2}$}{ulrike.luxburg@tuebingen.mpg.de}
\icmladdress{ $^{1}$ Max Planck Institute for Intelligent Systems,
 T\"{u}bingen, Germany\\
$^{2}$ Department of Computer Science, University of Hamburg, Germany}
%\icmladdress{Their Fantastic Institute}

% You may provide any keywords that you 
% find helpful for describing your paper; these are used to populate 
% the "keywords" metadata in the PDF but will not be shown in the document
\icmlkeywords{shortest path, nearest neighbor graph, density based distance, limit distance}
\vskip 0.2in
]

\begin{abstract} Consider a weighted or unweighted $k$-nearest
  neighbor graph that has been built on $n$ data points drawn randomly
  according to some density $p$ on $\R^d$. We study the convergence of
  the shortest path distance in such graphs as the sample size 
  tends to infinity.  We prove that for unweighted $\knn$ graphs, this
  distance converges to an unpleasant distance function on the
  underlying space whose properties are detrimental to machine
  learning. We also study the behavior of the shortest path distance in weighted
  $\knn$ graphs.  
\end{abstract} 

\section{Introduction}
\label{sec:int}
The shortest path distance is the most fundamental distance function between
vertices in a graph, and it is widely used in computer science and
machine learning. In this paper we want to understand the geometry
induced by the shortest path distance in
randomly generated geometric graphs like $k$-nearest neighbor graphs.

Consider a neighborhood graph $G$ built from an i.i.d. sample $X_1, ...,
X_n$ drawn according to some density $p$ on $ \Xcal \subset \R^d$ (for exact
definitions see Section \ref{sec:def}). Assume that the sample size $n$ goes to infinity. Two questions arise about the behavior of the shortest path distance between fixed points in this graph:

1. \textbf{Weight assignment:} Given a distance measure $D$
on $\Xcal$, how can we assign edge weights such that the 
shortest path distance in the graph converges to $D$? 

2. \textbf{Limit distance:} Given a function $h$ that assigns weights
of the form $h(\|X_i - X_j\|)$ to edges in $G$, what is the
limit of the shortest path distance in this weighted graph as $n \to \infty$?

%We ask the question whether the
%shortest path distance between fixed points in the graph converges to a
%meaningful distance on $\Xcal \subset \R^d$ as the sample size $n$ goes to infinity.

The first question has already been studied in some special
cases. \citet{TenSilLan00withproofs} discuss the case of $\eps$- and
$\knn$ graphs when $p$ is \textit{uniform} and $D$ is the geodesic
distance. \citet{Sajama2005} extend these results to $\eps$-graphs
from a general density $p$ by introducing edge weights that depend on an
explicit estimate of the underlying density. In a recent preprint, \citet{Hwang2012}
consider completely connected graphs whose vertices come from a
general density $p$ and whose edge weights  are powers
of distances. 

%In particular they assign edge weights depending on the Euclidean distance of the underlying points and an estimate of the density.
%In particular, they consider $\eps$-graphs where the edges have weights  
%The authors then show
%that the shortest path distance in this graph converges to a line
%integral in $\Xcal$ (see Section \ref{sec:def} for more details).  
%The results
%of both \citet{TenSilLan00withproofs} and \citet{Sajama2005} conform to the natural intuition in the sense that they prove a result that is not surprising. 

There is little work regarding
the second question. \citet{TenSilLan00withproofs} answer the question
for a very special case with $h(x)=x$ and uniform
$p$. \citet{Hwang2012} study the case $h(x)=x^a$, $a>1$ for arbitrary
density $p$.

We have a more general point of view.  In Section
\ref{sec:sp_weighted} we show that depending on properties of the
function $h(x)$, the shortest path distance operates in different
regimes, and we find the limit of the shortest path distance for
particular function classes of $h(x)$. Our method also reveals a
direct way to answer the first question without explicit density
estimation.

An interesting special case is the unweighted $\knn$ graph, which
corresponds to the constant weight function
$h(x)=1$. %We compare the shortest path distance in the unweighted and Euclidean weighted $\knn$-graphs. In particular we see that they measure completely different quantities.
We show that the shortest path distance on unweighted $\knn$-graphs
converges to a limit distance on $\Xcal$ that does {\em not} conform
to the natural intuition and induces a geometry on $\Xcal$ that can be
detrimental for machine learning applications.

%While $\eps$-graphs are appealing for theorists because of their
%mathematical simplicity, most machine learning practitioners prefer to
%use $\knn$ graphs  because they are much more
%robust.  
% This case is harder to analyze than
% $\eps$-graphs: points in low density regions are
% connected by ``longer'' edges than points in high density regions, and
% these random edge lengths have to be carried through all proofs. 
%We study the case of $k$-nearest neighbor graphs in Section \ref{sec:sp_unweighted}. 

Our results have implications for many machine learning algorithms,
see Section \ref{sec:conseq} for more discussion. (1) The shortest paths based
on unweighted $\knn$ graphs prefer to go through low density regions, and
they even accept large detours if this avoids passing through high
density regions (see Figure \ref{fig:path1} for an
illustration). This is exactly the opposite of what we would
like to achieve in most applications. %, and moreover this behavior is very unstable because
%the distance puts its focus on the low-density regions which are
%sparsely sampled.
%
(2) For manifold learning algorithms like Isomap, unweighted $\knn$
graphs introduce a
fundamental bias that leads to huge distortions in
the estimated manifold structure (see Figure \ref{fig:isomap_knn} for
an illustration). 
%Additionally to describing this phenomenon, NOTHING NEW.ISOMAP DO THE SAME
%we show how this behavior can be
%avoided by using particular edge weights in the $\knn$ graphs.
%
(3) In the area of semi-supervised learning, a standard approach is to
construct a graph on the  sample points, then compute
a distance between vertices of the graph, and finally use a standard
distance-based classifier % like the $k$-nearest neighbor classifier 
to label the unlabeled points (e.g., \citealp{Sajama2005} and \citealp{Bijral11}). 
The crucial property exploited in this
approach is that distances between points should be small if they are
in the same high-density region. Shortest path distances in unweighted
$\knn$ graphs and their limit distances do exactly the opposite, so
they can be misleading for this approach. 


%From a larger point of view, the results presented in this paper are
%one important step in a larger research programme. Our aim is to
%understand what type of graph preserves what kind of information about
%the density and geometry of the underlying data distribution. The
%convergence of the shortest path distance is an important piece in
%this puzzle. 

\begin{figure}[t]
\centering
\includegraphics[trim = 30mm 20mm 40mm 13mm, clip,
width=0.7\columnwidth,height=0.15\textheight]{figure/sp_gaussian.pdf}
\vspace{-10pt}
\caption{The shortest path based on an  unweighted (red) and Euclidean
  weighted (black) $\knn$ graph.}
\label{fig:path1}
\end{figure}

\begin{figure}
	\begin{minipage}{.49\linewidth}
		\includegraphics[width=\columnwidth]{figure/uniform_box.pdf}
	\end{minipage}
	\begin{minipage}{.49\linewidth}
		\includegraphics[width=\columnwidth]{figure/isomap_uniform_box.pdf}
	\end{minipage}
    \vspace{-10pt}
	\caption{Original data (left) and its Isomap
          reconstruction based on an unweighted $\knn$ graph (right).}
	\vspace{-10pt}
	\label{fig:isomap_knn}
\end{figure}


% \begin{figure*}[t]   
% 	\centerline
% 	{
% 		\subfigure[]{\includegraphics[trim = 30mm 20mm 40mm 13mm, clip, width=0.15\textwidth]{figure/sp_gaussian.pdf}}
% 		\hfill
% 		\subfigure[]{\includegraphics[width=0.35\textwidth]{figure/path_segment1.pdf}}
% 		\hfill
% 		\subfigure[]{\includegraphics[width=0.35\textwidth]{figure/path_segment2.pdf}} 
% 	}
% 	 \vspace{-10pt}
%   \caption{\textbf{a)} The shortest path in unweighted (red) and Euclidean weighted (black) $\knn$ graph.
% 	\textbf{b,c)} Path construction}
% 	 \vspace{-10pt}
%  \label{fig:path}
% \end{figure*}

\section{Basic definitions}
\label{sec:def}

%XXX I REALIZED THAT WE CANNOT CHOOSE X AS AN OPEN SET. THEN THE
%SHORTEST PATH DOES NOT NECESSARILY EXIST (BECAUSE THE SHORTEST PATH
%WOULD GO ALONG THE BOUNDARY). SO PLEASE THINK ABOUT A WAY TO STATE ALL
%STATEMENTS FOR A CLOSED SET. SOMETHING ALONG THE LINE THAT WE ONLY
%CONSIDER INTERIOR POINTS WHOSE SHORTEST PATH DOES NOT TOUCH THE
%BOUNDARY. 

Consider a closed, connected subset $\Xcal \subseteq \mathbb{R}^d$ that
is endowed with a density function $p$ with respect to the Lebesgue
measure. For the ease of presentation we assume for the rest of the
paper that the density $p$ is Lipschitz continuous with Lipschitz
constant $L$ and bounded away from $0$ by $p_{\min} > 0$. 
%WE CAN STATE THE THEOREM FOR  POINTS THAT THEIR SHORTEST PAST IS IN THE INTERIOR OF THE SET X.  CAN WE REMOVE ASSUMPTIONS FROM X, AND SAY THAT OUR THEOREM HOLDS FOR PAIR OF POINTS IN X THAT THEIR SHORTEST PATH IS INTERIOR? (BY INTERIOR I MEAN THAT THERE EXIST A GLOBAL EPSILON SUCH THAT EPSILON BALLS AROUND EACH POINT ON THE PATH IS COMPLETELY IN X )
%
%(DO WE  NEED
%CONNECTEDNESS OF X? PLEASE THINK ABOUT IT.  IT WOULD BE EASIER IF NOT. OTHERWISE WE MIGHT NEED MORE
%THAN CONNECTEDNESS, WE MIGHT NEED THAT THE $\SP$ACE IS CONNECTED ``NOT
%JUST BY A LINE'' BUT BY A SET OF A CERTAIN THIKNESS, BECAUSE LATER WE
%DO NOT WANT TO CONSIDER PATHS ON THE BOUNDARY) 
% 
To simplify
notation later on, we define the shorthand $q(x) := (p(x))^{1/d}$. % DO
%WE NEED Q OFTEN? IF NOT, I'D RATHER HAVE $p(x))^{1/d}$ INSTEAD


We will
consider different metrics on $\Xcal$.  A ball with respect to a
particular metric $D$ in $\Xcal$ will be written as $ B(x,r,D) :=
\{y \in \Xcal \mid D(x,y) \leq r \}$. We denote the Euclidean volume
of the unit ball in $\mathbb{R}^d$ by $\eta_d$.

Assume the finite dataset $X_1,...,X_n$ has been drawn i.i.d according
to $p$. We build a geometric graph $G = (V,E)$ that has the data
points as vertices and connects vertices that are close. Specifically,
for the $\knn$ graph we connect $X_i$ with $X_j$ if
$X_i$ is among the $k$ nearest neighbors of $X_j$ or vice versa. For
the $\epsilon$-graph, we connect $X_i$ and $X_j$ whenever their Euclidean
distance satisfies $\|X_i - X_j\| \leq \epsilon$. In this paper, all graphs
are undirected, but might carry edge weights $w_{ij} \geq 0$.  In
unweighted graphs, we define the length of a path by its number of
edges, in weighted graphs we define the length of a path by the sum of
the edge weights along the path. In both cases, the shortest path ($\SP$)
distance $D_{sp}(x,y)$ between two vertices $x,y \in V$ is  the
length of the shortest path connecting them. 

%To study the limit of the $\SP$ distance in $\knn$ graphs, we
%need to define corresponding distance functions on the underlying
%space $\Xcal$. 
Let $f$ be a positive continuous scalar function defined on
$\Xcal$. For a given path $\gamma$ in $\Xcal$ that connects
$x$ with $y$ and is parameterized by $t$, we define the
$f$-length of the path as
\[
D_{f,\gamma} = \int_{\gamma}{f(\gamma(t))|\gamma'(t)| dt}.
\]
This expression is also known as the \textit{line integral} along $\gamma$ with
respect to $f$. The $f$-geodesic path between $x$ and $y$ is the path
with minimum $f$-length. 




The $f$-length of the geodesic path is called the $f$-distance
between $x$ and $y$. We denote it by $D_{f}(x,y)$. If $f(x)$ is a
function of the density $p$ at $x$, then the $f$-distance is sometimes called
a {density based distance} \cite{Sajama2005}. %Such distances have
%been considered several times in the machine learning literature (see \citet{BouChaHei03} and \citet{Bijral11}). 

%PLEASE USE THE NATBIB CITATION STYLE WE ALWAYS HAD IN THE OTHER PAPERS
%AS WELL. 

The $f$-distance on $\Xcal$ is a metric, and
in particular it satisfies the
triangle inequality. Another useful property is that for a
point $u$ on the $f$-geodesic path between $x$ and $y$ we have
$D_f(x,y)=D_f(x,u)+D_f(u,y)$.

The function $f$ determines the behavior of the $f$-distance. When
$f(x)$ is a monotonically decreasing function of density $p(x)$,
passing through a high density region will cost less than passing
through a low density region. It works the other way round when $f$ is a monotonically increasing function of density. %The $f$-geodesic path will prefer passing through high(low) density regions based on the gradient of $f$. 
A constant function does not impose any preference between low and high density regions.%, so the Riemannian geodesic path is the preferred one.





The main purpose of this paper is to study the relationship between the $\SP$ distance in various geometric graphs and particular
$f$-distances on $\Xcal$. For example, in Section
\ref{sec:sp_unweighted} we show that the $\SP$ distance in unweighted
$\knn$ graphs converges to the $f$-distance with $f(x)
= p(x)^{1/d}$.


In the rest of the paper, all statements refer to points
$x$ and $y$ in the interior of $\Xcal$ such that their $f$-geodesic
path is bounded away from the boundary of $\Xcal$. 
%We avoid boundary effects by stating all proposition for interior points of $\Xcal$ which their $f$-geodesic path exists and does not touch the boundary of $\Xcal$.
%Note that under the given assumptions such a
%minimal path always exists IN FACT, CAN YOU CHECK WHETHER WE NEED
%ASSUMPTIONS ON $f$ FOR THIS?  IT LOOKS THAT POSITIVITY AND CONTINUITY SHOULD BE ENOUGH


% To be able to predict the behavior of the shortest path distance on
% geometric graphs, we need to require certain regularity conditions of
% the graphs. Note
% that the closeness is defined with respect to the $f$-distance and not
% the usual Euclidean distance.

%We assume that our graph holds the following assumptions. These assumptions are stated for a general metric $f$ and we will show in the Section \ref{sec:sp_unweighted} that in $\knn$ graphs, by choosing an appropriate $f$ these assumptions will hold with high probability.

% I REMOVED THE FAMILY OF GRAPHS IN THE ASSUMPTIONS, IT IS NOT NECESSARY
% HERE. DO THESE ASSUMPTIONS ONLY HOLD FOR KNN GRAPHS OR ALSO FOR
% R-GRAPHS? IN THE FIRST CASE, REPLACE ``GEOMETRIC GRAPH'' BY KNN
% GRAPHS. IN THE SECOND CASE, $K$ IS NOT DEFINED. WE ALSO NEED THESE
% ASSUMPTIONS FOR WEIGHTED GRAPHS, DO WE? 

% IN FACT, I THINK THAT THESE THINGS ARE NOT ASSUMPTIONS, THEY ARE
% DEFINITIONS. WE CAN {\bf DEFINE} $r_{low}$ AND $r_{up}$ IN ANY GRAPH, AND WE
% CAN ALSO DEFINE $EPS$. {\bf MY SUGGESTION IS:  MOVE WHAT HAS BEEN THE
%   GENERAL ASSUMPTIONS AFTER THEOREM 1, AND MAKE IT A DEFINITION. } 
% {\em
% \textbf{General assumptions on the graph}: Consider an  geometric graph
% $G_n$ which is based on $X_1, ..., X_n \in \Xcal \subset
% \mathbb{R}^d$. 
% We assume that there exist $\epsilon, r_{low}, r_{up} > 0$ 
% (depending on $k$, $n$ and $d$) 
% such that the following statements about $G_n$ 
% hold: 


% \begin{description}
% \item[Ga1] (Connectedness) A vertex $x$ is connected to $v$ if  $D_f(x,v) \leq r_{low}$. 
% PLEASE DON'T MIX NOTATIONS. I SUGGEST TO CALL ALL VERTICES BY X AND Y
% AND NOT BY V ... (HERE AND IN OTHER PLACES)
% \item[Ga2] (Disconnectedness) A vertex $x$ is not connected to any vertex $v$ with $D_f(x,v) > r_{up}$. 
% \item[Ga3] (Dense sampling) There exist an $\epsilon<r_{low}/2$ such that
%   for any point $m \in \Xcal$, there exist a sample point $x \in \{X_1,
%   ..., X_n\}$ such that $D_f(m,x) \leq \varsigma$. SIMILARLY HERE. PLEASE NEVER
%   CALL A POINT M, M IS USED FOR INTEGERS ... USE Z FOR EXAMPLE. 

% \end{description}
% }

\section{Shortest paths in unweighted graphs}
\label{sec:sp_unweighted}

In this section we study the behavior of the shortest path distance in the family of \textit{unweighted} $\knn$ graphs. %Access to more samples will increase the shortest path distance. 
%Getting a convergence result on unweighted $\SP$ distance will need a proper normalization. 
We show that the rescaled graph $\SP$ distance converges to the $q$-distance in the original space $\Xcal$.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}[$\SP$ limit in unweighted $\knn$ graphs]
\label{th:main} Consider the unweighted $\knn$ graph $G_n$ based on the
i.i.d. sample $X_1, ..., X_n \in \Xcal$ from the density $p$. Choose $\lambda$ and $a$ such that 
\[
\lambda \geq \frac{4 L}{\eta_d^{1/d} p_{\min}^{1+1/d} } \Big(\frac{k}{n}\Big)^{1/d} 
\; , \;
a < 1 - \log_{k}\Big( 4^d(1+\lambda)^2 \Big).
\]
Fix two points $x=X_i$ and $y=X_j$. 
Then there exist $e_1(\lambda, k)$,$e_2(\lambda, k, n)$,$e_3(\lambda)$ (see below for explicit definitions) such that with probability at least $1 - 3 e_3 n\exp(-\lambda^2 k^a/6) $
we have 
\[
e_1 D_q(x,y)
\leq 
e_2 D_{sp}(x,y) 
\leq
 D_q(x,y) - e_2.
\]
Moreover if $n\to \infty$, $k\to \infty$, $k/n \rightarrow 0$, $\lambda \rightarrow 0 $ and
$\lambda^2 k^a / \log(n)  \rightarrow \infty$, then the probability converges to $1$ and $(k / (\eta_d n ))^{1/d} D_{sp}(x,y) $ converges to $D_q(x,y)$ in probability.
\end{theorem}

The convergence conditions on $n$ and $k$ are the ones to be expected for random
geometric graphs. The condition $\lambda^2 k^a / \log(n)  \rightarrow
\infty$ is slightly stronger than the usual $k / \log(n)  \rightarrow
\infty$ condition. This condition is satisfied as soon as $k$ is of
the order a bit larger than $\log(n)$. For example $k \approx \log(n)^{1+\alpha}$ with a small $\alpha$ will work. For $k$ smaller
than $\log(n)$, the graphs are not connected anyway (see e.g. \citealp{Penrose99}) and are unsuitable for machine learning applications.

Before proving  Theorem \ref{th:main}, we need to state a couple of
propositions and lemmas. We start by introducing some ad-hoc notation:

\begin{definition} {\bf (Connectivity parameters)}
\label{def:connectivity} Consider a geometric graph based on a fixed set of points $X_1, ...,
X_n \in \R^d$. Let $r_{low}$
be a real number such that $D_f(X_i,X_j) \leq r_{low}$
implies that $X_i$ is connected to $X_j$ in the graph. Analogously, consider $r_{up}$ to be a real number such that $D_f(X_i,X_j) \geq r_{up}$ implies that  $X_i$ is not connected to $X_j$ in the graph. 
%Finally, let $\eps >0 $ be any real number such that for all $x \in \Xcal$ there exists an $y \in \{X_1, ..., X_n\}$ such that $D_f(x,y) \leq \eps$. 
\end{definition}
%The definition of connectivity parameter $r_{low}$ allows choosing arbitrary small values. It is desired for a graph to having vertices in all regions of the space. For a graph holding the dense sampling assumption, there exist a vertex in ball $B(x,\varsigma,D_f)$ for all $x \in \Xcal$. Moreover it 
\begin{definition}{\bf (Dense sampling assumption)}
Consider a graph $G$ with connectivity parameters $r_{low}$ and
$r_{up}$. We say that it satisfies the dense sampling assumption if there exists an $\varsigma<r_{low}/4$ such that for all $x \in \Xcal$ there exists a vertex $y$ in the graph with $D_f(x,y) \leq \varsigma$.
\end{definition}
% First we show that the length of graph
% shortest path between two points can be upper and lower bounded by their $f$-distance. The next step is to show that in a geometric $\knn$ graph from density $p$, our General assumptions hold with high probability with respect to the $q$-distance ($q(x) = p(x)^{1/d}$).
\begin{proposition}[Bounding $D_{sp}$ by $D_f$]
\label{pr:unweighted_sp} Consider any unweighted geometric graph based on
a fixed set 
$X_1, ..., X_n \in \Xcal \subset \mathbb{R}^d$ that satisfies the dense sampling assumption. Fix two vertices $x$ and $y$ of the graph and set 
\[
e_1 = (r_{low}-2\varsigma)/{r_{up}} 
\; \; , \; \;  
e_2 = r_{low}-2\varsigma.
\]
 Then the following statement holds: 
\[
e_1 D_f(x,y)
\leq 
e_2 D_{sp}(x,y) 
\leq
 D_f(x,y) - e_2.
\]
\end{proposition}

\begin{figure}[t]
\begin{center}\includegraphics[width=0.35\textwidth]{figure/path_segment1.pdf}
\includegraphics[width=0.35\textwidth]{figure/path_segment2.pdf}
\end{center}
\caption{Path constructions in the proofs of
  Proposition~\ref{pr:unweighted_sp} (top) and Theorem
  \ref{th:weighted} (bottom). }
\label{fig:pathconstruction}
\end{figure}


\begin{proof} \emph{Right hand side}. Consider the $f$-geodesic path $\gamma^*_{x,y}$ connecting $x$ to $y$.
Divide $\gamma^*_{x,y}$ to segments by $u_0 = x, u_1,...,u_{t},u_{t+1}=y$ such that $D_f(u_i,u_{i+1})=r_{low}-2\varsigma$ for $i=0,...,t-1$ and $D_f(u_{t},u_{t+1}) \leq r_{low}-2\varsigma$ (see Figure \ref{fig:pathconstruction}). 
Because of the dense sampling assumption, for all $i=1, ..., t$ there
exists a vertex $v_i$ in the ball $B(u_i,\varsigma; D_f)$ and we have
\begin{eqnarray*}
D_f(v_i,u_i) & \leq & \varsigma \\
D_f(u_i,u_{i+1}) & \leq &  r_{low} - 2\varsigma \\
D_f(u_{i+1},v_{i+1}) & \leq & \varsigma.
\end{eqnarray*}
Applying the triangle inequality gives $D_f(v_i,v_{i+1}) \leq r_{low}$, which shows that $v_i$ and $v_{i+1}$ are connected.
By summing up along the path we get
\begin{eqnarray*}
(r_{low}-2\varsigma) (D_{sp}(x,y)-1) & \leq & (r_{low}-2\varsigma) t \\
 =  \sum_{i=0}^{t-1}{D_f(u_i,u_{i+1})}  & \overset{(a)}{\leq} & D_f(x,y).
\end{eqnarray*}
In step (a) we use the simple fact that if $u$ is on the $f$-geodesic path from $x$ to $y$, then
\[
D_f(x,y) = D_f(x,u) + D_f(u,y).
\]
\emph{Left hand side.} Assume that the graph $\SP$ between $x$ and $y$
consists of vertices $z_0=x,z_1,...,z_s=y$. By $D_f(z_i,z_{i+1}) \leq r_{up}$ we can write
\begin{eqnarray*}
(r_{low}-2\varsigma) D_{sp}(x,y) 
 & \geq & \frac{r_{low}-2\varsigma}{r_{up}}  \textstyle{\sum_{i=0}^{s-1}{D_f(z_i,z_{i+1})}} \\
 & \geq & \frac{r_{low}-2\varsigma}{r_{up}} D_f(x,y).
\end{eqnarray*}
\end{proof} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The next lemma uses the Lipschitz continuity and boundedness of $p$ to
show that $q(x)\|x-y\|$ is a good  approximation of $D_q(x,y)$ in
small intervals. 

\begin{lemma}[Approximating $D_q$ in small balls]
%\label{lem:cont}
\label{lem:approx}
Consider any given $\lambda <1$. If $\|x-y\| \leq p_{\min}\lambda /L$ then
the following statements hold: 

1. We can approximate $p(y)$ by the density at $x$: 
\[
p(y)(1-\lambda) \leq p(x) \leq p(y)(1+\lambda).
\]
2. We can approximate $D_q(x,y)$ by $q(x)\|x-y\|$: 
\[
 (1-\lambda)^{1/d}  q(x)\|x-y\|
 \leq
 D_q(x,y)
 \leq
 (1+\lambda)^{1/d} q(x)\|x-y\|.
\]
\end{lemma}
\begin{proof} \textit{Part (1).}
By the Lipschitz continuity of $p$ for $\|x-y\| \leq \delta$ we have
\[
|p(x)-p(y)| \leq L \|x-y\| \leq L \delta.
\]
Setting $\delta = \lambda p_{\min} /L$ leads to  the result. 

\textit{Part (2).}
The previous part can be written as
\[
 (1-\lambda)^{1/d} q(x) 
 \leq
 q(y) 
 \leq
 (1+\lambda)^{1/d} q(x).
\]
Denote the $q$-geodesic path between $x$ and $y$ by $\gamma^*$ and the
line segment connecting $x$ to $y$ by $l$. Using the definition of a $q$-geodesic path, we can write
\begin{eqnarray*}
\int_{\gamma^*}{q(\gamma^*(t))}|\gamma^*(t)'|dt
 & \leq &
\int_{l}{q(l(t))}|l(t)'|dt  \leq \\
 (1+\lambda)^{1/d} \int_{l}{q(x)}|l(t)'|dt
  & = &
(1+\lambda)^{1/d}q(x)\|x-y\|.
\end{eqnarray*}
Also, 
\begin{eqnarray*}
\int_{\gamma^*}{q(\gamma^*(t))}|\gamma^*(t)'|dt
 & \geq &
(1-\lambda)^{1/d} \int_{\gamma^*}{q(x)}|\gamma^*(t)'|dt \\
 & \geq &
(1-\lambda)^{1/d}q(x)\|x-y\|.
\end{eqnarray*}
\end{proof}

Now we are going to show how the quantities $r_{low}$ and $r_{up}$ introduced
in Definition \ref{def:connectivity} can be bounded in random unweighted $\knn$ graphs
and how they are related to the metric $D_q$. 

To this end, we define
the  $\knn$ $q$-radii at vertex $x$ as $R_{q,k}(x) = D_q(x,y)$
and the approximated $\knn$ $q$-radii at vertex $x$ as 
$\hat{R}_{q,k}(x) = q(x) \|x - y \|$,
where $y$ is the $k$-nearest neighbor of $x$. 
The minimum and maximum values of  $\knn$ $q$-radii are defined as 
\[
R_{q,k}^{min}=\min_{u}{R_{q,k}(u)} \; \; , \; \; R_{q,k}^{max}=\max_{u}{R_{q,k}(u)}.
\]
Accordingly we define $\hat{R}_{q,k}^{min}$ and $\hat{R}_{p,k}^{max}$ for the approximated $q$-radii. 

The following proposition is a direct adaptation of Proposition 31 from \citet{LuxRadHei10_arxiv}. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proposition}[Bounding $R_{p,k}^{min}$ and $R_{p,k}^{max}$]
\label{pr:r_low}
Given $\lambda <1/2$ define $r_{low}$ and $r_{up}$ as 
\begin{equation*}
r_{low}:=
\Big(\frac{k}{(1+\lambda) n \eta_d}\Big)^{1/d}  \;\; , \;\;
r_{up}:=
\Big(\frac{k}{(1-\lambda) n \eta_d}\Big)^{1/d}
\end{equation*}

and radius $\hat{r}_{low}$ and $\hat{r}_{up}$ as
\[
\hat{r}_{low} = \frac{r_{low}}{(1+\lambda)^{1/d}}  \;\; , \;\;
\hat{r}_{up} =  \frac{r_{up}}{(1-\lambda)^{1/d} } .
\]
Assume that $\hat{r}_{up} \leq \lambda p_{\min}^{1+1/d}/L $. Then
\begin{eqnarray*}
P\Big(R_{p,k}^{min} \leq r_{low} \Big) \leq n\exp(-\lambda^2 k/6) \\
P\Big(R_{p,k}^{max} \geq r_{up} \Big) \leq n\exp(-\lambda^2 k/6).
\end{eqnarray*}
\end{proposition} 

\begin{proof} 
Consider a ball $B_x$ with radius $\hat{r}_{low}/q(x)$ around $x$. Note that $\hat{r}_{low}/q(x) \leq p_{\min} \lambda /L$ , so we can bound the density of points in $B_x$ by $(1+\lambda) p(x)$ using Lemma \ref{lem:approx}. Denote the probability mass of the ball by $\mu(x)$, which is bounded by
\begin{eqnarray*}
\mu(x) = \int_{B_x}{p(s) ds}
& \leq &
(1+\lambda) p(x)  \int_{B_x}{ds} \\
& = & 
(1+\lambda) \hat{r}_{low}^d \eta_d =: \mu_{\max}.
\end{eqnarray*}

Observe that $\hat{R}_{q,k}(x)\leq \hat{r}_{low}$ if and only if there are at least $k$ data points in $B_x$. Let $Q \sim Binomial(n,\mu(x))$ and $S \sim Binomial(n,\mu_{\max})$. By the choice of $\hat{r}_{low}$ we have $E(S)=k/(1+\lambda)$. It follows that
\begin{eqnarray*}
P\Big(\hat{R}_{q,k}(x) \leq \hat{r}_{low} \Big) & = & P\Big(Q \geq k \Big) \leq P\Big(S \geq k \Big) \\
& = & P\Big(S \geq (1+\lambda)E(S) \Big).
\end{eqnarray*}
Now we apply a concentration inequality for binomial random
variables (see Prop. 28 in \citealp{LuxRadHei10_arxiv}) and a union bound to get
\begin{eqnarray*}
P\Big(\hat{R}_{q,k}^{min} \leq \hat{r}_{low} \Big) %a \Big(\frac{k}{n}\Big)^{1/d} \Big) 
& \leq & 
P\Big(\exists i \; : \; \hat{R}_{q,k}(X_i) \leq \hat{r}_{low} \Big) \\
& \leq &
n\exp \Big(\frac{-\lambda^2 k}{3(1+\lambda)}\Big) \\
& \leq &
n\exp ({-\lambda^2 k}/6). 
\end{eqnarray*}
By a similar argument we can prove the analogous statement for $R_{p,k}^{max}$.
Finally,  Lemma \ref{lem:approx} gives 
\begin{eqnarray*}
\hat{R}_{q,k}^{min} \geq \frac{R_{q,k}^{min}}{(1+\lambda)^{1/d}}  \;,\; 
\hat{R}_{q,k}^{max} \leq \frac{R_{q,k}^{max}}{(1-\lambda)^{1/d}} .
\end{eqnarray*}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The following proposition shows how the sampling parameter $\varsigma$ can be
chosen to satisfy the dense sampling assumption. Note that we decided to choose $\varsigma$ in a form 
that keeps the statements in Theorem \ref{th:main} simple, rather than optimizing
over the parameter $\varsigma$ to maximize the probability of success. 

% For the assumption $[Ga3]$ we suggest an $\varsigma$ that make the assumption hold with high probability. We choose the $\varsigma$ in a way that keeps the final result simple. One can tighten the probability bound by choosing $\varsigma$ appropriately.

\begin{lemma}[Sampling lemma]
\label{lem:sampling}
Assume $X_1,...,X_n$ are sampled i.i.d. from a probability
distribution $p$ and a constant $a<1$ is given. Set $\lambda$ as in Theorem \ref{th:main}, 
\[
\varsigma := (1+\lambda)^{1/d} \Big( \frac{k^a}{\eta_d n }
\Big)^{1/d}, 
\]
and $e_3(\lambda) := 2^d/(1-\lambda)^2$. Then with probability at least $1- e_3 n \exp(-k^a /6)$, for every $x \in \Xcal$ exists a $y \in X_1,...,X_n$ such that $D_q(x,y)\leq \varsigma$.
\end{lemma}

%AS FAR AS I CAN SEE YOU DID NOT EXPLICITLY DEFINE $e_3?$ 

\begin{proof}
Define $\varsigma_0 =  (1+\lambda)^{-1/d} \varsigma $. We prove that  for every $x \in \Xcal$, there exist a vertex $y$ such that $q(x)\|x-y\| \leq \varsigma_0$. Then using Lemma \ref{lem:approx} will give the result.
 
The proof idea is a generalization of the covering argument in the
proof of the {sampling lemma} in \citet{TenSilLan00withproofs}. 
We first construct a covering of $\Xcal$ that consists of balls with approximately the same probability
mass. The centers of the balls are chosen by an iterative procedure that
ensures that no center is contained in any of the balls we have so
far. We choose the radius $\varsigma_0 / q(x)$ for the ball at point $x$ and call it $B_q(x,\varsigma_0)$. The probability mass of this ball can be bounded by
\[
\mathcal{V}(B_q(x,\varsigma_0)) \geq (1-\lambda) \varsigma_0^d \eta_d %= (1-\lambda) \frac{\sqrt{k} }{ n } 
\]
Note that smaller balls $B_q(u,(1-\lambda)^{1/d}\varsigma_0/2)$ are
all disjoint. To see this, consider two balls
$B_q(x,(1-\lambda)^{1/d}\varsigma_0/2)$,
$B_q(y,(1-\lambda)^{1/d}\varsigma_0/2)$. Observe that 
\[
\frac{(1-\lambda)^{1/d}\varsigma_0}{2q(x)}+\frac{(1-\lambda)^{1/d}\varsigma_0}{2q(y)}
\leq
\frac{\varsigma_0}{q(x)}.
\]
We can bound the total number of balls by
\[
S \leq \frac{1}{\mathcal{V}(B_q(x,(1-\lambda)^{1/d}\varsigma_0/2))} 
\leq
\frac{2^d}{\eta_d(1-\lambda)^2 \varsigma_0^{d}}.
\]
Now we sample points from the underlying space and apply the same concentration inequality as above. We bound the probability that a ball $B_q(u,\varsigma_0)$ does not contain any
sample point (``is empty'') by %($\delta=1$)
\[
Pr(\text{Ball }i\text{ is empty}) 
\leq
\exp(-n \varsigma_0^d \eta_d /6).
\]
Rewriting and Substituting the value of $\varsigma_0$ gives 
\ba
& Pr(\text{no ball is empty}) 
%=
%1 - Pr(\text{no ball }B_i\text{ is empty}) 
\;\; \geq \;\; 
1-\textstyle{\sum_i}{Pr(B_i\text{ is empty})} \\
& \geq 
1-S \cdot e^{-n \varsigma_0^d \eta_d /6} 
\;\; \geq \;\; 
1- \frac{2^d n e^{-k^a /6}}{(1-\lambda)^2 k^a} \\
&  \geq 
1- \frac{2^d n e^{-k^a /6}}{(1-\lambda)^2} 
\;\; = \;\;
1- e_3 n e^{-k^a /6}.
\ea
\vspace{-3pt}
\end{proof}
%Now we have enough material to prove Theorem \ref{th:main}.
%
%SOMEWHERE WE EXPLICITYL HAVE TO STATE THE RELATIONSHIP
%BETWEEN EPS AND $r_{up}$ WE USED TO HAVE IN THE GENERAL ASSUMPTIONS. 

\textbf{Proof of Theorem \ref{th:main}.}
Set $r_{low}$ and $r_{up}$ as in Proposition \ref{pr:r_low}. The assumption on $\lambda $ ensures that $\hat{r}_{up} \leq \lambda p_{\min}^{1+1/d}/L $. It follows from Proposition
\ref{pr:r_low} that the statements about $r_{low}$ and $r_{up}$ in
Definition \ref{def:connectivity} both hold for $G_n$  with probability at least $\mu_1 = 1- 2n\exp(-\lambda^2 k/6)$.  
Set $\varsigma$ as in Lemma \ref{lem:sampling} and define the constant 
$a < 1 - \log_{k}\Big( 4^d(1+\lambda)^2 \Big).$
By this choice we have $r_{low} > 4\varsigma $. Lemma \ref{lem:sampling} shows that the
sampling assumption holds in $G_n$ for the selected $\varsigma$  with probability at least
$\mu_2 = 1- e_3 n \exp(-k^a /6)$.
Together, all these statements about $G_n$ hold with probability at least $\mu := 1 - 3 e_3 n\exp(-\lambda^2 k^a/6)$. 

Using Proposition \ref{pr:unweighted_sp} completes the first part of the theorem. 
For the convergence we have
\[
e_1 = \frac{r_{low} - 2\varsigma}{r_{up}} = \Big(\frac{1-\lambda}{1+\lambda} \Big)^{1/d} - 2 \Big(\frac{1-\lambda^2}{k^{1-a}} \Big)^{1/d}.
\]
This shows that $e_1 \rightarrow 1$ as $\lambda \rightarrow 0$ and $k \rightarrow \infty$. For $\lambda \rightarrow 0$ and $k \rightarrow \infty$ we can set $a$ to any constant smaller than $1$. Finally it is easy to check that $e_2 \rightarrow 0$ and $\varsigma / r_{low} \rightarrow 0$.
\ulesqed


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Shortest paths in weighted graphs}
\label{sec:sp_weighted}

In this section we discuss both questions from the Introduction. We
also extend our results from the previous section to weighted $\knn$ graphs and $\eps$-graphs.

\subsection{Weight assignment problem}
\label{subsec:weight_ass_problem}

%In the weight assignment problem we are given a scalar function $f:\Xcal \rightarrow \mathbb{R}$ and we want to assign edge weights such that the $\SP$ distance converges to $f$-distance. 
%In the previous section we talked about the shortest path distance in unweighted $\knn$ graphs. In machine learning it is very usual to use weights on the edges of the graph. Gaussian kernel and Euclidean length of an edge are two common weightings methods. %In the latter they weight the edge between $x$ and $y$ by $exp(\|x-y\|^2)/\sigma$ where the parameter $\sigma$ is the width of the Gaussian. 
Consider a graph based on the i.i.d.\ sample $X_1, ..., X_n \in \Xcal$
from the density $p$. We are given a positive scalar function $f$ which is only
a function of the density: $f(x) = \tilde{f}(p(x))$.
%Moreover the following integral is finite:
%\[
%\varphi = \int_{\Xcal} f(x)^d dx.
%\]
We want to assign edge weights such that the graph $\SP$ distance converges to the $f$-distance in $\Xcal$. 

It is well known that the $f$-length of a curve $\gamma : [a,b]
\rightarrow \Xcal$ can be approximated by a Riemann sum over a partition of $[a,b]$ to subintervals $[x_i,x_{i+1}]$:  
\[
\textstyle{\hat{D}_{f,\gamma} = \sum_i{f\Big(\frac{\gamma(x_{i})+\gamma(x_{i+1})}{2} \Big) \|\gamma(x_{i})-\gamma(x_{i+1})\|}}.
\]
As the partition gets finer, the approximation $\hat{D}_{f,\gamma}$ converges to $D_{f,\gamma}$ (cf. Chapter 3 of \citealp{Gamelin2001}). This suggests using edge weights 
\[
w_{ij} = \tilde{f}\textstyle{\Big(p(\frac{X_i+X_j}{2})\Big)}\|X_i - X_j\|. 
\]
However the underlying density $p(x)$ is not known in many machine learning
applications. \citet{Sajama2005} already proved that the plug-in approach using
a  kernel density estimator $\hat p(x)$ for $p(x)$ will lead to
the convergence of the $\SP$ distance to $f$-distance in
$\eps$-graphs. Our next result hows how to choose edge weights in
$\knn$ graphs without estimating the density. It is a corollary from a
theorem that will be presented in Section \ref{ssec-limit}. 

We use a notational convention to simplify our arguments and hide
approximation factors that will eventually go to $1$ as the sample
size goes to infinity. We say that $f$ is approximately larger than
$g$ ($f \succcurlyeq_{\lambda}  g$) if there exists a function $e(\lambda)$ such that $f \geq e(\lambda) g$ and $e(\lambda) \rightarrow 1$ as $n \rightarrow \infty$ and $\lambda \rightarrow 0$. The symbol $\preccurlyeq_{\lambda}$ is defined similarly. We use the notation $f \approx_{\lambda} g$ if $f \preccurlyeq_{\lambda} g$ and $f \succcurlyeq_{\lambda}  g$.
%\citet{Bijral11} suggest using an approximation based estimator for $p(x)$, but there is no guaranty for the convergence.
\begin{corollary}
\label{th:edge_weights}
{\bf (Weight assignment)} 
Consider the $\knn$ graph based on the i.i.d. sample $X_1,
..., X_n \in \Xcal$ from the density $p$. Let $f$ be of the form $f(x) = \tilde{f}(p(x))$ with $\tilde{f}$ increasing. We assume that $\tilde{f}$ is Lipschitz continuous and $f$ is bounded away from 0. Define $r = (k/(n \eta_d))^{1/d}$ and set the edge weights
\vspace{-4pt}
\begin{equation}
\label{eq:weight_w}
w_{ij} = \|X_i - X_j\| \tilde{f}\Big(\frac{r^d}{\|X_i - X_j\|^d}\Big).
\end{equation}
Fix two points $x=X_i$ and $y = X_j$. Choose $\lambda$ and $a$ as in
Theorem \ref{th:weighted}. 
Then with probability at least 
$1 - 3 e_3 n\exp(-\lambda^2 k^a/6)$
we have $D_{sp}(x,y)\approx_{\lambda} D_f(x,y)$.
\end{corollary}
\vspace{-8pt}



%We define the length of the graph path $\pi : X_{i_1},...,X_{i_t}$ as
%
%Accordingly we can define the weighted shortest path between $x$ and $y$ as the path with minimum length and denote its length by $\hat{d}_{f}(x,y)$.
%
%Now consider a curve $\gamma$ connecting $x$ to $y$ in the space
%$\Xcal$. By a similar approach as in the last section, we can
%show there exist a path $\hat{\gamma} = u_1,...,u_t$ in the graph
%$G_n$ which $\hat{d}_{f,\hat{\gamma}}$ approximates
%$d_{f,\gamma}$. Assume that also the General assumptions XXX hold in our graphs. Then it is straightforward to show that for a fixed $x$ and $y$, $\hat{d}_{f}(x,y)$ will also converge to $d_{f}(x,y)$.

%XXXX Note that as opposed to the last section, we do not need any dense sampling
%assumptions for this to hold. 

\subsection{Limit distance problem} \label{ssec-limit}
Consider a weighted graph based on the i.i.d. sample $X_1, ..., X_n
\in \Xcal$ from the density $p$. We are given a increasing
edge weight function $h:\mathbb{R}^{+}\rightarrow \mathbb{R}^{+}$ which
assigns weight $h(\|x-y\|)$ to the edge $(x,y)$. We are interested in
finding the limit of the graph $\SP$ distance with respect to edge
weight function $h$ as the sample size goes to infinity. In particular
we are looking for a distance function $f$ such that the $\SP$
distance converges to the $f$-distance.
%We expect longer edges to have larger weights(distances). This implies that the function $h$ should be a positive increasing function. The task is to find $f$ such that the $\SP$ distance converges to $f$-distance. 

Assume we knew the solution $f^*=\tilde{f^*}(p(x))$ of this
problem. To guarantee the convergence of the distances, $f^*$ should
assign weights of the form of $w_{ij} \approx
\tilde{f^*}(p(X_i))\|X_i-X_j\|$. This would mean 
\[
 \tilde{f^*}(p(X_i))  \approx \frac{h(\|X_i-X_j\|)}{\|X_i-X_j\|}, 
\]
which shows that determining $\tilde{f^*}$ is closely related to finding a density based estimation for $\|X_i-X_j\|$.

Depending on $h$, we distinguish two regimes for this problem:
subadditive and superadditive. 




\subsubsection{Subadditive weights}
A function $h(x)$ is called subadditive if $\forall x,y\geq 0 :
h(x)+h(y)\geq h(x+y)$. Common examples of subadditive functions are
$f(x)=x^a$, $a<1$ and $f(x)=xe^{-x}$. For a subadditive $h$, the $\SP$ in the graph will satisfy the
triangle inequality and it will prefer jumping along distant
vertices. Based on this intuition, we come up with the following guess for vertices along the $\SP$: For $\epsilon$-graphs we have the approximation $\|X_i-X_j\| \approx \epsilon$ and $f(x)=h(\epsilon)/\epsilon$. For $\knn$-graphs we have $\|X_i-X_j\| \approx r/q(X_i)$ with $r = (k/(n \eta_d))^{1/d}$ and 
\vspace{-6pt}
\begin{equation*}
\label{eq:f_h}
f(x)=h(\frac{r}{q(x)}) \frac{q(x)}{r} \; , \; \tilde{f}(x)=h(\frac{r}{x^{1/d}}) \frac{x^{1/d}}{r}.
\vspace{-4pt}
\end{equation*}
We formally prove this statement for $\knn$ graphs in the next theorem. In contrast to Theorem \ref{th:main}, the scaling factor is moved into $f$. The
proof for $\epsilon$-graphs is much simpler and can be adapted by
setting $r = \epsilon$, $q(x)=1$, and $r_{low}=r_{up} = \epsilon$.

\vspace{-5pt}
\begin{theorem}[Limit of $\SP$ in weighted graphs]
\label{th:weighted}
Consider the $\knn$ graph based on the i.i.d. sample $X_1,
..., X_n \in \Xcal$ from the density $p$. Let $h$ be an increasing, Lipschitz continuous and subadditive function, and define the edge weights $w_{ij} = h(\|X_i-X_j\|)$. Fix two points $x=X_i$ and $y=X_j$. Define $r = (k/(n \eta_d))^{1/d}$ and set
\vspace{-5pt}
\[
f(x)=h(\frac{r}{q(x)}) \frac{q(x)}{r}.
\]
Choose $\lambda$ and $a$ such that 
\[
\lambda \geq \frac{4 L}{\eta_d^{1/d} p_{\min}^{1+1/d} } \Big(\frac{k}{n}\Big)^{1/d}
\; , \;
a < 1 - \log_{k}\Big( 4^d(1+\lambda)^2 \Big).
\]
Then with probability at least 
$1 - 3 e_3 n\exp(-\lambda^2 k^a/6)$
we have $D_{sp}(x,y)\approx_{\lambda} D_f(x,y)$.
\end{theorem}

\begin{proof}
The essence of the proof is similar to the one in Theorem
\ref{th:main}, we present a sketch only.  
The main step is to adapt Proposition \ref{pr:unweighted_sp} to
weighted graphs with weight function $h$. Adapting Lemma
\ref{lem:approx} for general $f$ is straightforward. The lemma states
that $D_f(x,y)\approx_{\lambda} f(x)\|x-y\|$ for nearby points. We set
$r_{low}$ and $\varsigma$ as in the sampling lemma and Proposition
\ref{pr:r_low} (these are properties of $\knn$ graphs and hold for any $f$). Proposition \ref{pr:r_low} says that in $\knn$ graphs, $x$ is connected to $y$ with high probability iff $\|x-y\| \preccurlyeq_{\lambda} r/q(x)$. The probabilistic argument and the criteria on choosing $\lambda$ are similar to Theorem \ref{th:main}.  

First we show that $D_{sp}(x,y) \preccurlyeq_{\lambda} D_f(x,y)$. 
Consider the $f$-geodesic path $\gamma^*_{x,y}$ connecting $x$ to $y$.
Divide $\gamma^*_{x,y}$ into segments $u_0 = x, u_1,...,u_{t},u_{t+1}=y$ such that $D_q(u_i,u_{i+1}) = r_{low}-2\varsigma$ for $i=0,...,t-1$ and $D_q(u_{t},u_{t+1}) \leq r_{low}-2\varsigma$ (see Figure \ref{fig:pathconstruction}). There exists a vertex $v_i$ near to $u_i$ such that $v_i$ and $v_{i+1}$ are connected. We show that the length of the path $x, v_1, ..., v_t, y$ is approximately smaller than $D_f(x,y)$. 
From the path construction we have 
\[
\|v_i-v_{i+1}\| \approx_{\lambda} \|u_i-u_{i+1}\| \approx_{\lambda} r/q(u_i).
\] 
By summing up along the path we get
\begin{eqnarray*}
D_{sp}(x,y) 
 & \leq & \textstyle{\sum_i{h(\|v_i-v_{i+1}\|)}} \\
 & \approx_{\lambda} & \textstyle{\sum_i{h(\|u_i-u_{i+1}\|)}}  \approx_{\lambda}  \textstyle{\sum_i{h(\frac{r}{q(u_i)})}} \\
 & = & \textstyle{\sum_i{f(u_i)\frac{r}{q(u_i)}}} \approx_{\lambda}  \textstyle{\sum_i{f(u_i)\|u_i-u_{i+1}\|}} 
\end{eqnarray*}
From the adaptation of Lemma \ref{lem:approx} we have
$D_f(u_i,u_{i+1})\approx_{\lambda} f(u_i)\|u_i-u_{i+1}\|$, which gives
\[
\textstyle{\sum_i{f(u_i)\|u_i-u_{i+1}\|}} \approx_{\lambda} \textstyle{\sum_i{D_f(u_i,u_{i+1})}} = D_f(x,y).
\]
This shows that $D_{sp}(x,y) \preccurlyeq_{\lambda} D_f(x,y)$. 

For the
other way round, we use a technique different from Proposition \ref{pr:unweighted_sp}. 
Denote the graph shortest path between $x$ and $y$ by $\pi:
z_0=x,z_1,...,z_s,z_{s+1}=y$. Consider $\pi'$ as a continuous path in
$\Xcal$ corresponding to $\pi$. As in the previous part, divide $\pi'$ into segments $u_0 = x, u_1,...,u_{t},u_{t+1}=y$ (see Figure \ref{fig:pathconstruction}). %Analogously construct the path $x, v_1, ..., v_t, y$. 
From $D_q(z_i,z_{i+1}) \preccurlyeq_{\lambda} r$ and $D_q(u_i,u_{i+1})
\approx_{\lambda} r$ we have $s \succcurlyeq_{\lambda} t$. Using this
and the subadditivity of $h$ we get
\begin{equation*}
\textstyle{D_{sp}(x,y) = \sum_i{h(\|z_i-z_{i+1}\|)} \succcurlyeq_{\lambda}  \sum_i{h(\|u_i-u_{i+1}\|)}.}
\end{equation*}
To prove  $D_{sp}(x,y) \succcurlyeq_{\lambda}
D_f(x,y)$, we can write
\begin{eqnarray*}
\textstyle{\sum_i{h(\|u_i-u_{i+1}\|)}} & \approx_{\lambda} & \textstyle{\sum_i{h(\frac{r}{q(u_i)})}} =  \textstyle{\sum_i{\frac{f(u_i)r}{q(u_i)}}} \\
& \approx_{\lambda} & \textstyle{\sum_i{f(u_i)\|u_i-u_{i+1}\|}} \\
& \approx_{\lambda} & \textstyle{\sum_i{D_f(u_i,u_{i+1})}} \geq  D_f(x,y).
\vspace{-10pt}
\end{eqnarray*}
\end{proof}



\vspace{-5pt}
%%%%%%%%%
The \textbf{proof of Theorem \ref{th:edge_weights}} is a direct
consequence of this theorem. It follows by choosing 
$ h(t) = t \tilde{f}( {r^d}/ {t^d})$ (which is subadditive if $\tilde
f$ is increasing) and setting $w_{ij} =
h(\|X_i-X_j\|)$. 

%Let us go over some special cases. Assigning weights $w_{ij} = \| X_i - X_j \|$ will imply that $f(x) = 1$. This shows that in $\knn$ and $\epsilon$-graphs weighted by $w_{ij} = \| X_i - X_j \|$, the $\SP$ distance converges to the geodesic distance in $\Xcal$. 
%
%In unweighted  $\knn$ graphs, we have $w_{ij} = 1$. Theorem \ref{th:main} can be thought as proving 
%\begin{equation}
%\label{eq:knn_approx_along_sp}
%\| X_i - X_j \| \approx \frac{r}{p(X_i)^{1/d}}
%\end{equation}
%for most edges $e=(X_i,X_j)$ on the graph shortest paths between vertices. This implies that $f(x) = p(x)^{1/d}/r$ or equivalently $\tilde{f}(x) = x^{1/d}/r$.
%%Here is the place that we need the assumption $[Ga2]$ to have a bound on the length of an edge. 
%In this case the convergence argument holds only for a shortest path. For an arbitrary curve in $X$ there exist several approximations in the the $\knn$ graph which their unweighted lengths don't converge to each other. 
%The proof for $\epsilon$-graphs is much simpler and can be yielded by replacing $D_q(x,y)$  with $\|x-y\|$ every where.
%Not that this is not possible using $\epsilon$-graphs. For any edge weight function $h$ the graph $\SP$ will converge to a constant times the Euclidean distance where the constant is $h(\epsilon) / \epsilon$.   
%while the density is not involved in edges of a shortest path. 
%This method looks promising for applications and is subject of our future work.
%Now consider a weighted $\knn$ graph with edge weights $w_{ij} = h(\|X_i-X_j\|)$. We need to distinguish two different cases for this problem. If the function $h$ is increasing and subadditive( $\forall a,b\geq 0 : h(a)+h(b)\geq h(a+b)$), then we have the triangle inequality on edge weights and the shortest path will prefer jumping over distant vertices. This results a behavior similar to the unweighted $\knn$ graphs and the approximate Euclidean length of edges on the shortest path will be similar to the Equation \ref{eq:knn_approx_along_sp}. The weighted shortest path will converge to $f$-distance where $f(x)=h(r/q(x))q(x)/r$  and $r=(k/(n \eta_d))^{1/d}$.
\vspace{-5pt}
\subsubsection{Supperadditive weights} 
A function $h$ is called superadditive if $\forall x,y\geq 0 :
h(x)+h(y)\leq h(x+y)$. Examples are $f(x)=x^a;a>1$ and $f(x)=xe^{x}$.
To get an intuition on the behavior of the $\SP$ for a superadditive $h$, take an
example of three vertices $x,y,z$ which are all connected in the graph
 and sit on a straight line such that $\|x-y\| + \|y-z\| = \|x-z\|.$ 
By the superadditivity, the $\SP$ between $x$ and $z$ will prefer going through $y$ rather
than directly jumping to $z$. More generally, the graph $\SP$ will prefer
taking many ``small'' edges rather than fewer ``long'' edges. For this reason, we do not
expect a big difference between superadditive weighted $\knn$ graphs
and $\epsilon$-graphs: the long edges in the $\knn$ graph
will not be used anyway. However, due to technical problems we did not
manage to prove a formal theorem to this effect. 

The special case of the superadditive family $h(x)=x^a$, $a>1$ is treated in \citet{Hwang2012} by completely different methods. Although their results are presented for complete graphs, we believe that it can be extended to $\epsilon$ and $\knn$ graphs.
We are not aware of any other result for the limit of $\SP$ distance
in the superadditive regime. 



%\citet{Bijral11} find an approximation for the distance between $x_i$ and its nearest neighbor which is $c/q(x_i)$ with $c=(\frac{\log{2} }{n \eta_d})^{1/d}$. %Comparing this result and ours for subadditive weights suggests having an approximation in the form of $\alpha/q(x)$. 
%Correctness of this conjecture will imply the convergence of the $\SP$ distance to $f$-distance where $f(x) = h(\alpha/q(x)) q(x)/\alpha$. 
%Gaussian edge weights are used in many machine learning applications. 
%XXXX I SHOULD CHECK THE CORRECTNESS OF THIS PART AGAIN.
 % It is easy to verify that $f$ is a monotonically decreasing function. 
%If we use Gaussian weighting where $w_{ij}=exp(\|X_i-X_j\|/\sigma)$. In $\knn$ graphs it implies that the weighted shortest path converges to
%\[
%D_{p}(x,y) = \min_{\gamma} \frac{1}{r} \int_{\gamma}{p(\gamma(t))^{1/d} e^{\frac{\|r^2\|}{p(\gamma(t))^{2/d} \sigma }} |\gamma'(t)| dt}.
%\]





%	\begin{minipage}{.49\linewidth}
%		\includegraphics[width=\columnwidth]{figure/uniform_box.pdf}
%	\end{minipage}
%	\begin{minipage}{.49\linewidth}
%		\includegraphics[width=\columnwidth]{figure/isomap_uniform_box.pdf}
%	\end{minipage}
%	\caption{a) Sample points. b)Corresponding Isomap embedding based on an unweighted $\knn$ graph.}


\section{Consequences in applications}
\label{sec:conseq} 
In this section we study the consequences of our results on manifold embedding using Isomap and on a particular semi-supervised learning method. %The message is that we should be aware of the $\SP$ distance behavior when we use unweighted $\knn$ graphs for these applications.

There are two cases where we do not expect a drastic difference
between the $\SP$ in weighted and unweighted $\knn$ graph: (1) If the
underlying density $p$ is close to uniform. (2) If
the intrinsic dimensionality of our data $d$ is high. The latter is
because in the $q$-distance, the underlying density arises in
the form of $p(x)^{1/d}$, where the exponent flattens the distribution for large
$d$.
\vspace{-5pt}
\subsection{Isomap}
Isomap is a widely used method for low dimensional manifold embedding
\citep{TenSilLan00withproofs}. The main idea is to use metric
multidimensional scaling on the matrix of pairwise geodesic
distances. Using the Euclidean length of edges as their weights will
lead to the convergence of the $\SP$ distance to the geodesic distance. But what would be the effect of applying Isomap to unweighted graphs? 

Our results of the last section already hint that there is no big difference between unweighted and weighted $\epsilon$-graphs for Isomap. 
However, the case of $\knn$ graphs is different because weighted and unweighted shortest paths measure different quantities. %eaking, we can see the unweighted $\knn$  graph as an $\epsilon$-graph with respect to metric $D_f$. 
The effect of applying Isomap to unweighted $\knn$ graphs can easily
be demonstrated by the following simulation. We sample 2000 points
in $\R^2$ from a distribution that has two uniform high-density
squares, surrounded by a uniform low density region. An unweighted $\knn$ graph is constructed with
$k=10$, and we apply Isomap with target dimension 2. The result is
depicted in Figure \ref{fig:isomap_knn}. We can see that the Isomap
embedding heavily distorts the original data: it stretches high
density regions and compacts low density regions to make the vertex
distribution close to uniform. 
%Assume there is a transformation $T:\Xcal \rightarrow \mathbf{X'}$ such that for all $x,y \in \Xcal$ we have $\|T(x)-T(y)\| = D_q(x,y)$. 
%distance + isomap: show and explain how unweighted knn + isomaps makes points uniform. Briefly discuss: Are there perhaps examples where such a behavior might be desired? In what situations is the behavior undesired?
%look for literature on isomap, is this behavior explained somewhere in a paper?

%In general, Isomap on unweighted $\knn$ graphs has the tendency to distribute the points such that they are approximately uniformly distributed. If the original distribution is not uniform, it introduces a large bias.
\subsection{Semi-supervised learning}

Our work has close relationship to some of the literature on
semi-supervised learning (SSL). In regularization based approaches,
the underlying density is either exploited implicitly as attempted in
Laplacian regularization (\citealp{ZhuGhaLaf03} but see 
\citealp{NadSreZho09,AlaLux11} and \citealp{ZhouB11}),  or more explicitly as in measure based regularization \citep{BouChaHei03}.
Alternatively, one defines new distance functions on the data that take the density of the unlabeled points into account.
Here, the papers by \citet{Sajama2005} and \citet{Bijral11} are most related to our paper. Both papers suggest different ways to approximate the density based distance from the data. In \citet{Sajama2005} it is achieved by estimating the underlying density while in \citet{Bijral11}, the authors omit the density estimation and use an approximation. 

Our work shows a simpler way to converge to a similar distance
function for a specific family of $f$-distances, namely constructing a $\knn$ graph and assigning edge
weights as in Equation \ref{eq:weight_w}.
%for a given density based distance function $f(x) = \tilde{f}(p(x))$.
%
%In direct regularization we need an increasing function for weights to penalize high density regions, but in distance based regularization we need a decreasing $f$ to prefer passing through high density regions.


\section{Conclusions and outlook} 

We have seen in this paper that the shortest path distance on
unweighted $\knn$ graphs has a very funny limit behavior: it prefers
to go through regions of low density and even takes large detours in
order to avoid the high density regions. In hindsight, this result seems
obvious, but most people are surprised when they first
hear about it. In particular, we believe that it is important to
spread this insight among machine learning practitioners, who
routinely use unweighted $\knn$-graphs as a simple, robust alternative
to $\eps$-graphs.

In some sense, unweighted $\eps$-graphs and unweighted $\knn$ graphs
behave as ``duals'' of each other: while
degrees in $\eps$-graphs reflect the underlying density, they are independent of the density in $\knn$
graphs. While the shortest path in
$\eps$-graphs is independent of the underlying density and converges
to the Euclidean distance, the shortest paths in $\knn$
graphs take the density into account. 
%Additionally, if we consider
%weighted $\knn$ graphs with edge weights of the form XX GAUSSIAN WITH
%POSITIVE SIGN XXX, these graphs
%tend to behave like unweighted $\eps$-graphs, whereas edge weights of the form XX GAUSSIAN WITH
%NEGATIVE SIGN XX
%lead to a behavior that is closer to unweighted $\knn$ graphs. 

%We believe that is important that the machine learning
%community becomes aware of these differences. 
Current practice
is to use $\eps$ and $\knn$ graphs more or less interchangeably in
many applications, and the decision for one or the other graph is
largely driven by robustness or convenience considerations. However,
as our results show it is important to be aware of the implicit 
consequences of this choice.  Each graph carries different information about the underlying
density, and depending on how a particular machine learning algorithms makes use
of the graph structures, it might either miss out or benefit from this
information.


% discuss a bit: what kind of properties are preserved in what kind of
% graph: * eps graph: density preserved (in degrees), geometry of points
% preserved (in shortest paths) * knn graph: tries to make everything
% uniform (degrees uniform, shortest paths behave a bit strange) *
% weighted knn graphs preserves everything we want: use negative
% gaussian weights leads to correct degree estimate, use positive
% gaussian weights leads to Euclidean distances ( is it true that if we
% choose the correct rates to make the degrees converge to the density,
% that then also the shortest paths wrt inverse weights converge to the
% Euclidean distance? or would we need different assumptions? )


% outlook: positive interpretation of the unweighted knn result in sampling/covering situations: state that properties of $D_f$ make it interesting for covering: sometimes we want to cover such that all balls have the same Euclidean distance, but often we want to cover such that all balls have the same probability mass. can achieve this with unweighted knn graphs. we are working on this.



\bibliography{knn_icml2012,ules_publications,general_bib}
\bibliographystyle{icml2012}

\end{document} 


ules_latex_defaults.tex
% ------------------------------------------------------------
% ------------------------------------------------------------

% Ule's latex default settings
% simply include per 'input' in the current latex file 

\typeout{Using Ule's latex defaults!}

% ------------------------------------------------------------
% ------------------------------------------------------------

% ------------------------------------------------------------
% packages:
% ------------------------------------------------------------

% mathematical stuff: 
\usepackage{amssymb}
\usepackage{amsmath}
\allowdisplaybreaks[3] % page breaks inside eqnarray, see ams doku  
%\usepackage{bbold} % used in definition of \charfct 
%\usepackage[mathcal]{euscript} % curlier version of mathcal symbols

% for figures: 

%\usepackage{flafter} % no figure before the place it is defined 
%\PassOptionsToPackage{pdftex}{graphicx} %flafter loads graphicx, but
                                %without option. will lead to option
                                %clash with graphicx package unless
                                %this line is put in ... 

%\usepackage[pdftex]{graphicx}
%\DeclareGraphicsExtensions{.pdf}


% for the layout and general stuff

% put in paper directly if necessary
% \usepackage{geometry}
% \geometry{verbose,a4paper,tmargin=2cm,bmargin=3cm,lmargin=3cm,rmargin=3cm}

\usepackage{fancyhdr} % for nice head-and footlines
\usepackage{ifthen} % for \ifthenelse
\usepackage{layout} 
\usepackage{xspace}% for nice spaces after macros 
%\usepackage{afterpage}% to flush floats nicely; use
                      % \afterpage{\clearpage} to flush all figures
                      % but without starting a new page
\usepackage{url}
\usepackage{textcomp} %for the euro symbol; \texteuro

% for smileys and lightnings: 
\usepackage{wasysym} 
%has to be included
% after amsmath because of a bug! 
% for other wasysym stuff see below. 

% to show labels:
%\usepackage[notref,notcite]{showkeys_tiny}

% ------------------------------------------------------------
% Language - force german or english: 
% ------------------------------------------------------------

%\usepackage[english]{babel}
%\usepackage{german}
\usepackage[latin1]{inputenc} %for 8bit-umlaute produced by emacs

% ------------------------------------------------------------
% bib:
% put this in the article directly, causes confusion when used to
% produce journal papers
% ------------------------------------------------------------


%%\usepackage[round,comma]{natbib}
%%\bibliographystyle{plainnat}
% option sectionbib: section rather than chapter

% undefine the cite command to make sure that no coauthor uses it
%\let\cite\undefined

% how to use natbib citations: 
% \citet{SchSmo02} = ``cite in text'', gives Schoelkopf and Smola (2002)
% \citep{SchSmo02} = ``cite in parantheses'', gives (Schoelkopf and Smola, 2002)
% \citealp = ``cite alternative way'', gives Schoelkopf and Smola, 2002


%% APA CITATION STYLE (in the refernece list, year directly after
%% names, not at the end): The translation between commands is as
%% follows
%%\citealp = \citeNP
%%\citet = \citeA
%%\citep = \cite
%% just use the normal natbib commands, here is a translation list: 

%%\usepackage{apacite}
%%\bibliographystyle{apacite}
%%\newcommand{\citealp}[1]{\citeNP{#1}}
%%\newcommand{\citet}[1]{\citeA{#1}}
%%\newcommand{\citep}[1]{\cite{#1}}
%%\renewcommand{\BBAA}{and}
%%\renewcommand{\BCBT}{}
%%\renewcommand{\BTR}{Technical Report}
%%\renewcommand{\BUPhD}{PhD Thesis}
%%\renewcommand{\BPhD}{PhD Thesis}

% \fullciteA -> generates full author list (no et al.)

% ------------------------------------------------------------
% environments: 
% ------------------------------------------------------------

% EQUATION ENVIRONMENTS: 

% abbreviations: \ba = \begin{algin}, \ea = \end{align}
% This cannot be done with a newcommand because of the processing of
% macros in the amslatex package, see tex newsgroup thread ``eeq and amstex''
\def\ba#1\ea{\begin{align*}#1\end{align*}} %\ba = \begin{algin*}, \ea = \end{align*}
\def\banum#1\eanum{\begin{align}#1\end{align}} %\banum = \begin{algin}, \eanum

\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}

\def\bv#1\ev{\begin{verbatim}#1\end{verbatim}} %\ba = \begin{algin*}, \ea = \end{align*}

%\newcommand{\nn}{\nonumber}



% THEOREM ENVIRONMENTS: 

% now distinguish whether llncs is used or not. if yes, then the
% following commands are already defined, so do not define them again
% (otherwise error message): 
% might be better to look for amsthm, where those things are
% defined. this is sometimes also used in other packages, like beamer


%define theorem environments:
\ifx\lemma\undefined
\typeout{ULE: LEMMA IS UNDEF, THUS DEF IT:}
%define theorem and proof environments:
\newtheorem{example}{Example} 
\newtheorem{theorem}{Theorem} 
\newtheorem{lemma}[theorem]{Lemma} 
\newtheorem{proposition}[theorem]{Proposition} 
\newtheorem{remark}[theorem]{Remark}
%\newtheorem{theorem}[theorem]{Theorem} 
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{conjecture}[theorem]{Conjecture}
\newcounter{ulesexercise}
\newtheorem{exercise}[ulesexercise]{Exercise} %other counter than rest
%
\else
\typeout{ULE: LEMMA IS ALREADY DEFINED }
\fi





% hack for a theorem without number (nn = no number): 
% I define a theorem with a new counter theoremnn. Then I redefine the 
% command which writes the number of this counter to write nothing. 
\newtheorem{theoremnn}{Theorem}
\renewcommand{\thetheoremnn}{\unskip}

% hack for a proposition with a given number: 
\newcounter{dummycounter}
\newtheorem{propcounter}[dummycounter]{Proposition}
% to apply this, set the dummycounter to the value you want, eg 
% \setcounter{dummycounter}{\ref{prop-eps-graph}}
% \addtocounter{dummycounter}{-1} %because will be increased when calling propcounter
% Then call the propcounter. 

% comments in calculations: 
%\newcommand{\comment}[1]{\hspace{1cm}(\text{#1})}



% PROOF ENVIRONMENTS: 
\newenvironment{proofof}[1]{\par\noindent{\em Proof of #1. }}{\hfill\\[2mm]}
\newcommand{\boringqed}{\hfill$\Box$} % unfilled box
\newcommand{\BlackBox}{\rule{1.5ex}{1.5ex}}  % filled black box 
\newcommand{\ulesqed}{\hfill\smiley}

\ifx\proof\undefined
\typeout{ULE: PROOF IS UNDEF, THUS DEF IT:}
\newenvironment{proof}{\par\noindent{\em Proof. }}{\ulesqed}
\else
\typeout{ULE: PROOF IS ALREADY DEFINED. }
\fi



% ------------------------------------------------------------
% colors
% ------------------------------------------------------------

%\input{ules_latex_colors.tex}

\definecolor{ulesred}{rgb}{0.7,0,0}
\newcommand{\ur}{\color{ulesred}}

% ------------------------------------------------------------
% dealing with pseudocode: 
% ------------------------------------------------------------
% \usepackage[noend]{algorithmic}

% \algsetup{linenosize=\scriptsize\slidegray}
% \algsetup{linenodelimiter=}
% \renewcommand{\algorithmiccomment}[1]{{\small\blue \# #1}}
% \renewcommand{\algorithmicthen}{} % don't want then statements
% \renewcommand{\algorithmicdo}{} % don't want do statements
% \newcommand{\balg}{\begin{algorithmic}[1]}
% \newcommand{\ealg}{\end{algorithmic}}
% \newcommand{\FORL}[2]{% for loop in one line
% \algorithmicfor\ {(#1),}\ \algorithmicdo\ {#2,} \;\algorithmicend\ \algorithmicfor\\%
% }
% \newcommand{\IFL}[2]{% for loop in one line
% \algorithmicif\ {(#1),}\ \algorithmicdo\ {#2,} \;\algorithmicend\ \algorithmicif\\%
% }
% \newcommand{\FORALLL}[2]{% forall loop in one line
% \algorithmicforall\ {(#1),}\ \algorithmicdo\ {#2,} \;\algorithmicend\ \algorithmicfor\\%
% }




% ALGORITHM ENVIRONMENT BY FOOT: 

% Usage: \ulesalgorithm{Name of alg}{contents of alg}, see NIPS 2007
% paper...
% nice version by foot is to use: 
% \begin{quote}{ \tt
% ...
% }
% \end{quote}
\newcommand{\ulesalgorithm}[2]{%
\fbox{\parbox{\textwidth}{%
{\bf #1}\\[2mm]
{\tt #2 }
}}
%\vspace{0.5cm}
}



% a similar thing: just moves text a bit to the left (similar to the
% quote environment, but no margin at the right side): 
% use it with \ulesquote{ ... } or perhaps \ulesquote{\texttt ... }
% see stability overview paper at ftml for an example
\newcommand{\ulesquote}[1]{
\begin{list}{}{%
\setlength{\leftmargin}{1cm}%
\setlength{\rightmargin}{0cm}%
\setlength{\topsep}{0cm}%
}
\item[] #1
\end{list}
}



% ------------------------------------------------------------
% math letters: 
% ------------------------------------------------------------


\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}} 
\newcommand{\Nat}{\mathbb{N}} 
\newcommand{\ZZ}{\mathbb{Z}} 
\newcommand{\QQ}{\mathbb{Q}} 
%%  low level versions:  
%%\newcommand{\R}{I\!\!R}
%%\newcommand{\RR}{I\!\!R}
%%\newcommand{\Nat}{I\!\!N} 
%%\newcommand{\CC}{I\!\!\!\!C}


% for compatibility reasons with other people: 
\let\R\undefined %sometimes it is defined as something I don't know
\newcommand{\R}{\RR}
\newcommand{\N}{\Nat}


% note that to generate more curly mathcal symbols i invoked the eucal
% package in the beginning
\newcommand{\Acal}{\mathcal{A}}
\newcommand{\Bcal}{\mathcal{B}}
\newcommand{\Ccal}{\mathcal{C}}
\newcommand{\Dcal}{\mathcal{D}}
\newcommand{\Ecal}{\mathcal{E}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gcal}{\mathcal{G}}
\newcommand{\Hcal}{\mathcal{H}}
\newcommand{\Kcal}{\mathcal{K}}
\newcommand{\Lcal}{\mathcal{L}}
\newcommand{\Mcal}{\mathcal{M}}
\newcommand{\Ncal}{\mathcal{N}}
\newcommand{\Ocal}{\mathcal{O}}
\newcommand{\Pcal}{\mathcal{P}}
\newcommand{\Qcal}{\mathcal{Q}}
\newcommand{\Rcal}{\mathcal{R}}
\newcommand{\Scal}{\mathcal{S}}
\newcommand{\Tcal}{\mathcal{T}}
\newcommand{\Ucal}{\mathcal{U}}
\newcommand{\Vcal}{\mathcal{V}}
\newcommand{\Wcal}{\mathcal{W}}
\newcommand{\Xcal}{\mathcal{X}}
\newcommand{\Ycal}{\mathcal{Y}}
\newcommand{\Zcal}{\mathcal{Z}}



% ------------------------------------------------------------
% math operators: 
%if they should have limits (such as a sum) use the * version
% ------------------------------------------------------------
% standard stuff: 

\DeclareMathOperator*{\argmin}{argmin} % * falls subscript
\DeclareMathOperator*{\argmax}{argmax}
\DeclareMathOperator*{\minimize}{minimize}
%\DeclareMathOperator{\aufspan}{span} replace this by linspan ...
\DeclareMathOperator{\linspan}{span}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\Cov}{Cov}
\DeclareMathOperator{\Tr}{Tr}% trace
\DeclareMathOperator{\tr}{Tr}% trace
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\supp}{supp} % support of a function
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\rg}{rg} %range of a funciton
\DeclareMathOperator{\vol}{vol} %volume


%more special stuff: 

\DeclareMathOperator{\rreg}{R_{reg}}
\DeclareMathOperator{\remp}{R_{emp}}
\DeclareMathOperator{\Rreg}{R_{reg}}
\DeclareMathOperator{\Remp}{R_{emp}}
\DeclareMathOperator{\train}{train}
\DeclareMathOperator{\test}{test}
\DeclareMathOperator{\reg}{reg}
%\DeclareMathOperator{\emp}{emp}
\newcommand{\emp}{{\text{emp}}}

\DeclareMathOperator{\Lip}{Lip}

% Norms: Attention, changed. 
% now use them with standard command with curly brackets: 
% \norm{something}
\newcommand{\norm}[1]{\|#1\|}
\newcommand{\norminf}[1]{\|#1\|_{\infty}}
\newcommand{\normone}[1]{\|#1\|_{1}}
\newcommand{\normtwo}[1]{\|#1\|_{2}}
\newcommand{\normltwo}[1]{\|#1\|_{L_2}}
\newcommand{\normltwopn}[1]{\|#1\|_{L_2(P_n)}}
\newcommand{\normltwop}[1]{\|#1\|_{L_2(P_n)}}

% min and max

\newcommand{\pmin}{p_{\min}}
\newcommand{\pmax}{p_{\max}}
\newcommand{\dmin}{d_{\min}}
\newcommand{\dmax}{d_{\max}}
\newcommand{\wmin}{w_{\min}}
\newcommand{\wmax}{w_{\max}}
\newcommand{\rkmin}{R_{k,\min}}
\newcommand{\rkmax}{R_{k,\max}}

% knn stuff: 
\newcommand{\knn}{\text{kNN}}


% Graph Laplacians: 
\newcommand{\Lsym}{L_{\text{sym}}}
\newcommand{\sym}{_{\text{sym}}}
\newcommand{\Lrw}{L_{\text{rw}}}
\newcommand{\Lun}{L}
% and, for lazyness, the same with lower case
\newcommand{\lsym}{\Lsym} 
\newcommand{\lrw}{\Lrw}
\newcommand{\lun}{\Lun}
% and same with n: 
\newcommand{\Lsymn}{L_{\text{sym,n}}}
\newcommand{\Lrwn}{L_{\text{rw,n}}}
\newcommand{\Lunn}{L_n}
\newcommand{\lsymn}{\Lsymn} 
\newcommand{\lrwn}{\Lrwn}
\newcommand{\lunn}{\Lunn}

\newcommand{\Lunpinv}{\Lun\pinv}
\newcommand{\Lsympinv}{\Lsym\pinv}
%
\newcommand{\lunpinv}{\Lun\pinv}
\newcommand{\lsympinv}{\Lsym\pinv}
%

\DeclareMathOperator{\val}{val}


% Graph cuts and objective functions: 
\DeclareMathOperator{\ratiocut}{RatioCut}
\DeclareMathOperator{\Ratiocut}{RatioCut}
\DeclareMathOperator{\ncut}{Ncut}
\DeclareMathOperator{\Ncut}{Ncut}
\DeclareMathOperator{\cut}{cut}
\DeclareMathOperator{\Cut}{cut}
\DeclareMathOperator{\mincut}{MinCut}
\DeclareMathOperator{\Mincut}{MinCut}
\DeclareMathOperator{\maxcut}{MaxCut}
\DeclareMathOperator{\minmaxcut}{MinMaxCut}
\DeclareMathOperator{\bal}{Balance}

%stability
\DeclareMathOperator{\stab}{Stab}% stabilty 
\DeclareMathOperator{\Stab}{Stab}% stability
\DeclareMathOperator{\instab}{Instab}% instability
\DeclareMathOperator{\InStab}{\instab}% instability




% ------------------------------------------------------------
% misc math stuff: 
% ------------------------------------------------------------

% various symbols: 

\newcommand{\eps}{\ensuremath{\varepsilon}}
\renewcommand{\epsilon}{\ensuremath{\varepsilon}}
\renewcommand{\phi}{\ensuremath{\varphi}}
%\newcommand{\charfct}{\ensuremath{\text{\bbfamily{1}}}} % hack
%\newcommand{\charfct}{\mathbb{1}}
\newcommand{\constantfct}{\mathbf{1}}% constant 1-function
\newcommand{\onevec}{\mathbf{1}}% constant 1-function
\newcommand{\nullfct}{{\bf 0}}
\newcommand{\preperp}[1]{{^\perp}#1} % orthogonal-sign in left upper corner of something
\newcommand{\uniondis}{\mathaccent\cdot\cup}  %disjoint union
\newcommand{\union}{\cup}  
\newcommand{\entspricht}{\widehat{=}}
% probability stuff: 

\newcommand{\as}{a.s.\xspace}
\newcommand{\condon}{\; \big| \;}%conditional on ...
\newcommand{\comma}{\; , \;}%conditional on ...
%\newcommand{\prob}{\mathbb{P}} %probability, the french way
%\newcommand{\expectation}{\mathbb{E}} %expectation, the french way;
\let\Pr\undefined %is defined as something I don't know
\DeclareMathOperator{\Pr}{Pr}


\newcommand{\hd}{\hdots}


%Convergence: 
\newcommand{\tocc}{  \overset{cc}{\to}  }%collectively compact
\newcommand{\tocompact}{  \overset{c}{\to}  }% compact
\newcommand{\topointwise}{  \overset{p}{\to}  }%pointwise
\newcommand{\tonorm}{  \overset{\norm}{\to}  }%in norm
\newcommand{\toplusminus}{ \overset{+-}{\to}  }%up to a change of sign

\newcommand{\CX}{C(\Xcal)} %continuous fct space

% spectral stuff: 
\newcommand{\sigmaess}{\sigma_{\text{ess}}} %essential spectrum
\newcommand{\sigmad}{\sigma_{\text{d}}} %discrete spectrum

% vertical and horizontal vectors, to be used either in text or in
% math mode formulas: 
\newcommand{\tvec}[2]{\ensuremath{\bigl(\begin{smallmatrix}#1\\#2\end{smallmatrix}\bigr)}}%text, vertical
\newcommand{\fvec}[2]{\begin{pmatrix}#1\\#2\end{pmatrix}} %formulas,vertical



% inverting: 
\newcommand{\inv}{^{-1}} %inverse
\newcommand{\pinv}{^{\dagger}} %pseudo-inverse



% ------------------------------------------------------------
% misc non-math: 
% ------------------------------------------------------------
%\newcommand{\maketilde}{\raisebox{0.4ex}{\tiny $\sim$}} % for ~ in
%urls, http addresses
% use \symbol{126} instead
% empty line in a slide: 
%\newcommand{\emptyline}{\bigskip}%is a bit less than an empty line
\newcommand{\emptyline}{\vspace*{0.4cm}} %vspace* also works at beginning of page
\newcommand{\el}{\emptyline}

% for easier references: 
\newcommand{\fig}[1]{Figure~\protect\ref{#1}}
\newcommand{\tab}[1]{Table~\protect\ref{#1}}
\newcommand{\chap}[1]{Chapter~\protect\ref{#1}}
\renewcommand{\sec}[1]{Section~\protect\ref{#1}}
\newcommand{\app}[1]{Appendix~\protect\ref{#1}}
\newcommand{\eq}[1]{Equation~\protect(\ref{#1})}
\newcommand{\pag}[1]{page \protect\pageref{#1}}

\newcommand{\prop}[1]{Proposition~\protect\ref{#1}}
%\newcommand{\coro}[1]{Corollary~\protect\ref{#1}}
%\newcommand{\rema}[1]{Remark~\protect\ref{#1}}
%\newcommand{\exam}[1]{Example~\protect\ref{#1}}
%\newcommand{\appl}[1]{Application~\protect\ref{#1}}
%\newcommand{\algo}[1]{Algorithm~\protect\ref{#1}}
\renewcommand{\th}[1]{Theorem~\protect\ref{#1}}

\newcommand{\ER}{Erd\H{o}s-R\'{e}nyi\xspace} % Erdoes-Renyi in correct spelling
\newcommand{\er}{Erd\H{o}s-R\'{e}nyi\xspace}



\newcommand{\incl}[2]{\hfill\includegraphics[width=#1\textwidth]{#2}\hfill} %width
\newcommand{\inclh}[2]{\hfill\includegraphics[height=#1\textheight]{#2}\hfill} %height



% ------------------------------------------------------------
% blob commands: 
% ------------------------------------------------------------
% simple \blob command, without indentation in second line: 

\newcommand{\blob}{\mbox{}\\[1mm]\mbox{}\hspace{1mm}$\bullet$ } 
\newcommand{\blobblob}{\mbox{}\\[1mm]\mbox{}\hspace{5mm} $\circ$ } 

% as in \itemize, with correct indentation over several lines, 
% without any extra space on top or bottom. call with \blobb{argument}
\newcommand{\blobb}[1]{%
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0cm}
%\setlength{\partopsep}{-\parskip}
\setlength{\leftmargin}{0.5cm}
}{\item #1}%
\end{list}
}


% as in \itemize, with correct indentation over several lines, 
% without any extra space on top or bottom. call with \blobb{argument}
\newcommand{\blobblobb}[1]{%
\begin{list}{$\circ$}{%
\setlength{\topsep}{0cm}
%\setlength{\partopsep}{-\parskip}
\setlength{\leftmargin}{1.1cm}
}{\item #1}%
\end{list}
}
\newcommand{\bb}[1]{\blobblobb{#1}}
\newcommand{\blbo}{\blob} %because of constant typo :-)
%\newcommand{\emptyblob}{\hspace*{0.4cm}}
%\newcommand{\strich}{\mbox{}\\ - }


% ------------------------------------------------------------
% manuscript preparation phase: 
% ------------------------------------------------------------
\newcommand{\todo}{{\bf TO DO } } 
%\newcommand{\comment}[1]{{\sc  Comment: #1}}
\newcommand{\ule}[1]{{\bf  \em ULE: #1}}


% ------------------------------------------------------------
% about the smileys... and wasysym: 
% ------------------------------------------------------------

% because of inconsistent spelling (smiley but frownie)
\newcommand{\smilie}{\smiley}
\newcommand{\neutralface}{\mbox{\small \ensuremath{\bigcirc \hspace{-0.38cm}\sim}}}

% to get rid of a font warning for bold math fonts I don't even use:
% (write each font size which occurs in <size> to suppress warning)
\wasyfamily
\DeclareFontShape{U}{wasy}{b}{n}{ <-10> ssub * wasy/m/n
<10> <10.95> <12> <14.4> <17.28> <20.74> <24.88>wasyb10 }{}

% to produce arbitrary large smileys with wasysym: 
% add the font sizes i want in the end (here: 40, 50, and 60). Then
% can be called with {\fontsize{40}{1} \smiley}: 
\DeclareFontShape{U}{wasy}{m}{n}{ <5> <6> <7> <8> <9> gen * wasy
<10> <10.95> <12> <14.4> <17.28> <20.74> <24.88> <35> <40> <50> <60> wasy10  }{}


% date command (in case one wants to have it consistent over several
% documents, eg in application documents} 
\newcommand{\ulesdateEnglish}{\today}
\newcommand{\ulesdateGerman}{\today} 

knn_icml2012.bbl
\begin{thebibliography}{12}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Alamgir \& {von~Luxburg}(2011)Alamgir and {von~Luxburg}]{AlaLux11}
Alamgir, M. and {von~Luxburg}, U.
\newblock Phase transition in the familiy of p-resistances.
\newblock In \emph{Neural Information Processing Systems (NIPS)}, 2011.

\bibitem[Bijral et~al.(2011)Bijral, Ratliff, and Srebro]{Bijral11}
Bijral, A., Ratliff, N., and Srebro, N.
\newblock Semi-supervised learning with density based distances.
\newblock In \emph{Uncertainty in Artificial Intelligence (UAI)}, 2011.

\bibitem[Bousquet et~al.(2004)Bousquet, Chapelle, and Hein]{BouChaHei03}
Bousquet, O., Chapelle, O., and Hein, M.
\newblock Measure based regularization.
\newblock In \emph{Neural Information Processing Systems (NIPS)}. 2004.

\bibitem[Gamelin(2007)]{Gamelin2001}
Gamelin, T.~W.
\newblock \emph{Complex Analysis}.
\newblock Springer-Verlag, New York, Inc., 2007.
\newblock ISBN 0-387-95093-1.

\bibitem[Hwang \& Hero(2012)Hwang and Hero]{Hwang2012}
Hwang, S.J, Damelin S.~B. and Hero, A.~O.
\newblock Shortest path through random points.
\newblock In \emph{Preprint available at Arxiv}, January 2012.
\newblock URL \url{http://arxiv.org/abs/1202.0045}.

\bibitem[Nadler et~al.(2009)Nadler, Srebro, and Zhou]{NadSreZho09}
Nadler, B., Srebro, N., and Zhou, X.
\newblock Semi-supervised learning with the graph {L}aplacian: The limit of
  infinite unlabelled data.
\newblock In \emph{Neural Information Processing Systems (NIPS)}, 2009.

\bibitem[Penrose(1999)]{Penrose99}
Penrose, M.
\newblock A strong law for the longest edge of the minimal spanning tree.
\newblock \emph{Ann. of Prob.}, 27\penalty0 (1):\penalty0 246~--~260, 1999.

\bibitem[Sajama \& Orlitsky(2005)Sajama and Orlitsky]{Sajama2005}
Sajama and Orlitsky, A.
\newblock Estimating and computing density based distance metrics.
\newblock In \emph{International Conference on Machine learning (ICML)}, 2005.

\bibitem[Tenenbaum et~al.(2000)Tenenbaum, de~Silva, and
  Langford]{TenSilLan00withproofs}
Tenenbaum, J., de~Silva, V., and Langford, J.
\newblock {Supplementary material to "A Global Geometric Framework for
  Nonlinear Dimensionality Reduction"}.
\newblock \emph{Science}, 2000.

\bibitem[{von~Luxburg} et~al.(2010){von~Luxburg}, Hein, and
  Radl]{LuxRadHei10_arxiv}
{von~Luxburg}, U., Hein, M., and Radl, A.
\newblock Hitting times, commute distances and the spectral gap in large random
  geometric graphs.
\newblock In \emph{Preprint available at Arxiv}, March 2010.
\newblock URL \url{http://arxiv.org/abs/1003.1266}.

\bibitem[Zhou \& Belkin(2011)Zhou and Belkin]{ZhouB11}
Zhou, X. and Belkin, M.
\newblock Semi-supervised learning by higher order regularization.
\newblock In \emph{International Conference on Artificial Intelligence and
  Statistics (AISTATS)}, 2011.

\bibitem[Zhu et~al.(2003)Zhu, Ghahramani, and Lafferty]{ZhuGhaLaf03}
Zhu, X., Ghahramani, Z., and Lafferty, J.
\newblock { Semi-Supervised Learning Using {G}aussian Fields and Harmonic
  Functions}.
\newblock In \emph{International Conference of Machine Learning (ICML)}, 2003.

\end{thebibliography}
