Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a clustering algorithm by learning from the weighted similarity of each data partition. More precisely, the authors propose an unsupervised framework which aims to minimize an objective of a similarity-based classifier. Then, the upper bound of excess risk of this classifier is provided by Rademacher complexity. They show that the weighted kernel similarity is a special case of the general framework, and they apply it to discriminative clustering by iteratively optimizing the class labels and the weights of similarity. Finally, experiments are conducted to verify the effectiveness of the proposed algorithm.
main_review: Strength: 
This paper presents a learnable similarity function that adaptively adjusts the weights of the similarity between one sample and the samples of some class. 
The authors also provide theoretical results to support the propose algorithm and give the strict proofs. 
The experimental results of the proposed algorithm outperform that of the other comparable clustering algorithms.

Weaknesses:
1. The expected loss in Eq. (4) seems to be not matched with the corresponding empirical loss. Moreover, the authors should explain how the empirical loss in Eq. (4) can be transformed into Eq. (5). The detailed derivative process should be listed in the appendix. This is important.
2. It’s not suitable to use boldface to represent a scalar variable. 
3. There are some typos in this paper.
4. Some variables lack necessary description, e.g., \mathbb{1}_{y_i \neq y_j} in Eq. (7).

summary_of_the_review: The details of the paper needs further refinement.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a new discriminative clustering framework by learning an unsupervised classifier from unlabeled data. An unsupervised classifier is learned from every hypothetical data partition, and the optimal data partition is then regarded as the partition corresponding to the minimum generalization error bound of the unsupervised classifier. The authors use a similarity-based classifier as the unsupervised classifier in this framework and derive its generalization error bound as the sum of discriminative similarity between different clusters. The proposed algorithm, CDS via unsupervised kernel classification (CDSK), then minimizes the between-cluster discriminative similarity. Extensive experimental results with the comparison with a broad range of baselines confirm the superior performance of the proposed algorithm.
main_review: Strengths: 

The proposed CDS framework seems interesting and it is a principled framework of data clustering. In fact, the maximum margin based clustering methods are implicitly based on such a framework, and it seems nice to explicitly formulate this framework in this paper. This paper also provides strong theoretical results for the generalization error bound of unsupervised similarity-based classifier using Rademacher complexity. As explained in Remark 3.4 and the appendix, the derived generalization bound is a generalized version of the well-established generalization bound for kernel machines, so it has an independent theoretical interest.

This paper also conducts extensive experimental results with various baselines from the similarity-based clustering and discriminative clustering literature. I particularly appreciate the detailed discussion in Section 5, which places CDSK in a clear position in the literature and explains its significance.

Weakness: 

It could add more value to this paper if the authors provide more examples showing why the derived discriminative similarity is better than conventional similarities, such as the regular kernel similarity and the similarity used in the sparse graph (especially subspace)-based clustering literature. 

summary_of_the_review: This paper presents a novel and interesting clustering method with theoretical explanations, and the detailed discussion with the similarity-based clustering and discriminative clustering literature is appreciated. I encourage the authors to add more examples showing the comparison between the derived discriminative similarity and conventional similarity used in data clustering.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new clustering framework called Clustering by Discriminative Similarity (CDS). CDS learns an unsupervised similarity-based classifier from each data partition, and searches for the optimal partition of the data by minimizing the generalization error of the learnt classifiers associated with the data partitions. In contrasts with kernel similarity with uniform weights, the induced discriminative similarity with learnable weights enhances its capability to represent complex inter-connection between data. Based on CDS, CDSK is proposed as a new clustering method, with its effectiveness demonstrated by experimental results.
main_review: Positive:
(1) Under the framework of CDS, discriminative similarity is induced by the generalization error bound for unsupervised similarity-based classifier. The authors conduct a complete and detailed theoretical analysis, and the results provide theoretical guarantee on the discriminative similarity can be induced from kernel density classification.
(2) Moreover, based on the CDS model, the authors develop a clustering algorithm termed Clustering by Discriminative Similarity via unsupervised Kernel classification (CDSK). 
(3) CDSK uses a PSD kernel as the similarity function, and outperforms competing clustering algorithms, including nonparametric discriminative similarity based clustering methods and similarity graph based clustering methods, demonstrating the effectiveness of CDSK. 

Negative:
(1)	Clustering performance highly depends on the effective data similarity. One of the main contributions of this paper is to propose a discriminative similarity. As is known to all, there exists a lot of classic similarity learning paradigms, such as metric learning methods and subspace learning methods. What are the main differences between these methods and the proposed method in this paper. I hope that the authors will theoretically or experimentally discuss the specific similarities and differences in a more detail way. Taking LRR as an example, the authors hope to obtain the similarity matrix has a property of low rank. What kind of properties does the discriminative similarity contain in this paper. 
(2)	The authors let S^K_ij=2(\alpha_i+\alpha_j-\lambda\alpha_i\alpha_j)K(x_i-x_j) be the discriminative similarity between data from different classes. The authors did not clearly explain what the essential definition of this formula is. Could the authors explain the physical meaning of this formula more specifically. I hope the author can give an example to explain how does the similarity with learnable weights reflect discrimination.
(3)	The authors use Gaussian kernel as the predefined kernel, whether different predefined kernel have an impact on the final clustering results.
(4)	Does there exist kernel learning methods based on samples weighting, I believe there may be exist. It is suggested that the authors make a deep analysis on the related work and summarize what are the key differences between these efforts and the proposed method in this paper.
(5)	The authors conduct a complete and detailed theoretical analysis, but the description of the algorithm process is not clear and the optimization process is not detailed enough.
(6)	The experiments are inadequate in this paper, it is hoped that the authors give the parameter analysis and convergence analysis of the algorithm in an experimental way. The authors should compare the efficiency of different algorithms through the running time of different algorithms.

summary_of_the_review: The paper contributes some new ideas and the motivation of this paper is clear. This paper proposes a new clustering framework termed Clustering by Discriminative Similarity (CDS). Based on this model, the authors develop a CDSK clustering algorithm. The paper is well organized. The authors conduct a complete and detailed theoretical analysis. Experiments on real-world datasets validated the effectiveness of the proposed methods.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a discriminative similarity clustering method via unsupervised classification and provides the generalization bound for the similarity classification. The experimental results show the effectiveness of the proposed method.
main_review: Strengths:
1. The paper is technically solid and it provides the theoretical analysis of the generalization bound.
2. The paper proposes a simple yet effective clustering method and provide the hyper-parameter tuning strategy.
3. The experimental results show the effectiveness of the proposed method.

Weaknesses:
1. The motivation is unclear for me. What are the benefits of the proposed discriminative similarity clustering method compared with other similarity based clustering methods?
2. The compared methods in Experiments are not the most recent ones. Among the 10 compared methods, only one was proposed in 2021, and all other methods were proposed before 2015. It would be better to compare with some more recent state-of-the-art clustering methods.
3. The computational complexity has been already analyzed in Page 6. I do not understand why  Section "Computational Complexity" is repeated in Experiments. Maybe the authors want to compare with other methods w.r.t. computational complexity? But I do not find such comparison. It would be better to show the comparison results of the  computational complexity and running time on the used data sets.
4. The Captions of Table 1 and Table 2 are exactly the same, which need to be corrected. Moreover, in the Caption, it says "$c$ in the left column is the cluster number", but I do not find $c$ in Tables 1 and 2.
summary_of_the_review: Although there are some concerns, the paper proposes an interesting and effective method and also provides some theoretical analysis.  Therefore I recommend for weak accept.
review_title: null

Meta-review: The authors provide a framework for unsupervised clarification based on minimizing a between-cluster discriminative similarity. It is more flexible than existing methods whose kernel similarity implicitly assumes uniform weights, and the authors connect to ideas such as max-margin and weighted kernel approaches. This yields a clustering algorithm naturally that alternates between updating class labels and similarity weights. Moreover the reviewers (and I) appreciate the analysis of generalization error through Rademacher complexity arguments and detailed author responses. I might add while the paper draws connections to weighted kernel methods and have since added references to sparse subspace clustering etc, there is recent interest in using similar arguments to derive error bounds and uniform concentration results for center-based methods that might be included in the survey of related work, for instance recent work from Swagatam Das and collaborators. The authors have importantly added details on the optimization using SMO, and the revision should include these details in a clear exposition together with the computational complexity discussion mentioned in their response.
Decision: Accept (Poster)