Spectral Graph Clustering: where does the 'scoring' function come from

[Master1022]

Homework Statement

For an undirected graph with affinity matrix (i.e. weighted adjacency matrix) $A$, how can we determine a good cluster using eigenvalues and eigenvectors.

Relevant Equations

Eigenvectors and eigenvalues

Hi,

I was reading through some slides about graph clustering. In the slides was a very short discussion about 'eigenvectors and segmentation'. I don't quite understand where one of the formulae comes from.

Context: We have some undirected graph with an affinity matrix (i.e. weighted adjacency matrix) $A$. The slide poses the question: What is a good cluster?
It then says: "The element associated with the cluster should have large values connecting one another in the affinity matrix." and then quotes the following formula:
\mathbf{w}_n ^T A \mathbf{w}
where it defines $\mathbf{w}_{n} ^ T$ = association of element $i$ to cluster $n$.
It then says we can impose a scaling requirement such that $\mathbf{w}_n ^T \mathbf{w}_n = 1$. Putting these two equations together yields the familiar eigenvalue equation.

Question: Where does this first formula come from: $\mathbf{w}_n ^T A \mathbf{w}$? As much as I think about it, it doesn't really make much sense to me. I can understand the latter parts of the slide, so if I just move past my misunderstanding, then the rest falls into place. However, I am keen to understand what that 'score' is really calculating.

 

[Office_Shredder]

You can write that as $\sum_{I,j} w_i a_{ij} w_j$, which for every choice of vertices $i$ and $j$ adds the products of their weights in the cluster and how strong their edge in the graph is.