acceptodds
Withdrawn from ICLR 2027

Coreset Spectral Clustering without Kernel Intermediary

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Existing coreset methods for spectral clustering commonly proceed through the equivalence between normalized cut and weighted kernel -means. We study whether the compressed graph can instead be constructed and solved directly in the graph domain. GCSC combines degree-stratified vertex sampling, retention of high-weight input edges, spectral clustering on the endpoints of those edges, and average-affinity lifting. Every retained edge keeps its original weight, and no off-support edge is introduced. For a fixed sample and edge count, we establish edge-tail optimality. We also derive an explicit stratified-sampling bound for endpoint coverage. Under stated perturbation/gap, tolerance-separation, balance, and margin conditions, same-vertex spectral stability and robust lifting yield two-sided full-graph NCut fidelity to a fixed reference partition, such as standard spectral clustering. On six benchmark datasets, GCSC attains the highest mean ARI among the compared coreset methods on five datasets at the largest shared coreset size. Mechanism studies further characterize sampling fidelity, edge-budget sensitivity, and affinity lifting.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
coreset, spectral clustering, kernel method

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_MvYuOpenReview ↗
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 VV, EE, WuvW_{uv}, SS+S_S^+, etc. were first used without giving their formal definitions. There seem no exact toy examples to illustrate what are VHV_H, EHE_H, and WHW_H.

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 WC{\bf{W}}_C, [K]C[{\bf{K}}]_C, σ\sigma 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.

1 comment

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}S=\{1,2,3,4,5,6\} and retained top edges {1,2}\{1,2\} and {2,3}\{2,3\}. The active set is then VH={1,2,3}V_H=\{1,2,3\}, with original weights W12W_{12} and W23W_{23} 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+\mathcal E_S^+ consists of positive undirected edges whose two endpoints lie in SS.

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 WuvW_{uv}, whereas the intermediary has off-diagonal weight ωuωvWuv/(dudv)\omega_u\omega_vW_{uv}/(d_ud_v). 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 rr selected vertices, WCW_C is the r×rr\times r diagonal coreset-weight matrix and [K]C[K]_C is the r×rr\times r principal submatrix of the full n×nn\times n kernel. Hence AC=WC[K]CWCA_C=W_C[K]_CW_C is also r×rr\times r.

The coefficient σ\sigma 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 pp and sample size independent of nn; Corollary B.6 provides a label-free spectral certificate; and Tables 7 and 8 distinguish successful real-graph parameter regimes from conservative sufficient conditions.

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

The paper proposes GCSC, a graph-based approach to accelerating spectral clustering without a kernel k-means intermediary. It combines degree-stratified vertex sampling, retention of high-weight edges with unchanged weights, spectral clustering on the reduced graph, and average-affinity label propagation. The paper provides conditional guarantees on full-graph NCut fidelity relative to a fixed reference partition and evaluates the method against existing coreset approaches on six benchmark datasets.

Critical strengths

GCSC constructs a reduced graph directly from the input graph, preserves the original weights of retained edges, and extends the resulting partition to the full vertex set via average-affinity assignment. The algorithm is simple and easy to implement. On Letters, MNIST, and Spambase, it achieves statistically significant ARI improvements over the strongest coreset baseline, providing evidence of its practical utility.

Critical weaknesses
  1. The theoretical analysis does not sufficiently connect the proposed construction to the quality of the resulting solution. The algorithm is not shown to satisfy the strong coreset guarantee in Definition 3.1; instead, the main result relies on coverage, spectral perturbation, clustering separation, and affinity-margin assumptions. The reported experimental diagnostics fail to satisfy a key sufficient condition, raising concerns about the applicability of the guarantee in practice.

  2. The experiments do not sufficiently establish the benefit of the proposed design choices over existing methods. Although GCSC improves ARI on some datasets, its overall running time is comparable to CSC. Consequently, the empirical results do not clearly establish an improved trade-off between clustering quality and computational cost.

Questions for authors

See Critical Weaknesses.

1 comment

Thanks for your review and suggestions.

W1(a) Connecting construction to the final solution

There are two concrete links. Deleted-degree fractions directly give uniform NCut control over all active partitions (Eq. (11)). For the actual spectral solver, coverage, spectral stability, tolerance-aware rounding, lifting, and full-graph objective stability form the proof chain for Theorem 5.7.

For example, Lemma 5.5 converts core-cell total-variation error θc\theta_c into lifting-score error at most ΩuHθc\Omega_u^H\theta_c. A sufficient reference margin then preserves the label, permitting core errors rather than assuming a correct final partition. New Proposition 5.8 and Appendix B.12 further verify the complete construction in a success regime with explicit dependence on pp.

W1(b) Empirical diagnostics and sufficient conditions

Failing a sufficient condition means that it cannot certify the configuration; it does not establish approximation failure. The revision examines both separately. In Table 8, the spectral condition holds in every m=1m=1 realization and on five of six datasets at m=2m=2.

For Waveform3 at m=5m=5, Table 7 still gives ARI-to-Full-SC 0.932. Independent confirmation achieves 0.926 and about 1.3% relative NCut difference after removing approximately 85% of sampled edges. Spambase, in contrast, needs a less restrictive existing setting, with Full-SC agreement recovering to 0.955 at common m=1m=1.

W2(a) Roles of the design choices

Tables 5, 6, and 9 separately test solving, lifting, sampling, and edge selection. The common-graph, common-objective comparison in Table 5 supports the spectral solve relative to cold kernel optimization. It addresses that optimization route, not superiority over CSC, which also uses a spectral solve.

Average affinity removes the multiplicative effect of representative counts. When minority cells retain one quarter of their representatives, it improves mean ARI-to-Full-SC over summation by 0.092; it also outperforms summation and nearest-representative lifting with actual spectral-core labels. We retain summation's better natural-sample result. The supported claim is robustness to representative imbalance, complemented by Lemma 5.5.

Stratification controls degree-range representation, while top-edge selection exactly maximizes retained weight at a fixed edge count. Table 9 distinguishes these structural purposes from clustering accuracy; retained-weight optimality is not recast as accuracy dominance on every graph.

W2(b) Quality and computational cost

Comparable total runtime does not rule out a quality–cost benefit. Both GCSC and CSC reduce the spectral problem to at most pp vertices; GCSC avoids kernel-centre distance estimation, importance weights, and reweighting. The common-budget comparison in Tables 1 and 4 shows quality improvements on four datasets, beyond merely counting fewer steps.

Figures 4 and 7 report original construction and total timings, with the direct implementation labelled GCSC-A and its attribution explained in Appendix C.1.

Reviewer_9fmzOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper develops a compressed-solve-lift pipeline (GCSC) that compresses a large graph, performs spectral clustering on the reduced graph, and lifts the labels back to the original graph. The new method is simpler than the previous CSC method because it avoids the kernel kk-means intermediary and preserves the original weights of retained edges. The paper establishes bounds on the error from edge selection and on full-graph NCut fidelity. It also conducts experiments comparing GCSC's performance with CSC, CoSC, and Cokkm.

Critical strengths

The paper proposes a simpler method for coreset spectral clustering that avoids the kernel kk-means intermediary and preserves the original weights of selected edges.

The paper establishes theoretical properties of the new method, including bounds on the error from edge selection and on full-graph NCut fidelity.

The paper includes numerical results comparing GCSC's performance with CSC, CoSC, and Cokkm. GCSC often shows better ARI performance. GCSC also has faster coreset construction on several datasets.

Critical weaknesses

Definition 3.1 in the problem formulation section describes a strong coreset guarantee (similar to Definition 4 in the reference CSC paper), but the proposed method does not seem to satisfy this property. The main guarantee of the proposed method is in Theorem 5.7. Putting a property that the method does not seem to satisfy in such a prominent place, instead of first summarizing the main property of the new method, makes the actual contribution less clear.

Theorem 5.7 involves a lot of notation, and the paper does not clearly explain what the theorem guarantees, what kinds of graphs satisfy its assumptions, whether those assumptions are tight, or how those assumptions compare with those in CSC. The theorem states that the result holds with probability at least 1−δcov−δcore−δmar1-\delta_{\rm cov}-\delta_{\rm core}-\delta_{\rm mar}, where δcore,δmar∈[0,1]\delta_{\rm core},\delta_{\rm mar}\in[0,1]. This does not seem sufficient. It is important to know how these terms decrease with the coreset size. The stated probability bound could even be zero.

For the graphs used in Figure 2, the number of edges in each graph is not reported. Figure 2 shows that, instead of approaching the ARI of full SC from below, GCSC's ARI on Letters exceeds that of full SC for coreset sizes above 750, even though the original graph has 20,000 vertices. This is confusing and may need further explanation. The performance of CoSC seems worse than that of the other methods on most datasets. Why does this happen?

Table 2 shows results for the unpruned sampled graph G[S]G[S]. Using this setting to isolate sampling and lifting from edge deletion is reasonable, but the default-pruned results in Appendix Table 6 would also be useful to see in the main text. Table 6 shows that, for Spambase, ARI-to-Full-SC is 0.9400.940 for G[S]G[S] but only 0.0490.049 for the default HH. This means the default edge-retention step can have a large effect on fidelity to Full SC. How should this be understood in relation to the theoretical results and the NCut results in Figure 3? This also raises the question of how to know whether the default edge budget is appropriate for a new large, dense graph. CoSC has NCut close to 0 on Spambase, USPS, and MNIST in Figure 3, which is confusing.

Questions for authors

See weaknesses.

2 comments

Thanks for your review.

W1 Strong definition and actual guarantee

The strong benchmark and the algorithm's reference-fidelity target must be distinguished, but this does not imply an absence of objective-level guarantees. The revision clarifies their relationship after Definition 3.1 and highlights in Eq. (11)

JGR(C)−kρH≤JH(C)≤JGR(C)1−ρH,J_{G_R}(C)-k\rho_H\le J_H(C)\le\frac{J_{G_R}(C)}{1-\rho_H},

simultaneously for every C∈Pk(VH)C\in\mathcal P_k(V_H). This requires no labels, eigengap, or rounding separation. Theorem 5.7 additionally analyzes the spectral solve and full-graph lift, while new Proposition 5.8 establishes a success regime with explicit sample complexity. We thus address the concern through the guarantees actually proved, without identifying the strong benchmark with the main theorem.

W2(a) What Theorem 5.7 guarantees

The theorem bounds the lifted solution's full-graph NCut relative to a fixed reference. Core-error volume and unreliable lifting are controlled by bHb_H and bLb_L, and the minimum reference-cell volume fraction by β\beta. The error in Eq. (19) decreases continuously with ρ=(bH+bL)/β\rho=(b_H+b_L)/\beta. Thus some incorrect core labels are permitted; perfect recovery is not required.

Taking the reference to be standard Full SC yields the guarantee relevant to our acceleration objective. Neither perfect external-class recovery on every graph nor convergence of external-label ARI to Full SC from below is required. Table 2 now directly reports same-graph partition agreement and objective differences.

W2(b) Success probability and coreset size

Coverage, core stability, and lifting correspond to different failure sources; their probabilities are not arbitrary constants. The coverage term explicitly depends on pp through the stratum sample sizes. New Proposition 5.8 provides a more direct sample-complexity statement.

For the disjoint union of k≥3k\ge3 balanced unweighted cliques, the original algorithm with m=1m=1, even 2k≤p≤n2k\le p\le n, its prescribed edge budget, and k-means++/Lloyd rounding recovers the Full-SC component partition with failure probability at most 2kexp⁡[−p/(2k2)]2k\exp[-p/(2k^2)]. Hence p≥2k2log⁡(2k/δ)p\ge2k^2\log(2k/\delta) is sufficient independently of nn on this class. Appendix B.12 verifies sampling, endpoint formation, rounding, and lifting, and gives a sharper probability bound. This neither adds a selection rule nor imposes the clique model on real benchmarks.

W2(c) Graph structure and tightness of the bounds

The general-graph sufficient bounds explain error propagation; they do not claim optimal constants. The revision separates directly verifiable results from conditional guarantees: Proposition 5.8 proves complete success on balanced separated cliques, while Corollary B.6 turns the spectral condition into a computable retained-graph certificate.

Tables 7 and 8 further relate certification to performance. Waveform3 maintains high Full-SC fidelity without satisfying the spectral sufficient condition, illustrating conservatism; Spambase recovers good results with a wider budget, showing that parameter regimes matter. Neither method-level failure from an unmet sufficient bound nor suitability of one budget for every graph follows from the theorem.

W2(d) Relationship to CSC's theory

The routes have different premises and targets. Kernel-intermediary methods use objective approximation for weighted kernel clustering; that property alone neither eliminates subsequent nonconvex optimization error nor guarantees higher output ARI. GCSC instead analyzes an original-weight subgraph and Full-SC fidelity after lifting.

Definitions 3.1 and 5.2 and Theorem 5.7 distinguish strong objective approximation, reference-solution approximation, and their conditions; Proposition 5.8 adds an explicit success regime. We do not rank theories with different premises as directly stronger or weaker. However, not using a kernel-coreset premise does not mean lacking coreset analysis. Tables 1 and 4 supply empirical evidence within the same coreset comparison scope.

W3(a) Input-graph edge counts

Table 3 now includes actual input-graph edge counts, counting each positive unordered pair once. For example, MNIST has 70,000 vertices and about 26.94 million edges, whereas the new p=3000p=3000 configuration solves its spectral problem on 3,000 endpoints.

Vertex compression and additional pruning are reported separately. Table 2 gives Full-SC fidelity for the common configuration; Section 6.4 and Appendix C.7 report Waveform3 retaining 90,000 of approximately 599,000 sampled edges and about 2,976 active endpoints. This distinguishes input size, spectral-problem size, and pruning, rather than equating the sample budget with the active count in every configuration.

W3(b) Why ARI can exceed Full SC

Full SC's ARI is not an upper bound on compressed methods. ARI measures external-label agreement, whereas spectral clustering uses a graph-objective relaxation and discrete rounding. Even on the same graph, similar NCut values can yield different ARI; an approximation can change the embedding and rounding in a way that better matches external labels.

Consequently, higher ARI on Letters is compatible with the approximation target and does not need a parameter-mismatch explanation. Figure 2 now shows Full SC on GCSC's input graph, and Table 2 reports both partition and objective fidelity. These same-graph quantities are the appropriate test, not an ARI ordering that theory does not require.

W3(c) Why CoSC is weaker and the independent evidence

Equivalence between kernel k-means and NCut objectives does not imply equally effective iterative optimization. A coreset guarantee controls objective representation error, not the difficulty of the subsequent nonconvex solve. This mechanism can explain weaker results without appealing to an unfair-setting explanation.

Independent support comes from CSC Section 6.2 and Appendix A, Figures 5–7: coreset kernel k-means similarly trails spectral coreset methods on PenDigits, Letters, and MNIST, with sparse-graph local-optimum difficulties discussed. Our main trend is consistent with these findings.

New Table 5 fixes the sampled graph and equivalent objective and changes only the solver. On Letters, MNIST, and PenDigits, the best cold kernel initialization gives mean NCut 22.34, 6.28, and 5.00, reduced to 10.76, 1.75, and 0.92 by spectral initialization. All six datasets show the same direction, and Proposition B.7 verifies the common partition ranking. This isolates optimization rather than reproducing the whole CoSC pipeline; Table 4 retains CoSC's competitive Waveform3 result.

W4(a) Unpruned versus restrictive-budget results

This identifies a parameter regime, not failure of the direct graph-coreset principle. Table 7 reports the complete sweep of the existing parameter mm: increasing mm also tightens the edge budget, so identical spectral fidelity should not be expected for every setting.

The new full quality curves use common m=1m=1 with the affinity settings selected at p=3000p=3000. On Spambase, ARI-to-Full-SC is 0.955, relative NCut difference is about −0.2%, and external-label ARI is 0.456 versus CSC's 0.396 (Tables 1 and 2). This uses the original formula without a new threshold. Waveform3 at m=5m=5 separately demonstrates genuine pruning.

W4(b) Assessing an edge budget on a new graph

New Corollary B.6: If the retained-graph gap gHg_H is positive, then

ρH<gH8+gH\rho_H<\frac{g_H}{8+g_H}

implies the original spectral condition ηH<gR/2\eta_H<g_R/2. It needs the retained gap and the degrees of HH and G[VH]G[V_H], not a full-graph eigendecomposition. It assesses existing configurations rather than adding an automatic tuning rule.

Failure of sufficiency does not imply approximation failure, as Waveform3 at m=5m=5 illustrates. Connectivity must also concern the actual endpoint graph: exactly kk components can have a well-defined kk-dimensional spectral structure. Global connectivity is not necessary for every spectral-clustering problem.

W4(c) CoSC's near-zero NCut

NCut measures cuts in the input graph, whereas ARI measures external-label agreement; lower NCut alone does not imply better semantic clustering. We checked and corrected the original plot's row indexing. Figure 3 now consistently uses each method's affinity setting selected once at p=3000p=3000 and then fixed. CoSC's corresponding NCut values on Spambase, USPS, and MNIST are approximately 0.66, 6.37, and 0.30, not uniformly near zero.

Figure 3 describes objectives on the respective selected graphs rather than ranking different graph objectives as one. Compression fidelity is evaluated by the same-graph Full-SC comparison in Table 2. This preserves the shared selection rule while distinguishing objective values from external-label performance.

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

This paper considers coreset spectral clustering, in which the objective is to extract a small (reweighted) subgraph of a graph, apply spectral clustering to the subgraph, and then propogate the labels to the rest of the original graph.

Previous work on coreset spectral clustering has exploited the correspondence between the kernel k-means objective and the normalised cut objective of spectral clustering and has used the (implicit) embedding of the graph vertices into kernel space in order to construct the coreset.

This paper proposes to instead construct the coreset by random sampling of the graph vertices, which avoids the need for the kernel-space representation of the graph.

Critical strengths

The proposed graph clustering algorithm appears to have good performance in practice. I think the primary strength of this paper is as an empirical result demonstrating that random sampling of graph vertices can reduce the computational cost of spectral clustering while retaining its empirical performance.

Critical weaknesses

This paper is very difficult to read. There is a lot of unnecessary notation which makes the theoretical claims very difficult to parse. The paper has very little in the way of high-level intuition given and so I could not follow the theory.

I recommend that the notation in the main part of the paper be significantly simplified, with all key definitions being given in the preliminaries. Then, the theoretical claims should be presented as simply as possible.

Definition 3.1 proposes a notion to measure the quality of a graph coreset, which has similarities to existing notions of graph sparsification and coarsening. However, the rest of the theoretical results do not relate the performance of the proposed algorithm back to this definition.

Questions for authors
  • Could you provide some high-level human-written intuition of what are the key theoretical properties of the proposed algorithm? Then, could you indicate where in the paper those properties are established?
  • Do you view this paper as a primarily theoretical or empirical result? It seems to me that its strength may be in the practical performance of the algorithm rather than the theory. If you agree, I recommend that you focus on this for the next iteration of the paper, expanding the experiments to demonstrate the practical value of the proposed algorithm. It is true that the proposed algorithm is simpler than CSC and so if it is consistently as effective in practice then that is a strength.
3 comments

Thanks for your review.

  1. W1 and Q1 Theoretical intuition and main conclusions

The analysis explains fidelity to Full SC, not perfect recovery of external classes after compression. Structurally, Proposition 5.1 establishes fixed-budget retained-weight optimality, Proposition B.2 analyzes actual endpoint coverage, and Proposition B.4 controls NCut simultaneously over all active-set partitions. The last result requires neither an eigengap nor rounding separation and is now highlighted in main-text Eq. (11).

For the solver, Lemmas 5.3–5.6 and Proposition B.5 connect deletion error, error-tolerant core clustering, and average-affinity lifting to the full-graph bound in Theorem 5.7. New Proposition 5.8 additionally gives a success probability explicitly dependent on sample size. Section 5 now introduces this progression through retention, solving, and lifting before the detailed analysis.

  1. Three objects must be distinguished: the sampled vertices SS, the graph HH formed by retained top edges and their endpoints, and the induced graph GR=G[VH]G_R=G[V_H] on those same endpoints. The algorithm solves on HH; comparing HH with GRG_R isolates deletion error without conflating it with a change of vertex set.

Sections 4 and 5.2 collect these definitions. Here ρH\rho_H is the maximum deleted-degree fraction, ηH=∥LH−LR∥2\eta_H=\|L_H-L_R\|_2 is spectral perturbation, and gR=λk+1(LR)−λk(LR)g_R=\lambda_{k+1}(L_R)-\lambda_k(L_R) is the relevant eigengap. These are analytical quantities, not additional tuning parameters. Appendix A also provides a concrete endpoint-subgraph example.

  1. W3 Definition 3.1 and the distinction from sparsification

Definition 3.1 is a strong benchmark without a particular-cut assumption; it does not assume that a chosen cut is preserved. The algorithm's end-to-end target is instead the reference-relative solution coreset in Definition 5.2: approximating standard spectral clustering after compression. The revision distinguishes these targets explicitly.

This distinction does not leave the method without graph-objective guarantees. Equation (11) holds simultaneously over all partitions of the actual endpoint set, and Theorem 5.7 controls the lifted full-graph NCut. Unlike vertex-preserving spectral sparsification or vertex-aggregating coarsening, GCSC uses an original-weight endpoint subgraph with solving and lifting. Proposition B.1 separately explains the solve-transfer consequence of the strong benchmark.

  1. Q2 Theoretical contribution and practical value

Removing the kernel intermediary has analytical as well as computational consequences: retained weights, endpoint coverage, deletion error, and lifting can be studied in one graph-domain framework. The new explicit probability result also goes beyond conditioning on an ultimately successful output.

Figures 2, 3, and 6 give complete budget curves for the common m=1m=1 configuration. At p=3000p=3000, GCSC improves ARI over CSC by 0.022, 0.062, 0.028, and 0.060 on Letters, MNIST, PenDigits, and Spambase, respectively (Tables 1 and 4). All four improvements remain significant after Holm correction across the 18 dataset–baseline comparisons; USPS and Waveform3 are close to the strongest baseline. These results complement the graph-domain analysis.

Thank you for your response to my questions, although I do not feel that my questions have been answered.

In particular, I cannot follow the intuitive properties presented. In particular, there are several phrases used without clear definitions or relationship to the theory. For example, what do the following phrases mean?

  • "fixed-budget retained-weight optimality" - What is the budget? Which weights are retained? What is optimal?
  • what is "endpoint coverage"?
  • What is an "active-set partition"?
  • What is "rounding separation"?

The new introductory paragraph to Section 5 has several similar examples.

I encourage the authors to consider substantially re-writing the paper without relying on generative AI which I suspect has been used heavily in the current version. Undefined phrases such as the above is a common feature of AI generated technical writing which makes it very difficult for a human to understand.

Thank you very much for your suggestion. We used AI solely for the purpose of refining the grammar of our manuscript, and in the process, some specific phrases were incorporated. We will withdraw the paper and revise the sections that were edited in this manner.

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

Related papers

Discussion (0)

Sign in to comment.