Spectral Clustering Using Multilinear SVD: Analysis, Approximations and Applications

Authors

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

DOI:

https://doi.org/10.1609/aaai.v29i1.9556

Keywords:

Clustering, Hypergraph partitioning, Multilinear SVD

Abstract

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.

Downloads

Published

2015-02-21

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

Issue

Section

Main Track: Novel Machine Learning Algorithms