Matrix representations of data relationships

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.

W = [[0, 0.9, 0.2],
     [0.9, 0, 0.3],
     [0.2, 0.3, 0]]

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.

Reading Node Degrees

Dᵢ,ᵢ = sum of the entries in row i of W

D = [[1.1, 0, 0],
     [0, 1.2, 0],
     [0, 0, 0.5]]

Forming the Laplacian

L = D - W

L = [[1.1, -0.9, -0.2],
     [-0.9, 1.2, -0.3],
     [-0.2, -0.3, 0.5]]

Three Matrices Three Roles

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

• Treating W as the degree matrix

  W records pairwise similarities, while D uses the sum of an entire row of W for each diagonal entry.

  Fix: For each i, calculate Dᵢ,ᵢ by summing row i of W, then set every off-diagonal entry of D to zero.

• Putting row sums throughout D

  The degree matrix is diagonal, so its nonzero degree values belong on matching diagonal positions.

  Fix: Place the degree for Point i at Dᵢ,ᵢ and use zero elsewhere in that row and column.

• Computing L as W - D

  The unnormalized graph Laplacian is defined as L = D - W.

  Fix: Start with D and subtract W entry by entry.

• Assuming clustering only requires strong internal edges

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

  Fix: Evaluate internal and between-group relationships together.

Check Your Construction

1. Begin 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.