Spectral Clustering Versus Watanabe Theorem

Abstract

We devote this paper to a special case of Graph Spectral Clustering of graphs with identical distances between nodes. This study is motivated by the special theorem presented by Watanabe which claims that given all derivable attributes are taken into account, all distinct objects are at the same distance. As the multi-view clustering becomes popular, the mentioned Watanabe theorem may imply serious problems for recovering the intrinsic structure of the collection of objects. We show that Graph Spectral Clustering should not be affected in the most favourable case that is block structure of similarity matrix in theory, but in practice the underlying k-means algorithm introduces up to 20% error rate in assignment of elements to clusters.