- 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 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
-
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.
-
The threshold parameter , 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 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.
-
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
-
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.
-
How was the threshold parameter 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.
-
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.
-
Some variable definitions are missing from the current manuscript. For example, in line 214, in line 227, and axes labels in Figure 1 and 3. In addition, the more information about is necessary for readers to understand.
Minor questions:
- Which datasets did you use for the experiment to generate Figure 8?
Rebuttal
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), 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×k representation, explicitly crediting transfer cut, kernel means and sampling tools as prior ingredients.
A2: Appendix S.8 fixes t=400,ψ=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.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×k is now defined as membership indicators, E∈Rn×k as a point–distribution affinity perturbation, and nj=∣Cj∣ 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 k 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.