2
$\begingroup$

I am given a weighted adjacency matrix where some of the entries are corrupted. My goal is to cluster it. I also do not know the number of clusters. I have looked for papers that talk about this problem and I have found these two methods

  • Decompose the adjacency matrix into a low rank and sparse matrix as done here. The low rank matrix represents the different clusters while the sparse matrix refers to the corruptions.
  • Use spectral clustering technique as done here. To compute the number of clusters, first the eigen values of the normalized graph laplacian are computed and arranged in ascending order and the number of clusters k is found by $max_i \{ abs\{{\lambda_i - \lambda_{i+1}}\} \}$ where $\lambda_i$ is the $i^{th}$ eigen value of normalized graph laplacian. ( this is the eigen gap heuristic as described in page 23}.

My question is which of these methods is better in practice and are there any new methods developed that are better than the ones I mentioned.

$\endgroup$
1
  • $\begingroup$ If you're given corrupted entries Robust PCA should be the way to go. Spectral methods assume Gaussian noise which may not correspond to the corruption mechanism present in your problem. Another method of clustering is via NMF which may be of some interest to you. $\endgroup$ May 11, 2018 at 12:50

0

You must log in to answer this question.

Browse other questions tagged .