Concepts / Graph-based clustering

Graph-based clustering

A similarity graph represents each data point as a vertex and each pairwise similarity as an edge weight.

  • Programming

From Points to Connections

Clustering is often introduced as the task of grouping similar data points. Graph-based clustering changes the representation of that task: each data point becomes a vertex, and the relationship between two points becomes a weighted edge. The edge weight records how similar the pair is. This lets the clustering problem be studied through the structure of a weighted graph.

Point 1Similarityweight between Point 1 andPoint 2Point 2Similarityweight between Point 1 andPoint 3Point 3Similarityweight between Point 2 andPoint 3pairpairpairpairpairpair
How do individual data points become vertices, and how do pairwise similarity values become weighted edges between them?

Similarity Weights

The similarity matrix W stores the pairwise similarity information used to build the graph. A data point corresponds to a vertex, and a pairwise similarity corresponds to an edge weight. A larger edge weight represents a stronger similarity relationship within the graph representation. The exact rule used to calculate a weight can depend on a distance function and a parameter, but the important structural role of W is to collect the pairwise weights.

Worked example

Reading a small similarity matrix

Use the generated similarity matrix W to identify the pairwise weights for three data points.

  1. 1
    Matrix

    Let W = [[0, 0.8, 0.2], [0.8, 0, 0.7], [0.2, 0.7, 0]]. The rows and columns correspond to Point 1, Point 2, and Point 3 in that order.

  2. 2
    Pairwise entries

    The entry in row 1, column 2 is 0.8, so the graph represents the relationship between Point 1 and Point 2 with weight 0.8. The entry in row 1, column 3 is 0.2, so that relationship has weight 0.2.

  3. 3
    Interpretation

    Within this example, the weight 0.8 represents a stronger similarity relationship than the weight 0.2. The matrix is therefore a compact representation of the graph's pairwise similarity information.

Result

W translates pairwise similarity information into a matrix that can be used to construct the degree matrix and the graph Laplacian.

Partitioning the Graph

Once the data has been represented as a graph, clustering becomes a graph-partitioning problem. The desired groups have high-weight internal edges: points placed in the same group should be strongly related. Edges between different groups should have low weights, because points assigned to different groups should be nonsimilar. A useful partition therefore keeps strong relationships inside groups and avoids cutting strong relationships between groups.

Point 1Point 3Point 2Point 4high weighthigh weightlow weight or cut
What changes when the graph is divided into clusters, and how do strong within-cluster edges differ from weak or cut between-cluster edges?

Building the Degree Matrix

Definition

The degree matrix D is a diagonal matrix. Its diagonal entry Dᵢ,ᵢ is the sum of the corresponding row of the similarity matrix W. In other words, row i of W contributes one total edge weight to the ith diagonal position of D. Entries outside the diagonal of D are zero.

Formula, step by step
  1. 1
    Take one row of W.
  2. 2
    Add the similarity weights in that row.
  3. 3
    Place the resulting sum in the matching diagonal position of D.
  4. 4
    Keep the other positions of D off the diagonal at zero.
Row 1 of W0, 0.8, 0.2D₁,₁1.0Row 2 of W0.8, 0, 0.7D₂,₂1.5Row 3 of W0.2, 0.7, 0D₃,₃0.9row sumrow sumrow sum
How does each row of the similarity matrix produce one diagonal entry in the degree matrix by summing its edge weights?
Worked example

Calculating D from W

For W = [[0, 0.8, 0.2], [0.8, 0, 0.7], [0.2, 0.7, 0]], calculate the degree matrix D.

  1. 1
    First diagonal entry

    Add row 1: 0 + 0.8 + 0.2 = 1.0. Therefore, D₁,₁ = 1.0.

  2. 2
    Second diagonal entry

    Add row 2: 0.8 + 0 + 0.7 = 1.5. Therefore, D₂,₂ = 1.5.

  3. 3
    Third diagonal entry

    Add row 3: 0.2 + 0.7 + 0 = 0.9. Therefore, D₃,₃ = 0.9.

  4. 4
    Place the sums on the diagonal

    Because D is diagonal, the off-diagonal entries are zero.

Result

D = [[1.0, 0, 0], [0, 1.5, 0], [0, 0, 0.9]]

Forming the Laplacian

Definition

The unnormalized graph Laplacian is defined by L = D - W. It combines the diagonal summary of graph connectivity in D with the pairwise similarity information in W. The subtraction is performed entry by entry, producing a matrix that represents the graph structure used in this formulation of clustering.

Ddiagonal degree totalsLD − W−entry by entryWpairwise similaritiescombinesubtractproduces
How are the degree matrix and similarity matrix combined entry by entry to produce the Laplacian using L = D - W?
Worked example

Calculating the unnormalized Laplacian

Use D = [[1.0, 0, 0], [0, 1.5, 0], [0, 0, 0.9]] and W = [[0, 0.8, 0.2], [0.8, 0, 0.7], [0.2, 0.7, 0]] to calculate L = D - W.

  1. 1
    Subtract the first row

    The first row of D is [1.0, 0, 0]. Subtracting the first row of W, [0, 0.8, 0.2], gives [1.0, -0.8, -0.2].

  2. 2
    Subtract the second row

    The second row of D is [0, 1.5, 0]. Subtracting [0.8, 0, 0.7] gives [-0.8, 1.5, -0.7].

  3. 3
    Subtract the third row

    The third row of D is [0, 0, 0.9]. Subtracting [0.2, 0.7, 0] gives [-0.2, -0.7, 0.9].

Result

L = [[1.0, -0.8, -0.2], [-0.8, 1.5, -0.7], [-0.2, -0.7, 0.9]]

Three Matrix Roles

MatrixWhat it containsRole in the formulation
WPairwise similarity valuesRepresents the weighted relationships between data points
DRow sums of W on the diagonalSummarizes the total edge weight associated with each data point
LThe result of D − WCombines degree information and pairwise similarity information into the graph Laplacian

W records relationships, D records diagonal degree totals, and L combines them through L = D − W.

Wpairwise similaritiesDdiagonal row sumsLD − Wrow sums createcombined with Wsubtracted from D
What does each matrix contain, and how do similarity information, node connectivity, and graph structure differ across W, D, and L?

Common Matrix Mistakes

  • Common mistake

    Treating D as another copy of W

    What it looks like

    Writing D with the same off-diagonal similarity values as W

    Why it fails

    The degree matrix is diagonal, and each diagonal entry is a row sum from W.

    Do this instead

    Sum each row of W and place the result on the matching diagonal position of D.

  • Common mistake

    Using column values instead of the corresponding row sums

    What it looks like

    Calculating D₂,₂ from a column without checking the stated row-sum definition

    Why it fails

    The degree matrix definition specifies that Dᵢ,ᵢ equals the sum of row i of W.

    Do this instead

    For each index i, add the entries in row i and use that sum for Dᵢ,ᵢ.

  • Common mistake

    Confusing W with L

    What it looks like

    Calling the original pairwise similarity matrix the graph Laplacian

    Why it fails

    W stores pairwise similarities, while L is constructed from D and W using L = D − W.

    Do this instead

    Keep the construction separate: first identify W, then calculate D, then subtract W from D.

  • Common mistake

    Describing any partition as a good clustering

    What it looks like

    Putting strongly connected points in different groups without considering the edge weights

    Why it fails

    The clustering objective favors high-weight internal edges and low-weight edges between groups.

    Do this instead

    Evaluate a partition by whether it keeps strong relationships within groups and weak relationships across groups.

Apply the Construction

MEDIUM

Given W = [[0, 0.4, 0.6], [0.4, 0, 0.1], [0.6, 0.1, 0]], calculate D and then calculate L using L = D − W. Finally, identify which pair has the largest similarity weight.

Hints
  • Calculate one row sum for each diagonal entry of D.
  • Remember that D has zeros away from its diagonal.
  • Subtract corresponding entries of W from D.
  1. 1
    A graph-based clustering formulation starts by turning data points into vertices and pairwise similarities into weighted edges. The similarity matrix W records those weights. The degree matrix D is diagonal, with each diagonal entry equal to the sum of one row of W. The unnormalized graph Laplacian is then constructed as L = D − W. The resulting graph-partitioning objective seeks groups with high-weight internal edges and low-weight edges between groups.

Key Takeaways

  • Each data point becomes a vertex, and each pairwise similarity becomes a weighted edge.
  • Graph-based clustering expresses the goal of finding high-weight edges within groups and low-weight edges between groups.
  • The degree matrix D is diagonal, and Dᵢ,ᵢ is the sum of row i of the similarity matrix W.
  • The unnormalized graph Laplacian is L = D − W.
  • W stores similarities, D stores diagonal degree totals, and L combines both kinds of information.

Related Topics

Related concepts

More concepts starting with G