Pith. sign in

REVIEW 3 major objections 6 minor 33 references

Deep Kernel Learning for Clustering

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A neural embedding trained jointly with a spectral target learns clustering kernels that beat spectral clustering and deep-clustering baselines on most tested datasets.

desk verdict KNet is a genuine step forward in deep clustering—jointly learning a kernel and spectral embedding via HSIC works well on non-convex data—but the λ=0 choice is the soft spot that needs a serious fix before publication. read the letter →

arxiv 1908.03515 v3 pith:HB6JU3BL submitted 2019-08-09 cs.LG stat.ML

Chieh Wu , Zulqarnain Khan , Yale Chang , Stratis Ioannidis , Jennifer Dy This is my paper · ORCID
classification cs.LGstat.ML MSC 68T1068T0762H30
keywords deepkernellearningclusteringHilbert-SchmidtIndependenceCriterionspectralneuralnetworkembeddingStiefelmanifoldout-of-samplegeneralizationnon-convexclusters
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to show that a clustering kernel can be learned from data instead of being chosen by hand. KNet trains a neural-network embedding so that a Gaussian kernel evaluated on the embedded points maximizes the Hilbert-Schmidt Independence Criterion (HSIC) against a coupled spectral embedding, initialized at the spectral embedding of the raw data. The joint training makes the learned embedding at least as expressive as spectral clustering while adding out-of-sample generalization and faster updates. Across three synthetic and four real datasets, the paper reports higher normalized mutual information than several deep clustering baselines and spectral clustering on all but one dataset, with the largest gains on non-convex clusters.

What carries the argument

The engine is the HSIC objective $H(\Psi_\theta(X), U) = \frac{1}{(N-1)^2}\operatorname{tr}(\tilde K_{\Psi} H U U^T H)$, where $\tilde K_{\Psi}$ is the degree-normalized Gaussian kernel on the embedded points and $H$ is the centering matrix. Holding the embedding fixed, maximizing over orthonormal $U$ recovers the top eigenvectors of the normalized Laplacian $L = H D^{-1/2} K_{\Psi} D^{-1/2} H$, which is exactly the spectral clustering step; learning $\Psi$ and $U$ together generalizes that step. Rewriting the objective as $\sum_{i,j} \Gamma_{i,j} e^{-\|\psi_\theta(x_i)-\psi_\theta(x_j)\|^2/2\sigma^2}$ shows that positive entries of $\Gamma$ attract embedded points and negative entries repel them, producing convex cluster images. Updates for $U$ are done either by eigendecomposition or by a Cayley-transform ascent on the Stiefel manifold that maintains orthonormality without a full matrix inversion.

What would settle it

Train KNet with $\lambda = 0$ on a dataset where spectral clustering is known to succeed, then check whether distinct inputs from different clusters map to nearly the same point while the initial spectral embedding separates them; a collapse of that kind would violate the claim that the trained embedding is at least as expressive as spectral clustering.

Watch

Extended reading notes

Core claim

The central claim is that jointly maximizing HSIC between a neural-network embedding $\Psi_\theta(X)$ and an orthonormal target $U$, with $U$ initialized to the spectral embedding, discovers a deep kernel that is at least as expressive as spectral clustering and clusters better in practice. The embedding and the spectral target are learned together, so each improves the other: the kernel becomes more informative, producing nearly block-diagonal similarity matrices, and the images of non-convex clusters become convex and linearly separable. Because the embedding is a neural network, it can be applied to new samples directly, and training on a small subset of the data clusters the full dataset with little loss of quality.

Load-bearing premise

The method assumes that setting the reconstruction penalty to zero ($\lambda = 0$) does not let the learned embedding collapse onto a non-injective map, even though the paper says that penalty is theoretically necessary for injectivity; if a $\lambda = 0$ embedding stops being faithful to the input on some dataset, the learned kernel could lose cluster structure.

Editorial extensions

If this is right

  • The learned kernel can be applied to out-of-sample data directly, so clustering a new point does not require rerunning spectral clustering on the combined dataset.
  • Training the embedding on as little as 1 to 35 percent of the data clusters the full dataset with only 0 to 3 percent degradation in normalized mutual information on the tested datasets.
  • The Stiefel-manifold update avoids repeated eigendecompositions, with complexity $O(N^2 c + c^3)$ per iteration when the number of clusters $c$ is much smaller than the sample count $N$.
  • On non-convex clusters such as spirals and moons, the embedding turns the clusters into convex, linearly separable shapes, so simple $k$-means on the embedding succeeds where $k$-means on the raw data fails.
  • Because the identity-map embedding reduces the joint problem to standard spectral clustering, the framework is at least as expressive as spectral clustering by construction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One implication the paper leaves implicit is that the coupled $U$ update could be made streaming or mini-batch based, since the Stiefel ascent updates orthogonality without eigendecomposition, suggesting an online clustering variant.
  • A testable extension is to replace the spectral initialization with a more robust affinity embedding on datasets where spectral clustering itself struggles; KNet may inherit spectral clustering's failure modes, such as highly imbalanced cluster sizes.
  • The same HSIC-plus-coupled-target objective could apply beyond clustering, for example to learn embeddings that preserve graph or manifold structure in semi-supervised settings, though the paper does not claim this.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes KernelNet (KNet), a deep kernel learning method for clustering. KNet parameterizes a Gaussian kernel over a neural-network embedding, and trains the network by maximizing the Hilbert-Schmidt Independence Criterion (HSIC) between the embedding matrix and a coupled spectral embedding U, while optionally including an autoencoder reconstruction penalty. The optimization alternates between stochastic gradient ascent on the network parameters and an update of U, either by eigendecomposition of the current normalized kernel Laplacian or by Cayley-based Stiefel manifold ascent. The authors initialize the encoder to approximate the identity and U to the spectral embedding of the original data. After training, k-means is run on the learned embedding, and the embedding can be applied to out-of-sample points without recomputing a spectral decomposition. The paper reports improved NMI over several deep clustering baselines, spectral clustering, and k-means on five of six evaluated datasets, and demonstrates out-of-sample performance after training on subsampled data.

Significance. If the central claims hold, the paper makes a useful contribution: it connects HSIC-based dependence maximization to spectral clustering, provides a deep kernel tailored to clustering, and offers a practical out-of-sample extension. The derivation in Appendix A relating HSIC maximization to the spectral embedding is correct and clearly presented. The paper also ships source code, reports mean and standard deviation over multiple runs, and includes comparisons with several recent deep clustering methods. The main weaknesses are that two load-bearing assertions are not fully supported: the claim that the method is at least as expressive as spectral clustering, and the decision to drop the reconstruction penalty despite its stated theoretical necessity for injectivity. Both issues are addressable, and the empirical evidence is otherwise reasonably strong.

major comments (3)
  1. [Sec. 4 (after Eq. 4.9) and Sec. 6.1 (Table 6)] The paper states that the autoencoder penalty is "theoretically necessary to ensure that the embedding Ψ is injective" (Sec. 4, after Eq. 4.9), yet all reported experiments set λ=0 (Sec. 6.1). The offered justification, that gradient descent from the identity initialization makes the final embedding "representative of the input X," does not imply injectivity or preservation of local structure; an initialization-dependent map can still be non-injective or can distort distances in ways that break out-of-sample transfer. The empirical grounding in Table 6 uses ground-truth label agreement (NMI) on the Wine dataset and is therefore not an unsupervised selection rule. Because injectivity of the embedding is what connects the learned kernel to the cluster structure of X, the current evidence does not rule out collapse or distance distortion on other datasets, and the out-of-sample generalization claim in Sec. 4 is not secured. Please either retain the reconstruction term, provide a label-free selection rule for λ, or prove or quantify the injectivity of the final embedding.
  2. [Sec. 4, Eqs. (4.7)-(4.8); Abstract] The claim that KNet is "at least as expressive as spectral clustering" is asserted but not proved. The initialization argument (Ψ as identity, U=U0) shows only that the initial feasible point of (4.8) attains the spectral-clustering objective value for the original kernel. Since the optimization then changes both Ψ and U and converges to a local maximum of the HSIC objective, it does not follow that the final embedding separates every pair of clusters that spectral clustering separates, nor that its NMI dominates spectral clustering. A formal statement and proof, or a precise definition of the claimed expressiveness, is needed; otherwise the abstract's headline claim should be weakened.
  3. [Table 1 and Tables 2-4] Spiral2 (N=30,000) is listed in Table 1 and used for the illustration in Fig. 1, but no quantitative clustering result or runtime for Spiral2 appears in Tables 2, 3, 4, or 5. The text's claim of results on "a broad array" of datasets and the "5 out of 6 datasets" statement refer to Table 2, which contains only six of the seven listed datasets. Either report Spiral2 results in the main tables or clarify its role in the evaluation; as written, the experimental record is incomplete.
minor comments (6)
  1. [Sec. 5 and Algorithm 1] The term "Stiefler Manifold Ascent" is a typo for "Stiefel Manifold Ascent."
  2. [Appendix C, Eq. (3.22)] The notation in Eq. (3.22) is inconsistent with the main text: the kernel matrix is denoted KΨθ(X) in one place and KU in another, and the relationship to the normalized kernel D^{-1/2}KD^{-1/2} from Eq. (3.2) should be made explicit.
  3. [Sec. 4 and Sec. 6.1] There are typos in the text, including "absense" (Sec. 4) and "Our choie of λ = 0" (Sec. 6.1).
  4. [Algorithm 1, line 8] The stopping criterion "until KU has converged" is not defined; please specify a concrete convergence condition for the outer loop.
  5. [Table 4] The training subset sizes vary by dataset and include 75% for Wine, which is not a "small subset"; the text's claim of using "as little as 6%" should be qualified by noting the dataset-dependent percentages.
  6. [Sec. 4, reference [30]] The sentence "as observed in [30]" appears to attribute an empirical observation about clustering autoencoders to a paper on MMD GANs; please either cite a directly relevant source or rephrase to avoid misattribution.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central HSIC-to-spectral-clustering equivalence is re-derived in Appendix A, and the empirical claims are tested against external benchmarks.

full rationale

KNet's training objective (4.8) maximizes HSIC between the neural embedding Ψθ(X) and a coupled orthonormal matrix U, after which U is updated to the top eigenvectors of the normalized kernel matrix induced by Ψθ (Eq. 5.14). This is a self-referential optimization, but it is not a circular derivation: the paper does not define the embedding's quality in terms of U and then claim the resulting U as an independent prediction; rather, improving the spectral clustering objective of the learned kernel is the intended method. The key equivalence between HSIC maximization and spectral embedding (Eqs. 3.5–3.6) is attributed to Niu et al. [13], a self-citation for co-author Dy, but the paper re-proves it in Appendix A, so the load-bearing step does not reduce to an unverified self-citation. The 'at least as expressive as spectral clustering' claim is supported by initializing Ψ as the identity and U as the spectral embedding U0, then optimizing a spectral objective, rather than by fitting a parameter to the reported NMI. The only notable weakness is the choice λ=0: Section 6.1 grounds it partly on label-based NMI in Table 6 on Wine and on an initialization-dependence argument from [30]; this is a generalization and evaluation risk, not a case of the derivation reducing to its own inputs. All benchmark comparisons and out-of-sample evaluations are measured against external implementations and reported outcomes, so no fitted quantity is renamed as a prediction.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The method rests on a few standard results (HSIC-spectral equivalence) plus several data-dependent choices (sigma, lambda, architecture width) and two unproven practical assumptions: that dropping the reconstruction term is harmless and that spectral initialization guarantees at least spectral-clustering expressiveness.

free parameters (5)
  • Gaussian kernel width sigma = median pairwise Euclidean distance per dataset (Table 1)
    Used to define the kernel in Eq. 1.1 and 4.10; chosen by a data-dependent heuristic rather than learned or derived.
  • reconstruction weight lambda = 0
    Set to 0 in all reported results; selection is informed by HSIC and label-based NMI on Wine and Spiral1 (Table 6, App. B), despite reconstruction being described as theoretically necessary for injectivity.
  • network hidden layer width = d or 20 depending on dataset
    Architecture hyperparameter chosen per dataset in Sec. 6; not justified by theory.
  • Cayley step length tau = not reported
    Stiefel manifold ascent in Eq. 5.16 depends on a pre-defined step length tau; no value or line-search schedule is given.
  • training subset fraction = 1% to 75% per dataset (Table 4)
    Out-of-sample experiments choose subset sizes so the spectrum of the subset is close to the full spectrum, a data-dependent selection.
assumptions (4)
  • standard math Maximizing HSIC with a linear kernel K_U = UU^T under U^T U = I recovers the spectral embedding of X
    Proved in Appendix A using the result of Niu et al. [13]; this is the theoretical bridge from HSIC to spectral clustering.
  • ad hoc to paper Initializing psi as identity and U as the spectral embedding U0 makes the joint optimization at least as expressive as spectral clustering
    Stated in Secs. 4 and 5 as intuition; no formal guarantee is provided that the alternating optimization cannot leave the spectral optimum or collapse.
  • ad hoc to paper The embedding psi remains sufficiently injective without the reconstruction penalty
    The paper states the reconstruction term is theoretically necessary for injectivity (Sec. 4) but sets it to zero, relying on local-minima behavior and empirical results.
  • domain assumption A Gaussian kernel in the embedded space with median-width sigma is a suitable similarity for clustering
    Standard kernel choice used throughout experiments; no analysis of sensitivity to sigma is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Deep Kernel Learning for Clustering." pith.science (2026). https://pith.science/paper/HB6JU3BL

@misc{pith2026190803515,
  author       = {Pith},
  title        = {Pith review of: Deep Kernel Learning for Clustering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HB6JU3BL}},
  note         = {Machine review of arXiv:1908.03515}
}
abstract

We propose a deep learning approach for discovering kernels tailored to identifying clusters over sample data. Our neural network produces sample embeddings that are motivated by--and are at least as expressive as--spectral clustering. Our training objective, based on the Hilbert Schmidt Information Criterion, can be optimized via gradient adaptations on the Stiefel manifold, leading to significant acceleration over spectral methods relying on eigendecompositions. Finally, our trained embedding can be directly applied to out-of-sample data. We show experimentally that our approach outperforms several state-of-the-art deep clustering methods, as well as traditional approaches such as $k$-means and spectral clustering over a broad array of real-life and synthetic datasets.

Figures

Figures reproduced from arXiv: 1908.03515 by the authors.

Figure 1
Figure 1. Illustration of our learned embedding on the [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Cluster images after several epochs of stochas [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Synthetic Datasets. Both dataset contain non [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (4 more)
Figure 5
Figure 5. Figure 5: This figure plots out the effect of applying a [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 4
Figure 4. Figure 4: This figure plots out the effect of training [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 6
Figure 6. Figure 6: This figure plots out the effect of training [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: This figure plots out the effect of applying Ψ [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 31 canonical work pages

  1. [1]

    Gretton, O

    A. Gretton, O. Bousquet, A. Smola, and B. Sch¨ olkopf, Measuring statistical dependence with Hilbert-Schmidt norms, International Conference on Algorithmic Learn- ing Theory (2005), pp. 63–77

    work page 2005

  2. [2]

    C. Song, F. Liu, Y. Huang, L. Wang, and T. Tan, Auto- encoder based data clustering , Iberoamerican Congress on Pattern Recognition (2013), pp. 117–124

    work page 2013

  3. [3]

    P. Ji, T. Zhang, H. Li, M. Salzmann and I. Reid, Deep Subspace clustering Network , Advances in Neural Information Processing Systems (2017)

    work page 2017

  4. [4]

    F. Tian, B. Gao, Q. Cui, E. Chen, and T. Liu, Learning deep representations for graph clustering. , AAAI (2014), pp. 1293–1299

    work page 2014

  5. [5]

    J. Xie, R. Girshick, and A. Farhadi, Unsupervised deep embedding for clustering analysis , International Conference on Machine Learning (2016), pp. 478–487

    work page 2016

  6. [6]

    X. Guo, X. Liu, E. Zhu, and J. Yin,Deep Clustering with Convolutional Autoencoders, International Conference on Neural Information Processing (2017), pp. 373–382

    work page 2017

  7. [7]

    W. Hu, T. Miyato, S. Tokui, E. Matsumoto, and M. Sugiyama, Learning Discrete Representations via In- formation Maximizing Self Augmented Training , arXiv preprint arXiv:1702.08720 (2017)

    arXiv 2017

  8. [8]

    Shaham, K

    U. Shaham, K. Stanton, H. Li, R. Basri, B. Nadler and Y. Kluger, SpectralNet: Spectral Clustering using Deep Neural Networks, International Conference on Learning Representations (2018)

    work page 2018

Show all 33 references
  1. [9]

    A. G. Wilson, Z. Hu, R. Salakhutdinov and E. P. Xing, Deep kernel learning , Artificial Intelligence and Statistics (2016), pp. 370–378

    2016

  2. [10]

    A. G. Wilson, Z. Hu, R. Salakhutdinov and E. P. Xing, Stochastic variational deep kernel learning , Advances in Neural Information Processing Systems (2016), pp. 2586–2594

    2016

  3. [11]

    A. G. Wilson, D. A. Knowles, and Z. Ghahramani Gaussian process regression networks , arXiv preprint arXiv:1110.4411 (2011)

    2011 arXiv

  4. [12]

    D. Zhou, O. Bousquet, T. N. Lal, J. Weston, B. and Sch¨ olkopf,Learning with local and global consistency , Advances in neural information processing systems (2004), pp. 321–328

    2004

  5. [13]

    D. Niu, J. Dy, and M. Jordan, Dimensionality reduction for spectral clustering , Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (2011), pp.552–560

    2011

  6. [14]

    C. Wu, S. Ioannidis, M. Sznaier, X. Li, Xi- angyu,D. Kaeli, David and J. Dy, Iterative Spectral Method for Alternative Clustering , International Con- ference on Artificial Intelligence and Statistics(2018), pp. 115–123

    2018

  7. [15]

    Fowlkes, S

    C. Fowlkes, S. Belongie, F. Chung, and J. Malik, Spec- tral grouping using the Nystrom method , IEEE trans- actions on pattern analysis and machine intelligence (2004), pp. 214–225

    2004

  8. [16]

    L. Song, A. Smola, A. Gretton K. M. Borgwardt, and J. Bedo, Supervised feature selection via dependence estimation, Proceedings of the 24th international con- ference on Machine learning (2007), pp. 823–830

    2007

  9. [17]

    Vladymyrov, and M

    M. Vladymyrov, and M. Carreira-Perpi˜ n´ an,The Varia- tional Nystrom method for large-scale spectral problems , International Conference on Machine Learning (2016), pp. 211–220

    2016

  10. [18]

    P. A. Absil, R. Mahony and R. Sepulchre, Optimization Algorithms on Matrix Manifolds , Princeton University Press,Princeton, NJ ,(2008)

    2008

  11. [19]

    Wen and W

    Z. Wen and W. Yin, A feasible method for optimization with orthogonality constraints , Mathematical Program- ming (2013), pp. 397–434

    2013

  12. [20]

    R. A. Horn, and R. A. Horn, and C. R. Johnson Matrix analysis, Cambridge university press (1990)

    1990

  13. [21]

    W. H. Wolberg, Wisconsin breast cancer dataset , Uni- versity of Wisconsin Hospitals (1992)

    1992

  14. [22]

    O. L. Mangasarian, Cancer diagnosis via linear pro- gramming, SIAM news (1990), pp.18

    1990

  15. [23]

    Dheeru, and E

    D. Dheeru, and E. Karra Taniskidou, year = ”2017”, UCI Machine Learning Repository , http://archive.ics.uci.edu/ml, University of California, Irvine, School of Information and Computer Sciences

    2017

  16. [24]

    S. D. Bay, D. Kibler, M. J. Pazzani, and P. Smyth, The UCI KDD archive of large data sets for data mining research and experimentation , ACM SIGKDD Explorations Newsletter (2000), pp. 81–85

    2000

  17. [25]

    Y. Ding, Y. Zhao, X. Shen, M. Musuvathi, and T. Mytkowicz, Yinyang k-means: A drop-in replace- ment of the classic k-means with consistent speedup , International Conference on Machine Learning (2015), pp. 579–587

    2015

  18. [26]

    A. Y. Ng, M. I. Jordan, and Y. Weiss, On spectral clustering: Analysis and an algorithm , Advances in Neural Information Processing Systems (2002), pp. 849– 856

    2002

  19. [27]

    Strehl and J

    A. Strehl and J. Ghosh, Cluster ensembles—a knowledge reuse framework for combining multiple partitions , Journal of machine learning research (2002), pp. 583– 617

    2002

  20. [28]

    X. H. Dang and J. Bailey, Generation of alternative clusterings using the cami approach , Proceedings of the 2010 SIAM International Conference on Data Mining (2010), pp. 118–129

    2010

  21. [29]

    Ross and J

    J. Ross and J. Dy, Nonparametric mixture of Gaussian processes with constraints, International Conference on Machine Learning (2013), pp. 1346–1354

    2013

  22. [30]

    C. L. Li, W. C. Chang, Y. Cheng, Y. Yang, and B. P´ oczos,MMD GAN: Towards deeper understanding of moment matching network , Advances in Neural Information Processing Systems (2017), pp. 2203–2213

    2017

  23. [31]

    Rahimi and B

    A. Rahimi and B. Recht, Random features for large- scale kernel machines , Advances in Neural Information Processing Systems (2008), pp. 1177–1184

    2008

  24. [32]

    Musco and C

    C. Musco and C. Musco, Recursive Sampling for the Nystrom Method , Advances in Neural Information Processing Systems (2017), pp. 3836–3848. Copyright © 20XX by SIAM Unauthorized reproduction of this article is prohibited Appendix A Relating HSIC to Spectral Clustering Proof. U...

    2017

  25. [33]

    Copyright © 20XX by SIAM Unauthorized reproduction of this article is prohibited In Figure 4, the Moon dataset X is plotted in Fig

    The kernel matrices shown in the figures below use white as 0 and dark blue as 1; all values in between are shown as a gradient between the two colors. Copyright © 20XX by SIAM Unauthorized reproduction of this article is prohibited In Figure 4, the Moon dataset X is plotted in...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.