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

In summary, the slides discussed graph clustering and the question of what makes a good cluster. It introduced the formula ## \mathbf{w}_n ^T A \mathbf{w} ##, where ##\mathbf{w}_{n} ^ T ## represents the association of an element to a cluster, to evaluate the strength of connections between elements in the cluster using the affinity matrix. To make this formula more meaningful, a scaling requirement was imposed, resulting in the familiar eigenvalue equation. The purpose of this formula is to calculate a score that takes into account both the weights of elements in the cluster and the strength of their connections in the graph.
  • #1
Master1022
611
117
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:
[tex] \mathbf{w}_n ^T A \mathbf{w} [/tex]
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.
 
Physics news on Phys.org
  • #2
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.
 

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

1. What is spectral graph clustering?

Spectral graph clustering is a machine learning technique used to group data points into clusters based on their similarity and connectivity in a graph. It involves analyzing the eigenvalues and eigenvectors of a graph's adjacency matrix to identify clusters.

2. How does spectral graph clustering work?

Spectral graph clustering works by first constructing a graph representation of the data, where each data point is a node and the edges represent the relationships or similarities between them. The graph's adjacency matrix is then calculated, and its eigenvalues and eigenvectors are analyzed to identify clusters. The data points are then assigned to clusters based on their corresponding eigenvectors.

3. What is the purpose of the 'scoring' function in spectral graph clustering?

The scoring function in spectral graph clustering is used to evaluate the quality of the identified clusters. It measures how well the data points are grouped together and how distinct the clusters are from each other. This helps to determine the optimal number of clusters and improve the overall accuracy of the clustering results.

4. Where does the 'scoring' function come from in spectral graph clustering?

The 'scoring' function in spectral graph clustering is derived from the graph's Laplacian matrix, which is a measure of the graph's connectivity. It is calculated by comparing the eigenvalues of the Laplacian matrix to the eigenvalues of the adjacency matrix and using this information to determine the quality of the clusters.

5. What are the advantages of using spectral graph clustering?

Spectral graph clustering has several advantages, including its ability to handle non-linear relationships between data points, its robustness to noise and outliers, and its ability to identify clusters of varying shapes and sizes. It also does not require prior knowledge of the number of clusters, making it a useful tool for exploratory data analysis.

Similar threads

Replies
1
Views
739
  • Linear and Abstract Algebra
Replies
1
Views
979
  • Calculus and Beyond Homework Help
Replies
2
Views
590
  • Programming and Computer Science
Replies
8
Views
2K
  • Atomic and Condensed Matter
Replies
0
Views
494
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Replies
1
Views
837
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Replies
4
Views
541
  • Calculus and Beyond Homework Help
Replies
7
Views
5K
Back
Top