Graph-based clustering
A similarity graph represents each data point as a vertex and each pairwise similarity as an edge weight.
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.
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.
Reading a small similarity matrix
Use the generated similarity matrix W to identify the pairwise weights for three data points.
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.
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.
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.
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.
Building the Degree Matrix
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.
Dᵢ,ᵢ = sum of the entries in row i of W
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.
First diagonal entry: Add row 1: 0 + 0.8 + 0.2 = 1.0. Therefore, D₁,₁ = 1.0.
Second diagonal entry: Add row 2: 0.8 + 0 + 0.7 = 1.5. Therefore, D₂,₂ = 1.5.
Third diagonal entry: Add row 3: 0.2 + 0.7 + 0 = 0.9. Therefore, D₃,₃ = 0.9.
Place the sums on the diagonal: Because D is diagonal, the off-diagonal entries are zero.
D = [[1.0, 0, 0], [0, 1.5, 0], [0, 0, 0.9]]
Forming the Laplacian
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.
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.
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].
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].
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].
L = [[1.0, -0.8, -0.2], [-0.8, 1.5, -0.7], [-0.2, -0.7, 0.9]]
Three Matrix Roles
| Matrix | What it contains | Role in the formulation |
|---|---|---|
| W | Pairwise similarity values | Represents the weighted relationships between data points |
| D | Row sums of W on the diagonal | Summarizes the total edge weight associated with each data point |
| L | The result of D − W | Combines degree information and pairwise similarity information into the graph Laplacian |
Common Matrix Mistakes
Treating D as another copy of W
The degree matrix is diagonal, and each diagonal entry is a row sum from W.
Fix:
Sum each row of W and place the result on the matching diagonal position of D.Using column values instead of the corresponding row sums
The degree matrix definition specifies that Dᵢ,ᵢ equals the sum of row i of W.
Fix:
For each index i, add the entries in row i and use that sum for Dᵢ,ᵢ.Confusing W with L
W stores pairwise similarities, while L is constructed from D and W using L = D − W.
Fix:
Keep the construction separate: first identify W, then calculate D, then subtract W from D.Describing any partition as a good clustering
The clustering objective favors high-weight internal edges and low-weight edges between groups.
Fix:
Evaluate a partition by whether it keeps strong relationships within groups and weak relationships across groups.
Apply the Construction
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.
- 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.