acceptodds
Withdrawn from ICLR 2027

Beyond Bottom-k: Structural Nullspaces in Spectral Clustering of Sparse Heterogeneous Graphs

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

Abstract

Spectral clustering is often reported to underperform on sparse heterogeneous graphs, motivating increasingly sophisticated spectral operators. We show that on several standard benchmarks the classical Laplacian is not the main obstacle: literal bottom-k selects structural zero modes created by disconnected components before it reaches the nonzero low-frequency spectrum. We prove that when these zero modes fill the k-dimensional embedding and the evaluated vertices lie in one component, row normalization collapses the representation and removes all within-component geometry available to k-means. We also quantify the partial-distortion regime below capacity. This suggests a minimal correction: skip the structurally known zero modes and use the first k nonzero eigenvectors, leaving the graph, Laplacian, normalization, and clustering algorithm unchanged. Across the sparse benchmarks we study, this corrected classical baseline reaches the highest mean AMI (0.62) in a strictly protocol-matched comparison against the sophisticated operators proposed for this regime (regularized spectral clustering, Bethe–Hessian, and Di-SIM). Because the nullspace is known from connected components, the correction can also be implemented directly in a sparse eigensolver without computing the discarded modes. Our results suggest that spectral benchmarks should verify which part of the spectrum a baseline actually extracts before attributing performance gains to a better operator.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
spectral clustering, graph Laplacian, structural nullspace, connected components, sparse heterogeneous graphs, kernel-aware embedding, spectral graph theory, benchmark reassessment

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_tDUGOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper points out that when applying spectral clustering to sparse graphs or graphs with multiple connected components, selecting the bottom-kk eigenvectors, if taken literally, may result in all of them falling into the structural null space (i.e., the indicator vectors of the connected components). This leads to a collapse of the embedding after row normalization, rendering the clustering ineffective. The authors characterize the precise correspondence between the null space and the connected components in Theorem 1, prove total collapse in the "saturated" case in Proposition 2, and describe partial distortion in the "below-capacity" case using a "null-occupancy" parameter, η\eta. To address this, the paper proposes a minimal correction, K0K_0: skipping the d0d_0 structural null modes and instead selecting the first kk non-zero modes. Furthermore, it introduces a constrained/shifted sparse eigensolver to avoid the explicit computation of the null space.

Critical strengths
  1. The paper precisely pinpoints the cause of "bottom-kk" failures to the structural null space. By linking mechanisms such as connected components, row-normalization collapse, and null occupancy, it transforms what might otherwise be a vague empirical phenomenon into a well-defined problem.

  2. Simply modifying feature indices allows for the recovery of AMI scores, from a state of degradation to a range of 0.5–0.84, on datasets such as Cora, Citeseer, and PolBlogs. The approach is straightforward to implement and compatible with sparse solvers.

  3. The paper includes extensive appendices, scripts, threshold audits, and multi-graph evaluations, all of which bolster the credibility of the core diagnosis.

Critical weaknesses
  1. The fact that connected components determine the null space is a classic result in spectral graph theory; K0K_0 is essentially an index adjustment, like implementation techniques used in LCC (Largest Connected Component) preprocessing or regularized spectral clustering. The paper is more of a diagnostic benchmark than a proposal for a new clustering method or theory.

  2. The empirical evidence is insufficient to support broad conclusions, the primary results are based on only six graphs, with the core of the four above-capacity graphs residing within a single connected component. Furthermore, the baseline comparisons suffer from issues such as inconsistent protocols, the use of only a single seed, and inadequate hyperparameter tuning. Additionally, K2/S3K_2/S_3 relies on a supervised parameter β⋆\beta^\star, which undermines the authors' claim of narrowing the performance gap between simple and complex methods.

  3. The theoretical bounds and empirical predictive power are limited. Proposition 3 provides a bound only when η\eta is close to 1, failing to predict whether K0K_0 is beneficial in the below-capacity regime. Moreover, the correlation between η\eta and Δ\DeltaAMI is based on just seven seeds; the authors themselves acknowledge that it does not serve as a general-purpose quantitative predictor.

Questions for authors
  1. Under strictly identical experimental settings—including the same hyperparameter tuning, the same set of random seeds, and the same core-restricted constraints—does the advantage of K0K_0 over LCC-based preprocessing, regularized spectral clustering (SC), and the Bethe-Hessian approach still hold?

  2. Could the choice of primary benchmarks lead to an overestimation of performance in the "above-capacity" regime? Is it possible to report the full distributions of d0/kd_0/k, η\eta, and the performance gains of K_0 across graphs with multi-component cores or a broader range of ground-truth labels?

  3. Do the conclusions regarding K_2/S_3 change if the supervised parameter β⋆\beta^\star is removed? Does the core thesis of the paper rely exclusively on the unsupervised K_0 metric?

  4. Are the end-to-end gains provided by the scalable solver significant enough to constitute an independent contribution? Specifically, how does it compare to simple LCC or regularization-based methods in terms of the trade-off between clustering quality and total runtime?

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

The paper identifies the cause of the underperformance of the bottom-kk spectral clustering approach for embedding sparse heterogeneous graphs. Because bottom-kk uses eigenvectors corresponding to zero eigenvalues, which are associated with connected components, the embedding collapses or contributes less to the geometry. The paper proves this analytically by showing, under two conditions, that when kk is less than the number of zero eigenvalues, the embedding is constrained, and when kk is greater than the number of zero eigenvalues, the embedding is less affected. It also quantifies how much the zero eigenvalues contribute to the embedding in which both zero and nonzero eigenvalues are present. The authors show that the null space can be derived from the graph topology and that one can choose the non-zero eigenvalues for clustering.

Critical strengths

The paper's main contribution is identifying the cause of failure in the bottom-kk clustering approach and proposing a method to select kk that improves the results. The second contribution is the analytical proofs provided by the authors supporting the claims, along with empirical results demonstrating the improvement. The third contribution is the computational efficiency of the proposed approach, since the structural nullspace can be skipped computationally.

Critical weaknesses
  1. The paper in general addresses a subset of the problem of spectral clustering for heterogeneous graphs. It is unclear whether selecting the kk smallest nonzero eigenvalues would generalize the results.

  2. The authors proposed skipping the eigenvectors corresponding to zero eigenvalues and keeping the nonzero ones. It is unclear how this will affect disconnected graphs, since the nonzero eigenvectors are specific to their respective connected components and zero elsewhere. This will cause overlap near the origin.

  3. The authors provided a comparison with a limited number of baseline graphs. They should compare it with more baselines to strengthen their claim.

  4. The literature review is fair but does not position the paper relative to the state of the art. This makes it difficult to assess the paper's novelty.

  5. The paper’s write-up is not clear enough to follow. Many variables are not defined at their first occurrences, and abbreviations are not defined when used for the first time. This makes it challenging to evaluate.

Questions for authors
  1. Could the authors explain more clearly which types of graphs the approach is more efficient for?
  2. The authors suggested skipping the eigenvectors corresponding to zero eigenvalues and keeping the nonzero ones. How does this affect disconnected graphs? Since the nonzero eigenvectors are specific to each connected component and zero for others, different components will overlap near the origin.
Reviewer_sXL6OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper makes a simple point: for spectral clustering, instead of employing the k eigenvectors corresponding to the smallest k eigenvalues of a normalized graph Laplacian, use the k eigenvectors corresponding to the smallest k NON-ZERO eigenvalues.

Critical strengths
  1. The paper makes a clear and succinct point about improving the spectral clustering performance simply by employing the k eigenvectors corresponding the smallest k non-zero eigeanvlues of the normalized graph Laplacian matrix, while keeping every other components in the algorithm the same.
Critical weaknesses
  1. The contribution is incremental and hardly groundbreaking. It's more an astute observation than any fundamental contribution to the field of spectral clustering.

  2. I don't undertand how this topic is suitable for a machine learning conference. Spectral clustering would belong to a pure theoretical algorithm conference.

Questions for authors
  1. How is the contribution non-trivial in the field of graph theory? This is just an admitted astute observation that one should employ the k eigenvectors corresponding to the k smallest non-zero eigenvalues instead of the first k eigenvalues.

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

Related papers

Discussion (0)

Sign in to comment.