11

Background: In Newman's PNAS 2006 paper Modularity and community structure in networks, the first eigenvector splits the graph in two clusters, and then each cluster can be further divided by eigenvector of a modified Laplacian of the nodes within this cluster. This leads to further splitting and a binary tree kind of structure of the nodes can be achieved. This makes sense in terms of maximizing the modularity of the clusters.

In Ng, Jordan and Weiss's NIPS 2001 paper On Spectral Clustering, they simply take the first $k$ eigenvectors and then use $k$-means to make clusters using the eigenvectors as features. I understand that this is not maximizing the modularity, but it makes sense for clustering. However, I am curious whether it maximizes any objective function.

Question: Are there other approaches to making more than two clusters from spectral clustering?

What if I take the first $k$ eigenvectors and make clusters based on the sign of the components? Will I get $2^k$ clusters? For $k=1$ will it reduce to Newman's algorithm? Does this make sense? If not, why not?

Are there any other approaches to make more than two clusters either by taking the first $k$ eigenvectors or by hierarchical partitioning?

Chill2Macht
  • 5,639
  • 4
  • 25
  • 51
highBandWidth
  • 2,092
  • 2
  • 21
  • 34
  • There is absolutely no guarantee that the first $k$ eigenvectors will lead to $2^k$ clusters. Neither of the papers linked suggest this. If anything in the 2001 NIPS paper they get up to 8 clusters with just two components. (Also for the examples shown I somehow fail to see how DBSCAN would not get great results given someone is not totally naive in regards with the choice of epsilon.) – usεr11852 Mar 19 '17 at 22:12
  • @usεr11852 What I meant with $2^k$ clusters is that you assign clusters based on the sign of each of the $k$ eigenvectors. I didn't say the papers suggest this. My question is theoretical: What methods make sense, and why? – highBandWidth Mar 19 '17 at 23:46
  • @William why were my assertions changed to questions? – highBandWidth Mar 19 '17 at 23:49
  • Cool, thanks for the clarification. You might want to make this more clear to the body of the question. I am a bit uncertain what is asked. (In general it is an interesting question and I have starred it but I am a bit uncertain about the answer you are looking for) – usεr11852 Mar 19 '17 at 23:51
  • @usεr11852 Well, my question is what are the ways of thinking about making more than two clusters from spectral methods? Specifically, the way I think of it, is to take the signs of the first k eigenvectors of the Laplacian and use these. For $k=1$, I think this is Newman's method. Why should we not extend it to $k>1$? What is theoretically different from this vs. NIPS paper? By theoretically I mean what objective function is each solving for? Or qualitatively, what kind of clusters is each looking for? Any one answer to these would be nice. DBSCAN is not a spectral method, is it? – highBandWidth Mar 19 '17 at 23:58
  • Well, in that case I think that the fact we use $k$-means means we can get as many clusters as you want. No need to use "signs". (Or maybe I misunderstand what you want to do?..) No DBSCAN is not a spectral method; I mentioned it as a simple and established method that would do fine in the 2D examples shown. – usεr11852 Mar 20 '17 at 00:05
  • @usεr11852 Yes, so using k-means basically means we are just transforming the data using PCA and then doing k-means. That's sort of spectral. I am interested in the theory of what spectral methods do. Newman's paper says that they maximize modularity. Their way of further splitting proceeds one way, and I am asking what are other ways of extending spectral clustering. Which of them should work and which won't? I am less interested in the actual clustering of a real data set with other methods. – highBandWidth Mar 20 '17 at 00:51

0 Answers0