- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper reformulates kernel k-means and spectral clustering objectives using similarities between empirical distributions defined through kernel mean embeddings. It also proposes a new objective by raising the degree matrix D to the power of a hyperparameter \lambda \in [0,1] and the corresponding \lambda-spectral clustering algorithm. For the \lambda=0 and \lambda=1 the kernel k-means and spectral objectives are obtained respectively. Experimental results are presented indicating how the variation of \lambda affects clustering results.
Critical strengths
S1. The proposed (\lamda dependent) objective and the \lambda spectral clustering method constitute an adaptation (although very simple technically) that deserves to be explored since they constitute a kind of interpolation between the original objectives.
Critical weaknesses
W1. The obtained expressions of the clustering objectives are straightforward rewritings of the formulas using empirical kernel mean embeddings. In my opinion this just constitutes a change in wording; it does not establish substantive mathematical novelty.
W2. The paper contribution would be more important if there were ways to select the critical hyperparameter \lambda.
Questions for authors
Q1. The technical novelty of the proposed criterion and its optimization is limited. Choosing vertex weights (w_x=d_x^\lambda) in the weighted-association framework of Dhillon, Guan, and Kulis (TPAMI, 2007) yields the proposed objective and spectral relaxation. The characterization of previous work as primarily methodological, understates its established objective-level connections.
Q2. It would be interesting to test whether setting \lambda=0.5 provides better results (on average) compared to \lamba=0 or \lambda=1. However, a much larger number of clustering problems should be examined.
Q3. The definition of κ(δ(x), P) is not clear.
Q4. The equation in line 156 contains two equalities and an obvious mistake.
4 comments
rebuttal
Q2: The expanded test gives a direct answer. Fixed averages 0.473/0.397 NMI/ARI over 22 datasets, exceeding at 0.427/0.324 on both metrics. Against at 0.470/0.399, NMI is slightly higher and ARI is close. This supports utility from a fixed interior choice, not only label-selected maxima. The 13 real and nine synthetic datasets comprise the 18-dataset experimental collection plus Iris, Wine, Breast Cancer, and Digits;
All settings share raw numerical features, a dense RBF kernel with (mean pairwise distance ), and Algorithm 1. Datasets above 5,000 points are uniformly subsampled to 5,000, with identical samples across settings. The known class count supplies ; labels do not select , bandwidth, or samples. Entries are mean NMI / ARI over five rounding runs; the largest run-level standard deviation is 0.006. This tests the paper's common preprocessing protocol, without an additional feature-scaling search. (Table 13)
Macro-averages weight datasets equally. The overall ARI is 0.002 below that of the zero endpoint, so the average does not establish dominance over both endpoints. The real-data joint gains below address the separate question of whether a fixed interior choice can be beneficial. Breast Cancer improves over by approximately 0.070 NMI and 0.059 ARI without tuning ; Wine and Gaussian–Line favor zero.
We also standardized each feature to zero mean and unit variance on all 13 real datasets, retaining samples, parameters, and the bandwidth rule. Full mean NMI / ARI results over five rounding runs are: Table 14.
After standardization, both Breast Cancer and Digits gain on both metrics at the fixed midpoint, showing that useful effects extend beyond raw feature scales. The standardized macro-average instead favors the zero endpoint, particularly on Spambase. These contrasting preferences motivate retaining objective choice rather than declaring any endpoint or midpoint universally best.
For targeted confirmation, we used Breast Cancer and Digits, where the preceding study observed interior gains. We tested raw and standardized features over 20 uniform 80% subsamples, fixed , and with . Each subset uses the same kernel and Algorithm 1 for all three settings. Labels provide evaluation and the common known class count only. All scale and bandwidth settings are retained; entries are mean NMI/ARI. (Table 15)
BC denotes Breast Cancer; std denotes per-feature standardization. Breast Cancer yields joint wins at 4/5 raw-scale and 5/5 standardized bandwidths; Digits yields 0/5 and 1/5, respectively. Breast Cancer’s benefit extends across bandwidth and sampling perturbations, whereas Digits is more setting-sensitive. This targeted confirmation complements the complete dataset comparison and supports a practical role for the interior.
We further compared matched subsamples, requiring the fixed midpoint to exceed both endpoints on both NMI and ARI in the same trial. This is stricter than comparing averages. The revised paper reports joint-win counts among the 20 subsamples for every prespecified bandwidth: (Table 17)
At the original bandwidth (), Breast Cancer gives joint wins in 18/20 raw and 17/20 standardized subsamples. Thus the positive result is not driven by one favorable run. These counts describe robustness on the same dataset, not independent-dataset significance tests. Digits shows a different pattern, supporting data-dependent objective choice rather than a claim that one fixed value always dominates.
Q3: Here is the Dirac probability measure at . Applying to distributions denotes the inner product of their mean embeddings, not inserting a distribution as an ordinary data vector into the original kernel. For
\mu_C=\frac{1}{|C|}\sum_{y\in C}\phi(y),\qquad \mu_{\delta_x}=\phi(x),$$ the definition is $$\kappa(\delta_x,\mathcal P_C) =\langle\phi(x),\mu_C\rangle =\frac{1}{|C|}\sum_{y\in C}\kappa(x,y) =s(x,C).$$ Consequently, $|D|\kappa(\delta_x,\mathcal P_D)=\sum_{y\in D}\kappa(x,y)=d_x$. This exactly identifies degree with point-to-global-empirical-distribution similarity. For PSD kernels and finite empirical distributions, no additional density estimation is needed. Q4: Both equalities at line 156 of the original submission are correct. Lowercase $s$ is average similarity and uppercase $S$ is total similarity; the expression does not equate quantities with different normalizations. Written separately, $$s(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum_{x\in C_i,y\in C_j}\kappa(x,y),$$ $$S(C_i,C_j)=|C_i||C_j|\,s(C_i,C_j) =\sum_{x\in C_i,y\in C_j}\kappa(x,y).$$ Both equalities are valid. For example, if $|C_i|=2$, $|C_j|=3$, and all six kernel values equal one, then $s=1$ and $S=6=2\times3\times s$.I thank the authors for the response and additional experimental work. The fact that setting \lambda=0.5 generally leads to improved results increases the value of the paper. Nevertheless, from a practical point of view, the only modification of the proposed \lambda-SC algorithm (compared to typical SC) is the use of {d_i}^\lambda.
rebuttal
Thank you for your further feedback. Our primary contribution is establishing a theoretical connection between spectral clustering and kernel -means. This connection allows us to develop a unified framework that previous work has been unable to achieve, which also delivers superior clustering performance.
Rebuttal
Thanks for your review and valuable suggestions.
W1/Q1: We disagree that the contribution is only a change in wording. Substituting wx=dxλ does place the main objective within Dhillon's family. Our analysis concerns how that choice arises from distributional relationships, when it changes clustering preference, and which aggregation permits the algorithm. Prior work includes objective equivalence, not only solver interchange; our complementary contribution is the distributional explanation on the original common kernel and its design consequences. [Dhillon et al., 2007]
Write S(C,B)=∑x∈C,y∈Bκ(x,y) and dx=S(x,D)=∣D∣κ(δx,PD). The main formulation transforms point-to-global-distribution similarity before aggregating within a cluster; Appendix C.2 reverses that order:
\overline Q_\lambda=\sum_C\frac{S(C,C)}{|C|^{1-\lambda}S(C,D)^\lambda}.$$ The endpoints agree. For $0<\lambda<1$, strict concavity distinguishes the denominators when within-cluster degrees differ. The second denominator cannot be fixed additive point weights: singletons require $w_x=d_x^\lambda$, while a pair would require $a^\lambda+b^\lambda=2^{1-\lambda}(a+b)^\lambda$, false for $a\ne b$. Thus the distributional design choice determines whether the original numerator admits Algorithm 1's fixed-diagonal relaxation, rather than merely changing notation. The interior can also produce a distinct discrete optimum. For $x=(0.3,0.7,2.0,2.5,2.6,4.0,5.6,8.1)$ and the fixed PSD kernel $K_{ij}=\exp[-(70/213)^2(x_i-x_j)^2]$, exhaustive evaluation of all 127 nonempty unordered bipartitions gives: Table 10 This construction directly verifies interior non-redundancy: without changing the kernel or invoking spectral rounding, it gives a unique optimum selected by neither endpoint. Conversely, constant degrees give $Q_\lambda=d_0^{-\lambda}Q_0$ and invariant rankings. The explanation thus characterizes both change and invariance. The construction tests objective behavior; the expanded real and synthetic dataset study below tests practical effects. The interior optimum also persists over a continuous parameter interval. Fix a nonnegative kernel with positive degrees and a number of nonempty clusters. Let $\mathcal C_*$ uniquely maximize $Q_{\lambda_0}$ over those partitions and define $$R=\frac{Q_{\lambda_0}(\mathcal C_*)}{\max_{\mathcal C\ne\mathcal C_*}Q_{\lambda_0}(\mathcal C)}>1, \qquad r=\frac{\max_x d_x}{\min_x d_x}>1.$$ Then $\mathcal C_*$ remains the unique maximizer whenever $$|\lambda-\lambda_0|<\frac{\log R}{\log r},\qquad \lambda\in[0,1].$$ To prove this, set $\Delta=\lambda-\lambda_0$, $a=\min_x d_x^\Delta$, and $b=\max_x d_x^\Delta$. Each cluster denominator satisfies $a m_{\lambda_0}(C)\le m_\lambda(C)\le b m_{\lambda_0}(C)$, where $m_\lambda(C)=\sum_{x\in C}d_x^\lambda$. Nonnegative cluster numerators therefore give $Q_{\lambda_0}(\mathcal C)/b\le Q_\lambda(\mathcal C)\le Q_{\lambda_0}(\mathcal C)/a$. The ratio between the incumbent and any competitor is at least $R/r^{|\Delta|}>1$. If $r=1$, all rankings are invariant. For the eight-point example, the best and second-best scores at $\lambda_0=0.5$ are 3.024 and 2.983, and $r=3.082$. Using the unrounded scores gives a certified radius greater than 0.0118; thus every $\lambda\in[0.489,0.511]$ selects $P_m=\{1,\ldots,6\}/\{7,8\}$, not either endpoint optimum. This conclusion concerns the exact discrete objective, independent of spectral rounding. It predicts when a parameter change must preserve the solution, in terms of the objective margin and degree heterogeneity. The coordinate-perturbation experiment provides a separate check. At Gaussian noise standard deviations 0.01, 0.025, 0.05, and 0.1, the three parameter values still yield pairwise distinct optimal partitions in 100.0%, 99.6%, 85.6%, and 48.5% of 1,000 trials per level. The midpoint retains the original $P_m$ in 100.0%, 99.9%, 98.8%, and 84.3%, respectively. The former statistic tests separation from both endpoints; the latter tests retention of a particular partition. These are controlled objective tests, not labeled benchmark accuracy. W2: A parameter-selection rule would strengthen deployment, as you suggest. We address your accompanying empirical question directly by fixing $\lambda=0.5$ before evaluation. This tests whether useful interior behavior requires label-guided parameter search, while keeping the paper's central question—the distributional relationship and controllable objective choice—distinct from adaptive model selection. Following Q2, we completed the 22-dataset fixed-$\lambda=0.5$ comparison and additional standardization, bandwidth, and resampling checks. The parameter is fixed before evaluation: benefit need not depend on searching with labels. Full results and endpoint comparisons are now included in Appendix H of the revised paper.