\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{algorithm,algpseudocode}
\usepackage{bm}
\usepackage{hyperref}
\usepackage{float}
\usepackage{subcaption}
\usepackage{enumitem}
\usepackage{xcolor}
\definecolor{darkgreen}{rgb}{0.0, 0.5, 0.0}
\definecolor{aaltoBlue}{RGB}{0, 51, 102}
\definecolor{pinegreen}{cmyk}{0.92,0,0.59,0.25}
\definecolor{royalblue}{cmyk}{1,0.50,0,0}
\definecolor{lavander}{cmyk}{0,0.48,0,0}
\definecolor{violet}{cmyk}{0.79,0.88,0,0}
\definecolor{lightblue}{RGB}{173, 216, 230}
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{calc,arrows.meta,positioning,fit,shapes.geometric,shapes.misc,intersections,patterns,decorations.pathreplacing,backgrounds,matrix}
\usepgfplotslibrary{fillbetween,groupplots}
\setcounter{secnumdepth}{-\maxdimen}
% Long unbreakable tokens (the ISO/IEC author names in citations, term names
% in the title) otherwise overflow the margin by a few points; a modest
% emergency stretch lets TeX loosen the paragraph instead.
\emergencystretch=2em
\usepackage{mleftright}
% Project macros used by this entry (auto-extracted).
\newcommand{\LapMat}[1]{\mL^{(#1)}}
\newcommand{\cluster}{\mathcal{C}}
\newcommand{\defeq}{:=}
\newcommand{\degreemtx}{\mathbf{D}}
\newcommand{\edgeweight}{A}
\newcommand{\eigval}[1]{\lambda_{#1}}
\newcommand{\featurevec}{\vx}
\newcommand{\graph}{\mathcal{G}}
\newcommand{\mA}[0]{{\bf A}}
\newcommand{\mL}[0]{{\bf L}}
\newcommand{\mV}{\mathbf{V}}
\newcommand{\nodedegree}[1]{d^{(#1)}}
\newcommand{\nodeidx}{i}
\newcommand{\nodes}{\mathcal{V}}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\nrcluster}{k}
\newcommand{\nrnodes}{n}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\vu}[0]{{\bf u}}
\newcommand{\vv}[0]{{\bf v}}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{spectral clustering}

\subsection*{Author and editors}
Alexander Jung\textsuperscript{*}, Department of Computer Science, Aalto University, Espoo, Finland (ORCID \mbox{\href{https://orcid.org/0000-0001-7538-0990}{0000-0001-7538-0990}}) \\
Editors: Konstantina Olioumtsevits (ORCID \mbox{\href{https://orcid.org/0000-0003-2697-8659}{0000-0003-2697-8659}}), Ekkehard Schnoor (ORCID \mbox{\href{https://orcid.org/0000-0001-8252-1499}{0000-0001-8252-1499}}), Aalto University, Espoo, Finland \\
\textsuperscript{*}Corresponding author: \href{mailto:alex.jung@aalto.fi}{alex.jung@aalto.fi}



\subsection{Abstract}
Spectral clustering is a graph clustering method that
		computes the clusters of a dataset from the
		eigenvectors of the Laplacian matrix of a graph whose
		nodes are the data points and whose edge weights
		express their similarity. The Laplacian matrix is positive semi-definite (psd), and the
		multiplicity of its eigenvalue $0$ equals the number of
		connected components of the graph, with their
		indicator vectors as eigenvectors. For
		$\nrcluster$ clusters, the entries of the $\nrcluster$
		eigenvectors with the smallest eigenvalues form a
		new feature vector for each node, and $k$-means on these
		feature vectors delivers the clusters. For two
		clusters, the method thresholds the Fiedler vector.
		Spectral clustering is a relaxation of the ratio cut, which divides the
		total weight of the edges between the clusters by their
		sizes, and the second-smallest eigenvalue is a lower bound
		on the ratio cut of every bipartition. Unlike $k$-means on the
		raw feature vectors, spectral clustering finds clusters
		that are connected in the graph but not convex
		in the feature space. The number of clusters and the
		construction of the graph are its hyperparameters.

\subsection{Definition}
Each day of 2024 at the
		weather station Krems an der Donau is a data point with a
		feature vector $\featurevec \in \reals^{2}$ that holds the
		morning minimum and the maximum daytime temperature of the day.
		Connecting each day with its ten nearest days, measured by the
		Euclidean distance between their feature vectors, turns the
		$366$ days into the nodes $\nodeidx = 1, \ldots, \nrnodes$ of a
		$k$-nearest-neighbor graph ($k$-NN graph) $\graph$ with $\nrnodes = 366$ nodes and $2209$
		edges (Fig.~\ref{fig_specclustering_krems_dict}(a)). A
		cluster of this graph is a set of days that are
		joined by many edges among themselves and by few edges to the
		remaining days. Spectral clustering is a graph clustering
		method that finds such clusters from the
		eigenvectors of the Laplacian matrix of the graph
		(Hastie et al., 2009, Sect.~14.5.3;
		von Luxburg, 2007; Ng et al., 2001; Shi and Malik, 2000).
\par
		Consider a similarity graph of the dataset: a
		weighted graph $\graph$ with nodes
		$\nodeidx = 1, \ldots, \nrnodes$, one node per data point,
		and edge weights
		$\edgeweight_{\nodeidx,\nodeidx'} = \edgeweight_{\nodeidx',\nodeidx}
		\geq 0$ that express the similarity between the data points
		$\nodeidx$ and $\nodeidx'$; a missing edge has weight $0$. The
		edge weights form the adjacency matrix
		$\mA^{(\graph)} \in \reals^{\nrnodes \times \nrnodes}$, and the
		node degree
		$\nodedegree{\nodeidx} = \sum_{\nodeidx'=1}^{\nrnodes}
		\edgeweight_{\nodeidx,\nodeidx'}$ of node $\nodeidx$ is the sum of
		its edge weights. The Laplacian matrix of $\graph$ is
		\begin{equation}
			\label{equ_specclustering_laplacian_dict}
			\LapMat{\graph} \defeq \degreemtx - \mA^{(\graph)}
			\quad \text{with } \degreemtx \defeq
			\operatorname{diag}\big\{\nodedegree{1}, \ldots,
			\nodedegree{\nrnodes}\big\} \text{.}
		\end{equation}
		For every vector $\vu \in \reals^{\nrnodes}$ with entries
		$u_{\nodeidx}$, the Laplacian matrix
		\eqref{equ_specclustering_laplacian_dict} satisfies
		\begin{equation}
			\label{equ_specclustering_quadform_dict}
			\vu^{\top} \LapMat{\graph} \vu = \frac{1}{2}
			\sum_{\nodeidx=1}^{\nrnodes} \sum_{\nodeidx'=1}^{\nrnodes}
			\edgeweight_{\nodeidx,\nodeidx'}
			\big( u_{\nodeidx} - u_{\nodeidx'} \big)^{2} \text{,}
		\end{equation}
		a weighted sum of squared differences across the edges
		(von Luxburg, 2007, Prop.~1). The quadratic form
		\eqref{equ_specclustering_quadform_dict} is never negative, so
		$\LapMat{\graph}$ is a symmetric matrix that is positive semi-definite (psd).
		It has an eigenvalue decomposition (EVD)
		$\LapMat{\graph} = \mV {\bm \Lambda} \mV^{\top}$ with an
		orthogonal matrix
		$\mV = \big( \vv^{(1)}, \ldots, \vv^{(\nrnodes)} \big)$ of
		eigenvectors and with eigenvalues
		$0 = \eigval{1} \leq \eigval{2} \leq \ldots \leq \eigval{\nrnodes}$.
		The constant vector is an eigenvector for the
		eigenvalue $0$, since every row of $\LapMat{\graph}$ sums to
		zero. More generally, the multiplicity of the eigenvalue
		$0$ is the number of connected components of $\graph$, and
		the indicator vectors of the components span its
		eigenvectors (von Luxburg, 2007, Prop.~2). The reason is
		the quadratic form \eqref{equ_specclustering_quadform_dict}:
		$\LapMat{\graph} \vu = \mathbf{0}$ forces
		$u_{\nodeidx} = u_{\nodeidx'}$ across every edge, so $\vu$ is
		constant on each component.
		Fig.~\ref{fig_specclustering_components_dict} shows an
		undirected graph with two components; its two
		eigenvectors for the eigenvalue $0$ place the nodes
		of each component on a single point of a scatterplot.
		\begin{figure}[H]
			\centering
			\begin{tabular}{@{}c@{\hspace{0.06\textwidth}}c@{}}
			\begin{tikzpicture}[baseline=(current bounding box.center)]
				\begin{scope}[every node/.style={circle, fill=black, inner sep=0pt, minimum size=0.25cm}]
					\node (n1) at (0,0) {};
					\node (n2) at (-1.3,-1.5) {};
					\node (n3) at (1.3,-1.5) {};
					\node (n4) at (0,-1.1) {};
				\end{scope}
				\draw (n1) -- (n2);
				\draw (n1) -- (n3);
				\node[above=0.12cm, font=\small] at (n1) {$\nodeidx = 1$};
				\node[left=0.15cm, font=\small] at (n2) {$2$};
				\node[right=0.15cm, font=\small] at (n3) {$3$};
				\node[below=0.12cm, font=\small] at (n4) {$4$};
			\end{tikzpicture}
			&
			$\LapMat{\graph} = \begin{pmatrix}
				2 & -1 & -1 & 0 \\
				-1 & 1 & 0 & 0 \\
				-1 & 0 & 1 & 0 \\
				0 & 0 & 0 & 0
			\end{pmatrix}$ \\
			(a) & (b) \\[0.8em]
			\begin{tikzpicture}[scale=2.0, baseline=(current bounding box.center)]
				\draw[->] (-0.15,0) -- (1.2,0) node[below, font=\small] {$v^{(1)}_{\nodeidx}$};
				\draw[->] (0,-0.15) -- (0,1.25) node[above, font=\small] {$v^{(2)}_{\nodeidx}$};
				\draw (0.577,0.03) -- (0.577,-0.03) node[below, font=\small] {$1/\sqrt{3}$};
				\draw (0.03,1) -- (-0.03,1) node[left, font=\small] {$1$};
				\filldraw[black] (0.577,0) circle (1.2pt) node[above right, font=\small] {$\nodeidx = 1, 2, 3$};
				\draw[black, thick] (0,1) circle (1.2pt) node[right=0.1cm, font=\small] {$\nodeidx = 4$};
			\end{tikzpicture}
			&
			$\vv^{(1)} = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 0 \end{pmatrix},
			\quad
			\vv^{(2)} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}$ \\
			(c) & (d)
			\end{tabular}
		\caption{(a) An undirected graph $\graph$ with four nodes
			$\nodeidx = 1, 2, 3, 4$ and unit edge weights, each
			node a data point; node $4$ has no edge, so the
			graph has two connected components.
			(b) Its Laplacian matrix $\LapMat{\graph} \in \reals^{4 \times 4}$,
			whose eigenvalue $0$ has multiplicity two.
			(c) Scatterplot of the nodes using the new
			feature vectors
			$\widetilde{\featurevec}^{(\nodeidx)} = \big( v^{(1)}_{\nodeidx}, v^{(2)}_{\nodeidx} \big)^{\top}$:
			the nodes $1$, $2$, $3$ of the first component share one point
			(filled circle) and node $4$ sits at another (open circle).
			(d) The two eigenvectors
			$\vv^{(1)}, \vv^{(2)} \in \reals^{4}$ for the eigenvalue
			$0$, the normalized indicator vectors of the two
			components
			\label{fig_specclustering_components_dict}}
		\end{figure}
		A graph whose clusters are joined by few edges of
		small weight is a perturbation of a graph with several
		components. The eigenvectors of its smallest
		eigenvalues are then a perturbation of the indicator
		vectors (von Luxburg, 2007, Sect.~7). Spectral clustering
		with $\nrcluster$ clusters therefore uses these
		eigenvectors as new features: node $\nodeidx$ is
		represented by the feature vector
		\begin{equation}
			\label{equ_specclustering_embedding_dict}
			\widetilde{\featurevec}^{(\nodeidx)} \defeq \big(
			v^{(1)}_{\nodeidx}, \ldots, v^{(\nrcluster)}_{\nodeidx}
			\big)^{\top} \in \reals^{\nrcluster} \text{,}
		\end{equation}
		which holds the $\nodeidx$th entries of the $\nrcluster$
		eigenvectors with the smallest eigenvalues.
		$k$-means is then applied to the feature vectors
		$\widetilde{\featurevec}^{(1)}, \ldots, \widetilde{\featurevec}^{(\nrnodes)}$
		(von Luxburg, 2007, Sect.~4).
		Algorithm~\ref{alg_specclustering_dict} states the method in full.
		\begin{algorithm}[H]
		\caption{Spectral clustering (von Luxburg, 2007, Sect.~4)
			\label{alg_specclustering_dict}}
		\begin{algorithmic}[1]
			\Statex \textbf{Input:} weighted graph $\graph$ with
				nodes $\nodeidx = 1, \ldots, \nrnodes$ and
				edge weights $\edgeweight_{\nodeidx,\nodeidx'}$,
				cluster count $\nrcluster$
			\State compute the Laplacian matrix
				\eqref{equ_specclustering_laplacian_dict} of $\graph$
			\State compute eigenvectors
				$\vv^{(1)}, \ldots, \vv^{(\nrcluster)}$ of $\LapMat{\graph}$
				for its $\nrcluster$ smallest eigenvalues
			\State form the feature vectors
				\eqref{equ_specclustering_embedding_dict} for
				$\nodeidx = 1, \ldots, \nrnodes$
			\State run $k$-means with $\nrcluster$ clusters on
				$\widetilde{\featurevec}^{(1)}, \ldots, \widetilde{\featurevec}^{(\nrnodes)}$
			\Statex \textbf{Output:} the cluster of each node
				$\nodeidx$, i.e., of each data point
		\end{algorithmic}
		\end{algorithm}
		For $\nrcluster = 2$ the first eigenvector is constant, so
		the new feature of node $\nodeidx$ is its entry
		$v^{(2)}_{\nodeidx}$ in the Fiedler vector, the
		eigenvector of the algebraic connectivity $\eigval{2}$
		(Fiedler, 1973). The Fiedler vector is orthogonal
		to the constant vector, so it has entries of both signs,
		and $k$-means on its entries amounts to a threshold. On the
		days at Krems, the graph is connected with
		$\eigval{2} = 0.044$ and $\eigval{3} = 0.179$, and the
		Fiedler vector has $190$ negative and $176$ positive entries
		(Fig.~\ref{fig_specclustering_krems_dict}(b)). $k$-means on
		these entries delivers $192$ cold days and $174$ warm days. Every
		day of January, February, November, and December is a cold day,
		and every day from May to August is a warm day. Each of the two
		clusters is connected in the graph, and the two
		are joined by $25$ of the $2209$ edges. $k$-means on the raw
		feature vectors $\featurevec^{(\nodeidx)}$, whose
		clusters are always convex regions of the
		feature space, delivers almost the same hard clustering:
		the two methods disagree on two days of October only. The methods
		differ once the clusters are not convex.
		Data points on two concentric rings are joined by the edges
		of a $k$-NN graph along each ring; spectral clustering returns
		the rings, while $k$-means on the raw feature vectors cuts
		through them (Hastie et al., 2009, Sect.~14.5.3).
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}
		\begin{groupplot}[
			group style={group size=2 by 1, horizontal sep=1.7cm},
			width=0.5\linewidth, height=0.46\linewidth,
			axis lines=left,
			tick label style={font=\scriptsize},
			label style={font=\scriptsize, align=center},
			legend style={draw=none, fill=none, font=\scriptsize},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={morning minimum temperature\\(a) the $10$-nearest-neighbor graph of the $366$ days},
				ylabel={maximum daytime temperature},
				xmin=-12, xmax=24, ymin=-6, ymax=46,
				legend style={at={(0.03,0.97)}, anchor=north west}]
			\addplot[gray!60, line width=0.25pt, forget plot, unbounded coords=jump]
				table[col sep=comma, x=tmin, y=tmax]{specclustering_edges.csv};
			\addplot[only marks, mark=*, mark size=1.1pt, black,
				restrict expr to domain={\thisrow{cluster}}{0:0}]
				table[col sep=comma, x=tmin, y=tmax]{specclustering_nodes.csv};
			\addlegendentry{cold days (filled circles)}
			\addplot[only marks, mark=square*, mark size=1.1pt, black,
				restrict expr to domain={\thisrow{cluster}}{1:1}]
				table[col sep=comma, x=tmin, y=tmax]{specclustering_nodes.csv};
			\addlegendentry{warm days (filled squares)}
			\nextgroupplot[
				xlabel={day of the year $2024$\\(b) entries of the Fiedler vector $\vv^{(2)}$},
				ylabel={$v^{(2)}_{\nodeidx}$},
				xmin=0, xmax=370, ymin=-0.09, ymax=0.125,
				ytick={-0.05,0,0.05,0.1}, scaled y ticks=false,
				yticklabel style={/pgf/number format/fixed, /pgf/number format/precision=2},
				legend style={at={(0.03,0.97)}, anchor=north west}]
			\addplot[gray, dashed, thin, forget plot] coordinates {(1,0) (366,0)};
			\addplot[black, line width=0.4pt]
				table[col sep=comma, x=doy, y=v2]{specclustering_fiedler.csv};
			\addlegendentry{every day (thin curve)}
			\addplot[only marks, mark=o, mark size=1.8pt, black,
				restrict expr to domain={\thisrow{cluster}}{0:0}]
				table[col sep=comma, x=doy, y=v2]{specclustering_plot.csv};
			\addlegendentry{cold days (circles)}
			\addplot[only marks, mark=square, mark size=1.7pt, black,
				restrict expr to domain={\thisrow{cluster}}{1:1}]
				table[col sep=comma, x=doy, y=v2]{specclustering_plot.csv};
			\addlegendentry{warm days (squares)}
		\end{groupplot}
		\end{tikzpicture}
		\caption{(a) The $366$ days of $2024$ at Krems, each a node drawn
			at its feature vector, and the $2209$ edges (thin gray lines)
			of the $10$-nearest-neighbor graph; all days are drawn, since
			the connectivity of the graph is what the panel shows.
			The two clusters found by spectral clustering with
			$\nrcluster = 2$ are the cold days (filled circles) and the
			warm days (filled squares). (b) The entry $v^{(2)}_{\nodeidx}$
			of the Fiedler vector for every day (thin curve) against
			the day of the year, with every $18$th day, $21$ days in all,
			marked as a cold day (circles) or a warm day (squares); the
			dashed line is the zero level. Data generated by
			\texttt{pythondemos/specclustering.py}
			\label{fig_specclustering_krems_dict}}
		\end{figure}
		Spectral clustering approximately solves a graph partitioning
		problem (von Luxburg, 2007, Sect.~5). For a subset
		$\cluster \subseteq \nodes$ of the nodes, the cut
		$\operatorname{cut}(\cluster) \defeq \sum_{\nodeidx \in \cluster}
		\sum_{\nodeidx' \notin \cluster} \edgeweight_{\nodeidx,\nodeidx'}$
		is the total weight of the edges leaving $\cluster$. The subset
		with the smallest cut is often a single node, so the ratio cut
		divides the cut by the sizes of both parts
		(Hagen and Kahng, 1992; von Luxburg, 2007, Sect.~5),
		\begin{equation}
			\label{equ_specclustering_ratiocut_dict}
			\operatorname{RatioCut}(\cluster) \defeq
			\operatorname{cut}(\cluster) \bigg( \frac{1}{|\cluster|} +
			\frac{1}{|\nodes \setminus \cluster|} \bigg) \text{.}
		\end{equation}
		Minimizing the ratio cut \eqref{equ_specclustering_ratiocut_dict}
		over all subsets $\cluster$ is NP-hard
		(von Luxburg, 2007, Sect.~5.1). The vector $\vu$
		with entries
		$u_{\nodeidx} = \sqrt{|\nodes \setminus \cluster| / |\cluster|}$
		for $\nodeidx \in \cluster$ and
		$u_{\nodeidx} = -\sqrt{|\cluster| / |\nodes \setminus \cluster|}$
		otherwise satisfies
		$\vu^{\top} \LapMat{\graph} \vu = \nrnodes \operatorname{RatioCut}(\cluster)$
		by the quadratic form \eqref{equ_specclustering_quadform_dict},
		as well as $\vu^{\top} \mathbf{1} = 0$ and
		$\normgeneric{\vu}{2}^{2} = \nrnodes$ (von Luxburg, 2007, Sect.~5.1).
		Dropping the requirement that $\vu$ takes only these two values
		leaves the relaxed problem
		\begin{equation}
			\label{equ_specclustering_relaxed_dict}
			\min_{\vu \in \reals^{\nrnodes}} \vu^{\top} \LapMat{\graph} \vu
			\quad \text{subject to } \vu^{\top} \mathbf{1} = 0
			\text{ and } \normgeneric{\vu}{2}^{2} = \nrnodes \text{,}
		\end{equation}
		and the relaxed problem \eqref{equ_specclustering_relaxed_dict}
		has the minimum $\nrnodes \eigval{2}$, attained at
		$\sqrt{\nrnodes}\, \vv^{(2)}$ by the Rayleigh--Ritz theorem
		(von Luxburg, 2007, Sect.~5.1). Thresholding the
		Fiedler vector turns this minimizer back into a subset, and
		every subset has a ratio cut of at least $\eigval{2}$. On the days
		at Krems, the spectral bipartition has a ratio cut of $0.274$, the
		bipartition of $k$-means on the raw feature vectors one of
		$0.383$ (it cuts $35$ edges), and a random bipartition one of
		$12.5$, against $\eigval{2} = 0.044$. For general $\nrcluster$,
		the same relaxation of the ratio cut leads to the first
		$\nrcluster$ eigenvectors and the feature vector
		\eqref{equ_specclustering_embedding_dict}
		(von Luxburg, 2007, Sect.~5.2). Replacing $|\cluster|$ by the
		sum of the node degrees in $\cluster$ gives the normalized
		cut (Shi and Malik, 2000), whose relaxation leads to the
		eigenvectors of the normalized Laplacian matrix
		$\degreemtx^{-1} \LapMat{\graph}$ (von Luxburg, 2007, Sect.~5.3).
		A variant uses the eigenvectors of
		$\degreemtx^{-1/2} \LapMat{\graph} \degreemtx^{-1/2}$ and scales
		each feature vector \eqref{equ_specclustering_embedding_dict}
		to unit norm (Ng et al., 2001).
\par
		Spectral clustering is not a fixed-point iteration: the EVD
		is computed once, and iterations occur only in the
		$k$-means step. That step is empirical risk minimization (ERM) with the
		clustering error measured in the
		feature vectors \eqref{equ_specclustering_embedding_dict}
		rather than in the raw ones. The learned hypothesis assigns
		a cluster to each node of the given graph only; a new
		data point needs a new node, a new Laplacian matrix, and a new
		EVD. The hyperparameters are the number $\nrcluster$
		of clusters and the construction of the graph: how
		many neighbors the $k$-NN graph connects, or the bandwidth
		of a Gaussian kernel that turns distances into
		edge weights (von Luxburg, 2007, Sect.~8.1). A gap in the
		spectrum, as between $\eigval{2} = 0.044$ and
		$\eigval{3} = 0.179$ at Krems, is the usual informal guide to
		$\nrcluster$ (von Luxburg, 2007, Sect.~8.3); with
		$\nrcluster = 3$, the days at Krems split into $107$ cold, $170$
		mild, and $89$ warm days, each cluster connected in
		the graph.
\par
		Spectral clustering is used for image segmentation, where
		the nodes are pixels or patches and the edge weights
		decrease with the difference in color and in position
		(Shi and Malik, 2000), and for community detection in social
		networks, where the edges are given and no feature vector is
		needed (Fortunato, 2010).

\subsection{Cross References}
clustering, graph clustering, cluster, $k$-means, clustering error, hard clustering, Laplacian matrix, adjacency matrix, node degree, EVD, eigenvalue, eigenvector, Fiedler vector, algebraic connectivity, connected, psd, $k$-NN graph, similarity graph, weighted graph, edge weight, image segmentation, hyperparameter

\subsection{References}
\begin{enumerate}
  \item Fiedler (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), pp.~298--305.
  \item Fortunato (2010). Community detection in graphs. Physics Reports, 486(3--5), pp.~75--174.
  \item Hagen and Kahng (1992). New Spectral Methods for Ratio Cut Partitioning and Clustering. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 11(9), pp.~1074--1085.
  \item von Luxburg (2007). A tutorial on spectral clustering. Statist. Comput., 17(4), pp.~395--416.
  \item Ng et al. (2001). On Spectral Clustering: Analysis and an Algorithm. In: Adv. Neural Inf. Process. Syst., pp.~849--856.
  \item Shi and Malik (2000). Normalized Cuts and Image Segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8), pp.~888--905.
  \item Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed., Springer Science+Business Media, New York, NY, USA.
\end{enumerate}

\end{document}
