\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{\clusteridx}{c}
\newcommand{\datacluster}[1]{\mathcal{C}^{(#1)}}
\newcommand{\defeq}{:=}
\newcommand{\edgeweight}{A}
\newcommand{\featurevec}{\vx}
\newcommand{\graph}{\mathcal{G}}
\newcommand{\mL}[0]{{\bf L}}
\newcommand{\nodedegree}[1]{d^{(#1)}}
\newcommand{\nodeidx}{i}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\nrcluster}{k}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\samplesize}{m}
\newcommand{\vs}[0]{{\bf s}}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{graph 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}
Graph clustering decomposes the nodes of a
		weighted graph, one node per data point, into
		clusters: subsets of nodes with a large total
		edge weight inside and a small total edge weight to
		the rest. Each edge weight expresses the similarity of two
		data points. The graph is either a
		similarity graph built from feature vectors, such as a
		$k$-nearest-neighbor graph ($k$-NN graph), or given by the application, such as papers
		joined by citations or users joined by friendships. The cut of a
		cluster is the total edge weight of the edges leaving
		it, and the ratio cut of a clustering is the sum of the
		cuts of its clusters, each divided by the number of nodes
		in the cluster, which keeps a single node from being split
		off. Finding the partition with the smallest ratio cut is
		computationally hard, so spectral clustering approximates it
		through eigenvectors of the Laplacian matrix,
		flow-based clustering through network flows, and
		convex clustering through a penalty term weighted by the
		edge weights. Applications include image segmentation,
		with pixels as nodes, and the detection of communities in social
		networks.

\subsection{Definition}
Consider every $18$th day of
		$2024$ at Krems an der Donau, $21$ days in all, each a
		data point with a feature vector $\featurevec \in
		\reals^{2}$ that holds the morning minimum and the maximum
		daytime temperature. Instead of measuring how far apart two days
		are, record which days are similar. Each day is a node of a
		graph, and two days are joined by an edge if one is among
		the six nearest neighbors of the other. The edge carries
		an edge weight between $0$ and $1$ that is close to $1$
		for days with almost the same temperatures
		(Fig.~\ref{fig_graphclustering_dict}(a)). Graph clustering
		decomposes the nodes of such a graph into clusters:
		subsets of nodes with a large total edge weight inside and
		a small total edge weight to the rest of the graph.
		For the $21$ days, the two clusters are $11$ cold days
		and $10$ warm days, joined by a single edge.
\par
		The graph is built from feature vectors, as a
		similarity graph such as the $k$-nearest-neighbor graph ($k$-NN graph) with Gaussian
		edge weights (Hastie et al., 2009, Sect.~14.5.3;
		von Luxburg, 2007, Sect.~2), or it is given by the
		application: scientific papers joined by citations, users of a
		social network joined by friendships, or web pages joined by
		links. In the second case the data points need no
		feature vectors at all, which is the main reason for
		clustering a graph rather than a feature space.
\par
		Formally, the data points are the nodes $\nodeidx = 1,
		\ldots, \samplesize$ of a weighted graph $\graph$ that is
		an undirected graph with the edge weights
		$\edgeweight_{\nodeidx,\nodeidx'} = \edgeweight_{\nodeidx',\nodeidx}
		\geq 0$, where $\edgeweight_{\nodeidx,\nodeidx'} = 0$ means
		that the nodes $\nodeidx$ and $\nodeidx'$ are not joined by an
		edge. The cut of a cluster $\cluster \subseteq \{1,
		\ldots, \samplesize\}$ is the total edge weight of the
		edges that leave it,
		\begin{equation}
			\label{equ_graphclustering_cut_dict}
			\operatorname{cut}(\cluster) \defeq
			\sum_{\nodeidx \in \cluster} \,
			\sum_{\nodeidx' \notin \cluster}
			\edgeweight_{\nodeidx,\nodeidx'} \text{.}
		\end{equation}
		The cut \eqref{equ_graphclustering_cut_dict} of a single node
		is its node degree $\nodedegree{\nodeidx} =
		\sum_{\nodeidx'=1}^{\samplesize} \edgeweight_{\nodeidx,\nodeidx'}$.
		For a vector $\vs \in \{-1, 1\}^{\samplesize}$
		with $s_{\nodeidx} = 1$ for $\nodeidx \in \cluster$ and
		$s_{\nodeidx} = -1$ otherwise, the cut is the quadratic form
		$\operatorname{cut}(\cluster) = (1/4) \, \vs^{\top}
		\LapMat{\graph} \vs$ of the Laplacian matrix
		$\LapMat{\graph}$ (von Luxburg, 2007, Sect.~5.1). A
		clustering into $\nrcluster$ clusters
		$\datacluster{1}, \ldots, \datacluster{\nrcluster}$ assigns
		each node to exactly one of them, and the sum of their cuts
		counts every edge between two clusters twice. Choosing
		the clusters to minimize this sum alone often splits off
		a single node (von Luxburg, 2007, Sect.~5). For the $21$ days,
		the smallest cut over all $2^{20}$ two-way partitions is $0.32$,
		for the cold and the warm days, but the second smallest, $1.15$,
		already splits off the single day $26$ December, the day with
		the smallest node degree.
\par
		The ratio cut divides the cut of each cluster by its
		number of nodes (Hagen and Kahng, 1992),
		\begin{equation}
			\label{equ_graphclustering_ratiocut_dict}
			\sum_{\clusteridx=1}^{\nrcluster}
			\frac{\operatorname{cut}(\datacluster{\clusteridx})}
			{|\datacluster{\clusteridx}|} \text{.}
		\end{equation}
		A small cluster is charged a large share of its cut, so
		the ratio cut \eqref{equ_graphclustering_ratiocut_dict} favors
		clusters of similar size. The normalized cut divides by
		the total node degree of the cluster instead
		(Shi and Malik, 2000), so that a cluster is measured by
		its edge weights rather than by its number of nodes
		(von Luxburg, 2007, Sect.~5). For the $21$ days, the smallest
		ratio cut over all two-way partitions is $0.061$, again for the
		cold and the warm days. Splitting off $26$ December has the
		ratio cut $1.21$, $20$ times as much. Ranked by the cut, this
		split was the second best partition; ranked by the ratio cut,
		it is the $54$th. A random partition into $11$ and $10$ days
		cuts $43$ of the $80$ edges, with the cut $24.9$ and the ratio
		cut $4.75$. Over all $167960$ partitions of these sizes, the
		ratio cut averages $4.67$. Finding a partition with the smallest
		ratio cut or normalized cut is computationally hard
		(von Luxburg, 2007, Sect.~5). For $21$ nodes every partition can
		be enumerated, for the $12288$ patches of a photograph it cannot.
\par
		Graph clustering methods differ in how they approximate a
		minimizer. Spectral clustering relaxes the constraint that
		each node is assigned to one cluster and solves the
		relaxed problem through eigenvectors of the Laplacian matrix
		(von Luxburg, 2007, Sect.~5; Ng et al., 2001). For the
		ratio cut \eqref{equ_graphclustering_ratiocut_dict} of a
		connected graph and $\nrcluster = 2$, the relaxed
		minimizer is the Fiedler vector (Fiedler, 1973), the
		eigenvector of the second smallest eigenvalue, the
		algebraic connectivity. The nodes are then split by the signs of its
		entries or at the best of the $\samplesize - 1$ thresholds along
		its sorted entries. For the $21$ days, whose graph is
		connected, the Fiedler vector is negative on the $11$
		cold days and positive on the $10$ warm days, and the best of the
		$20$ thresholds returns the exact minimizer of the ratio cut
		(Fig.~\ref{fig_graphclustering_dict}(b)).
		Flow-based clustering builds a feature vector for each
		node from network flows between selected nodes and applies
		$k$-means to these feature vectors
		(SarcheshmehPour et al., 2021). Convex clustering uses both
		the graph and the feature vectors of the nodes. It
		gives each node its own cluster centroid and adds a
		penalty term, weighted by the edge weights, that
		pulls the cluster centroids of joined nodes together
		until they coincide (Hocking et al., 2011). The nodes that share
		a cluster centroid form a cluster.
\par
		Graph clustering is unsupervised learning: the nodes carry
		no labels, and the hypothesis learned is the
		assignment of each node to a cluster index. The cut
		\eqref{equ_graphclustering_cut_dict} is a sum over the edges
		rather than over the data points. An edge costs its
		edge weight when its two nodes are assigned to different
		clusters and nothing otherwise, so the cut is the
		generalized total variation (GTV) of the assignment for the discrepancy that is
		$1$ for two different indices and $0$ for equal ones. Without the
		denominator of the ratio cut
		\eqref{equ_graphclustering_ratiocut_dict}, assigning all but
		one node to the same cluster would be the cheapest
		choice, in the way that a training error of zero is reached by
		a hypothesis that is useless elsewhere.
\par
		A photograph is clustered into regions by graph clustering
		with the pixels as nodes and edge weights that are large
		for nearby pixels of similar color, which is the
		image segmentation method that introduced the normalized
		cut (Shi and Malik, 2000). In a social network, graph clustering
		with the friendships as edges finds communities, groups of
		users with many friendships inside and few to the rest
		(Fortunato, 2010).
		\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.44\linewidth,
			axis lines=left,
			tick label style={font=\scriptsize},
			label style={font=\scriptsize, align=center},
			legend style={draw=none, fill=none, font=\scriptsize,
				at={(0.03,0.97)}, anchor=north west},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={morning minimum temperature\\(a) the graph over the $21$ days},
				ylabel={maximum daytime temperature},
				xmin=-9, xmax=23, ymin=0, ymax=40]
			\addplot[gray!70, thin, forget plot, -,
				quiver={u=\thisrow{u}, v=\thisrow{v}}]
				table[col sep=comma, x=x, y=y]{graphclustering_edges_within.csv};
			\addplot[black, thick, dashed, forget plot, -,
				quiver={u=\thisrow{u}, v=\thisrow{v}}]
				table[col sep=comma, x=x, y=y]{graphclustering_edges_cut.csv};
			\addplot[only marks, mark=o, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{cluster}}{0:0}]
				table[col sep=comma, x=tmin, y=tmax]{graphclustering_nodes_plot.csv};
			\addlegendentry{cold days (circles)}
			\addplot[only marks, mark=square, mark size=1.5pt, black,
				restrict expr to domain={\thisrow{cluster}}{1:1}]
				table[col sep=comma, x=tmin, y=tmax]{graphclustering_nodes_plot.csv};
			\addlegendentry{warm days (squares)}
			\nextgroupplot[
				xlabel={number of days on the negative side\\(b) the $20$ cuts along the Fiedler vector},
				ylabel={ratio cut}, xmin=0, xmax=21, ymin=0, ymax=5.5,
				legend style={at={(0.03,0.97)}, anchor=north west}]
			\addplot[black, thick, mark=*, mark size=1.2pt]
				table[col sep=comma, x=nfirst, y=ratiocut]{graphclustering_sweep.csv};
			\addlegendentry{cuts along the Fiedler vector (solid curve)}
			\addplot[black, dashed, thin]
				table[col sep=comma, x=nfirst, y=ratiocut]{graphclustering_random.csv};
			\addlegendentry{random partition (dashed line)}
		\end{groupplot}
		\end{tikzpicture}
		\caption{(a) Every $18$th of the $366$ days of $2024$ at Krems,
			$21$ days, as the nodes of a graph: two days are
			joined if one is among the six nearest neighbors of
			the other, and an edge carries the edge weight
			$\exp(-\normgeneric{\featurevec - \featurevec'}{2}^{2}/50)$
			computed from the feature vectors of its two days. The partition
			with the smallest ratio cut
			\eqref{equ_graphclustering_ratiocut_dict}, $0.061$, consists
			of $11$ cold days (circles) and $10$ warm days (squares);
			$79$ edges stay inside a cluster (thin gray segments)
			and one edge, with the edge weight $0.32$, is cut
			(dashed segment).
			(b) The ratio cut of the $20$ partitions that put the days
			with the smallest entries of the Fiedler vector on one
			side (solid curve): the minimum, at $11$ days, is the
			partition in (a). The dashed line is the ratio cut $4.75$ of
			a random partition into $11$ and $10$ days. Data generated
			by \texttt{pythondemos/graphclustering.py}
			\label{fig_graphclustering_dict}}
		\end{figure}

\subsection{Cross References}
clustering, cluster, graph, weighted graph, undirected graph, edge weight, similarity graph, $k$-NN graph, node degree, Laplacian matrix, Fiedler vector, algebraic connectivity, eigenvector, spectral clustering, flow-based clustering, convex clustering, $k$-means, GTV, image segmentation, unsupervised learning

\subsection{References}
\begin{enumerate}
  \item Fiedler (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), pp.~298--305.
  \item SarcheshmehPour et al. (2021). Flow-Based Clustering and Spectral Clustering: A Comparison. In: 2021 55th Asilomar Conf. Signals, Syst., Comput., pp.~1292--1296.
  \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 Hocking et al. (2011). Clusterpath: An Algorithm for Clustering using Convex Fusion Penalties. In: Proc. of the 28th International Conference on Machine Learning,.
  \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}
