\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{\LapMatEntry}[3]{L^{(#1)}_{#2,#3}}
\newcommand{\defeq}{:=}
\newcommand{\edge}[2]{\{#1,#2\}}
\newcommand{\edges}{\mathcal{E}}
\newcommand{\edgeweight}{A}
\newcommand{\eigval}[1]{\lambda_{#1}}
\newcommand{\genericnodeset}{\mathcal{A}}
\newcommand{\graph}{\mathcal{G}}
\newcommand{\mA}[0]{{\bf A}}
\newcommand{\mD}[0]{{\bf D}}
\newcommand{\mI}{\mathbf{I}}
\newcommand{\mL}[0]{{\bf L}}
\newcommand{\nodedegree}[1]{d^{(#1)}}
\newcommand{\nodeidx}{i}
\newcommand{\nodes}{\mathcal{V}}
\newcommand{\nrnodes}{n}
\newcommand{\pair}[2]{\left( #1,#2 \right)}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\regparam}{\alpha}
\newcommand{\truelabel}{y}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{Laplacian matrix}

\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}
The Laplacian matrix of a weighted graph with
		$\nrnodes$ nodes is the $\nrnodes \times \nrnodes$ matrix
		$\LapMat{\graph} = \mD^{(\graph)} - \mA^{(\graph)}$, the degree
		matrix minus the adjacency matrix of the
		edge weights. Its quadratic form $\vx^{\top}
		\LapMat{\graph} \vx$ is the sum, over the edges, of the
		edge weight times the squared difference of the two entries
		of $\vx$ at the ends of the edge. The Laplacian matrix is
		therefore a symmetric matrix and positive semi-definite (psd), the constant
		vector is an eigenvector with eigenvalue $0$,
		and the multiplicity of the eigenvalue $0$ equals the number
		of connected components of the graph. Two normalized
		variants divide the edge weights by the node degrees;
		they share their eigenvalues, which lie between $0$ and
		$2$. In machine learning (ML), the quadratic form is the penalty term of
		Laplacian regularization, which makes the values learned at
		connected nodes similar and predicts the value at an
		unlabeled node as the weighted average of its neighbors.
		The eigenvectors of its smallest eigenvalues are the
		coordinates that spectral clustering feeds to $k$-means.

\subsection{Definition}
Twelve weather stations around
		Krems an der Donau, from Melk and Zwettl in the west to Retz and
		Langenlebarn in the east, each recorded a mean temperature for the
		year $2024$: $12.6$ degrees Celsius at Krems, $9.6$ on the
		Jauerling mountain. Two stations at most $35$ km apart are joined
		by an edge whose weight decays with their distance, so the
		stations form a weighted graph $\graph$ with $27$ edges
		(Fig.~\ref{fig_LapMat_krems_dict}(a)). How much does the
		temperature vary along the edges of $\graph$? One answer is the
		sum, over the edges, of the edge weight times the squared
		difference of the two temperatures at its ends. The Laplacian
		matrix of $\graph$ is the matrix that computes this sum as
		a quadratic form in the vector of the twelve temperatures.
\par
		Consider an undirected graph $\graph = \pair{\nodes}{\edges}$
		with nodes $\nodes = \{1, \ldots, \nrnodes\}$ and nonnegative
		edge weights $\edgeweight_{\nodeidx,\nodeidx'} =
		\edgeweight_{\nodeidx',\nodeidx}$, where
		$\edgeweight_{\nodeidx,\nodeidx'} = 0$ when $\graph$ has no edge
		$\edge{\nodeidx}{\nodeidx'}$ (von Luxburg, 2007, Sect.~2.1). The
		edge weights are the entries of the adjacency matrix
		$\mA^{(\graph)} \in \reals^{\nrnodes \times \nrnodes}$, and the
		node degree $\nodedegree{\nodeidx} \defeq
		\sum_{\nodeidx'=1}^{\nrnodes} \edgeweight_{\nodeidx,\nodeidx'}$
		of node $\nodeidx$ is the sum of the weights of its edges. The
		Laplacian matrix of $\graph$ is the difference
		\begin{equation}
			\label{equ_LapMat_def_dict}
			\LapMat{\graph} \defeq \mD^{(\graph)} - \mA^{(\graph)}
			\text{, with the degree matrix } \mD^{(\graph)} \defeq
			\operatorname{diag}\big\{ \nodedegree{1}, \ldots,
			\nodedegree{\nrnodes} \big\} \text{.}
		\end{equation}
		The diagonal entry $\LapMatEntry{\graph}{\nodeidx}{\nodeidx}$ of
		the Laplacian matrix \eqref{equ_LapMat_def_dict} is the
		node degree $\nodedegree{\nodeidx}$, and the off-diagonal
		entry $\LapMatEntry{\graph}{\nodeidx}{\nodeidx'}$ is the negated
		edge weight $-\edgeweight_{\nodeidx,\nodeidx'}$, so every row
		sums to zero (Hastie et al., 2009, Sect.~14.5.3;
		von Luxburg, 2007, Sect.~3.1). Fig.~\ref{fig_lap_mtx_dict}
		carries out the construction for a graph with three nodes
		and two edges. For the station graph, the edge between Krems
		and Langenlois, $8$ km apart, has weight $0.92$, the longest edges
		have weight $0.23$, and Krems has degree $3.18$ from its six
		neighbors.
		\begin{figure}[H]
		\begin{center}
		\begin{minipage}{0.32\textwidth}
			\centering
			\begin{tikzpicture}[font=\small,
				vertex/.style={draw, circle, inner sep=2pt, minimum size=6mm}]
				\node[vertex] (v1) at (0,0) {$1$};
				\node[vertex] (v2) at (2.4,1.0) {$2$};
				\node[vertex] (v3) at (2.4,-1.0) {$3$};
				\draw[thick] (v1) -- node[above, sloped, font=\scriptsize] {$\edgeweight_{1,2} = 1$} (v2);
				\draw[thick] (v1) -- node[below, sloped, font=\scriptsize] {$\edgeweight_{1,3} = 1$} (v3);
			\end{tikzpicture}
		\end{minipage}
		\begin{minipage}{0.64\textwidth}
			\[
			\LapMat{\graph} = \mD^{(\graph)} - \mA^{(\graph)}
			= \begin{pmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}
			- \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}
			= \begin{pmatrix} 2 & -1 & -1 \\ -1 & 1 & 0 \\ -1 & 0 & 1 \end{pmatrix}
			\]
		\end{minipage}
		\end{center}
		\caption{An undirected graph with three nodes and two edges,
			both with edge weight $1$, and its Laplacian matrix
			\eqref{equ_LapMat_def_dict}. Node $1$ has degree $2$ and nodes
			$2$ and $3$ have degree $1$, which are the diagonal entries;
			each edge contributes $-1$ to the two off-diagonal entries it
			joins, and the remaining entries are $0$
			\label{fig_lap_mtx_dict}}
		\end{figure}
		The Laplacian matrix is characterized by its quadratic form. For
		every vector $\vx = (x_{1}, \ldots, x_{\nrnodes})^{\top} \in
		\reals^{\nrnodes}$, one entry per node,
		\begin{equation}
			\label{equ_LapMat_quadform_dict}
			\vx^{\top} \LapMat{\graph} \vx
			= \sum_{\edge{\nodeidx}{\nodeidx'} \in \edges}
			\edgeweight_{\nodeidx,\nodeidx'}
			\big( x_{\nodeidx} - x_{\nodeidx'} \big)^{2} \text{.}
		\end{equation}
		The identity follows from expanding $\vx^{\top} \mD^{(\graph)} \vx
		- \vx^{\top} \mA^{(\graph)} \vx = \sum_{\nodeidx=1}^{\nrnodes}
		\nodedegree{\nodeidx} x_{\nodeidx}^{2} - \sum_{\nodeidx=1}^{\nrnodes}
		\sum_{\nodeidx'=1}^{\nrnodes} \edgeweight_{\nodeidx,\nodeidx'}
		x_{\nodeidx} x_{\nodeidx'}$ and collecting the two terms of each
		edge (Hastie et al., 2009, Sect.~14.5.3;
		von Luxburg, 2007, Prop.~1). For the station graph and
		the vector of mean temperatures, the quadratic form
		\eqref{equ_LapMat_quadform_dict} equals $26.9$ squared degrees;
		the edge between Jauerling and Melk, with weight $0.79$ and
		a temperature difference of $2.8$ degrees, contributes $6.0$ of
		it.
\par
		Three properties of the Laplacian matrix follow from the
		quadratic form \eqref{equ_LapMat_quadform_dict}
		(von Luxburg, 2007, Prop.~1, Prop.~2; Mohar, 1991).
		First, $\LapMat{\graph}$ is a
		symmetric matrix and positive semi-definite (psd), since every term of the sum
		is nonnegative, so its eigenvalues are real and can be
		ordered as $0 \leq \eigval{1} \leq \eigval{2} \leq \ldots \leq
		\eigval{\nrnodes}$. Second, the constant vector
		$\mathbf{1} = (1, \ldots, 1)^{\top}$ makes every term vanish, and
		$\LapMat{\graph} \mathbf{1} = \mathbf{0}$ since every row sums to
		zero, so $\eigval{1} = 0$ with the eigenvector $\mathbf{1}$.
		Third, the multiplicity of the eigenvalue $0$ equals the
		number of connected components of $\graph$. A vector
		$\vx$ with $\vx^{\top} \LapMat{\graph} \vx = 0$ takes the same
		value at the two ends of every edge, so it is constant on each
		component, and the indicator vectors of the components
		span the nullspace of $\LapMat{\graph}$. The station
		graph is connected, so $\eigval{1} = 0$ is simple and
		$\eigval{2} = 0.25$ is positive. Joining only stations at most
		$25$ km apart leaves Langenlebarn without an edge and the
		graph with two components, and the limit $20$ km leaves six
		components; the eigenvalue $0$ then has multiplicity two
		and six (Fig.~\ref{fig_LapMat_krems_dict}(b)). The
		second-smallest eigenvalue $\eigval{2}$ is the
		algebraic connectivity of $\graph$, and the eigenvector of
		$\eigval{2}$ is the Fiedler vector (Fiedler, 1973). The
		signs of its entries split the nodes into two clusters with
		few edges between them (Fiedler, 1975). For the station
		graph, the three stations more than $20$ km east of Krems,
		Langenlebarn, Sch\"{o}ngrabern, and Retz, have negative entries and
		the other nine have positive entries.
		\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={km east of Krems\\(a) the station graph},
				ylabel={km north of Krems},
				xmin=-40, xmax=52, ymin=-32, ymax=46]
			\addplot[gray!70, thin, -, forget plot,
				quiver={u=\thisrow{u}, v=\thisrow{v}},
				restrict expr to domain={\thisrow{w}}{0:0.4999}]
				table[col sep=comma, x=x, y=y]{LapMat_edges.csv};
			\addplot[gray!70, line width=1.3pt, -, forget plot,
				quiver={u=\thisrow{u}, v=\thisrow{v}},
				restrict expr to domain={\thisrow{w}}{0.5:1}]
				table[col sep=comma, x=x, y=y]{LapMat_edges.csv};
			\addplot[only marks, mark=*, mark size=1.8pt, black,
				nodes near coords, point meta=explicit symbolic,
				visualization depends on={value \thisrow{anchor} \as \anc},
				every node near coord/.append style={font=\tiny, anchor=\anc, inner sep=1.5pt},
				restrict expr to domain={\thisrow{side}}{1:1}]
				table[col sep=comma, x=east, y=north, meta=name]{LapMat_nodes.csv};
			\addplot[only marks, mark=square*, mark size=1.7pt, black,
				nodes near coords, point meta=explicit symbolic,
				visualization depends on={value \thisrow{anchor} \as \anc},
				every node near coord/.append style={font=\tiny, anchor=\anc, inner sep=1.5pt},
				restrict expr to domain={\thisrow{side}}{0:0}]
				table[col sep=comma, x=east, y=north, meta=name]{LapMat_nodes.csv};
			\nextgroupplot[
				xlabel={index $\nodeidx$ of the eigenvalue\\(b) eigenvalues of the Laplacian matrix of three graphs},
				ylabel={$\nodeidx$-th smallest eigenvalue $\eigval{\nodeidx}$},
				xmin=0.5, xmax=12.5, ymin=-0.15, ymax=5.6,
				xtick={1,...,12},
				legend style={at={(0.03,0.97)}, anchor=north west}]
			\addplot[only marks, mark=*, mark size=1.8pt, black]
				table[col sep=comma, x=i, y=lam35]{LapMat_eigenvalues.csv};
			\addlegendentry{$35$ km (filled circles)}
			\addplot[only marks, mark=square, mark size=1.8pt, black]
				table[col sep=comma, x=i, y=lam25]{LapMat_eigenvalues.csv};
			\addlegendentry{$25$ km (squares)}
			\addplot[only marks, mark=triangle, mark size=2.3pt, black]
				table[col sep=comma, x=i, y=lam20]{LapMat_eigenvalues.csv};
			\addlegendentry{$20$ km (triangles)}
		\end{groupplot}
		\end{tikzpicture}
		\caption{(a) Twelve weather stations around Krems an der Donau,
			drawn at their positions in km east and north of Krems and
			joined by an edge when at most $35$ km apart; a thick line
			marks an edge weight above $1/2$, a thin line one below.
			Filled circles mark the stations with a nonnegative entry of
			the Fiedler vector, filled squares those with a negative
			entry. (b) The eigenvalues of the Laplacian matrix in
			increasing order for the graph in (a) (filled circles)
			and for the graphs that join stations at most $25$ km
			(squares) and $20$ km (triangles) apart, the legend naming the
			largest edge length. The eigenvalue
			$0$ appears once, twice, and six times, the number of
			connected components of each graph. Data generated
			by \texttt{pythondemos/LapMat.py}
			\label{fig_LapMat_krems_dict}}
		\end{figure}
		Two normalized variants of the Laplacian matrix divide the
		edge weights by the node degrees
		(von Luxburg, 2007, Sect.~3.2),
		\[
		\mL^{(\mathrm{sym})} \defeq \big( \mD^{(\graph)} \big)^{-1/2}
		\LapMat{\graph} \big( \mD^{(\graph)} \big)^{-1/2}
		\text{ and }
		\mL^{(\mathrm{rw})} \defeq \big( \mD^{(\graph)} \big)^{-1}
		\LapMat{\graph} \text{,}
		\]
		for a graph without isolated nodes. The first is a
		symmetric matrix whose quadratic form is the sum
		\eqref{equ_LapMat_quadform_dict} with each $x_{\nodeidx}$ replaced
		by $x_{\nodeidx} / \sqrt{\nodedegree{\nodeidx}}$. The second is
		$\mI - \big( \mD^{(\graph)} \big)^{-1} \mA^{(\graph)}$, the
		identity matrix minus the transition matrix of the
		random walk on $\graph$ that moves to a neighbor with
		probability proportional to the edge weight. The two
		variants have the same eigenvalues, which lie between $0$
		and $2$ (Chung, 1997, Lemma~1.7); the
		eigenvalue $0$ has the eigenvector $\mathbf{1}$ for
		$\mL^{(\mathrm{rw})}$ and $\big( \mD^{(\graph)} \big)^{1/2}
		\mathbf{1}$ for $\mL^{(\mathrm{sym})}$, and its multiplicity again
		counts the connected components
		(von Luxburg, 2007, Prop.~3, Prop.~4). For the station graph,
		the largest eigenvalue of $\mL^{(\mathrm{sym})}$ is $1.57$.
		Which of the three matrices a method uses is a design choice
		(von Luxburg, 2007, Sect.~8.5): spectral clustering has been
		formulated with $\mL^{(\mathrm{rw})}$ (Shi and Malik, 2000), with
		$\mL^{(\mathrm{sym})}$ (Ng et al., 2001), and with $\LapMat{\graph}$
		(von Luxburg, 2007, Sect.~4).
\par
		In machine learning (ML), the Laplacian matrix enters through its quadratic
		form \eqref{equ_LapMat_quadform_dict} as a penalty term.
		Consider data points that are the nodes of $\graph$, which
		is then a similarity graph, with a label $\truelabel_{\nodeidx}$
		known only for the nodes in a subset $\genericnodeset \subset
		\nodes$. Examples are the stations with a record, or the users of
		a social network who filled in a profile field. A hypothesis
		is a vector $\vx \in
		\reals^{\nrnodes}$ that assigns one value to every node, and the
		hypothesis space is $\reals^{\nrnodes}$. Laplacian
		regularization adds the quadratic form to the average
		squared error loss on the labeled nodes,
		\begin{equation}
			\label{equ_LapMat_reg_dict}
			\min_{\vx \in \reals^{\nrnodes}}
			\frac{1}{|\genericnodeset|}
			\sum_{\nodeidx \in \genericnodeset}
			\big( x_{\nodeidx} - \truelabel_{\nodeidx} \big)^{2}
			+ \regparam \, \vx^{\top} \LapMat{\graph} \vx \text{,}
		\end{equation}
		with a hyperparameter $\regparam > 0$
		(Belkin et al., 2004;
		Zhou and Schölkopf, 2004). Adding a penalty term is
		one of the three routes that regularization distinguishes,
		and this one implements the assumption that nodes joined by a
		heavy edge carry similar values. The training error alone says
		nothing about a node outside $\genericnodeset$; the
		penalty term is the only term that constrains its value, so
		the generalization from the labeled to the unlabeled nodes
		comes from the edges. The objective \eqref{equ_LapMat_reg_dict} is
		convex and its minimizer solves a linear system, since the
		gradient of the quadratic form is $2 \LapMat{\graph} \vx$.
		As $\regparam \to 0$, the minimizer pins $x_{\nodeidx} =
		\truelabel_{\nodeidx}$ on the labeled nodes and minimizes the
		quadratic form over the remaining entries. The entry of
		$\LapMat{\graph} \vx$ at an unlabeled node is then zero. Such a
		node takes the weighted average of its neighbors,
		$x_{\nodeidx} = (1/\nodedegree{\nodeidx})
		\sum_{\nodeidx'=1}^{\nrnodes} \edgeweight_{\nodeidx,\nodeidx'}
		x_{\nodeidx'}$, which is the harmonic solution of
		Zhu et al. (2003).
\par
		Leaving each station of Fig.~\ref{fig_LapMat_krems_dict}(a) out
		in turn and predicting its mean temperature by this average of
		its neighbors gives a mean absolute error of $0.86$
		degrees. Predicting the mean of the other eleven stations
		instead gives $1.12$ degrees. The largest error is at Jauerling,
		$955$ m above sea level, predicted at $12.3$ degrees against
		$9.6$ recorded. The edge weights encode distance but
		not altitude, so the penalty asks a mountain station to resemble
		the valley stations around it. The same quadratic form, with the
		model parameters of local models in place of the scalars
		$x_{\nodeidx}$, is the generalized total variation (GTV) that generalized total variation minimization (GTVMin) penalizes in
		federated learning (FL). The eigenvectors of the smallest
		eigenvalues of a Laplacian matrix are the coordinates that
		spectral clustering hands to $k$-means
		(von Luxburg, 2007, Sect.~4).

\subsection{Cross References}
graph, weighted graph, edge weight, adjacency matrix, node degree, matrix, psd, eigenvalue, eigenvector, EVD, connected, algebraic connectivity, Fiedler vector, spectral clustering, graph clustering, similarity graph, regularization, penalty term, GTV, GTVMin

\subsection{References}
\begin{enumerate}
  \item Chung (1997). Spectral Graph Theory. American Mathematical Society, Providence, RI, USA.
  \item Fiedler (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), pp.~298--305.
  \item Fiedler (1975). A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal, 25(4), pp.~619--633.
  \item von Luxburg (2007). A tutorial on spectral clustering. Statist. Comput., 17(4), pp.~395--416.
  \item Mohar (1991). The Laplacian Spectrum of Graphs. In: Graph Theory, Combinatorics, and Applications, pp.~871--898. Wiley.
  \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 Belkin et al. (2004). Regularization and semi-supervised learning on large graphs. In: COLT, pp.~624--638.
  \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.
  \item Zhou and Schölkopf (2004). A regularization framework for learning from graph data. In: ICML workshop on statistical relational learning and Its connections to other fields, pp.~67--68.
  \item Zhu et al. (2003). Semi-supervised learning using gaussian fields and harmonic functions. In: ICML, pp.~912--919.
\end{enumerate}

\end{document}
