acceptodds
Under review as a conference paper at ICLR 2027

Mass-Aware Spectral Clustering on Adaptive Supernodes

Abstract

Spectral clustering can recover clusters of arbitrary shape, but only from the graph it is given, and graphs built from local affinities or compact representatives poorly describe extended clusters with unequal sample support. Density peaks provide complementary cues about which regions are well supported and well separated, but local prominence alone does not determine which regions share a label. We treat these cues as evidence for graph construction rather than as clustering decisions. The result is mass-aware spectral clustering (MASC) on adaptive supernodes: hierarchical grouping forms supernodes that follow the manifold structure and remain linked where they touch. Each nonroot supernode connects to its nearest predecessor in the mass order, forming a sparse peak-affinity tree whose weights are the reciprocal of mass times separation, so that heavy, prominent groups can be cut at low cost. A mass-normalized spectral objective then determines memberships jointly, and mass-weighted rounding propagates the same sample counts to the final labels. We prove that the reduced problem is exactly RatioCut on a lifted sample-level graph over supernode-respecting partitions and derive a boundary perturbation bound whose boundary-to-gap ratio predicts spectral stability. MASC tunes a single resolution parameter besides the cluster count and requires no kernel bandwidth or neighborhood size, and the eigenproblem scales with the number of supernodes rather than the number of samples. On real datasets, MASC attains the highest ACC and NMI against density-peak and spectral baselines, with average gains of 9.11/4.17 points over the best density-peak baseline and 9.62/5.79 over the best spectral baseline on each dataset.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Clustering, Spectral clustering, Density peak clustering, Multi-view clustering

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_YHgUOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes Mass-Aware Spectral-Clustering (MASC), a three-step clustering algorithm. The method rely on the notion of "supernode", which are groups of nodes that are formed using a single-linkage hierarchy. These supernodes are then ordered in a tree strucutre on which spectral clustering is applied. On the theory side, the autors show that this reduced problem is exactly a RatioCut on a sample-level graph, and they give a Davis-Kahan bound on the stability of the embedding. Experimentally, MASC reaches the best ACC and NMI on the showcased dataset.

Critical strengths

Overall I like the simplicity of the appraoch. Once the supernodes are built, the graph to cut is just a tree, which is cheap to cluster. The method is light on hyper-parameters, besides the number of clusters KK, the only parameter is λ\lambda, and it seems that there is no kernel bandwidth or neighbourhood size to tune, which is often a painful part in traditional spectral clustering. Moreover, the method is well-motivated, and bridging density-based and spectral clustering is an interesting and challenging problem.

Critical weaknesses

I would say that there are still a few weaknesses in the paper that would need a treatment.

  • The paper says λ\lambda is searched over {0.05,…,1.00}\{0.05, \dots, 1.00\}, but I couldn't find how the reported value is chosen. If it is the value that maximises ACC against the ground-truth labels, this should be stated carefully, as this could be an important factor in the method's performance in the experimental result. Fig 4a is reassuring on this aspect as it would seem that the selection of λ\lambda is stable, but this is shown only for five datasets. Results at a fixed λ\lambda on all datasets would make the comparison more convincing, alternatively, having a way to select λ\lambda without using the labels would also be interesting to have.
  • The contribution of each stage doesn't seem so clear to me. The supernodes come from CHC, but CHC itself doesn't appear in the comparison table. Without it, it is hard to tell how much of the performance comes from the tree and the spectral step, and how much is already achieved by the proper hierarchy. Related methods such as FINCH or DBSCAN would also be natural baselines.
  • One of the main weakness of the paper to me is the clarity. I found the paper hard to follow. The text relies a lot on abstract phrasing and new vocabulary, sometimes before it is properly defined. For example: "The saliency γi\gamma_i, the product of mass and separation by which DPC selects centers, serves here as evidence." A figure showing the full pipeline would help a lot. The notations could also be lighter. The same edge weight appears as Wi,p(i)W_{i,p(i)}, aia_i, aea_e and se=1/aes_e = 1/a_e. The level index hh in νh(A)\nu_h(A) is only introduced implicitly, dd is used both for the dimension and for the dissimilarity and mhm_h and mem_e introduce confusion.
Questions for authors
  1. How is the reported λ\lambda selected? Does the selection use the ground-truth labels?
  2. The peak-affinity graph is a tree, so a KK-way partition into connected parts amounts to deleting K−1K-1 edges. How does the spectral relaxation compare with simpler tree cuts, for instance removing the K−1K-1 edges with the largest saliency, or solving the objective exactly when MM is small?
  3. What is the value of MM in each datasets ? How does it compare to KK? How well does CHC alone perform?
Reviewer_4vaQOpenReview ↗
Rating
4(+1)
Confidence
4(+1)
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes MASC, which combines adaptive supernodes with mass-based spectral partitioning to handle complex cluster structures within a simple framework. I find the core idea interesting, particularly the connection between structural heuristics and spectral theory. Its approach to graph representation also offers a perspective that may be useful beyond clustering. The theoretical analysis and experiments provide support for the method. Overall, I am positive about the paper.

Critical strengths
  1. The central idea is simple and offers a fresh way to connect structural representation with global clustering. Adaptive supernodes organize the data structure, while mass-based spectral partitioning determines cluster memberships jointly. The resulting method is easy to follow and uses only one resolution parameter beyond the number of clusters.
  2. The paper brings structural heuristics into a spectral framework and provides a theoretical account of their relationship to graph partitioning and spectral stability. I appreciate this connection between intuitive design rules and formal analysis. It could motivate further work in spectral graph theory on graphs constructed using similar structural principles.
  3. The paper’s perspective on representing complex clusters in a spectral graph is potentially useful beyond this particular algorithm. Organizing the data into adaptive supernodes provides a way to retain complex structural information for subsequent inference. I see potential for this perspective to inform node construction and structural modeling in graph representation learning.
  4. MASC achieves the highest reported ACC and NMI among the evaluated methods on all ten real datasets in Table 1, with substantial gains on several datasets. The synthetic experiments and grouping controls provide additional support for the central ideas, making the empirical results a clear strength of the paper.
Critical weaknesses
  1. The resolution analysis is helpful, but the guidance on choosing the parameter for a new dataset could be more direct. A recommended starting value or a simple selection principle would make the method easier to use.
  2. Some experimental settings for both MASC and the baselines could be summarized more clearly in one place, particularly the preprocessing approaches used for the real datasets. A compact table of these settings would make the experiments easier to reproduce.
  3. The stability experiment usefully complements the theoretical analysis, although its construction is described briefly. Explaining the experimental design and the scenarios represented by the different settings in Fig. 4c-e would help readers interpret the results.
Questions for authors
  1. How was the resolution parameter selected for Table 1? Can this parameter be determined automatically? Would the authors recommend 0.45 as a starting value for a new dataset?
  2. Which preprocessing approaches were used for the image and tabular datasets?
  3. Could the authors explain the design of the stability experiment and the main conclusions that each set of controls is intended to assess?
  4. How do the authors view the potential applications of this graph representation approach to graph representation learning?
Reviewer_JkpcOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes Mass-Aware Spectral Clustering, which combines adaptive supernode construction with a mass-aware graph partitioning procedure. Adjacency-constrained hierarchical clustering groups samples using minimum-pair distances. The resulting supernodes are ordered by sample mass and connected to their nearest predecessors, producing a sparse tree whose affinities are inversely proportional to mass-times-separation saliency. Finally, the spectral clustering algorithm determines the final partition.

Critical strengths

The paper introduces a mass-aware affinity construction on hierarchically formed supernodes for clustering extended structures with unequal sample support. By combining minimum-pair separation with supernode mass, the method incorporates both geometric information and sample support into the graph. This provides a way to represent noncompact clusters that may be poorly captured by centroid-based or equally weighted representative graphs.

Critical weaknesses
  1. The distinction from granular-ball-based spectral clustering is insufficiently established. Existing methods, such as An Efficient Spectral Clustering Algorithm Based on Granular-Ball, already construct reduced similarity representations using groups of samples. The paper should more clearly explain how its adaptive supernodes, affinity construction, and mass-aware objective differ from these approaches, and provide direct comparisons to establish the methodological and empirical advantages.

  2. The justification for handling extended clusters with unequal sample support remains incomplete. This paper does not sufficiently establish why hierarchical grouping and mass-dependent affinities address these challenges.

Questions for authors
  1. What are the key methodological differences between MASC and granular-ball-based spectral clustering, particularly in group construction, affinity design, and the treatment of sample mass? Which limitations of these methods does MASC specifically address?

  2. Can you provide direct comparisons with granular-ball-based spectral clustering? Replacing the proposed supernodes with granular balls while retaining the same downstream affinity and spectral procedures, preferably at matched group counts, would help isolate the contribution of the representation.

  3. Under what structural conditions does the proposed hierarchical grouping preserve extended clusters without irreversibly merging samples from different classes? How does the minimum-pair contact rule distinguish meaningful within-cluster connectivity from accidental cross-cluster proximity?

  4. Why is the reciprocal affinity 1/(qiδi)1/(q_i\delta_i) appropriate for unequal sample support? Can separate ablations of mass-dependent affinities, mass normalization, and weighted rounding establish how each component contributes to handling this challenge?

  5. How does the proposed graph construction produce the favorable boundary-to-gap conditions required by Theorem 3? Can you evaluate this relationship on the constructed graphs under controlled variations in cluster shape and sample support, beyond the existing experiments on controlled tree graphs?

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

This paper proposes MASC, which combines adaptive supernodes, quality-weighted graphs, and spectral clustering, along with a graph-cut equivalence and stability analysis. This work is compared against 10 baselines on 10 datasets and get solid clustering results.

Critical strengths
  1. Combining supernodes with quality information to improve spectral clustering is practically useful.
  2. The results are clear, and there's solid ablation and theory work.
Critical weaknesses

The core contribution isn't clear enough. The method basically combines existing hierarchical clustering, density peaks, and weighted graph cuts, but there's no experiment that directly isolates what quality weighting adds on its own. Scalability and parameter selection are also underdeveloped. The exact algorithm still needs quadratic complexity, and there's no clear unsupervised way to pick parameters.

Questions for authors
  1. Compared with existing CHC, density peaks, and weighted RatioCut, what does this paper add that you can't get elsewhere?
  2. Can you fix the supernodes and graph structure, then drop quality-weighted edge weights, quality normalization, and weighted rounding one at a time to see how much each actually contributes?
  3. Proving RatioCut equivalence on an artificial expanded graph so what does that actually guarantee on the original sample graph?
  4. Without true labels, how do you pick λ? Does Table 1 use a fixed λ, or tune it per dataset?
  5. The exact version still costs O(n²d) so how does that back up the scalability claim? Does the runtime include all the distance computations?
  6. Why doesn't Table 1 report std over independent random seeds? Can those ACC numbers, some as high as 100%, be reproduced with independent repeated runs?

I'm willing to raise my rating if the authors address my concerns above.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.