# edge weight

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-19. [HTML](https://dictionaryofml.org/terms/edgeweight.html) · [typeset PDF](https://dictionaryofml.org/terms/edgeweight.pdf) · [LaTeX](https://dictionaryofml.org/terms/edgeweight.tex) · [Python demo](https://dictionaryofml.org/terms/edgeweight.py) · [notebook](https://dictionaryofml.org/terms/edgeweight.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

An edge weight is a nonnegative number $A_{i,i'}$ attached to the edge $\{i,i'\}$ of a weighted graph that measures how strongly the two nodes it joins are connected. Collected in the weight matrix ${\mathbf A}$, 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, 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; an k-nearest-neighbor 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. Machine learning 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, which are model parameters.

## 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 ${\mathbf x} \in \mathbb{R}^{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 $i = 1,
\ldots, n$, here with $n = 8$, and an edge $\{i,i'\}$ between two days carries a number that says how similar they are: the edge weight $A_{i,i'} \geq 0$. In Fig. 1(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.

A weighted graph $\mathcal{G} = (\mathcal{V}, \mathcal{E}, {\mathbf A})$ consists of a node set $\mathcal{V} = \{1, \ldots, n\}$, an edge set $\mathcal{E}$, and an edge weight $A_{i,i'}$ for every edge $\{i,i'\} \in \mathcal{E}$. The weights of an undirected graph without self-loops are collected in the weight matrix ${\mathbf A} \in \mathbb{R}^{n \times
n}$. Its entries satisfy

\begin{equation}
\tag{1}
A_{i,i'} = A_{i',i}
\geq 0 \text{,} \quad
A_{i,i} = 0 \text{,} \quad \text{and} \quad
A_{i,i'} = 0 \text{ for }
\{i,i'\} \notin \mathcal{E} \text{.}
\end{equation}

The first condition in the weight matrix Eq. (1) holds because the edge $\{i,i'\}$ of an undirected graph is the edge $\{i',i\}$, 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; Luxburg, 2007, Sect. 2). An unweighted graph is the special case in which every edge has weight $1$. The weighted node degree of node $i$ is the row sum $\sum_{i'=1}^{n} A_{i,i'}$ of the weight matrix (Hastie et al., 2009, Sect. 14.5.3).

In machine learning, edge weights come from two sources. The first source is the feature vectors of the data points: the $m$ data points of a dataset become the nodes of a similarity graph, with $n = m$, 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}
\tag{2}
A_{i,i'} := \exp \Big( -
\left\lVert {\mathbf x}^{(i)} -
{\mathbf x}^{(i')} \right\rVert_{2}^{2} \big/ (2 \sigma^{2}) \Big)
\quad \text{for } i \neq i' \text{,}
\end{equation}

with a width $\sigma > 0$ (Hastie et al., 2009, Sect. 14.5.3; Luxburg, 2007, Sect. 2). The Gaussian weight Eq. (2) 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. 1(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 (Luxburg, 2007, Sect. 8).

The Gaussian weight Eq. (2) 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. The pair $\{i,i'\}$ is an edge if ${\mathbf x}^{(i')}$ is among the $k$ nearest neighbors of ${\mathbf x}^{(i)}$ or ${\mathbf x}^{(i)}$ among those of ${\mathbf x}^{(i')}$. An edge keeps the Gaussian weight Eq. (2), and every other weight is set to zero (Hastie et al., 2009, Sect. 14.5.3; 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-nearest-neighbor 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. 1(b) marks the kept pairs by filled circles and the dropped pairs by open squares. The k-nearest-neighbor 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 (Luxburg, 2007, Sect. 8).

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, 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.

The edges of an artificial neural network also carry weights, and those are a different object: an artificial neural network 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.

Edge weights enter machine learning methods through weighted sums over the edges. A node signal $\mathbf{u} = (u_{1}, \ldots,
u_{n})^{\top} \in \mathbb{R}^{n}$ assigns one number to every node, such as a label or a prediction. The Laplacian matrix ${\mathbf L}^{(\mathcal{G})}$ of the graph satisfies

\begin{equation}
\tag{3}
\mathbf{u}^{\top} {\mathbf L}^{(\mathcal{G})} \mathbf{u} =
\sum_{\{i,i'\} \in \mathcal{E}}
A_{i,i'}
\big( u_{i} - u_{i'} \big)^{2} \text{,}
\end{equation}

the Laplacian quadratic form (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 $\mathcal{C} \subseteq \mathcal{V}$ of the nodes, $u_{i} = 1$ for $i \in \mathcal{C}$ and $u_{i} = 0$ otherwise, the quadratic form Eq. (3) is the total weight of the edges between $\mathcal{C}$ 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 ${\mathbf L}^{(\mathcal{G})}$ (Luxburg, 2007, Sect. 5).

Semi-supervised learning on a graph seeks a node signal that agrees with the labels of the few labeled nodes and makes the quadratic form Eq. (3) 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 replaces the squared difference in the quadratic form Eq. (3) by a measure of the discrepancy between the local models of the two nodes. Generalized total variation minimization adds it to the local training errors, as in federated learning 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).

Convex clustering uses the edge weights in its objective function. Every data point ${\mathbf x}^{(i)}$ gets its own cluster centroid ${{\mathbf w}}^{(i)}$, and the cluster centroids minimize

\begin{equation}
\tag{4}
\sum_{i=1}^{n}
\left\lVert {\mathbf x}^{(i)} -
{{\mathbf w}}^{(i)} \right\rVert_{2}^{2} + \alpha
\sum_{\{i,i'\} \in \mathcal{E}}
A_{i,i'}
\left\lVert {{\mathbf w}}^{(i)} -
{{\mathbf w}}^{(i')} \right\rVert_{2} \text{,}
\end{equation}

with a regularization parameter $\alpha \geq 0$ (Hocking et al., 2011; Sun et al., 2021, Eq. (1)). The first sum in the objective function Eq. (4) is the clustering error of the cluster centroids, the training error that empirical risk minimization 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 $\alpha$ 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$.

![Figure 1 of the entry edgeweight](https://dictionaryofml.org/terms/fig/edgeweight-fig1.svg)

*Figure 1: (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 Eq. (2) 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-nearest-neighbor graph with $k = 2$, open squares the pairs it drops. Data generated by pythondemos/edgeweight.py*

**See also:** [weighted graph](https://dictionaryofml.org/terms/weightedgraph.html), graph, undirected graph, adjacency matrix, [Laplacian matrix](https://dictionaryofml.org/terms/LapMat.html), node degree, similarity graph, $k$-nearest-neighbor graph, neighbor, [graph clustering](https://dictionaryofml.org/terms/graphclustering.html), [spectral clustering](https://dictionaryofml.org/terms/specclustering.html), convex clustering, [clustering](https://dictionaryofml.org/terms/clustering.html), [clustering error](https://dictionaryofml.org/terms/clusteringerror.html), generalized total variation, generalized total variation minimization, network Lasso, federated learning network, [transfer learning](https://dictionaryofml.org/terms/transferlearning.html), semi-supervised learning, [matrix](https://dictionaryofml.org/terms/matrix.html), [artificial neural network](https://dictionaryofml.org/terms/ann.html).

## References

- Chung (1997). Spectral Graph Theory. *American Mathematical Society*.
- Luxburg (2007). A tutorial on spectral clustering. *Statist. Comput.*. <https://doi.org/10.1007/s11222-007-9033-z>
- Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-84858-7>
- Shi and Malik (2000). Normalized Cuts and Image Segmentation. *IEEE Trans. Pattern Anal. Mach. Intell.*. <https://doi.org/10.1109/34.868688>
- Zhu et al. (2003). Semi-supervised learning using gaussian fields and harmonic functions. *ICML*.
- Hallac et al. (2015). Network Lasso: Clustering and Optimization in Large Graphs. *Proc. 21st ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining*. <https://doi.org/10.1145/2783258.2783313>
- Hocking et al. (2011). Clusterpath: An Algorithm for Clustering using Convex Fusion Penalties. *Proc. of the 28th International Conference on Machine Learning,*.
- Sun et al. (2021). Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm. *J. Mach. Learn. Res.*. <https://jmlr.org/papers/v22/18-694.html>

## Cite this entry

```bibtex
@misc{dictml_edgeweight,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {edge weight},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-20},
  url = {https://dictionaryofml.org/terms/edgeweight.html}
}
```
