- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper considers the spectral clustering with coreset constructions and proposes GCSC, a graph‑native coreset spectral clustering approach that eliminates the kernel‑k‑means intermediary. This paper also delivers theoretical guarantees for edge optimality, endpoint coverage and robust lifting. Empirically, GCSC outperforms SOTA coreset baselines in most cases.
Critical strengths
S1. The proposed method has several theoretical guarantees.
S3. This paper anonymously provides its code to ensure reproducibility of experiments.
Critical weaknesses
W1. The overall presentation of this paper is hard to read with many confusing or inconsistent statements, which need further clarifications.
Some abbreviations (e.g., CSC and GCSC) were first used without giving their full names.
In Section 1, notations , , , , etc. were first used without giving their formal definitions. There seem no exact toy examples to illustrate what are , , and .
It should be a good presentation to illustrate the basic motivation using a toy example, i.e., Fig. 1. However, some important details of Fig. 1 are missing. For instance, it is unclear, what do vertices and edges with different colors mean. It was claimed that GCSC "combines degree-stratified sampling with a weight-preserving edge subgraph". However, Fig. 1 does not present any information about vertex degrees and edge weights, which may be inconsistent with the text description. As a result, it is still hard to understand what do Fig. 1 mean even after reading Section 1 (Introduction).
In Section 3, the formal definitions (e.g., matrix dimensionality, value of each entry, etc.) of , , were also not given.
The overall presentation of Section 5 (Theoretical Analysis) is also hard to read, with many notations, propositions, lemmas, and theorems. It is suggested to add some brief sentences to describe their basic logic (which theorem depends on which lemma/proposition) and also the key ideas of proof in the main text.
W2. It was claimed that this work studies whether the compressed graph can be constructed and solved directly in the graph domain. There seem no discussions or theoretical analysis to demonstrate the potential advantages of such a graph-native compressed-solve-lift pipeline over existing approaches (e.g., CSC),
W3. Most of the theoretical analysis in Section 5 relies on some specific conditions. There seem no qualitative discussions or quantitative evaluations about whether these conditions can satisfy in real applications and when they may fail (i.e., the theoretical analysis becomes trivial).
Questions for authors
See W1-W3.
rebuttal
Thanks for your review and feedback.
W1(a) Algorithm abbreviations
GCSC denotes Graph Coreset Spectral Clustering and CSC denotes Coreset Spectral Clustering; the revision gives both names. Both use spectral solving, but GCSC selects original graph edges and endpoints directly, whereas CSC constructs a reweighted object through a kernel coreset. CoSC is a separate spectral-clustering baseline using the kernel-k-means equivalence, and Cokkm is a kernel-clustering coreset baseline. Sections 2 and 3 distinguish their roles and construction routes.
W1(b) A concrete endpoint-graph example
The new example in Appendix A takes S={1,2,3,4,5,6} and retained top edges {1,2} and {2,3}. The active set is then VH={1,2,3}, with original weights W12 and W23 unchanged. The other three sampled vertices are not retained endpoints, so they do not enter the reduced spectral solve and instead receive labels through lifting.
This follows Eqs. (3)–(4) and explains why sampled vertices are not automatically all part of the reduced graph. The set ES+ consists of positive undirected edges whose two endpoints lie in S.
W1(c) Figure 1 colours and weights
Figure 1 depicts computational routes rather than an experimental graph with class labels. Its revised caption identifies purple and pink as graph and kernel domains and red as selected objects; colours encode neither degree nor class. The red edges and their endpoints on the right form GCSC's reduced graph, while stratification uses input weighted degrees.
Equation (2) gives the numerical distinction: GCSC preserves Wuv, whereas the intermediary has off-diagonal weight ωuωvWuv/(dudv). Equal support need not mean equal weights. The schematic connections on the left do not imply that CSC necessarily creates off-support edges; the text explicitly states this.
W1(d) Kernel notation and dimensions
Section 3 now states the dimensions. For r selected vertices, WC is the r×r diagonal coreset-weight matrix and [K]C is the r×r principal submatrix of the full n×n kernel. Hence AC=WC[K]CWC is also r×r.
The coefficient σ is the diagonal shift in the equivalent kernel representation. It changes diagonal entries, not the off-diagonal relation in Eq. (2). GCSC neither constructs this intermediary kernel nor uses its shift as a tuning parameter. Appendix B.13 uses it only to analyze kernel optimization.
W1(e) Proof dependencies
Section 5 now follows the algorithmic progression. The structural branch uses the exchange argument in Proposition 5.1 and stratified sampling with top-edge rank protection in Proposition B.2. The error branch proceeds through graph perturbation in Lemma 5.3, spectral stability in Lemma 5.4, tolerance-aware rounding in Proposition B.5, lifting stability in Lemma 5.5, and NCut stability in Lemma 5.6.
Theorem 5.7 combines these results on the coverage and stability events and uses a union bound, without requiring event independence. Strong-coreset transfer in Proposition B.1, the computable certificate in Corollary B.6, and the explicit graph-class result in Proposition 5.8 answer distinct questions rather than forming one undifferentiated collection of assumptions.
W2 Value of direct graph construction
Even one importance-sampling round still requires kernel-centre distances, importance weights, and reweighting. Thus “one round is often enough” does not make eliminating the intermediary immaterial. More importantly, preserving original weights lets deleted-degree fractions control uniform active-graph NCut and connect to spectral solving and lifting.
The evidence goes beyond counting steps: Tables 1 and 4 show improvements over CSC on four datasets under a common configuration, Table 5 isolates a kernel-optimization effect, and Waveform3 demonstrates substantial pruning with high fidelity.
“Direct graph” refers to coreset construction after receiving the input graph, not exclusion of vector-derived kNN graphs. Building such a graph is standard spectral-clustering practice and is also used in [CSC Section 6.2], as the revised introduction explicitly explains.
W3 Meaning of the conditions in applications
The conditions measure representation coverage, deletion effects on the relevant eigenspace, and separation of lifting scores. The reference can be Full SC; weighted degree need not predict external labels. Structural optimality and uniform active-graph NCut control require no eigengap, whereas the complete solve-and-lift guarantee additionally uses stability conditions.
The revision addresses applicability in three ways: Proposition 5.8 gives an explicit success class with improvement in p and sample size independent of n; Corollary B.6 provides a label-free spectral certificate; and Tables 7 and 8 distinguish successful real-graph parameter regimes from conservative sufficient conditions.