matrix factorization

multi-view clustering

tex-math notation latex

graph theory

spectral clustering

IEEE Journal of Selected Topics in Signal Processing

Spectral clustering is a celebrated algorithm that partitions objects based\non pairwise similarity information. While this approach has been successfully\napplied to a variety of domains, it comes with limitations. The reason is that\nthere are many other applications in which only \\emph{multi}-way similarity\nmeasures are available. This motivates us to explore the multi-way measurement\nsetting. In this work, we develop two algorithms intended for such setting:\nHypergraph Spectral Clustering (HSC) and Hypergraph Spectral Clustering with\nLocal Refinement (HSCLR). Our main contribution lies in performance analysis of\nthe poly-time algorithms under a random hypergraph model, which we name the\nweighted stochastic block model, in which objects and multi-way measures are\nmodeled as nodes and weights of hyperedges, respectively. Denoting by $n$ the\nnumber of nodes, our analysis reveals the following: (1) HSC outputs a\npartition which is better than a random guess if the sum of edge weights (to be\nexplained later) is $\\Omega(n)$; (2) HSC outputs a partition which coincides\nwith the hidden partition except for a vanishing fraction of nodes if the sum\nof edge weights is $\\omega(n)$; and (3) HSCLR exactly recovers the hidden\npartition if the sum of edge weights is on the order of $n \\log n$. Our results\nimprove upon the state of the arts recently established under the model and\nthey firstly settle the order-wise optimal results for the binary edge weight\ncase. Moreover, we show that our results lead to efficient sketching algorithms\nfor subspace clustering, a computer vision application. Lastly, we show that\nHSCLR achieves the information-theoretic limits for a special yet practically\nrelevant model, thereby showing no computational barrier for the case.\n

Hypergraph Spectral Clustering in the Weighted Stochastic Block Model