Matrix representations of data relationships
A similarity graph represents each data point as a vertex and each pairwise similarity as an edge weight.
From Data Points to Relationships
Clustering is often introduced as grouping similar data points. A graph-based representation makes that goal visible: each data point becomes a vertex, and the relationship between two points becomes a weighted edge. The resulting similarity graph can then be represented with matrices that record pairwise similarity, node connectivity, and the structure used for graph-based clustering.
Building the Similarity Matrix
The similarity matrix W records the pairwise relationships represented by the graph. An entry of W corresponds to the similarity weight associated with a pair of data points. Large weights represent stronger relationships, while small weights represent weaker relationships. The way weights are assigned depends on the chosen similarity definition. One possible construction uses a distance function d and a parameter σ, applying the specified exponential expression to the distance between two points.
For this illustration, the three rows and three columns correspond to three data points. The value 0.9 represents a stronger relationship between Point 1 and Point 2 than the values 0.2 and 0.3 represent for the other pairings. These numbers are an illustrative choice; the source concept is that W stores pairwise similarity weights.
Partitioning the Graph
Once the data has been represented as a similarity graph, clustering becomes a graph-partitioning problem. A good partition places strongly connected points in the same group and leaves weaker connections between groups. In matrix terms, the clustering objective is expressed through high-weight internal edges and low-weight edges between groups.
A Three-Point Partition
Using the illustrative weights W[1,2] = 0.9, W[1,3] = 0.2, and W[2,3] = 0.3, identify a partition that reflects stronger internal similarity and weaker connections between groups.
- 1Compare the pairwise weights
The relationship between Points 1 and 2 has weight 0.9, which is larger than the relationships from Point 3 to Points 1 and 2.
- 2Propose the groups
Place Points 1 and 2 in one group and Point 3 in another group.
- 3Check the partition
The 0.9 relationship is internal to the first group, while 0.2 and 0.3 are connections between the proposed groups.
The partition {Point 1, Point 2} and {Point 3} illustrates the objective of high-weight internal connections and lower-weight connections between groups.
Reading Node Degrees
The degree matrix D records the total similarity associated with each data point. D is diagonal, and each diagonal entry Dᵢ,ᵢ equals the sum of the corresponding row of W. Every off-diagonal entry of D is zero.
- 1For Point 1, add the first row: 0 + 0.9 + 0.2 = 1.1.
- 2For Point 2, add the second row: 0.9 + 0 + 0.3 = 1.2.
- 3For Point 3, add the third row: 0.2 + 0.3 + 0 = 0.5.
- 4Place 1.1, 1.2, and 0.5 on the diagonal of D.
- 5Place zero in every off-diagonal position.
Forming the Laplacian
The unnormalized graph Laplacian is defined by L = D - W. It combines the degree information in D with the pairwise similarity information in W.
Entry-by-Entry Construction
Construct L for the illustrative matrices W and D.
- 1Subtract on the diagonal
At position [1,1], calculate 1.1 - 0 = 1.1. At [2,2], calculate 1.2 - 0 = 1.2. At [3,3], calculate 0.5 - 0 = 0.5.
- 2Subtract off the diagonal
At [1,2], calculate 0 - 0.9 = -0.9. At [1,3], calculate 0 - 0.2 = -0.2. At [2,3], calculate 0 - 0.3 = -0.3. The corresponding remaining positions are calculated in the same way.
- 3Assemble the result
Place each calculated difference in the matching position of L.
L = [[1.1, -0.9, -0.2], [ -0.9, 1.2, -0.3], [ -0.2, -0.3, 0.5]]
Three Matrices Three Roles
| Matrix | What it represents | How it is constructed |
|---|---|---|
| W | Pairwise similarity relationships | Its entries contain similarity weights between data points |
| D | Total similarity associated with each data point | It is diagonal; Dᵢ,ᵢ is the sum of row i of W |
| L | The unnormalized graph Laplacian | L = D - W |
The three matrix roles in the graph-based formulation
The construction is sequential but the roles are different. W starts with pairwise relationships. D compresses each row of W into one diagonal value, representing the row's total similarity. L then compares this diagonal degree information with the original pairwise similarities through subtraction.
Common Matrix Mistakes
Common mistake Treating W as the degree matrix
What it looks likeUsing the individual pairwise weights as the diagonal entries of D.
Why it failsW records pairwise similarities, while D uses the sum of an entire row of W for each diagonal entry.
Do this insteadFor each i, calculate Dᵢ,ᵢ by summing row i of W, then set every off-diagonal entry of D to zero.
Common mistake Putting row sums throughout D
What it looks likeWriting 1.1 in several positions of the first row of D.
Why it failsThe degree matrix is diagonal, so its nonzero degree values belong on matching diagonal positions.
Do this insteadPlace the degree for Point i at Dᵢ,ᵢ and use zero elsewhere in that row and column.
Common mistake Computing L as W - D
What it looks likeReversing the subtraction in the Laplacian formula.
Why it failsThe unnormalized graph Laplacian is defined as L = D - W.
Do this insteadStart with D and subtract W entry by entry.
Common mistake Assuming clustering only requires strong internal edges
What it looks likeChoosing a group with strong internal relationships while ignoring the weights connecting it to other groups.
Why it failsThe clustering objective includes both high-weight internal edges and low-weight edges between groups.
Do this insteadEvaluate internal and between-group relationships together.
Check Your Construction
Suppose a three-point similarity matrix is W = [[0, 0.6, 0.1], [0.6, 0, 0.2], [0.1, 0.2, 0]]. Calculate D and then construct L using L = D - W. Finally, identify which pair of points has the strongest similarity and propose a partition that places that pair together.
Hints
- Calculate each diagonal entry of D by summing one row of W.
- Put zero in every off-diagonal position of D.
- Subtract the corresponding entry of W from the corresponding entry of D.
- 1Begin with W, the matrix of pairwise similarity weights. Sum each row of W to obtain the diagonal entries of D, and keep every off-diagonal entry of D equal to zero. Then form the unnormalized graph Laplacian with L = D - W. The clustering objective is represented by a partition with high-weight internal connections and low-weight connections between groups.
Key Takeaways
- A similarity graph turns data points into vertices and pairwise similarities into weighted edges.
- The matrix W records the pairwise similarity weights.
- The diagonal degree matrix D is obtained by summing each row of W.
- The unnormalized graph Laplacian is L = D - W.
- Graph partitioning seeks groups with strong internal connections and weak connections between groups.