acceptodds
Under review as a conference paper at ICLR 2027

Distributional Equivalence of Kernel -means and Spectral Clustering

Abstract

The relationship between spectral clustering and kernel -means has long been a subject of interest, but existing work primarily focuses on methodological connections, i.e., how to achieve the objectives of spectral clustering through kernel -means or vice versa. This work, however, overlooks the fundamental connection between their objectives. This paper explores the relationship between their optimization objectives from a distributional perspective and provides a unified framework encompassing both. From a distributional perspective, kernel -means aims to maximize the similarity of the distribution of each cluster, while spectral clustering also minimizes the similarity between the distribution of each cluster and the overall data distribution. Ncut combines these two through division, while Rcut uses subtraction. Based on this connection, a unified framework is proposed that simultaneously overcomes the shortcomings of both NCut and kernel -means.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
spectral clustering, kernel k-means, distritbuion kernel

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_sNAJOpenReview ↗
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

Thanks for your review and valuable suggestions.

W1/Q1: We disagree that the contribution is only a change in wording. Substituting wx=dxλw_x=d_x^\lambda 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)S(C,B)=\sum_{x\in C,y\in B}\kappa(x,y) and dx=S(x,D)=∣D∣κ(δx,PD)d_x=S(x,D)=|D|\kappa(\delta_x,\mathcal P_D). 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.

Q2: The expanded test gives a direct answer. Fixed λ=0.5\lambda=0.5 averages 0.473/0.397 NMI/ARI over 22 datasets, exceeding λ=1\lambda=1 at 0.427/0.324 on both metrics. Against λ=0\lambda=0 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 γ=1/du2\gamma=1/d_u^2 (mean pairwise distance dud_u), and Algorithm 1. Datasets above 5,000 points are uniformly subsampled to 5,000, with identical samples across settings. The known class count supplies kk; labels do not select λ\lambda, 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 λ=0\lambda=0 by approximately 0.070 NMI and 0.059 ARI without tuning λ\lambda; 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 λ∈{0,0.5,1}\lambda\in\{0,0.5,1\}, and γ=a/du2\gamma=a/d_u^2 with a∈{0.5,0.75,1,1.5,2}a\in\{0.5,0.75,1,1.5,2\}. 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 (a=1a=1), 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 δx\delta_x is the Dirac probability measure at xx. Applying κ\kappa 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.

Thank you for your further feedback. Our primary contribution is establishing a theoretical connection between spectral clustering and kernel kk-means. This connection allows us to develop a unified framework that previous work has been unable to achieve, which also delivers superior clustering performance.

Reviewer_EJWEOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper reformulates the objectives of kernel k-means and spectral clustering using kernel mean embedding (KME) of empirical distributions. It uses cluster self-similarity and the similarity between each cluster distribution and the overall data distribution as common components to explain the relationships among kernel k-means, normalized cut, and ratio cut. It also interprets degree as the similarity between a data point and the overall data distribution.

For D=diag(dx)D={diag}(d_x), the proposed algorithm computes the leading eigenvectors of D−λ/2KD−λ/2D^{-\lambda/2}KD^{-\lambda/2} and then applies row normalization and k-means to obtain a partition. The effect of λ\lambda is evaluated on synthetic datasets and benchmark datasets. The main empirical observation is that, for some datasets and graphs, interior values of λ\lambda yield higher NMI and ARI than both endpoints.

Critical strengths
  1. A consistent distributional representation for comparing existing objectives.

-Describing within-cluster similarity and similarity to the overall distribution using common notation helps clarify how normalization affects clustering.

-Appendix C.2 also clearly distinguishes between applying a power to individual degrees before aggregation and applying a power to the mean degree of a cluster.

-It explains that these two constructions share the same endpoints but define different objectives at interior parameter values. This clarification is useful for understanding design choices in existing methods.

  1. Experiments examining the effect of normalization strength with a fixed affinity.

-Varying λ\lambda while holding the kernel or graph fixed is an appropriate way to isolate the effect of normalization strength. In Table 6, the NMI/ARI improvements over the better endpoint are 0.036/0.029 for Letters--20NN and 0.043/0.068 for Spambase--10NN, respectively, demonstrating the potential practical value of interior parameter values.

-The inclusion of iterative kernel k-means, kNN spectral clustering, and regularized Ncut as additional baselines is also a positive aspect.

Critical weaknesses
  1. The objective function and its spectral relaxation fall within an existing general framework.

-Dhillon et al.(2004) already established the equivalence between the objectives of Ncut and weighted kernel k-means. Their subsequent work also studied the general weighted association objective WAssocA,W(C)=∑C∈C1C⊤A1C1C⊤W1CWAssoc_{A,W}(\mathcal C)= \sum_{C\in\mathcal C} \frac{\mathbf1_C^\top A\mathbf1_C} {\mathbf1_C^\top W\mathbf1_C} and its spectral relaxation based on W−1/2AW−1/2W^{-1/2}AW^{-1/2} (Sections 4.2-3, Dhillon et al. (2007)).

Substituting A=KA=K and W=DλW=D^\lambda directly recovers Eqs.(8)--(9) of this paper.

I acknowledge that the authors do not claim novelty for the matrix operations themselves in Section 2.3. However, the main discrete objective and its relaxation also fall within the existing framework. Therefore, the claim that prior work was limited to methodological connections, whereas this paper newly establishes a fundamental connection between the objectives, does not appear to accurately characterize the relationship to prior work.

  1. The distinct research contribution of the distributional reinterpretation is insufficiently justified.

-Using KME to express existing kernel sums as inner products of cluster distribution embeddings is useful for exposition. However, it remains unclear what additional properties, predictions, or conclusions this reformulation provides beyond those already available from the existing objectives.

-In particular, the distinction in Table 1 between kernel k-means considering only compactness and Ncut considering both compactness and separation is difficult to regard as an exclusive mathematical distinction between the two methods.

-Let the cluster centroid be μC=∣C∣−1∑x∈Cϕ(x)\mu_C=|C|^{-1}\sum_{x\in C}\phi(x) and the overall data centroid be μ=n−1∑xϕ(x)\mu=n^{-1}\sum_x\phi(x), where nn is the total number of data points. For fixed data and a fixed kernel, ∑C∈C∣C∣∥μC∥2=n∥μ∥2+∑C∈C∣C∣∥μC−μ∥2.\sum_{C\in\mathcal C}|C|\|\mu_C\|^2 = n\|\mu\|^2 + \sum_{C\in\mathcal C}|C|\|\mu_C-\mu\|^2.

-Thus, kernel k-means is also equivalent to maximizing the cluster-size-weighted between-cluster variance in the RKHS. This identity concerns an aggregate weighted variance and does not guarantee separation for every individual pair of clusters. Nevertheless, it shows that the characterization of kernel kk-means as not considering separation requires qualification.

[1] Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. (2004). Kernel k-means, Spectral clustering and normalized cuts, KDD2004.

[2] Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. (2007). Weighted graph cuts without Eigenvectors: a Multilevel Approach. TPAMI

Questions for authors
  1. Which results go beyond the existing general weighted association framework?

-Do the authors agree that substituting A=KA=K and W=DλW=D^\lambda into the general formulation of Dhillon et al.\ yields Eqs(8)--(9)?

-If so, the authors should explicitly identify which of the paper's main results do not follow directly from this formulation. If there are cases in which this correspondence does not hold, the authors should specify the relevant conditions and clearly distinguish reformulations of existing results from results claimed to be new.

  1. What new conclusions does the distributional perspective provide?

-Given the identity showing that kernel k-means also maximizes weighted between-cluster variance, how precisely should the distinction between compactness and separation in Table 1 be understood?

-The authors should clearly state what new, testable conclusions follow from the distributional formulation and explain why these conclusions go beyond an interpretation of degree normalization.

3 comments

W1/Q1: The substitution A=K,W=DλA=K,W=\mathbf D^\lambda is valid. It establishes membership in a general spectrally tractable family; it does not by itself explain why this instance is designed this way, which preference it changes, or how it unifies the endpoints' contrasting failure modes. We therefore disagree with treating family membership as sufficient to reduce the contribution to a rewrite. With dx=S(x,D)>0d_x=S(x,D)>0 and D=diag⁡(dx)\mathbf D=\operatorname{diag}(d_x),

=\sum_{C\in\mathcal C}\frac{S(C,C)}{\sum_{x\in C}d_x^\lambda} =Q_\lambda(\mathcal C),$$ and $W^{-1/2}AW^{-1/2}=\mathbf D^{-\lambda/2}K\mathbf D^{-\lambda/2}$. This is compatible with the objective-equivalence theory of [Dhillon et al., 2007](https://www.cs.utexas.edu/~inderjit/public_papers/multilevel_pami.pdf). The precise distinction is between earlier equivalence after transformation and our analysis of normalization differences on the original common kernel. Earlier work should not be described as lacking objective connections, nor should that containment obscure the present contribution. The contribution claimed here is the cluster-to-global distributional decomposition and the consequences of controlling its degree moment on a fixed kernel. Population-level Ncut equivalence and density-bias analyses also have important precedents: [Terada and Yamamoto, 2019](https://proceedings.mlr.press/v97/terada19a.html) and [Marin et al., 2019](https://cs.uwaterloo.ca/~yboykov/Papers/pami19.pdf). Our response therefore identifies the specific finite-data design and predictions below, rather than claiming the first objective-level or distribution-level connection. This positioning preserves the paper's explanatory contribution while crediting the established results. Three distinctions are important. First, the main objective and relaxation are within that family. The algebra requires positive degrees, not constant degrees; the KME interpretation additionally requires $K\succeq0$. For a PSD kernel, set $w_x=d_x^\lambda$ and $\widetilde\phi(x)=\phi(x)/w_x$. Expanding weighted KKM gives $$\mathcal L_{\mathrm{WKKM}}(\mathcal C) =\sum_{x\in D}\frac{K_{xx}}{w_x} -\sum_{C\in\mathcal C}\frac{S(C,C)}{\sum_{x\in C}w_x}.$$ The first term is partition independent. Thus implementation through weighted KKM involves both feature remapping and weighting, not merely changing point weights in the original feature space. Second, the order of distributional aggregation matters. Appendix C.2 considers $$\overline Q_\lambda(\mathcal C) =\sum_{C\in\mathcal C}\frac{S(C,C)}{|C|^{1-\lambda}S(C,D)^\lambda}.$$ The endpoints agree. For $0<\lambda<1$ and heterogeneous within-cluster degrees, strict concavity gives $$\frac{1}{|C|}\sum_{x\in C}d_x^\lambda <\left(\frac{S(C,D)}{|C|}\right)^\lambda.$$ Its denominator cannot be a sum of fixed partition-independent diagonal weights: singleton clusters force $w_x=d_x^\lambda$, whereas a pair with degrees $a\ne b$ would require $$a^\lambda+b^\lambda=2^{1-\lambda}(a+b)^\lambda,$$ contradicting strict concavity. This excludes a fixed additive diagonal denominator with the original numerator $S(C,C)$, not every conceivable transformed representation. It explains why the main objective admits Algorithm 1's relaxation while the alternative needs different optimization; we do not attribute the latter's properties to the main algorithm. Third, the decomposition yields testable distinctions. W2/Q2 below gives a PSD construction in which every KKM distance and loss remains unchanged but Ncut preference changes, together with an exact response law for heterogeneous degrees. These provide mechanism and prediction beyond the implementation correspondence. A precise formulation of the paper's positioning is: “Classical work established equivalence through kernel transformations and weighting. We compare the objectives on a common kernel through cluster self-similarity and cluster-to-global normalization, and analyze the controllable degree-moment continuum that results.” The supplementary propositions are now included, with proofs, in Appendix G of the revised paper. They substantiate this contribution and are explicitly identified as additions to the original submission.

W2/Q2: The between-cluster variance identity is valid, but it does not identify that variance with the relative cluster-to-global normalization analyzed in the paper. Let n=∣D∣n=|D| and μ=μD\mu=\mu_D. Since ∑C∣C∣μC=nμ\sum_C|C|\mu_C=n\mu, expansion gives

=\sum_C|C|\|\mu_C\|^2-n\|\mu\|^2.$$ The exact distinction for Table 1 is: KKM maximizes $\sum_C|C|\|\mu_C\|^2$, equivalently aggregate size-weighted between-cluster variance up to a constant; Ncut maximizes $\sum_C |C|\|\mu_C\|^2/(|D|\langle\mu_C,\mu_D\rangle)$, adding a cluster-specific normalization relative to the global distribution. Thus the appropriate labels are “unnormalized self-similarity” and “globally normalized self-similarity,” not an exclusive presence or absence of separation. The normalization distinction remains exact after the variance identity is acknowledged. Take $x=(1,2,4,8)$ and features $\phi_t(x)=(x,\sqrt t)$, $t>0$. The entrywise nonnegative kernel $K_t=xx^\top+t\mathbf1\mathbf1^\top$ is PSD. Every squared RKHS distance equals $(x_i-x_j)^2$, independently of $t$, so KKM loss and between-cluster variance are unchanged for every partition. For $P=\{1,2\}/\{4,8\}$ and $R=\{1,2,4\}/\{8\}$, direct evaluation gives: Table 12 (Appendix G.4). Among these two partitions, KKM always prefers $R$, whereas Ncut prefers $P$ at $t=1$ and $R$ at $t=100$. This pairwise comparison isolates normalization while preserving all RKHS distances and both KKM variance quantities. Shift invariance of size-normalized objectives and the contrasting behavior of Ncut are established observations; see [Chehreghani, 2023, §6]. Here the explicit PSD construction allows a quantitative prediction for our full continuum, as derived next. Consider any fixed entrywise nonnegative PSD kernel $K$, $n=|D|$, and $K_t=K+t\mathbf1\mathbf1^\top$. Adding the shared feature $\sqrt t$ changes neither RKHS distances nor KKM loss. For every fixed $\lambda\in[0,1]$, $$(nt)^\lambda Q_\lambda^{(t)}(\mathcal C) =nt+Q_0^{(0)}(\mathcal C)-\frac{\lambda S(D,D)}{n}+O(t^{-1}).$$ To see this directly in distributional sums, $S_t(C,C)=S(C,C)+t|C|^2$ and $d_x^{(t)}=d_x+nt$. Taylor expansion gives $$\sum_{x\in C}(d_x+nt)^\lambda =(nt)^\lambda\left[|C|+\frac{\lambda S(C,D)}{nt}+O(t^{-2})\right].$$ Dividing the numerator by this expression yields $$(nt)^\lambda q_\lambda^{(t)}(C) =t|C|+\frac{S(C,C)}{|C|}-\frac{\lambda S(C,D)}{n}+O(t^{-1}).$$ Summing over clusters proves the claim. Hence, for any two partitions, the rescaled objective difference converges to their original KKM association difference. For fixed $k$, there are finitely many partitions; a unique KKM optimum is therefore also optimal for all sufficiently large $t$ at each fixed $\lambda$. This predicts convergence of preferences without changing the KKM geometry. The four-point construction gives an exact, non-asymptotic crossing: $$Q_1^{(t)}(P)-Q_1^{(t)}(R) =-\frac{t(16t+225)(46t-1935)}{12(t+30)(2t+45)(4t+35)(8t+45)}.$$ Thus Ncut changes its preference between these two partitions at $t=1935/46\approx42.065$, while KKM's preference remains unchanged. Direct enumeration verifies the objective values. This is a controlled mechanism result for the kernel family, not a modification of Algorithm 1 or the RBF benchmark experiments. For general heterogeneous degrees, define $$m_\lambda(C)=\sum_{x\in C}d_x^\lambda,\quad q_\lambda(C)=\frac{S(C,C)}{m_\lambda(C)},\quad p_{\lambda,C}(x)=\frac{d_x^\lambda}{m_\lambda(C)},\quad \ell_C=\sum_{x\in C}p_{\lambda,C}(x)\log d_x.$$ For a fixed nonempty cluster with $d_x>0$ and $S(C,C)>0$, $$\frac{\partial\log q_\lambda(C)}{\partial\lambda}=-\ell_C, \qquad \frac{\partial^2\log q_\lambda(C)}{\partial\lambda^2} =-\sum_{x\in C}p_{\lambda,C}(x)(\log d_x-\ell_C)^2\leq0.$$ Proof: $m_\lambda'(C)=\sum_xd_x^\lambda\log d_x$ and $\partial_\lambda p_{\lambda,C}(x)=p_{\lambda,C}(x)(\log d_x-\ell_C)$. Differentiating $\log S(C,C)-\log m_\lambda(C)$ once and twice gives the identities. These yield testable consequences: (i) globally constant degrees give $Q_\lambda=d_0^{-\lambda}Q_0$, hence no change in partition ranking; (ii) within-cluster weighted dispersion of log-degrees exactly determines log-curvature; and (iii) two candidate clusters satisfy $$\frac{\partial}{\partial\lambda}\log\frac{q_\lambda(C)}{q_\lambda(B)} =\ell_B-\ell_C.$$ Increasing $\lambda$ therefore raises the relative contribution of the cluster with lower weighted log-degree. This explains why normalization can help low-density clusters yet also favor low-degree outliers; neither effect guarantees improved label accuracy. The distributional decomposition therefore leads to explicit, falsifiable statements: invariance of KKM under a shared feature, a quantitative preference crossing for Ncut, convergence of the continuum toward the KKM preference as that feature grows, and an exact degree-response law. These analyses substantiate the interpretation with predicted objective behavior.

I thank the authors for the clarifications and additional analyses and experiments. These additions strengthen the paper and partially address my concerns, and I am therefore raising my rating. However, the main objective and its spectral relaxation remain within the existing weighted-association framework, and I remain unconvinced that the additional results sufficiently establish the distinctiveness and significance of the contribution.

Reviewer_aiHPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper looks at kernel k-means and spectral clustering through the lens of distribution similarity, and proposes a unified spectral clustering method with a parameter λ. They test it on two synthetic datasets and six real ones.

Critical strengths
  1. Explaining the two classic clustering methods from a distribution angle is a nice theoretical touch.
  2. The unified framework is pretty simple, and the experiments show how different normalization choices affect clustering results.
Critical weaknesses

The distribution-similarity rewrite mostly builds on existing kernel mean embeddings, and the final algorithm is still just spectral normalization with a parameter so it's unclear what substantive conclusion this adds beyond existing theory. The gains on most datasets are pretty small, and there's no way to pick λ without true labels, so it's unclear whether the framework can reliably improve real clustering performance.

Questions for authors
  1. Compared with existing equivalence results for kernel k-means and spectral clustering, what new conclusion does this paper actually prove that you couldn't get before?
  2. The final algorithm is basically just applying λ-th power normalization to the kernel matrix so how is it fundamentally different from existing spectral normalization methods?
  3. Does λ=0 correspond to the spectral relaxation of kernel k-means, or to the original discrete optimization? Are the two being mixed up?
  4. The performance changes on most datasets are tiny so why does that show the unified framework has any real advantage?
  5. Without true labels, how do you pick a suitable λ? And if you can't, what's the practical value?
  6. The appendix shows that changing the adjacency graph structure gives bigger gains. So why should anyone prefer this paper's λ tuning over existing graph construction or normalization methods? I'm willing to raise my score if the authors can address the concerns above.
3 comments

Thanks for your review and suggestions.

Concern: What substantive conclusions does the distributional view add beyond existing equivalence results?

The contribution is a distributional account of how objectives on the same kernel express different clustering preferences, together with a controllable family and testable consequences. The numerator measures cluster self-similarity; the denominator measures normalization against the global distribution. The analysis below characterizes both changes in preference and stability of the resulting optimum. This directly addresses what the formulation contributes beyond an implementation correspondence.

Write S(C,B)=∑x∈C,y∈Bκ(x,y)S(C,B)=\sum_{x\in C,y\in B}\kappa(x,y) and dx=S(x,D)d_x=S(x,D). The endpoint contributions are

q_1(C)=\frac{S(C,C)}{S(C,D)} =\frac{|C|\kappa(\mathcal P_C,\mathcal P_C)}{|D|\kappa(\mathcal P_C,\mathcal P_D)}.$$ Thus cluster self-similarity is distinguished from normalization relative to the global distribution. Section 5 controls this normalization through $q_\lambda(C)=S(C,C)/\sum_{x\in C}d_x^\lambda$. Two consequences make the interpretation testable. First, if every degree equals $d_0$, then $Q_\lambda=d_0^{-\lambda}Q_0$: all discrete partition rankings are unchanged. If clusters $C,B$ have internally constant degrees $d_C,d_B$, then $$\frac{q_\lambda(C)}{q_\lambda(B)} =\frac{S(C,C)/|C|}{S(B,B)/|B|} \left(\frac{d_B}{d_C}\right)^\lambda.$$ Increasing $\lambda$ therefore raises the relative contribution of a lower-degree cluster. This can recover a low-density cluster or favor low-degree outliers, explaining both the benefit and the risk of normalization through the same mechanism. Second, the interior is not redundant with the endpoints. Consider $x=(0.3,0.7,2.0,2.5,2.6,4.0,5.6,8.1)$ and the fixed PSD RBF kernel $K_{ij}=\exp[-(70/213)^2(x_i-x_j)^2]$. Exhaustive evaluation of all 127 nonempty unordered bipartitions gives three different unique maximizers: Full results are reported in Table 10 of the revised paper (Appendix G.2). The best-to-runner-up gaps are 0.053, 0.040, and 0.027. Scores are compared within columns only. This constructed illustration, not a performance benchmark, isolates the objective from graph changes, relaxation, and randomized rounding. The formulation gives explicit conditions for unchanged rankings, degree-dependent changes in cluster preference, and an interior optimum absent at both endpoints. These answer the request for substantive conclusions. The next result strengthens the example from an isolated parameter value to a guaranteed interval. 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. The stability bound and its proof are now Proposition G.2 in the revised paper; the coordinate-perturbation results are in Table 11 (Appendix G.2).

Q2: Concern: Is the algorithm fundamentally different from existing spectral normalization?

The distinction lies in objective design and behavior, rather than renaming a familiar matrix operation. Equation (6) specifies how cluster self-similarity and global normalization are combined, leading to the discrete objective in Eq. (8) and its spectral implementation in Eq. (9). Substitution A=K,W=DλA=K,W=\mathbf D^\lambda embeds this instance in weighted association; that compatibility explains its spectral implementation but does not replace its distributional analysis. Dhillon et al., 2007, §§4.2–4.3

The distributional choice in Eq. (6) is explicit:

g_\lambda(\mathcal P_C,\mathcal P_D) =\frac{1}{|C|}\sum_{x\in C}\bigl(|D|\kappa(\delta_x,\mathcal P_D)\bigr)^\lambda.$$ This gives $g_0=1$, $g_1=|D|\kappa(\mathcal P_C,\mathcal P_D)$, and the discrete objective whose relaxation uses $\mathbf D^{-\lambda/2}K\mathbf D^{-\lambda/2}$. Reversing aggregation and exponentiation produces the different objective in Appendix C.2, not the same spectral derivation. The matrix also matches the first Coifman–Lafon kernel reweighting at $\alpha=\lambda/2$, but their subsequent degree recomputation and Markov normalization generally produce a different final diffusion operator. [Coifman–Lafon, 2006](https://www.math.ucdavis.edu/~strohmer/courses/270/diffusion_maps.pdf). Regularized spectral clustering instead uses $\mathbf D+\tau I$. [Qin–Rohe, 2013](https://proceedings.neurips.cc/paper_files/paper/2013/file/0ed9422357395a0d4879191c66f4faa2-Paper.pdf) The distributional choices determine the optimization problem and its implementation; a similar matrix expression does not identify the objective interpretation, aggregation order, or final operator. Section 2.3 already disclaims novelty for the matrix operations themselves. The contribution to assess is the unified explanation and verifiable consequences of those design choices. Q3: Concern: Does $\lambda=0$ recover discrete kernel $k$-means or its spectral relaxation? The endpoint is exact at the discrete-objective level; Algorithm 1 implements it through spectral relaxation and rounding. These are compatible statements, corresponding to Eqs. (8) and (9). In particular, $$\mathcal L_{\mathrm{KKM}}(\mathcal C) =\operatorname{Tr}K-\sum_{C\in\mathcal C}\frac{S(C,C)}{|C|} =\operatorname{Tr}K-Q_0(\mathcal C).$$ Thus maximizing $Q_0$ exactly minimizes the original KKM loss. For $h_C=\mathbf1_C/\sqrt{\sum_{x\in C}d_x^\lambda}$, the discrete objective is $\operatorname{Tr}(H^\top KH)$ with $H^\top\mathbf D^\lambda H=I$. Dropping the discrete indicator structure while retaining this constraint and setting $U=\mathbf D^{\lambda/2}H$ gives $$\max_{U^\top U=I}\operatorname{Tr}\bigl(U^\top\mathbf D^{-\lambda/2}K\mathbf D^{-\lambda/2}U\bigr).$$ Algorithm 1 at $\lambda=0$ therefore uses the spectral relaxation of the KKM association objective. Row normalization and $k$-means are rounding steps, not an exact discrete solver; their partition need not equal that of iterative KKM. Likewise, $\lambda=1$ exactly recovers the NAssoc objective, while the algorithm uses its spectral relaxation and rounding. All parameter values use the same spectral solver and rounding procedure, isolating the change in objective normalization. This is distinct from asserting identical partitions from different solvers. The endpoint identities, spectral derivation, and experimental pipeline remain valid; Algorithm 1 needs no modification. W2/Q4: Concern: Are the improvements too small to demonstrate practical value? The gains should be assessed against the mechanism being tested: changing normalization preference on a fixed kernel. The framework does not predict an improvement on every dataset; constant degrees even imply invariant objective rankings. On affected data, the manuscript and the new fixed-parameter experiments show gains of practical magnitude. For example, revised-paper Table 7 holds each graph fixed: Full results are reported in Table 7 of the revised paper (Appendix F). Entries are NMI / ARI; gains use unrounded values. These interior values come from a parameter sweep, showing attainable benefit, not guaranteed label-free selection. The sparse-graph results concern graph objectives, not an RKHS interpretation of potentially non-PSD affinities. More importantly, with a PSD RBF kernel and fixed $\lambda=0.5$, Breast Cancer improves from the zero endpoint's 0.494/0.605 to 0.565/0.664 NMI/ARI, exceeding Ncut on both metrics as well. The joint gain persists after standardization, with bandwidth and resampling confirmation in Appendix H.3 of the revised paper. This is real-data evidence without label-based tuning of $\lambda$; small changes on other data do not invalidate it.

W3/Q5: Concern: Without labels, how is λ\lambda chosen, and what practical value remains?

For the reported use case, a concrete label-untuned setting is λ=0.5\lambda=0.5, fixed before evaluation. We distinguish this baseline from an adaptive rule for choosing the best value on new data. The completed comparisons in revised-paper Appendix H test whether an interior choice has practical value without label-based parameter search. Its demonstrated benefit is relevant to the unified framework even though adaptive selection remains a further practical problem.

The new study covers 22 problems: 13 real and nine synthetic datasets. All settings use raw numerical features, the same dense PSD RBF kernel with γ=1/du2\gamma=1/d_u^2 (mean pairwise distance dud_u), and Algorithm 1. Datasets above 5,000 points are uniformly subsampled to 5,000, shared across settings. Scores average five rounding runs and then weight datasets equally. Labels do not select λ\lambda, bandwidth, or samples; the class count supplies the same known kk to all settings.

Full results are reported in Table 13 of the revised paper (Appendix H.1).

Entries are NMI/ARI. Across all 22 datasets, the fixed midpoint exceeds Ncut on both averages while remaining close to the zero endpoint. Standardizing all 13 real datasets gives macro-scores 0.487/0.424, 0.460/0.387, and 0.318/0.256 for 0,0.5,10,0.5,1: a single fixed value is not best across every representation. Nevertheless, Breast Cancer improves over both endpoints under both scale protocols, establishing directly usable interior benefit.

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 λ∈{0,0.5,1}\lambda\in\{0,0.5,1\}, and γ=a/du2\gamma=a/d_u^2 with a∈{0.5,0.75,1,1.5,2}a\in\{0.5,0.75,1,1.5,2\}. 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 16 ) Scores average the five prespecified bandwidths equally. Joint wins count bandwidths where the midpoint exceeds both endpoints on both mean metrics; std denotes 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. 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: Full results are reported in Table 17 of the revised paper (Appendix H.3). At the original bandwidth (a=1a=1), 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 show a different pattern, supporting data-dependent objective choice rather than a claim that one fixed value always dominates.

The key results are now in Section 6.3 and Table 3 of the main paper; Appendix H retains the full comparisons.

Q6: Concern: Why is λ\lambda needed when graph construction can produce larger gains?

Graph construction and objective choice can be used together; a larger gain from the former does not make the latter redundant. Letters–20NN already uses sparse graph construction, yet the interior reaches 0.496/0.200 NMI/ARI on that same graph, exceeding both endpoints. A precise operator-level result also establishes that bandwidth and λ\lambda are distinct degrees of freedom. Let Kγ,ij=exp⁡(−γ∥xi−xj∥2)K_{\gamma,ij}=\exp(-\gamma\|x_i-x_j\|^2), γ>0\gamma>0, and Mλ,γ=Dγ−λ/2KγDγ−λ/2.M_{\lambda,\gamma}=\mathbf D_\gamma^{-\lambda/2}K_\gamma\mathbf D_\gamma^{-\lambda/2}. If at least two points differ and the degrees in Dγ\mathbf D_\gamma are not all equal, then, for c>0c>0,

\quad\Longrightarrow\quad\gamma'=\gamma,\ \mu=\lambda,\ c=1.$$ Proof. Because $K_{\gamma,ii}=1$, $$\frac{M_{\lambda,\gamma,ij}}{\sqrt{M_{\lambda,\gamma,ii}M_{\lambda,\gamma,jj}}} =\exp(-\gamma\|x_i-x_j\|^2).$$ Both the global scale and degree factors cancel. Proportional operators therefore force $\gamma'=\gamma$ on any pair at nonzero distance. Their diagonals then imply $d_i^{\mu-\lambda}=c$ for every point. Two distinct positive degrees force $\mu=\lambda$, hence $c=1$.Thus bandwidth alone cannot reproduce the operator for a different $\lambda$, even up to eigenvector-preserving global scaling. This is operator non-redundancy, not a claim that different operators can never happen to yield the same partition. Together with the fixed-graph gains and robustness experiments, it establishes an objective choice that remains after graph construction. (Appendix G.3)

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.