acceptodds
Under review as a conference paper at ICLR 2027

Is a Small Matrix Eigendecomposition Sufficient for Spectral Clustering?

Abstract

Spectral clustering is effective but expensive at large scales because its standard formulation constructs an affinity matrix and solves a large spectral problem. A central challenge is to retain informative cluster representations while reducing the matrix size to depend only on the number of clusters . We address this challenge from a distributional perspective: each representative summarizes a distribution rather than an individual point. D-SPEC constructs an point–distribution bipartite graph and reduces its spectral problem to a matrix. We establish exact partition recovery under explicit affinity-profile conditions, perturbation-to-clustering error guarantees, and finite-partition bounds valid for adaptively selected representatives. Extensive experiments on synthetic and real-world datasets demonstrate the effectiveness and scalability of this distributional construction.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
spectral clustering, distribution kernel, matrix eigende

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_pbE4OpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces an efficient computational framework for spectral clustering. To reduce computational overhead, the proposed method first constructs a sparse graph by thresholding affinity values between instances. Next, cluster representatives are derived from the kernel means of the kk largest connected components, and a bipartite graph is generated based on the affinities between these representatives and instances. Finally, spectral clustering is applied to the bipartite graph. The computational efficiency is validated both theoretically and empirically, while its performance and robustness against perturbations are demonstrated on benchmark datasets.

Critical strengths

This study addresses the important issue of computational efficiency in spectral clustering. The superiority of the proposed method over the standard spectral clustering and existing methods has been empirically demonstrated.

Critical weaknesses
  1. The core framework and theoretical components relying on a bipartite graph heavily overlap with existing work, specifically U-SPEC. Consequently, the proposed method (D-SPEC) appears to offer only an incremental extension of U-SPEC. The authors should explicitly highlight their novel contributions and clarify how D-SPEC fundamentally differs from U-SPEC.

  2. The threshold parameter τ\tau, used for graph edge removal in the initial step, plays a crucial role as it directly impacts both clustering accuracy and computational speed. However, the manuscript lacks a discussion on how τ\tau is tuned and how sensitive the results are to this parameter. Consequently, the performance comparisons reported in the numerical experiments may not be entirely fair or convincing.

  3. Essential details, including variable definitions and axis labels for figures, are lacking in the current manuscript. Specifically, the top- and bottom-right panels of Figures 1 and 3 lack axis labels. Additionally, the figure titles in the top section remain unclear due to an insufficient explanation of the underlying computational procedures.

Questions for authors
  1. As noted in my comments on weaknesses above, could the authors clarify the fundamental differences between the proposed method and U-SPEC? U-SPEC already accounts for probability distribution via a hybrid approach combining random sampling and k-means. Moreover, U-SPEC does not rely on hard-to-tune thresholding parameters.

  2. How was the threshold parameter τ\tau tuned in the numerical experiments? Additional numerical experiments are needed to analyze the sensitivity of this parameter with respect to clustering accuracy and computational time. This issue is directly relevant to the findings presented in Figure 7.

  3. Is there any novel result related with Theorem 3.2, compared with the U-SPEC paper? The main framework relies on the previous study. Thus, it cannot be the novel result in this main text.

  4. Some variable definitions are missing from the current manuscript. For example, HH in line 214, EE in line 227, and axes labels in Figure 1 and 3. In addition, the more information about xnkjx_nk^j is necessary for readers to understand.

Minor questions:

  1. Which datasets did you use for the experiment to generate Figure 8?
1 comment

Thanks for your review.

A1: The distinction is not whether multiple observations are used, but how they become graph vertices. Hybrid sampling improves U-SPEC's point-landmark placement, while each column remains a distance affinity to one point/center. A D-SPEC column is Bij=∣Gj∣−1∑z∈Gjκ(xi,z)B_{ij}=|G_j|^{-1}\sum_{z\in G_j}\kappa(x_i,z), retaining mean kernel responses to multiple observations. For nonlinear kernels this generally differs from the kernel evaluated at an input-space centroid. More observations can therefore estimate a representative without increasing the vertex count.

Tables 19 and 23 distinguish this mechanism from merely reducing the point budget or relying on core construction alone. Proposition C.15 analyzes the corresponding normalized compression. The introduction and related work now emphasize distribution vertices and the n×kn\times k representation, explicitly crediting transfer cut, kernel means and sampling tools as prior ingredients.

A2: Appendix S.8 fixes t=400,ψ=512t=400,\psi=512 and retains all 13 thresholds on Pendigits/MNIST rather than only their peaks. Tables 40–41 show that the threshold primarily changes core structure and quality: at 0.20/0.25/0.300.20/0.25/0.30, NMI is 0.800/0.855/0.837 on Pendigits and 0.749/0.755/0.553 on MNIST. Downstream times range only from 0.117–0.170 s and 0.333–0.514 s, against shared feature preprocessing of 2.536 and 355.410 s. Stage sums are not separate end-to-end reruns at each threshold.

Automatic selection is separately tested with the same B rule for both methods in main-text Table 2 and Appendices S.10 and S.13; CH controls remain separate. Table 46 reports per-run threshold selection within each scale followed by averaging only over scales, never over thresholds. Maximizing CH does not guarantee maximal NMI. Figure 7 compares three geometric examples, not arbitrary-threshold or all-dataset recovery guarantees.

A3: At first use, H∈{0,1}n×kH\in\{0,1\}^{n\times k} is now defined as membership indicators, E∈Rn×kE\in\mathbb R^{n\times k} as a point–distribution affinity perturbation, and nj=∣Cj∣n_j=|C_j| as the true cluster size without an equal-size implication. The captions of Figures 1 and 3 and Appendix S.16 identify eigenvalue index/value in the upper panels and embedding coordinates, not input features, below.

We also checked the actual operators: the original point graph uses a normalized Laplacian; the point-bipartite illustration uses an unnormalized Laplacian because of isolated points; the distribution-bipartite graph uses a normalized Laplacian; and reduced graphs display normalized-affinity spectra. The revision does not interpret these bars as errors for the same operator or numerical verification of Theorems 3.3–3.4, and states the full/reduced spectral relationships.

A4: Transfer cut is the established reduction of an eigenproblem on the same bipartite graph to its representative side; we explicitly do not claim it as a new theorem. Theorem 3.2 concerns representation: which response directions with only kk distribution vertices yield one distinguishable center per class. It permits nonzero cross-class affinities and rank deficiency, illustrated by the connected rank-deficient example in Appendix C.5.

New Propositions C.14–C.16 analyze response averaging, exact normalized compression and actual-core-to-profile error. Theorems C.7 and C.17 control actually returned labels, while Theorem C.9 uniformly handles finite-partition error for adaptive representatives. Complete proofs are in the paper, with standard perturbation tools explicitly credited. Studying distributional representation and its propagation to clustering is distinct from reproving spectral reduction.

A5: The caption of Figure 8 and Appendix S.16 now specify the 15 datasets in Table 1 plus DSSS, DSDS and OGOL, for 18 in total. Each point is a recorded dataset-level NMI, not a different seed on one dataset; million-scale datasets are excluded. Checking the source arrays also identified interchanged D-SPEC/U-SENC plotting labels, which we corrected without changing the values. Correct means are 0.672, 0.762, 0.757 and 0.765 for U-SPEC, D-SPEC, U-SENC and D-SENC. The main text therefore states a similar, slightly higher descriptive mean for D-SPEC than U-SENC, without significance or an established causal explanation for the limited ensemble gain.

Reviewer_yk3EOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a spectral clustering method based on a bipartite graph constructed using distributional representations. The method first samples the data and partitions the sampled points into several groups by thresholding graph edges to construct distributional representatives. It then uses IDK to compute the similarities between data points and distributional representatives and constructs a bipartite graph. Finally, Transfer Cut is applied to obtain the spectral embedding and perform clustering.

Critical strengths

The paper provides an interesting perspective on whether a very small number of representatives, regardless of whether they are individual points or distributions, can sufficiently support subsequent spectral clustering. In particular, reducing the number of representatives to the number of clusters offers a relatively novel perspective. The overall method is also simple and does not introduce many additional hyperparameters, making it relatively easy to implement and apply. The paper further provides theoretical analyses from several perspectives, including exact recovery, perturbation stability, and finite approximation, although I have concerns about how some of these guarantees connect to the actual construction.

Critical weaknesses

My main concern with the theoretical analysis is that the core guarantees rely on a relatively strong structural assumption on the bipartite affinity matrix B. Several subsequent theoretical results mainly analyze the stability of the spectral embedding and clustering results when B is perturbed from this ideal structure. However, the proposed heuristic construction of distributional representatives does not establish that the resulting B satisfies, or is even close to, this assumed structure. Therefore, while these theoretical results may be valid under their respective assumptions, there appears to be a missing theoretical link between these guarantees and the actual algorithm. More importantly, even if we further assume that the preceding step correctly identifies the underlying cluster distributions, it is still not clear that the point-to-distribution affinities would produce a B close to the assumed structure. Overall, the theoretical analysis does not sufficiently establish that the proposed construction satisfies the conditions required by its main guarantees. My second concern is that recovering the distributional representatives through thresholding requires relatively strong structural conditions on the data. Therefore, it remains unclear to what extent the subsequent clustering performance benefits from the distributional representation itself rather than from these favorable conditions. More importantly, the current analysis does not sufficiently explain why k distributional representatives can compensate for the information loss caused by reducing the number of representatives from p to k.

Questions for authors

Could the authors clarify whether the proposed construction of distributional representatives can theoretically guarantee that the resulting affinity matrix B satisfies or approximates the structural assumption required by the main theoretical results? Could the authors further explain why reducing the number of representatives from p to k does not result in substantial information loss for subsequent spectral clustering? To what extent does the performance benefit from the distributional representation itself rather than from the favorable structural conditions required for representative recovery?

1 comment

We thanks for your review.

A1: New Proposition C.16 supplies this explicit error chain and its complete proof. Let μr\mu_r be the empirical class mean in the limiting-kernel feature space, mjm_j the actual selected-core mean, and Crj=⟨μr,μj⟩C_{rj}=\langle\mu_r,\mu_j\rangle. For observation ii in class rr, set βj=∥mj−μj∥\beta_j=\|m_j-\mu_j\| and ηi=max⁡j∣⟨ϕ(xi)−aiμr,mj⟩∣\eta_i=\max_j|\langle\phi(x_i)-a_i\mu_r,m_j\rangle|. On the uniform finite-tt event,

∣Bt,ij−aiCrj∣≤ϵt+ηi+aiβj.|B_{t,ij}-a_iC_{rj}|\le\epsilon_t+\eta_i+a_i\beta_j.

The proof uses uniform kernel approximation, insertion of ai⟨μr,mj⟩a_i\langle\mu_r,m_j\rangle, and Cauchy–Schwarz; it does not assume independence of adaptively selected core members. The event in Theorem C.9 covers cores selected from the same random features, with a union bound over a finite scale grid. Entrywise bounds control relative-degree and normalized-operator perturbations, then connect to Proposition C.6 and Theorem C.7 for embeddings and actually returned labels.

This separates finite-partition error, within-class response variation and core-representation error. It neither requires spherical input clusters nor equates purity with the profile condition. Tables 38–39 are finite-kernel post-hoc diagnostics, not limiting-kernel probability certificates. The result makes the construction–representation–recovery connection explicit.

A2: We do not claim arbitrary graphs compress losslessly to kk vertices. Main-text equation 2 and Proposition C.15 exactly characterize the implemented mean construction. For the core-size-reweighted point affinity AwA_w, its normalized operator TwT_w and distribution operator TBT_B satisfy TB=TwRT_B=T_wR and R⊤R=IR^\top R=I. The operator difference is positive semidefinite and its spectral norm equals ∥Tw(I−RR⊤)∥22\|T_w(I-RR^\top)\|_2^2.

This identity holds pathwise for actual cores without purity or labels. If the discarded directions vanish, the entire normalized point-side operator and spectrum are preserved. Otherwise their squared norm is the exact spectral cost; subspace/label preservation additionally requires a gap or margin. The reference is the point graph with the same core-mean weights, not an arbitrary U-SPEC construction.

Proposition C.14 additionally shows exact preservation of shared response patterns and an aggregation-error bound. Empirically, Table 19 shows that merely reducing point representatives to kk loses quality, whereas Table 23 holds cores fixed and isolates distributional representation. Together, these explain why kk distribution vertices do not mean retaining only kk raw observations.

A3: Table 23 is the direct control: all three variants share bounded-graph/core construction and change only distribution vertices, point vertices or input-space centroids. Their NMI is 0.847/0.674/0.691 on Pendigits, 0.778/0.418/0.507 on USPS and 0.747/0.458/0.527 on MNIST; seven-dataset means are 0.581/0.447/0.481. Core difficulty is held fixed and therefore cannot by itself explain these differences. The revised introduction highlights this ablation, with Propositions C.14–C.15 analyzing response preservation and normalized compression.

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

The paper proposes D-SPEC, a scalable spectral clustering method. It thresholds an Isolation Distribution Kernel graph on p sampled points and uses the k largest connected components as kernel-mean “distribution” representatives. It then builds an n × k bipartite graph and solves a k × k eigenproblem via transfer cut. The paper provides exact-recovery, perturbation and misclustering guarantees, and reports the best average ranks on 15 benchmarks and five synthetic datasets of up to 20M points.

Critical strengths
  • The appendix is careful and honest about the scope of each result. Theorem C.7 bounds the error of the labels k-means actually returns, and Theorem C.9 covers representatives selected adaptively from the same random features.

  • The empirical coverage is broad: three metrics, a Nemenyi test, informative ablations (Tables 20–23) .

  • Limitations are acknowledged, including parameter sensitivity and failure cases. The use of the Calinski–Harabasz (CH) index as a label-free selection criterion (Fig. 10) is a good step.

Critical weaknesses
  • The spectral step appears not to affect the result. With k representatives and all k eigenvectors, the proof of Prop. C.6 gives Y = rownorm(B D_y^{-1/2}) V with V orthogonal. Since k-means is rotation-invariant, D-SPEC reduces to k-means on normalized point-to-representative affinities. This undermines the framing of the title and contributions.

  • The guarantees do not establish the claimed advantages.

    • Exact recovery (Thm 3.2) follows almost directly from the assumption B = diag(a)HC, which already encodes the cluster structure. The difficult part, ensuring that each representative is pure, relies on near-separability conditions (Cor. C.12).
    • The “tighter” robustness over SC (Thms 3.3–3.4) holds only if εd ≤ εs, which is never verified, and it compares different operators under different perturbation models.
  • Hyperparameters are selected with labels, under unequal budgets. Appendix E reports the best result over grids, with 104 configurations for D-SPEC against 11 for the baselines (Table 4). CH is proposed but not used for the reported numbers.

  • Some claims contradict the paper’s own tables.

    • Appendix J claims superiority over GGC and Spectral Bridges, but on MNIST Table 15 shows 0.862 and 0.788 against 0.746 for D-SPEC.
    • Sec. 4.2 claims very low runtime, but Table 10 shows DNCSC is 2–5× faster.
  • Scalability and protocol issues.

    • All million-scale data are 2-D synthetic.
    • No standard deviations are reported.
    • The complexity count omits the IDK feature-map cost and treats p as a constant.
Questions for authors

Suggestions

  • Check whether k-means on rownorm(B D_y^{-1/2}) yields the same labels as D-SPEC. If so, reframe the paper as a kernel-mean representative method and position it against Kernel-bounded clustering.
  • Re-report all methods with CH-based selection and equal budgets, with standard deviations.
  • Add large-scale, high-dimensional real data with a runtime breakdown that includes IDK construction, and state conditions under which εd ≤ εs.

Questions

  • How many eigenvectors are used, and are they rescaled by the singular values?
  • How was τ chosen on the 20M-point datasets?
2 comments

Thanks for your review.

A1: This observation yields an exact solver simplification, not an explanation away of the distributional construction. The implementation uses all kk right-side eigenvectors, without additional singular-value scaling. For positive degrees, its mathematical row-normalized embedding is Y=rownorm⁡(BDy−1/2)V=ZVY=\operatorname{rownorm}(BD_y^{-1/2})V=ZV, where VV is orthogonal.

Proposition C.13 proves equality of the kk-means objectives for every partition and correspondingly rotated centers, hence equality of globally optimal partitions. It also handles zero rows and the numerical denominator offset; with a nonzero offset, the same pre-normalized representation is retained. Matched-center Lloyd iterations agree with consistent tie handling, whereas independently initialized runs need not. The seven-dataset paired check in Appendix S.7 gives minimum ARI 1.000 and maximum relative objective difference 4.333×10−144.333\times10^{-14}.

The main text now attributes the benefit to distributional affinities and normalized geometry, not the rotation. The fixed-core ablation in Table 23 directly tests that representation. KBC shares thresholded cores and kernel means, but its maximum point-to-core affinity assignment differs from jointly optimizing kk-means on the column-degree/row-normalized response vectors. Removing the rotation preserves this difference

A2: Theorem 3.2 characterizes which distributional response profiles permit recovery with only kk vertices; it is not restricted to already disconnected graphs. It allows nonzero cross-class affinities and rank-deficient CC, provided the relevant row directions are distinguishable. Appendix C.5 adds an entrywise-positive, rank-two example with three classes: a connected bipartite graph still yields three distinct normalized centers and exact globally optimal partition recovery.

Real-data evidence supports the structural motivation. Across Landsat–MNIST, Table 4 reports a macro strict-Assumption-3.1 rate of 0.877, a 0.024% rate of genuinely stronger cross-class comparisons, and post-hoc kernel-class-mean separability of 0.952. These directly characterize local structure and aggregation, without asserting a global exact-profile certificate. Lemma C.1 requires a surviving within-class bottleneck spanning tree, not every within-class edge. The stronger Corollary C.12 supplies one explicit sampling-probability regime, not the sole premise of every result.

Nor does fragmentation imply singleton distribution vertices. Tables 32–33 report every selected core size, top-kk coverage and small-component mass at t=400t=400. MNIST has 5842 sampled-graph components, yet its ten selected cores contain 87–797 observations; the ranges are 212–1860 for Pendigits and 37–954 for USPS. Small-core exceptions on Landsat/Waveform3 are retained. Proposition C.16 provides the additional construction-to-profile link instead of treating purity as a proof.

A3: Averaging has quantitative support independent of matrix dimension. With the kernel and other members fixed, replacing one observation in an mm-member core changes its mean embedding by at most 2κ/m2\kappa/m when feature norms are bounded by κ\kappa. Corollary C.4 propagates representative error to affinities. New Proposition C.14 additionally bounds mean-aggregation error by ∥F∥F/mmin⁡\|F\|_F/\sqrt{m_{\min}} under shared response patterns, without independence or zero-mean errors.

Operator/subspace comparisons still require explicit perturbation and spectral-gap conditions, retained in Theorems 3.3–3.4 and their proofs. They do not follow from a k×kk\times k dimension alone. Figure 5 measures observed noise performance; Tables 38–39 separately disclose actual-core and degree diagnostics. These do not provide a nonvacuous full-data label certificate on the seven audited datasets. New Theorem C.17 proves a counting bound with an explicit exception set, clarifying the handling of zero-affinity rows.

A4: Revised Table 16 supports a quantifiable aggregate advantage: five wins, one tie and one loss against GGC, and six wins and one loss against Spectral Bridges. Seven-dataset mean NMI is 0.581/0.561/0.551/0.520 for D-SPEC/GGC/Spectral Bridges/FSC-PLGB. The MNIST exception is retained: GGC 0.862 and Spectral Bridges 0.788 exceed D-SPEC 0.746. We added the means and revised the interpretation to a majority of wins and a higher benchmark mean.

A5: Main-text Table 2 now directly reports a shared label-free rule B. Both methods search 104 joint configurations on each of eight full datasets. B uses only agreement between two predicted partitions and cluster entropy; D-SPEC uses t=400t=400. Three fresh calibration pairs independently select configurations. After all 48 choices are sealed, each is validated using the same five fresh seeds. D-SPEC has higher macro NMI in every recalibration, with overall means 0.487/0.419 and higher dataset-level NMI/ARI/F-measure means on 7/8, 8/8 and 7/8 datasets. Appendices S.10 and S.13 report the complete rule, fallback, configurations and outcomes, including the reverse NMI ordering on Landsat.

Tables 43–45 also retain the first fixed-B ten-seed validation. D-SPEC/U-SPEC NMI is 0.757/0.586 on USPS, 0.737/0.582 on MNIST and 0.819/0.763 on Pendigits. D-SPEC uses ten distribution vertices, whereas the corresponding selected U-SPEC configurations use 2000 point representatives.

Original Table 1 is now explicitly label-informed grid evaluation. Full-data CH and equal-candidate NMI controls appear separately in Tables 28–31, with macro NMI 0.441/0.445 and 0.565/0.522. Appendices S.11–S.12 distinguish per-run threshold selection followed by averaging only over scales from joint per-run selection. Candidate counts are matched, not computation time. B was developed after prior benchmark exploration, so fresh seeds test randomization, not unseen-dataset generalization. The directly supported conclusion is an aggregate quality advantage against the most closely related U-SPEC baseline under a shared label-free pipeline.

A6: A smaller eigenproblem, scalability, and fastest runtime execution are distinct claims; the representation contribution does not depend on the last one.

A7: Figure 6 and Appendix S.14 now include full SIFT1M (106×12810^6\times128) and GIST1M (106×96010^6\times960), without replication or dimensionality reduction. Three-run D-SPEC/U-SPEC times are 5.265±1.060/15.842±3.8435.265\pm1.060/15.842\pm3.843 s for SIFT1M and 6.026±0.646/25.370±0.8716.026\pm0.646/25.370\pm0.871 s for GIST1M. Tables 53–57 disclose all stages, seeds, process-memory peaks and exceptional outcomes.

D-SPEC uses t=400,ψ=128,k=10t=400,\psi=128,k=10; U-SPEC uses p=1000,KNN=5,k=10p=1000,K_{\mathrm{NN}}=5,k=10. SIFT1M retains fixed τ=0.55\tau=0.55. A label-free sampled-graph feasibility rule selects 0.200.20 for all three GIST1M seeds.

Labeled high-dimensional quality evidence is in Table 20: D-SPEC/U-SPEC NMI is 0.708/0.674 on UCI HAR, 0.492/0.447 on Abdominal CT, 0.578/0.008 on Gas Sensor Drift and 0.421/0.338 on Sensorless Drive, with higher D-SPEC ARI in all four cases.

A8: Tables 28, 30 and 43–44 report ten-seed means and sample SDs for fixed configurations: 140 validations each for CH/NMI controls and 160 for shared B, with selection preceding validation. Main-text Table 2 and Tables 48–52 additionally distinguish between-recalibration SD from within-configuration five-seed SD.

A9: Section 4.2 and Appendix S.15 now give the full leading numerical cost for the direct-distance implementation:

O(tnψd+tψ2d+p2t+pt+ktψ+nkt+nk2+k3+RInk2).O(tn\psi d+t\psi^2d+p^2t+pt+kt\psi+nkt+nk^2+k^3+RInk^2).

This includes feature construction, sampled affinities, core means, full bipartite affinities, reduction, eigendecomposition and RR restarts of II Lloyd iterations. Here p=min⁡(n,10000)p=\min(n,10000). Features, sampled graph, representatives and bipartite affinities require O(nt+tψ+p2+ktψ+nk)O(nt+t\psi+p^2+kt\psi+nk) storage, in addition to input and temporary distance arrays. Linearity in nn conditions on fixed d,t,ψ,p,k,I,Rd,t,\psi,p,k,I,R.

A10: The parameter in 20M-point $(\psi,\tau) = (512,0.35)(512,0.35)

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.