Distance functions for similarity construction

From distances to connections

Clustering is often introduced as the task of grouping similar data points. A graph-based formulation makes that idea visible: each data point becomes a vertex, and the relationship between two points becomes a weighted edge. The central challenge is to decide how strongly two points should be connected. A distance function measures how far apart two points are, and a similarity construction converts that distance into an edge weight.

The weight should represent similarity rather than distance. In the clustering formulation described by the source, points placed in the same group should have high-weight internal edges, while points placed in different groups should have low-weight edges between them. Thus, the graph stores the pairwise evidence that a clustering method uses.

Data points as weighted vertices

Suppose a collection contains three data points. The graph representation gives each point a vertex. Every pairwise relationship is represented by an edge whose weight records the similarity assigned to that pair. A larger edge weight means that the pair has been assigned a stronger similarity in the graph.

A distance function is one possible starting point for assigning these weights. The source describes using a distance function d together with a parameter σ in a specified exponential expression. That expression uses the distance between two points to define an entry of the similarity matrix W. The important construction idea is that pairwise distances are transformed into pairwise similarity weights before the graph is partitioned.

Reading the similarity matrix

The weighted graph can be recorded as a similarity matrix W. Each entry Wᵢ,ⱼ represents the similarity weight associated with the relationship between data point i and data point j. In this way, the matrix is not a separate idea from the graph: it is a tabular representation of the graph's pairwise edge weights.

Degrees from row sums

Partitioning the graph

Once pairwise similarities have been represented as weighted edges, clustering becomes a graph-partitioning problem. A useful partition places strongly connected points in the same group and keeps weakly connected relationships between groups. This expresses both sides of the clustering objective: high-weight internal edges and low-weight edges that cross from one group to another.

In the generated example, Points 1 and 2 have weight 0.8 between them, while their relationships with Point 3 have weights 0.2 and 0.3. A partition placing Points 1 and 2 together and Point 3 in another group follows the stated objective: the strongest relationship remains internal, and the weaker relationships cross the group boundary.

Subtracting W from D

Three matrices, three roles

A reliable way to remember the sequence is: first construct W from pairwise similarity information; then sum each row of W to obtain the diagonal entries of D; finally subtract W from D to obtain L. W describes relationships, D summarizes each point's total relationship weight, and L combines those two views.

Common construction mistakes

• Treating W as a distance matrix rather than a similarity matrix.

  The graph formulation described here uses entries of W as similarity weights on edges.

  Fix: Interpret Wᵢ,ⱼ as the similarity weight assigned to the relationship between points i and j.

• Using one W entry as the degree of a point.

  The degree matrix is defined from the sum of the corresponding row of W.

  Fix: Add all similarity weights in the relevant row before placing the result on D's diagonal.

• Putting degree values throughout D.

  D is diagonal.

  Fix: Place each degree only in its matching diagonal position.

• Constructing L by adding D and W.

  The unnormalized graph Laplacian is defined by subtraction.

  Fix: Use L = D - W and subtract corresponding entries.

• Choosing groups based only on isolated point labels.

  The graph-partitioning objective concerns high-weight internal edges and low-weight edges between groups.

  Fix: Inspect the weight structure represented by W.

Check your construction

1. A distance function can provide pairwise information that is converted into similarity weights. Those weights form W, where each data point is a vertex and each pairwise relationship is a weighted edge. Graph partitioning seeks groups with high-weight internal edges and low-weight edges between groups. The degree matrix D is diagonal, with each Dᵢ,ᵢ equal to the sum of row i of W. The unnormalized graph Laplacian is then constructed as L = D - W.