acceptodds
Withdrawn from ICLR 2027

A Projective Theory of Local Stability for Generalized Spectral Clustering

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

Abstract

Generalized Spectral Clustering (GSC) on directed graphs depends on a tunable vertex measure, but it is unclear when changing this measure can change the resulting partition. We show that a naïve perturbation analysis can be misleading: positive rescaling of the measure rescales the GSC Laplacian but leaves its eigenspaces (and, whenever the bottom-k target is well defined, the clustering) unchanged. We therefore study stability after quotienting out this irrelevant scale. Before measuring stability, we check whether the target bottom-k eigenspace is uniquely defined, and give a cheap, linear-time structural test that detects an important class of non-identifiable cases. When the target is identifiable, we derive a local anchored-rounding stability radius that factors into three interpretable terms: how strongly the measure moves the operator, how well the target eigenspace is spectrally isolated, and how robust the embedding is to rounding. Local certificates then compose through continuation. Experiments on directed graphs show that removing scale changes the inferred stability by an order of magnitude, that clustering quality and stability need not coincide, that the radius tracks directly verified finite perturbations, and that local certificates compose through continuation into reachable regions more than 58× larger.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
generalized spectral clustering, spectral clustering, directed graphs, stability analysis, perturbation theory, eigenspace identifiability, gauge invariance, learning on graphs

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_KFpVOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the local stability of generalized spectral clustering (GSC), building on the framework of Sevi et al. (2026), in which a tunable vertex measure ν\nu determines a family of graph Laplacians. Since multiplying ν\nu by a positive scalar rescales the Laplacian without changing its eigenspaces, the paper removes this irrelevant scale by analyzing the normalized operator Lπ=Lν/(1⊤ν)L^\pi=L_\nu/(\mathbf1^\top\nu).

The analysis has two main stages. First, a linear-time structural test detects a class of cases where the bottom-kk eigenspace is not uniquely defined, followed by a numerical spectral-resolution check. Passing these checks is not itself a proof of exact identifiability. Second, under a positive eigengap and rounding margin, Theorem 1 gives a sufficient operator-perturbation condition for preserving a reference partition under anchored rounding. The authors derive an associated first-order stability scale, decomposed into operator response, spectral separation, and embedding geometry, and show how individually verified steps can be composed through continuation.

Critical strengths
  1. The paper addresses a natural question about the sensitivity of a parameterized clustering method.

  2. I think Theorem 1 is potentially interesting as a sufficient condition for evaluating the stability of a spectral clustering algorithm.

Critical weaknesses
  1. I am not yet convinced that the paper adequately motivates why this particular generalization of spectral clustering (GCS) from Sevi et al. (2026) deserves a dedicated stability theory. In particular, it does not explain clearly enough what practical problem this GCS solves, when users should prefer GSC to other spectral-clustering variants, or how a stability certificate would guide their decisions.

  2. The exposition is difficult to follow, especially before the formal setup. The introduction introduces substantial notation and terminology before establishing the basic algorithmic picture. For example, ϑ\vartheta appears in the measure-to-partition map at manuscript line 47 before being explicitly identified as (t,α)(t,\alpha) in the prose. Similarly, νt,α\nu_{t,\alpha} appears in the scale discussion at line 61, while its construction is deferred to Section 2. The Contributions section reads more like a list of technical components and a workflow than an explanation of the scientific contribution.

  3. The main technical novelty is unclear. Theorem 1 appears to follow from a relatively direct combination of Davis–Kahan perturbation theory, Procrustes alignment, and a nearest-centroid margin argument. The paper itself acknowledges that these are standard ingredients.

Questions for authors

NA.

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

This paper investigates the stability of generalized spectral clustering (GSC) on directed graphs under changes to the vertex measure. By exploiting the scale invariance of the associated eigenspaces, the authors formulate a projective Laplacian and introduce a structural test for non-identifiable bottom-k eigenspaces. They then derive a sufficient partition-preservation condition for anchored rounding and a factorized first-order stability radius involving operator sensitivity, spectral separation, and embedding geometry. A continuation procedure composes directly verified finite steps. Experiments on directed graph benchmarks and synthetic models demonstrate the impact of projective normalization, the distinction between clustering quality and stability, and the potential benefits of continuation.

Critical strengths
  1. A well-motivated formulation of the stability problem. Separating irrelevant positive scaling from genuine changes in the operator is conceptually appropriate for the measure-parameterized GSC family. The zero-incoming-vertex test also provides an inexpensive and rigorous sufficient condition for non-identifiability before numerical perturbation analysis. Together, these steps clarify when a stability certificate is meaningful (Sections 2–3.2; Proposition 1).
  2. A precise connection from operator perturbation to verifiable partition preservation. Theorem 1 explicitly links the eigengap and Voronoi margin to preservation under anchored rounding, while Corollary 1 distinguishes a first-order diagnostic from an actual finite-step guarantee. The continuation argument offers a coherent way to extend locally verified results. The manuscript also carefully acknowledges that these guarantees apply to anchored rounding rather than fresh k-means (Sections 3.3–3.5; Appendix A).
Critical weaknesses
  1. The main theoretical guarantee does not directly apply to the standard GSC clustering pipeline. Theorem 1 certifies nearest-reference-centroid rounding after Procrustes alignment, whereas the standard GSC pipeline independently reruns k-means. This distinction has substantial empirical consequences. Appendix E reports a 14.4% anchor–vertex disagreement rate on Email-EU-Core within the near-optimal-quality region. On Amazon Photo, 13 of 14 anchors in that region produce nonidentical full partitions under the two rounding rules, although the vertex-level disagreement is only 3.9%. Moreover, on the sampled grid, the anchored stability set contains only the reference anchor for both graphs. While the authors acknowledge this limitation, it substantially weakens the connection between the proposed certificates and the motivating question of when standard GSC partitions remain unchanged.
  2. The incremental theoretical novelty and empirical generality are not yet sufficiently compelling. Several ingredients of the framework, including positive-scale invariance, null directions induced by zero-incoming vertices, Davis–Kahan perturbation bounds, and centroid-margin rounding, are based on established mathematical tools. The contribution primarily lies in their integration for the GSC operator family. Although this integration is coherent, its broader significance remains insufficiently demonstrated. Only four real graphs receive a full Stage-2 evaluation, and the reported continuation gain of at least 58.6× is obtained from a single synthetic DiSBM trajectory that terminates at the 80-step cap rather than a certified stability boundary. Furthermore, the quality-conditioned reference anchor is selected using ground-truth AMI, making the reported selection procedure unsuitable for direct unsupervised deployment. Stronger evidence of practical benefit and generalizability is needed (Sections 4–5; Appendices D, E, and K).
Questions for authors
  1. Connection to standard k-means. Can the authors report the number and extent of nonzero directly verified steps on each real Stage-2 graph, together with their agreement with freshly rerun k-means? In particular, what practical conclusions can be drawn from a valid anchored-rounding certificate when fresh k-means differs materially, as observed on Email-EU-Core?
  2. Unsupervised anchor selection. Can the quality-conditioned reference anchor be selected without access to ground-truth labels while maintaining a useful quality–stability trade-off? A comparison with fully unsupervised reference-selection baselines would materially improve the practical relevance of the approach.
  3. Generality of continuation. How robust is the reported continuation gain across multiple random seeds, other real or synthetic graph families, and different choices of the safety factor and step cap? Reporting reachable intervals and computational costs, rather than only the multiplicative improvement on a single synthetic trajectory, would strengthen the evidence.
Reviewer_pJakOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper develops some stability theory for generalized spectral clustering (in the sense of Sevi et al) and conduct empirical experiments.

Critical strengths

None.

Critical weaknesses
  • readability: the paper did not strictly follow ICLR formatting (e.g. all headings/subheadings where not bolded etc). The text in figure 1 is too small to be legible. The terminology used are nonstandard in the literature and they were used in the article without sufficient elaboration or clarity, which makes reading extremely difficult...for example "Which changes of ν are meaningful, which can move the partition, and which are pure gauge?" (what is "gauge"? this is not standard terminology in spectral graph theory etc). "A projective stability theory with a three-factor radius. " "A zero-incoming null-mode proposition" . I suggest taking a serious pass to remove all this confusing language.

  • Relevance: The premise of the paper is based on a stability/perturbation analysis of Generalized Spectral Clustering (GSC) by Sevi et al, which, at the time of review, is a very recent (2026) preprint and has a citation of 2. This in itself is not a problem, but the authors cannot expect a general audience to immediately know what GSC is. The current manuscript did not sufficiently articulate why GSC is relevant/important/worthwhile to study (as supposed to competing/more established approaches to spectral clustering/directed graphs), nor did it give sufficient background to set up the machinery used. In contrast, GSC was mentioned at the beginning of the abstract and introduction immediately. It is unclear to me that the current exposition is sufficiently convincing to meet the importance/relevance bar of ICLR.

Questions for authors
  • Can you clarify/define mathematically what exactly a gauge is in the context of this paper?
  • Can you clarify why GSC is important for a dedicated theoretical study, as supposed to more established approaches/competitors?

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

Related papers

Discussion (0)

Sign in to comment.