Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies the problem of clustering out-of-sample data over multiple kernel clustering dataset. The authors of the paper seek to solve the problem by learning the embedding functions with a novel approximation strategy by take advantage of the relation between empirical kernel matrix and integral operator of the kernel function. Then, the generalization ability of the method is studied with valuable depth from single kernel setting to multiple kernel setting. Finally, numerical experiments are conducted to verify the superiority of the proposed algorithm.
strengths_and_weaknesses: Strengths:
1. The proposed method can greatly accelerate MKC on handling out-of-sample problem. Though the method is simple, it can reduce the time complexity from $\mathcal{O}(N^3)$ to $\mathcal{O}(N)$. Consequently, the method can enable MKC to be performed on large-scale dataset.
2. The authors offer theoretical analysis about the proposed method. It is the first time the stability of clustering algorithm is analyzed. The paper is technically sound, and the proofs are strict.
3. The paper establishes a connection between the stability of MKC algorithm and the output kernel weights, which enlightens a design principle for this type of algorithms.
Weakness:
1. Some other methods for large-scale implementation of kernel clustering algorithms should be referred, e.g., Nystr\"om [1] and random Fourier feature [2].

2. The proposed clustering risk bound should be compared with other relevant works.

[1] Cameron Musco and Christopher Musco. Recursive sampling for the Nystr\"om method. In NeurIPS 2017.

[2] Radha Chitta, Rong Jin, and Anil K. Jain. Efficient Kernel Clustering Using Random Fourier Features. In ICDM 2012.

3. Experiments are not sufficient. In Section 5.1, the authors provide theoretical analysis of clustering on single kernel. However, the paper lacks corresponding experiments.

4. The codes of experiments are not available.

questions: In experiments, the clustering performance of SimpleMKKM with the proposed method on some datasets is superior to the original one. I think that the authors should give more discussions about this phenomenon.
limitations: None.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper provides a general method that enables multiple kernel clustering algorithms to compute the embedding of out-of-sample points efficiently. Instead of re-computing the sample embedding of the unseen samples with the support of the whole data matrix, the authors directly obtain the embedding by constructing the embedding functions through approximating the eigen function of the integral operator defined by the optimal kernel function. With these functions, the embedding of the out-of-sample data can be easily and accurately calculated. Moreover, the upper bound of excess clustering risk is established based on the studying of stability of the proposed method. Experimental results demonstrate the effectiveness and efficiency of the proposed method.
strengths_and_weaknesses: Strengths

1. The out-of-sample problem of MKC studied by this paper is important and challenging. The idea of enabling kernel clustering algorithms to obtain the embedding of out-of-sample data is novel and interesting. 

2. The conducted generalization study of clustering algorithms is an important theoretical contribution. 
(1) The paper for the first time establishes the excess risk bound of kernel k-means by the analysis of its algorithmic stability. 
(2)  The analysis is extended to multiple kernel setting. The proposed theoretical results enlighten a new way to study the generalization ability of multiple kernel clustering algorithms. 

3. The paper is well written with clear and rational motivation. It presents a novel way of scaling the method to large scale multiple kernel clustering scenario and a new perspective of generalization analysis of MKC. These are valuable for AI researchers in this field. 


Weakness

1. In the paper, only SimpleMKKM is used as an example to verify the effectiveness of the out-of-sample method. As a consequence, the experimental support of the paper is relatively weak. It will be better if more state-of-the-art multiple kernel clustering algorithms, such as [1][2], can be analyzed.

[1] Liu, X.; Dou, Y.; Yin, J.; Wang, L.; and Zhu, E. 2016. Multiple kernel k-means clustering with matrix-induced regularization. In AAAI, 1888–1894.

[2] Gonen, M., and Margolin, A. A. 2014. Localized data fusion for kernel k-means clustering with application to cancer biology. In NIPS, 1305–1313.

2. Some minor issues are as follows.

I. In the proof of Proposition 4.1, $R(H)$ should be written as $R(H,P)$ as its definition in the main text.

II. “Denote the k-th eigenvalue/vector pairs” in Line 483.
questions: 1. Why do the authors select SimpleMKKM as a baseline for the implementation of the proposed method? 

2. The proposed method for construction of the approximated indicator functions is inspired by [3]. However, the contribution over the mentioned method is not clearly described in the manuscript. More information should be given.

[3] Rosasco L, Belkin M, De Vito E., On learning with integral operators. In JMLR, page 905–934, 2010.
limitations: The limitation of the proposed method is considered in the conclusions. The societal impact is not discussed, and this will not cause any potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a new method for efficient multiple kernel clustering (MKC) over out-of-sample data. This method has the potential to scale the existing MKC algorithms to handle large-scale datasets. Then, the generalization ability of the method is studied from the single kernel setting to the multiple kernel setting, which provides valuable insight of the algorithm. Finally, numerical experiments are conducted to verify the superiority of the proposed algorithm.
strengths_and_weaknesses: Some strengths:
1. This work studies the generalization ability of the clustering algorithm based on algorithmic stability, which is a significant and interesting research topic.  By selecting $n$ samples as landmarks, the approximation embedding of the remaining samples can be computed with $O(N)$ time complexity, where $N$ is the sample number. Thus, the method can make existing MKC scalable to large-scale datasets.
2. The theoretical analysis of the paper is novel and sound. Theoretical analysis has proved that the proposed method has desirable generalization ability ($\mathcal{O}((m+1)Kn^{-3/2}+n^{-1/2})$), which provides a tighter bound than the one ($\mathcal{O}(mKn^{-1/2})$) provided in [1]. It guarantees the effectiveness of the proposed method. Moreover, the analysis can be scalable to multiple kernel clustering and the proofs are correct.
3. The paper is easy to follow and well-written.

Some weaknesses:
1. The paper only discusses uniform sampling as the selected method of landmarks. Other sampling strategies (e.g., leverage score [2]) could be tried to further improve the performance of the algorithm.
2. The authors haven’t analyzed the optimal number of landmarks. In the experiments, the number of landmarks is regarded as a hyper-parameter, which seems to require more effort to select the best one.
3. The authors only provide the theoretical and empirical results about SimpleMKKM. Some classic MKC algorithms are not discussed.

[1] Xinwang Liu, En Zhu, Jiyuan Liu, Timothy Hospedales, Yang Wang, and Meng Wang. Simplemkkm: Simple multiple kernel k-means. In arXiv preprint arXiv:2005.04975, 2020.

[2] Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff. Fast approximation of matrix coherence and statistical leverage. Journal of Machine Learning Research, 13:3441–3472, 2012.
questions: Please check the Weakness box.
limitations: None.
review_title: null

Meta-review: metareview: The paper introduces a methodology for clustering out-of-sample data in the multiple kernel clustering (MKC) problem by leveraging the relationship between the empirical kernel matrix and the integral operator of the kernel function. Clustering risk bounds for the proposed method are provided that compare favorably with the literature, and numerical experimentation shows that the methodology performs well when applied to algorithms developed for both single and multiple kernel clustering. The reviewers concur that the methodology enables efficient large-scale MKC and provides a novel perspective on its generalization analysis.
confidence: Certain
Decision: Accept