Multi-view clustering is a powerful approach for discovering underlying structures hidden behind diverse views of datasets. Most existing multi-view spectral clustering methods use fixed similarity matrices or alternately updated ones. However, the former often fall short in adaptively capturing relationships among different views, while the latter are often time-consuming and even impractical for large-scale datasets. To the best of our knowledge, there are no multi-view spectral clustering methods can both construct multi-view similarity matrices inexpensively and preserve the valuable clustering insights from previous cycles at the same time. To fill in this gap, we present a Sum-Ratio Multi-view Ncut model that share a common representation embedding for multi-view data. Based on this model, we propose a restarted multi-view multiple kernel clustering framework with self-guiding. To release the overhead, we use similarity matrices with strict block diagonal representation, and present an efficient multiple kernel selection technique. Comprehensive experiments on benchmark multi-view datasets demonstrate that, even using randomly generated initial guesses, the restarted algorithms can improve the clustering performances by 5-10 times for some popular multi-view clustering methods. Specifically, our framework offers a potential boosting effect for most of the state-of-the-art multi-view clustering algorithms at very little cost, especially for those with poor performances.
