Spectral Clustering a graph in python

Question

I'd like to cluster a graph in python using spectral clustering.

Spectral clustering is a more general technique which can be applied not only to graphs, but also images, or any sort of data, however, it's considered an exceptional graph clustering technique. Sadly, I can't find examples of spectral clustering graphs in python online.

Scikit Learn has two spectral clustering methods documented: SpectralClustering and spectral_clustering which seem like they're not aliases.
Both of those methods mention that they could be used on graphs, but do not offer specific instructions. Neither does the user guide. I've asked for such an example from the developers, but they're overworked and haven't gotten to it.
A good network to document this against is the Karate Club Network. It's included as a method in networkx.

I'd love some direction in how to go about this. If someone can help me figure it out, I can add the documentation to scikit learn.

Notes:

A question much like this one has already been asked on this site.

user_6347358 · Answer

Here is a dummy example just to see what it does to a simple similarity matrix -- inspired by sascha's answer.

Code

import numpy as np
from sklearn.cluster import SpectralClustering
from sklearn import metrics
np.random.seed(0)

adj_mat = [[3,2,2,0,0,0,0,0,0],
           [2,3,2,0,0,0,0,0,0],
           [2,2,3,1,0,0,0,0,0],
           [0,0,1,3,3,3,0,0,0],
           [0,0,0,3,3,3,0,0,0],
           [0,0,0,3,3,3,1,0,0],
           [0,0,0,0,0,1,3,1,1],
           [0,0,0,0,0,0,1,3,1],
           [0,0,0,0,0,0,1,1,3]]

adj_mat = np.array(adj_mat)

sc = SpectralClustering(3, affinity='precomputed', n_init=100)
sc.fit(adj_mat)

print('spectral clustering')
print(sc.labels_)

Output

spectral clustering
[0 0 0 1 1 1 2 2 2]

user_4706171 · Answer

Let's first cluster a graph G into K=2 clusters and then generalize for all K.

We can use the function linalg.algebraicconnectivity.fiedler_vector() from networkx, in order to compute the Fiedler vector of (the eigenvector corresponding to the second smallest eigenvalue of the Graph Laplacian matrix) of the graph, with the assumption that the graph is a connected undirected graph.

Then we can threshold the values of the eigenvector to compute the cluster index each node corresponds to, as shown in the next code block:

import networkx as nx
import numpy as np

A = np.zeros((11,11))
A[0,1] = A[0,2] = A[0,3] = A[0,4] = 1
A[5,6] = A[5,7] = A[5,8] = A[5,9] = A[5,10] = 1
A[0,5] = 5

G = nx.from_numpy_matrix(A)
ev = nx.linalg.algebraicconnectivity.fiedler_vector(G)
labels = [0 if v < 0 else 1 for v in ev] # using threshold 0
labels
# [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]

nx.draw(G, pos=nx.drawing.layout.spring_layout(G), 
           with_labels=True, node_color=labels)

We can obtain the same clustering with eigen analysis of the graph Laplacian and then by choosing the eigenvector corresponding to the 2nd smallest eigenvalue too:

L = nx.laplacian_matrix(G)
e, v = np.linalg.eig(L.todense()) 
idx = np.argsort(e)
e = e[idx]
v = v[:,idx]
labels = [0 if x < 0 else 1 for x in v[:,1]] # using threshold 0
labels
# [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]

drawing the graph again with the clusters labeled:

With SpectralClustering from sklearn.cluster we can get the exact same result:

sc = SpectralClustering(2, affinity='precomputed', n_init=100)
sc.fit(A)
sc.labels_
# [0 0 0 0 0 1 1 1 1 1 1]

We can generalize the above for K > 2 clusters as follows (use kmeans clustering for partitioning the Fiedler vector instead of thresholding):

The following code demonstrates how k-means clustering can be used to partition the Fiedler vector and obtain a 3-clustering of a graph defined by the following adjacency matrix:

A = np.array([[3,2,2,0,0,0,0,0,0],
         [2,3,2,0,0,0,0,0,0],
         [2,2,3,1,0,0,0,0,0],
         [0,0,1,3,3,3,0,0,0],
         [0,0,0,3,3,3,0,0,0],
         [0,0,0,3,3,3,1,0,0],
         [0,0,0,0,0,1,3,1,1],
         [0,0,0,0,0,0,1,3,1],
         [0,0,0,0,0,0,1,1,3]])

K = 3 # K clusters
G = nx.from_numpy_matrix(A)
ev = nx.linalg.algebraicconnectivity.fiedler_vector(G)
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=K, random_state=0).fit(ev.reshape(-1,1))
kmeans.labels_
# array([2, 2, 2, 0, 0, 0, 1, 1, 1])

Now draw the clustered graph, with labeling the nodes with the clusters obtained above:

Spectral Clustering a graph in python

Notes:

3 Answers