Distance functions for similarity construction

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.

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.

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.

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.

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.