\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{\cluster}{\mathcal{C}}
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\discrepancy}[2]{d^{(#1,#2)}}
\newcommand{\edge}[2]{\{#1,#2\}}
\newcommand{\edges}{\mathcal{E}}
\newcommand{\edgeweight}{A}
\newcommand{\edgeweights}{\mA}
\newcommand{\featuredim}{d}
\newcommand{\featurevec}{\vx}
\newcommand{\graph}{\mathcal{G}}
\newcommand{\hypothesis}{h}
\newcommand{\localhypothesis}[1]{\hypothesis^{(#1)}}
\newcommand{\mA}[0]{{\bf A}}
\newcommand{\nodedegree}[1]{d^{(#1)}}
\newcommand{\nodeidx}{i}
\newcommand{\nodes}{\mathcal{V}}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\nrnodes}{n}
\newcommand{\pair}[2]{\left( #1,#2 \right)}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{weighted graph}

\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}
A weighted graph is a graph whose edges carry
		nonnegative numbers, the edge weights, that measure how
		strongly two nodes are tied. It consists of a finite set of
		nodes, a set of undirected edges joining pairs of distinct nodes,
		and a positive weight for each edge; a pair of nodes that is not
		an edge has weight zero. The weights form the weight matrix
		$\edgeweights$, a symmetric matrix with a zero diagonal that
		is also the adjacency matrix of the graph, and the sum of a
		row is the weighted node degree of its node. In machine learning (ML), the
		nodes are often the data points of a dataset and the
		weight of an edge is the similarity of two data points,
		e.g., a Gaussian function of the Euclidean distance between their
		feature vectors, kept for the $k$ nearest neighbors of
		each data point. Graph clustering seeks subsets of nodes
		whose outgoing edges carry little weight. Transfer learning
		and federated learning (FL) use the weights of a graph of learning tasks as
		the coefficients of a penalty term that couples the
		hypotheses of neighboring tasks.

\subsection{Definition}
Consider ten days of the year
		$2024$ at Krems an der Donau, every $37$th day from 1 January to
		29 November, each a data point with a feature vector
		$\featurevec \in \reals^{2}$ that holds the morning minimum and
		the maximum daytime temperature of the day. Two days are similar
		when their feature vectors are close. A drawing records the
		similarities: each day is a dot, called a node, two similar days
		are joined by a line, called an edge, and a number on the edge
		says how similar the two days are.
		Fig.~\ref{fig_weightedgraph_krems_dict}(a) shows this drawing for
		the ten days, with an edge between two days whenever one of them
		is among the three days nearest to the other and a number between
		$0$ and $1$ that falls off with the Euclidean distance between them.
		Nodes, edges, and a number on every edge make a weighted graph
		(von Luxburg, 2007, Sect.~2.1; Newman, 2010).
\par
		Formally, a weighted graph $\graph = \pair{\nodes}{\edges}$
		consists of a finite set of nodes $\nodes = \{1, \ldots,
		\nrnodes\}$, a set $\edges$ of edges, and an edge weight
		for each edge. Each edge is an unordered pair
		$\edge{\nodeidx}{\nodeidx'}$ of two distinct nodes, so the graph
		is an undirected graph without self-loops, and the two nodes
		of an edge are neighbors of each other. The weight of an
		edge $\edge{\nodeidx}{\nodeidx'} \in \edges$ is a positive number
		$\edgeweight_{\nodeidx,\nodeidx'} > 0$, and a pair of nodes that
		is not an edge has weight $\edgeweight_{\nodeidx,\nodeidx'} = 0$
		(Chung, 1997, Sect.~1.4). With this convention,
		the weights determine the edge set, and they are collected in the
		weight matrix
		\begin{equation}
			\label{equ_weightedgraph_weightmtx_dict}
			\edgeweights \in \reals^{\nrnodes \times \nrnodes}
			\text{ with entries }
			\edgeweight_{\nodeidx,\nodeidx'} = \edgeweight_{\nodeidx',\nodeidx}
			\geq 0 \text{ and } \edgeweight_{\nodeidx,\nodeidx} = 0
			\text{ for } \nodeidx, \nodeidx' \in \nodes \text{.}
		\end{equation}
		The weight matrix \eqref{equ_weightedgraph_weightmtx_dict} is a
		symmetric matrix with a zero diagonal. It is the
		adjacency matrix of the graph: the entry in row $\nodeidx$
		and column $\nodeidx'$ is the weight of the edge between
		$\nodeidx$ and $\nodeidx'$, or zero when there is no edge
		(Hastie et al., 2009, Sect.~14.5.3;
		von Luxburg, 2007, Sect.~2.1). An unweighted graph is the
		special case in which every edge has weight $1$, so the entries of
		its weight matrix \eqref{equ_weightedgraph_weightmtx_dict} are
		$0$ and $1$ (Chung, 1997, Sect.~1.4).
		Fig.~\ref{fig_weightedgraph_four_dict} shows a weighted graph with
		four nodes beside its weight matrix.
		\begin{figure}[H]
			\centering
			\begin{tikzpicture}[scale=1.3, font=\small,
				node/.style={circle, fill=black, inner sep=1.9pt}]
				\node[node] (v1) at (0,0) {};
				\node[node] (v2) at (2,0) {};
				\node[node] (v3) at (1,1.5) {};
				\node[node] (v4) at (3.2,-1.0) {};
				\node[below=2pt] at (v1) {$1$};
				\node[below=2pt] at (v2) {$2$};
				\node[above=2pt] at (v3) {$3$};
				\node[below=2pt] at (v4) {$4$};
				\draw[line width=2.4pt] (v1) -- node[midway, below=1pt] {$\edgeweight_{1,2} = 0.9$} (v2);
				\draw[line width=1.0pt] (v2) -- node[midway, right=1pt] {$\edgeweight_{2,3} = 0.4$} (v3);
				\draw[line width=1.8pt] (v3) -- node[midway, left=1pt] {$\edgeweight_{1,3} = 0.7$} (v1);
				\draw[line width=0.5pt] (v2) -- node[midway, above right=1pt] {$\edgeweight_{2,4} = 0.2$} (v4);
				\node[anchor=west] at (4.8,0.3) {$\edgeweights = \begin{pmatrix} 0 & 0.9 & 0.7 & 0 \\ 0.9 & 0 & 0.4 & 0.2 \\ 0.7 & 0.4 & 0 & 0 \\ 0 & 0.2 & 0 & 0 \end{pmatrix}$};
			\end{tikzpicture}
		\caption{A weighted graph with four nodes $\nodes = \{1, 2, 3,
			4\}$ and four edges, each drawn as a line whose width grows
			with its weight, beside its weight matrix
			\eqref{equ_weightedgraph_weightmtx_dict}. The entry in row
			$2$ and column $4$ is the weight $0.2$ of the edge
			$\edge{2}{4}$, and the zero in row $1$ and column $4$ records
			that the nodes $1$ and $4$ are not joined by an edge
			\label{fig_weightedgraph_four_dict}}
		\end{figure}
		The sum of the weights of the edges at a node is its weighted
		node degree,
		\begin{equation}
			\label{equ_weightedgraph_degree_dict}
			\nodedegree{\nodeidx} = \sum_{\nodeidx' \in \nodes}
			\edgeweight_{\nodeidx,\nodeidx'} \text{,}
		\end{equation}
		which is the sum of row $\nodeidx$ of the weight matrix
		(Chung, 1997, Sect.~1.4;
		von Luxburg, 2007, Sect.~2.1). For an unweighted graph the
		node degree \eqref{equ_weightedgraph_degree_dict} counts the
		neighbors of the node. The Laplacian matrix of the graph is
		built from the weight matrix and the degrees
		\eqref{equ_weightedgraph_degree_dict}, and its eigenvectors
		are what spectral clustering computes
		(von Luxburg, 2007, Sect.~3).
\par
		What a weight means is fixed by the application, and two
		conventions are in use. In a road network, the nodes are
		intersections, the edges are road segments, and the weight of an
		edge is the length of the segment or the time needed to travel
		it (Newman, 2010). A large weight then means far apart, and
		the shortest route between two intersections is the path whose
		weights add up to the smallest value. In machine learning (ML), the weight of
		an edge usually measures similarity: a large weight means close
		together. A method that reads a similarity as a length, or a
		length as a similarity, inverts every conclusion it draws, so the
		convention must be stated. The graph in
		Fig.~\ref{fig_weightedgraph_krems_dict}(a) uses the similarity
		convention.
\par
		The main use of a weighted graph in ML is the
		similarity graph of a dataset $\dataset = \{\featurevec^{(1)},
		\ldots, \featurevec^{(\samplesize)}\}$. Its nodes are the
		data points, $\nodes = \{1, \ldots, \samplesize\}$ with node
		$\sampleidx$ standing for $\featurevec^{(\sampleidx)}$, and the
		weight of an edge measures the similarity of its two
		data points. For feature vectors in $\reals^{\featuredim}$,
		a common choice is the Gaussian weight
		\begin{equation}
			\label{equ_weightedgraph_gauss_dict}
			\edgeweight_{\sampleidx,\sampleidx'} = \exp \Big( -
			\normgeneric{\featurevec^{(\sampleidx)} -
			\featurevec^{(\sampleidx')}}{2}^{2} \big/ (2 \sigma^{2}) \Big)
			\text{,}
		\end{equation}
		which is $1$ for two identical feature vectors and falls off
		with their Euclidean distance at a rate set by the width
		$\sigma > 0$ (Hastie et al., 2009, Sect.~14.5.3;
		von Luxburg, 2007, Sect.~2.2; Shalev-Shwartz and Ben-David, 2014, Sect.~22.3).
		Giving the Gaussian weight \eqref{equ_weightedgraph_gauss_dict} to
		every pair of data points produces a fully connected graph
		with $\samplesize(\samplesize-1)/2$ edges, whose weight matrix has
		no zero off the diagonal. A sparse alternative is the
		$k$-nearest-neighbor graph ($k$-NN graph): an edge joins $\sampleidx$ and $\sampleidx'$ when
		one of the two data points is among the $k$ nearest
		data points of the other, it carries the Gaussian weight
		\eqref{equ_weightedgraph_gauss_dict}, and every other pair has
		weight zero (von Luxburg, 2007, Sect.~2.2). The width $\sigma$
		and the number $k$ of neighbors are hyperparameters
		of the construction; a usual choice for $\sigma$ is the mean
		distance of a data point to its $k$-th nearest
		neighbor (von Luxburg, 2007, Sect.~8.1). For the ten days at
		Krems and $k = 3$, this choice gives $\sigma = 8.27$ degrees, and
		$19$ of the $45$ pairs of days are edges. Their weights range
		from $0.11$, between 10 August and 16 September, to $0.95$,
		between 16 September and 23 October, and the weighted degrees
		\eqref{equ_weightedgraph_degree_dict} from $1.13$, on 10 August,
		to $4.61$, on 7 February. Fig.~\ref{fig_weightedgraph_krems_dict}(b)
		shows the weight matrix.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}
		\begin{groupplot}[
			group style={group size=2 by 1, horizontal sep=2.0cm},
			width=0.44\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.5,-0.36)}, anchor=north},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={morning minimum temperature\\(a) the ten days and the $19$ edges},
				ylabel={maximum daytime temperature},
				xmin=-3, xmax=20, ymin=4, ymax=37,
				unbounded coords=jump]
			\addplot[black, line width=1.4pt, no marks]
				table[col sep=comma, x=x, y=y]{weightedgraph_edges_strong.csv};
			\addlegendentry{edges of weight at least one half (thick lines)}
			\addplot[black!55, line width=0.5pt, no marks]
				table[col sep=comma, x=x, y=y]{weightedgraph_edges_weak.csv};
			\addlegendentry{edges of weight below one half (thin lines)}
			\addplot[only marks, mark=*, mark size=1.8pt, black,
				nodes near coords, point meta=explicit symbolic,
				every node near coord/.append style={font=\scriptsize, anchor=south west, xshift=1pt}]
				table[col sep=comma, x=tmin, y=tmax, meta=node]{weightedgraph_nodes.csv};
			\addlegendentry{the ten days (filled circles)}
			\nextgroupplot[
				xlabel={node $\nodeidx'$\\(b) the weight matrix $\edgeweights$},
				ylabel={node $\nodeidx$},
				xmin=0.5, xmax=10.5, ymin=0.5, ymax=10.5,
				y dir=reverse, enlargelimits=false,
				xtick={1,...,10}, ytick={1,...,10},
				colorbar, colorbar style={font=\scriptsize, width=0.2cm, xshift=0.2cm},
				colormap={bw}{gray(0cm)=(1); gray(1cm)=(0)},
				point meta min=0, point meta max=1]
			\addplot[matrix plot*, mesh/cols=10, point meta=explicit]
				table[col sep=comma, x=ip, y=i, meta=w]{weightedgraph_matrix.csv};
		\end{groupplot}
		\end{tikzpicture}
		\caption{(a) Ten of the $366$ days of $2024$ at Krems, every
			$37$th day, numbered $1$ to $10$ in order of date (node $1$
			is 1 January, node $10$ is 29 November), as the nodes of
			their $3$-nearest-neighbor graph, drawn in the plane of the
			morning minimum and the maximum daytime temperature: an edge
			of weight at least $0.5$ is a thick line, an edge of weight
			below $0.5$ a thin line.
			(b) The weight matrix \eqref{equ_weightedgraph_weightmtx_dict}
			of the graph: the darker the cell in row $\nodeidx$ and
			column $\nodeidx'$, the larger the weight
			$\edgeweight_{\nodeidx,\nodeidx'}$, and a white cell is a
			pair of days that is not an edge. Data generated by
			\texttt{pythondemos/weightedgraph.py}
			\label{fig_weightedgraph_krems_dict}}
		\end{figure}
		A similarity graph turns clustering into a question about
		the weights. A cluster is a subset $\cluster \subseteq
		\nodes$ of nodes whose inner edges carry large weights and whose
		outgoing edges carry small ones. The total weight of the edges
		that leave the subset,
		\begin{equation}
			\label{equ_weightedgraph_cut_dict}
			\sum_{\nodeidx \in \cluster} \;
			\sum_{\nodeidx' \in \nodes \setminus \cluster}
			\edgeweight_{\nodeidx,\nodeidx'} \text{,}
		\end{equation}
		is the cut of $\cluster$. Graph clustering methods such as
		spectral clustering choose the clusters to make their
		cuts \eqref{equ_weightedgraph_cut_dict} small relative to their
		sizes (von Luxburg, 2007, Sect.~5;
		Shalev-Shwartz and Ben-David, 2014, Sect.~22.3.1; Shi and Malik, 2000).
		For the ten days at Krems, take the seven days with a maximum
		temperature below $18$ degrees as the subset $\cluster$. Its cut
		\eqref{equ_weightedgraph_cut_dict} is $1.92$ out of a total edge
		weight of $13.25$: the four edges that leave it are $21$ percent
		of the edges and carry $14.5$ percent of the weight. On all $366$
		days of $2024$ and with $k = 10$, the graph has $2209$ edges. The
		edges between the $186$ cold and the $180$ warm days carry $3.7$
		percent of the total weight, and no edge joins a day of January
		or February with a day of July or August. On a photograph cut
		into patches, the
		same construction with the mean color of a patch as its
		feature vector gives a weighted graph whose clusters are
		the regions of an image segmentation.
\par
		A weighted graph also enters empirical risk minimization (ERM) through a
		penalty term. In transfer learning and in federated learning (FL), the
		nodes are learning tasks, each with its own
		local dataset and a local hypothesis
		$\localhypothesis{\nodeidx}$, and the weight
		$\edgeweight_{\nodeidx,\nodeidx'}$ states how similar two tasks
		are. Generalized total variation minimization (GTVMin) minimizes the sum of the local training errors
		plus the generalized total variation (GTV)
		\begin{equation}
			\label{equ_weightedgraph_gtv_dict}
			\sum_{\edge{\nodeidx}{\nodeidx'} \in \edges}
			\edgeweight_{\nodeidx,\nodeidx'}
			\discrepancy{\nodeidx}{\nodeidx'} \text{,}
		\end{equation}
		with $\discrepancy{\nodeidx}{\nodeidx'}$ a measure of the
		discrepancy between $\localhypothesis{\nodeidx}$ and
		$\localhypothesis{\nodeidx'}$. The GTV
		\eqref{equ_weightedgraph_gtv_dict} couples the tasks: an edge
		with a large weight pulls the two hypotheses at its nodes
		together, and a zero weight leaves them independent. The
		network Lasso is the special case with the Euclidean distance
		between the local model parameters as the discrepancy
		(Hallac et al., 2015). Adding a penalty term is one of the
		three routes that regularization distinguishes, and the
		weighted graph is where this penalty term is specified. On a
		similarity graph of labeled and unlabeled data points, the
		penalty term \eqref{equ_weightedgraph_gtv_dict} with the
		squared difference $\big(\hypothesis(\featurevec^{(\sampleidx)}) -
		\hypothesis(\featurevec^{(\sampleidx')})\big)^{2}$ as the
		discrepancy is the Laplacian regularizer of semi-supervised learning (SSL)
		(Belkin et al., 2006, Sect.~2.2). It asks a hypothesis to take
		similar values on two data points joined by an edge of
		large weight, which is how the unlabeled data points shape
		the hypothesis. A graph neural network (GNN) uses the weights for a
		third purpose, to combine the feature vectors of the
		neighbors of each node into a new feature vector of the
		node.

\subsection{Cross References}
graph, undirected graph, edge weight, adjacency matrix, Laplacian matrix, node degree, neighbor, similarity graph, $k$-NN graph, graph clustering, spectral clustering, clustering, transfer learning, GTV, GTVMin, SSL, GNN, matrix

\subsection{References}
\begin{enumerate}
  \item Belkin et al. (2006). Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. J. Mach. Lear. Research, 7, pp.~2399--2434.
  \item Chung (1997). Spectral Graph Theory. American Mathematical Society, Providence, RI, USA.
  \item von Luxburg (2007). A tutorial on spectral clustering. Statist. Comput., 17(4), pp.~395--416.
  \item Hallac et al. (2015). Network Lasso: Clustering and Optimization in Large Graphs. In: Proc. 21st ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, pp.~387--396.
  \item Newman (2010). Networks: An Introduction. Oxford Univ. Press, New York, NY, USA.
  \item Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, New York, NY, USA.
  \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}
