\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{\clustercentroid}[1]{{\vw}^{(#1)}}
\newcommand{\defeq}{:=}
\newcommand{\edge}[2]{\{#1,#2\}}
\newcommand{\edges}{\mathcal{E}}
\newcommand{\edgeweight}{A}
\newcommand{\edgeweights}{\mA}
\newcommand{\featurevec}{\vx}
\newcommand{\graph}{\mathcal{G}}
\newcommand{\mA}[0]{{\bf A}}
\newcommand{\mL}[0]{{\bf L}}
\newcommand{\nodeidx}{i}
\newcommand{\nodes}{\mathcal{V}}
\newcommand{\nodesigvec}{\mathbf{u}}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\nrnodes}{n}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\regparam}{\alpha}
\newcommand{\samplesize}{m}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{edge weight}

\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}
An edge weight is a nonnegative number
		$\edgeweight_{\nodeidx,\nodeidx'}$ attached to the edge
		$\edge{\nodeidx}{\nodeidx'}$ of a weighted graph that
		measures how strongly the two nodes it joins are connected.
		Collected in the weight matrix $\edgeweights$, the edge
		weights of an undirected graph form a symmetric matrix
		with a zero entry for every pair that is not an edge. In
		machine learning (ML), the nodes are often the data points of a
		dataset, and the weight of a pair is the Gaussian
		similarity of their feature vectors, a decreasing
		function of their Euclidean distance with a width $\sigma$ as
		hyperparameter; a $k$-nearest-neighbor graph ($k$-NN graph) keeps only the weights of
		nearby pairs. Edge weights can also encode a relation given with
		the data, such as citations between papers or the collaboration
		between the devices of a federated learning network (FL network). ML methods
		use the weights through weighted sums over the edges. The
		quadratic form of the Laplacian matrix is the weighted sum of the
		squared differences of a node signal, which for the indicator of
		a cluster is the total weight of the cut edges. The
		penalty term of convex clustering charges the
		distance between two cluster centroids in proportion
		to the weight of their edge. Edge weights are given before
		training and differ from the weights of an artificial neural network (ANN),
		which are model parameters.

\subsection{Definition}
Consider eight days of $2024$ at Krems an
		der Donau, every $46$th day from 1 January, 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 with similar temperatures are similar
		data points. One way to record the similarity of every pair
		of days is a graph. The days are its nodes $\nodeidx = 1,
		\ldots, \nrnodes$, here with $\nrnodes = 8$, and an edge
		$\edge{\nodeidx}{\nodeidx'}$ between two days carries a number
		that says how similar they are: the edge weight
		$\edgeweight_{\nodeidx,\nodeidx'} \geq 0$. In
		Fig.~\ref{fig_edgeweight_dict}(a), a thick edge joins 1 January
		and 18 November, whose temperatures differ by less than two
		degrees Celsius, while no visible edge joins 1 January and
		18 August.
\par
		A weighted graph $\graph = (\nodes, \edges, \edgeweights)$
		consists of a node set $\nodes = \{1, \ldots, \nrnodes\}$, an
		edge set $\edges$, and an edge weight
		$\edgeweight_{\nodeidx,\nodeidx'}$ for every edge
		$\edge{\nodeidx}{\nodeidx'} \in \edges$. The weights of an
		undirected graph without self-loops are collected in the
		weight matrix $\edgeweights \in \reals^{\nrnodes \times
		\nrnodes}$. Its entries satisfy
		\begin{equation}
			\label{equ_edgeweight_matrix_dict}
			\edgeweight_{\nodeidx,\nodeidx'} = \edgeweight_{\nodeidx',\nodeidx}
			\geq 0 \text{,} \quad
			\edgeweight_{\nodeidx,\nodeidx} = 0 \text{,} \quad \text{and} \quad
			\edgeweight_{\nodeidx,\nodeidx'} = 0 \text{ for }
			\edge{\nodeidx}{\nodeidx'} \notin \edges \text{.}
		\end{equation}
		The first condition in the weight matrix
		\eqref{equ_edgeweight_matrix_dict} holds because the edge
		$\edge{\nodeidx}{\nodeidx'}$ of an undirected graph is the
		edge $\edge{\nodeidx'}{\nodeidx}$, so the weight matrix is a
		symmetric matrix. The third condition makes a zero weight and
		a missing edge the same thing, so the weight matrix
		determines the graph and is its adjacency matrix
		(Chung, 1997, Sect.~1.4;
		von Luxburg, 2007, Sect.~2). An unweighted graph is the
		special case in which every edge has weight $1$. The weighted
		node degree of node $\nodeidx$ is the row sum
		$\sum_{\nodeidx'=1}^{\nrnodes} \edgeweight_{\nodeidx,\nodeidx'}$
		of the weight matrix
		(Hastie et al., 2009, Sect.~14.5.3).
\par
		In machine learning (ML), edge weights come from two sources. The first source
		is the feature vectors of the data points: the
		$\samplesize$ data points of a dataset become the
		nodes of a similarity graph, with $\nrnodes = \samplesize$, and the
		weight of a pair is a decreasing function of the
		distance between their feature vectors. The usual choice
		is the Gaussian similarity
		\begin{equation}
			\label{equ_edgeweight_gauss_dict}
			\edgeweight_{\nodeidx,\nodeidx'} \defeq \exp \Big( -
			\normgeneric{\featurevec^{(\nodeidx)} -
			\featurevec^{(\nodeidx')}}{2}^{2} \big/ (2 \sigma^{2}) \Big)
			\quad \text{for } \nodeidx \neq \nodeidx' \text{,}
		\end{equation}
		with a width $\sigma > 0$
		(Hastie et al., 2009, Sect.~14.5.3;
		von Luxburg, 2007, Sect.~2). The Gaussian weight
		\eqref{equ_edgeweight_gauss_dict} is $1$ for identical
		feature vectors, $\exp(-1/2) \approx 0.61$ at Euclidean distance
		$\sigma$, and about $0.01$ at Euclidean distance $3 \sigma$. For the
		eight days and $\sigma = 5$ degrees, the weight is $0.95$ for
		1 January and 18 November, whose feature vectors are $1.6$
		degrees apart, and $6 \cdot 10^{-7}$ for 1 January and 18 August,
		$26.8$ degrees apart. Six of the $28$ pairs weigh at least $0.5$,
		and eight weigh below $0.01$ (Fig.~\ref{fig_edgeweight_dict}(b)).
		The width $\sigma$ is a hyperparameter. With $\sigma = 1$,
		only two pairs weigh at least $0.01$, so the graph falls
		apart into isolated days. With $\sigma = 50$, every pair weighs at
		least $0.87$, so the weights no longer separate similar from
		dissimilar days. A width $\sigma$ in the order of the mean
		distance of a data point to its $k$-th nearest
		neighbor is a common choice (von Luxburg, 2007, Sect.~8).
\par
		The Gaussian weight \eqref{equ_edgeweight_gauss_dict} is positive
		for every pair, so every pair is an edge and the weight
		matrix has no zero off its diagonal. A sparse graph is
		obtained from the $k$-nearest-neighbor graph ($k$-NN graph). The pair
		$\edge{\nodeidx}{\nodeidx'}$ is an edge if
		$\featurevec^{(\nodeidx')}$ is among the $k$ nearest
		neighbors of $\featurevec^{(\nodeidx)}$ or
		$\featurevec^{(\nodeidx)}$ among those of
		$\featurevec^{(\nodeidx')}$. An edge keeps the Gaussian weight
		\eqref{equ_edgeweight_gauss_dict}, and every other weight is set
		to zero (Hastie et al., 2009, Sect.~14.5.3;
		von Luxburg, 2007, Sect.~2). For the eight days and $k = 2$,
		ten of the $28$ pairs are edges, and the graph is
		connected. The $k$-NN graph is not a threshold on the
		weights. It keeps 18 May and 18 August at weight $0.07$, since
		18 May is one of the two days nearest to 18 August. It drops
		3 October and 18 November at weight $0.54$, since each of the two
		has two closer days. Fig.~\ref{fig_edgeweight_dict}(b) marks the
		kept pairs by filled circles and the dropped pairs by open
		squares. The $k$-NN graph therefore
		connects data points in sparse and in dense regions of the
		feature space alike, which is why it is the recommended first
		choice (von Luxburg, 2007, Sect.~8).
\par
		The second source is a relation given with the data rather than
		computed from feature vectors: citations between scientific
		papers, friendships between the users of a social network, links
		between web pages, or the number of measurements that two weather
		stations share. In an image, the pixels are the nodes, and the
		weight of two pixels falls with the difference of their brightness
		and with their distance in the image, a construction used in
		image segmentation by normalized cuts (Shi and Malik, 2000).
		In a federated learning network (FL network), the nodes are devices, and the edge
		weight measures the extent of their collaboration, e.g., the
		capacity of the communication link between them or the
		statistical similarity of their local datasets. In
		transfer learning, the nodes are learning tasks, and
		the weight couples the tasks of nearby weather stations more
		strongly than those of distant ones.
\par
		The edges of an artificial neural network (ANN) also carry weights, and those are
		a different object: an ANN weight is a model parameter,
		learned by training, and it can be negative. The edge
		weights of a weighted graph are nonnegative and are given
		before training starts; they belong to the data, not to the
		model.
\par
		Edge weights enter ML methods through weighted sums over the
		edges. A node signal $\nodesigvec = (u_{1}, \ldots,
		u_{\nrnodes})^{\top} \in \reals^{\nrnodes}$ assigns one number
		to every node, such as a label or a prediction. The
		Laplacian matrix $\LapMat{\graph}$ of the graph satisfies
		\begin{equation}
			\label{equ_edgeweight_quadform_dict}
			\nodesigvec^{\top} \LapMat{\graph} \nodesigvec =
			\sum_{\edge{\nodeidx}{\nodeidx'} \in \edges}
			\edgeweight_{\nodeidx,\nodeidx'}
			\big( u_{\nodeidx} - u_{\nodeidx'} \big)^{2} \text{,}
		\end{equation}
		the Laplacian quadratic form (von Luxburg, 2007, Prop.~1). It is
		a weighted sum of squared differences. A heavy edge charges a
		difference between its two nodes more than a light edge, and the
		sum is zero for a signal that is constant on every
		connected component of the graph. For the indicator
		of a subset $\cluster \subseteq \nodes$ of the nodes,
		$u_{\nodeidx} = 1$ for $\nodeidx \in \cluster$ and
		$u_{\nodeidx} = 0$ otherwise, the quadratic form
		\eqref{equ_edgeweight_quadform_dict} is the total weight of the
		edges between $\cluster$ and the rest of the graph, the
		weight of the cut. For the eight days, the five days with a
		maximum temperature below $20$ degrees cut edges of total weight
		$1.09$, which is $15$ percent of the total weight $7.44$ of all
		pairs. Splitting the days into the first four and the last four
		of the year cuts $4.97$, or $67$ percent. Graph clustering
		methods seek clusters that cut little weight;
		spectral clustering approximately minimizes the cut weight
		divided by the size of the cluster through
		eigenvectors of $\LapMat{\graph}$
		(von Luxburg, 2007, Sect.~5).
\par
		Semi-supervised learning (SSL) on a graph seeks a
		node signal that agrees with the labels of the few labeled
		nodes and makes the quadratic form
		\eqref{equ_edgeweight_quadform_dict} small (Zhu et al., 2003).
		The weights then carry the labels from labeled to unlabeled
		nodes. They decide to which data points outside the
		training set a learned hypothesis is extended, which is the
		question of generalization. The generalized total variation (GTV) replaces the
		squared difference in the quadratic form
		\eqref{equ_edgeweight_quadform_dict} by a measure of the
		discrepancy between the local models of the two nodes.
		Generalized total variation minimization (GTVMin) adds it to the local training errors, as in
		federated learning (FL) and transfer learning. The network Lasso is
		the case of the unsquared distance between the
		model parameters of the two local models
		(Hallac et al., 2015).
\par
		Convex clustering uses the edge weights in its objective function.
		Every data point $\featurevec^{(\nodeidx)}$ gets its own
		cluster centroid $\clustercentroid{\nodeidx}$, and the
		cluster centroids minimize
		\begin{equation}
			\label{equ_edgeweight_cvx_dict}
			\sum_{\nodeidx=1}^{\nrnodes}
			\normgeneric{\featurevec^{(\nodeidx)} -
			\clustercentroid{\nodeidx}}{2}^{2} + \regparam
			\sum_{\edge{\nodeidx}{\nodeidx'} \in \edges}
			\edgeweight_{\nodeidx,\nodeidx'}
			\normgeneric{\clustercentroid{\nodeidx} -
			\clustercentroid{\nodeidx'}}{2} \text{,}
		\end{equation}
		with a regularization parameter $\regparam \geq 0$ (Hocking et al., 2011;
		Sun et al., 2021, Eq.~(1)). The first sum in the
		objective function \eqref{equ_edgeweight_cvx_dict} is the
		clustering error of the cluster centroids, the
		training error that empirical risk minimization (ERM) minimizes; the second sum is a
		penalty term, so the method regularizes by loss penalization,
		one of the three routes that regularization distinguishes.
		The weights decide which pairs of cluster centroids are
		pulled together. A pair with weight zero is never charged, and a
		heavy pair is charged in proportion to its weight. For
		$\regparam$ large enough, the cluster centroids of a heavy
		pair coincide, which puts the two data points into one
		cluster. For
		a hard clustering in which every data point of a
		cluster shares one cluster centroid, the
		penalty term is the distance between the two
		cluster centroids times the cut weight. For the cold and the
		warm days above, it is $17.0$, the distance $15.6$ between
		their cluster centroids times the cut weight $1.09$.
		\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,
				at={(0.5,-0.3)}, anchor=north},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={morning minimum temperature\\(a) the eight days and their edges},
				ylabel={maximum daytime temperature},
				xmin=0, xmax=25, ymin=7, ymax=34,
				unbounded coords=jump,
				visualization depends on={value \thisrow{anchor} \as \labelanchor}]
			\addplot[black, line width=1.6pt, no marks]
				table[col sep=comma, x=x, y=y]{edgeweight_edges_strong.csv};
			\addlegendentry{weight $\edgeweight_{\nodeidx,\nodeidx'} \geq 0.5$ (thick edges)}
			\addplot[black!60, thin, no marks]
				table[col sep=comma, x=x, y=y]{edgeweight_edges_medium.csv};
			\addlegendentry{weight $0.1 \leq \edgeweight_{\nodeidx,\nodeidx'} < 0.5$ (thin edges)}
			\addplot[black!60, thin, dotted, no marks]
				table[col sep=comma, x=x, y=y]{edgeweight_edges_weak.csv};
			\addlegendentry{weight $0.01 \leq \edgeweight_{\nodeidx,\nodeidx'} < 0.1$ (dotted edges)}
			\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=\labelanchor, inner sep=1.5pt}]
				table[col sep=comma, x=tmin, y=tmax, meta=label]{edgeweight_nodes.csv};
			\addlegendentry{days $\nodeidx = 1, \ldots, 8$ (filled circles)}
			\nextgroupplot[
				xlabel={Euclidean distance between the feature vectors\\(b) the $28$ pairs on the Gaussian curve},
				ylabel={edge weight},
				xmin=0, xmax=28, ymin=0, ymax=1.08]
			\addplot[black, thick, no marks]
				table[col sep=comma, x=distance, y=weight]{edgeweight_curve.csv};
			\addlegendentry{Gaussian weight $\edgeweight_{\nodeidx,\nodeidx'}$ (solid curve)}
			\addplot[only marks, mark=*, mark size=1.8pt, black,
				restrict expr to domain={\thisrow{knn}}{1:1}]
				table[col sep=comma, x=distance, y=weight]{edgeweight_pairs.csv};
			\addlegendentry{pair kept by the $k$-NN graph, $k = 2$ (filled circles)}
			\addplot[only marks, mark=square, mark size=1.8pt, black,
				restrict expr to domain={\thisrow{knn}}{0:0}]
				table[col sep=comma, x=distance, y=weight]{edgeweight_pairs.csv};
			\addlegendentry{pair dropped by the $k$-NN graph, $k = 2$ (open squares)}
		\end{groupplot}
		\end{tikzpicture}
		\caption{(a) Eight of the $366$ days of $2024$ at Krems, every
			$46$th day from 1 January (filled circles), with the morning
			minimum temperature and the maximum daytime temperature of a
			day as its feature vector. Every pair of days is an edge
			with the Gaussian weight \eqref{equ_edgeweight_gauss_dict} for
			$\sigma = 5$ degrees: thick edges weigh at least $0.5$, thin
			edges between $0.1$ and $0.5$, dotted edges between $0.01$ and
			$0.1$, and the eight pairs below $0.01$ are not drawn. (b) The
			$28$ pairs on the Gaussian curve (solid curve) of the weight
			against the Euclidean distance between the feature vectors:
			filled circles are the ten pairs kept by the $k$-NN graph with
			$k = 2$, open squares the pairs it drops. Data generated by
			\texttt{pythondemos/edgeweight.py}
			\label{fig_edgeweight_dict}}
		\end{figure}

\subsection{Cross References}
weighted graph, graph, undirected graph, adjacency matrix, Laplacian matrix, node degree, similarity graph, $k$-NN graph, neighbor, graph clustering, spectral clustering, convex clustering, clustering, clustering error, GTV, GTVMin, network Lasso, FL network, transfer learning, SSL, matrix, ANN

\subsection{References}
\begin{enumerate}
  \item Chung (1997). Spectral Graph Theory. American Mathematical Society, Providence, RI, USA.
  \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 Sun et al. (2021). Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm. J. Mach. Learn. Res., 22(9), pp.~1--32.
  \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 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.
  \item Zhu et al. (2003). Semi-supervised learning using gaussian fields and harmonic functions. In: ICML, pp.~912--919.
\end{enumerate}

\end{document}
