Spectral Clustering Using Multilinear SVD: Analysis, Approximations and Applications


  • Debarghya Ghoshdastidar Indian Institute of Science, Bangalore
  • Ambedkar Dukkipati Indian Institute of Science, Bangalore




Clustering, Hypergraph partitioning, Multilinear SVD


Spectral clustering, a graph partitioning technique, has gained immense popularity in machine learning in the context of unsupervised learning. This is due to convincing empirical studies, elegant approaches involved and the theoretical guarantees provided in the literature. To tackle some challenging problems that arose in computer vision etc., recently, a need to develop spectral methods that incorporate multi-way similarity measures surfaced. This, in turn, leads to a hypergraph partitioning problem. In this paper, we formulate a criterion for partitioning uniform hypergraphs, and show that a relaxation of this problem is related to the multilinear singular value decomposition (SVD) of symmetric tensors. Using this, we provide a spectral technique for clustering based on higher order affinities, and derive a theoretical bound on the error incurred by this method. We also study the complexity of the algorithm and use Nystr ̈om’s method and column sampling techniques to develop approximate methods with significantly reduced complexity. Experiments on geometric grouping and motion segmentation demonstrate the practical significance of the proposed methods.




How to Cite

Ghoshdastidar, D., & Dukkipati, A. (2015). Spectral Clustering Using Multilinear SVD: Analysis, Approximations and Applications. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9556



Main Track: Novel Machine Learning Algorithms