|
Is a Small Matrix Eigendecomposition Sufficient for Spectral Clustering? |
Soundness: 3: good
Presentation: 3: good
Contribution: 2: fair
Rating: 4: marginally below the acceptance threshold
Confidence: 4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. |
This paper proposes D-SPEC, a distribution-based spectral clustering method that reduces the computational cost of spectral clustering by performing eigen-decomposition on only a small matrix. The key idea is to construct a bipartite graph between $n$ data points and $k$ distributions (representing clusters), rather than between points and landmarks as in traditional landmark-based methods. The authors argue that this distribution-based approach preserves more graph information and is more robust to noise. The paper includes theoretical analysis, extensive experiments on synthetic and real-world datasets (up to 20 million points), and comparisons with state-of-the-art scalable spectral clustering methods.
- The shift from point-based to distribution-based representation is a novel and well-motivated idea.
- Theorems 3.2–3.4 provide solid grounding for the method’s robustness and graph preservation properties.
- Experiments on datasets with up to 20 million points demonstrate practical utility.
- The initial graph construction (bounded graph) may still be $O(p^2)$ in the worst case, which could undermine efficiency gains for very large $n$.
- While the distribution-based idea is novel, the overall pipeline (bipartite graph + k-means) shares similarities with existing landmark methods. A clearer conceptual and empirical distinction is needed.
- The claim of "eigen-decomposition on only a $k\times k$ matrix" is misleading. The final decomposition is on a
$n\times k$ matrix, the overall complexity is dominated by the $O(nk^2)$ term from the transfer cut method, not the $O(k^3)$ eigen-decomposition. This misrepresentation undermines the central claim.
- The sampling number $p$ is not treated as a hyper parameter. It's unclear how $p$ was chosen for different experiments. It directly controls: 1) the quality of the bounded graph construction; 2) how well the sampled points represent the underlying distributions; 3) the computational cost of the initial graph construction $O(p^2)$; 4)the overall clustering quality.
- How was the sampling number $p$ determined in your experiments? Why wasn't $p$ included in your hyperparameter analysis? Can you provide a sensitivity analysis showing how performance varies with $p$ across different datasets?
- Could you provide an ablation study to analyze the contribution of each component of the method? For example, the contribution of the bounded graph construction, and the distribution-based bipartite graph? |
Fully AI-generated |
|
Is a Small Matrix Eigendecomposition Sufficient for Spectral Clustering? |
Soundness: 2: fair
Presentation: 3: good
Contribution: 2: fair
Rating: 4: marginally below the acceptance threshold
Confidence: 4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. |
This paper is an interesting work, it proposes D-SPEC, a distribution-based spectral clustering method that performs eigendecomposition on only a 𝑘 × 𝑘 matrix. The goal is to maintain clustering quality while drastically reducing computational cost.
1. The motivation is clear and relevant — speeding up spectral clustering for large datasets；2. The distribution-based bipartite formulation is an interesting angle and fairly well explained; 3. The theoretical parts are written carefully and show good understanding of spectral clustering basics.
1. The novelty is limited. The method largely builds on existing transfer-cut and landmark-based spectral clustering, with the “distribution” step being a modest variation rather than a fundamentally new concept; 2. Several theoretical assumptions (such as Assumption 3.1 on perfect intra-cluster connectivity) are unrealistic for real-world data, making some of the guarantees less meaningful in practice; 3. Experimental results are not convincing enough: most datasets are small and low-dimensional, and scalability claims (up to millions of samples) are not demonstrated with wall-clock or memory comparisons; 4. No statistical variance or significance tests are shown; many tables lack error bars or runtime comparisons, so it’s hard to judge robustness; 5. The link between the theoretical results and empirical behavior is weak — proofs are long but not clearly tied to observed performance.
1. How sensitive is D-SPEC to the choice of the number of distributions 𝑘 and the threshold parameter 𝜏? Have you tested the stability of results under different settings? 2. In Assumption 3.1, you assume perfect intra-cluster connectivity in RKHS. Could you clarify how realistic this is for noisy or high-dimensional data, and what happens when this assumption fails? 4. The scalability claim mentions datasets up to 20 million points, but Table 1 only covers small benchmarks. Could you provide runtime or memory results on truly large-scale data? 5. The theoretical results (Theorem 3.2–3.4) are elegant, but their empirical implications remain unclear. Could you give one concrete example linking a theorem to an observed performance gain? 6. Have you compared D-SPEC with other recent graph-based or distributional spectral clustering methods (e.g., GBSC 2023 or transfer-cut variants)?
I would be glad to improve my scores if the authors give me satisfying answers. |
Fully AI-generated |
|
Is a Small Matrix Eigendecomposition Sufficient for Spectral Clustering? |
Soundness: 2: fair
Presentation: 2: fair
Contribution: 2: fair
Rating: 4: marginally below the acceptance threshold
Confidence: 4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. |
This paper proposes a distribution-based spectral clustering method named D-SPEC, aiming to address the high computational complexity of traditional spectral clustering on large-scale datasets. By constructing a bipartite graph between data points and distributions, D-SPEC reduces the eigendecomposition matrix size from n×n to k×k (where k is the number of clusters), while striving to preserve the original graph information. The authors theoretically and empirically validate the advantages of D-SPEC in terms of clustering performance, robustness, and scalability. Extensive tests on multiple real-world and synthetic datasets demonstrate that D-SPEC outperforms existing methods in most cases.
1. The proposed method elevates the traditional point-based graph representation to a distribution-based one, thereby reducing computational complexity while retaining the global structural information of the graph.
2. The proposed method provides solid theoretical analysis, offering rigorous proofs concerning eigenvalue perturbation and embedding stability, which enhances the method's credibility and robustness guarantees.
3. Comprehensive experimental design, covering datasets ranging from hundreds to twenty million instances and comparing against five other mainstream methods across multiple dimensions, validating the method's effectiveness and scalability.
1. Distribution estimation relies on bounded graph construction, but the selection of the threshold τ lacks theoretical guidance, leading to subjective bias.
2. Although the IDK kernel addresses the dimensionality issue of the Gaussian kernel, its expressive power in capturing complex distributions is not sufficiently justified.
3. Regarding non-ideally distributed data, D-SPEC's reliance on distribution representation may lead to misjudgment of boundary points.
4. The analysis of the sensitivity of the size p is not clear, and a small p might render the distribution estimate unrepresentative.
5. The theoretical claim that λ_dk+1^(0)>λ_k+1^(0) lacks rigorous derivation and is presented based largely on intuitive analogy.
6. The complexity analysis does not account for the hidden costs in the distribution estimation phase.
7. The method's strong assumptions about data distribution do not work in real-world scenarios, limiting its generalizability.
Some confusing points undermine the credibility of the proposed method, for example, performance is mediocre on structured data like 'covertype', indicating limited adaptability of the method to high-dimensional sparse data. The ensemble learning version D-SENC fails to improve performance. The image segmentation experiment only shows visual results without quantitative evaluation. There is no discussion on the method's sensitivity to class-imbalanced data. The theoretical assertion of 'no loss of graph information' is described absolutely. |
Moderately AI-edited |
|
Is a Small Matrix Eigendecomposition Sufficient for Spectral Clustering? |
Soundness: 1: poor
Presentation: 3: good
Contribution: 2: fair
Rating: 2: reject
Confidence: 5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully. |
The authors propose a novel distribution-based spectral clustering method that constructs a bipartite graph, enabling eigendecomposition on a smaller $k\times k$ matrix while preserving clustering quality, which is validated through extensive experiments.
- Proposing a distribution-based spectral clustering algorithm, termed D-SPEC, that only requires the eigendecomposition of a k × k matrix.
- Proving theoretically that D-SPEC retains the graph information and providing a bound for noise tolerance indicates the enhanced robustness of D-SPEC
The primary limitation of this work lies in its lack of significant advantages. The proposed algorithm does not demonstrate any notable improvement in time complexity over existing methods, and the enhancements observed in clustering quality metrics are also marginal. Therefore, I cannot recommend acceptance of this paper.
NaN |
Moderately AI-edited |