Pith. sign in

REVIEW 3 major objections 6 minor 77 references

Revisiting Degree-Corrected Spectral Clustering: a Condition-Free Spectral Analysis and Extension

T0 review · 3 major / 6 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Degree-corrected spectral clustering now has a deterministic error bound: the number of misclustered nodes is controlled by degree heterogeneity and cluster weakness, with no random-graph model required.

desk verdict Real condition-free bound for DCSC, but the ASCENT proposition has a sign error in the main text and the empirical edge is tuned on the outcome metric. read the letter →

arxiv 2607.21435 v1 pith:K6JEOID3 submitted 2026-07-23 cs.SI

Wei Li , Xiaojian Li , Meng Qin , Chaorui Zhang , Weixi Zhang , Yiwen Zhong , Jianfeng Hou This is my paper
classification cs.SI MSC 05C5068R1062H30
keywords graphclusteringdegree-correctedspectraltheoryaverageconductancecondition-freeboundnode-wisecorrectionover-smoothingneuralnetworks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a deterministic, model-free error bound for degree-corrected spectral clustering: the number of nodes that the ISC method misclusters is at most a constant times K times a single spectral quantity, and that quantity grows with degree heterogeneity and shrinks with cluster strength. No stochastic block model or probabilistic side condition is needed. The same analysis extends to NJW, RSC, SCORE+, and to the paper's new algorithm ASCENT, which assigns each node its own degree correction by repeatedly averaging neighbor degrees. A reader should care because the bound converts a previously model-dependent guarantee into a purely spectral one and identifies node-wise corrections as a concrete lever for improving cluster quality.

What carries the argument

The load-bearing object is the regularized graph Laplacian D_τ^{-1/2} A D_τ^{-1/2} with degree-correction term τ, and the derived spectral quantity Ψ_ISC that combines degree heterogeneity (d_min/(d_max+τ)) and cluster weakness (1−λ_{K+2})^{-1}. The proof machinery is the classic spectral-embedding approximation: construct a matrix F of leading reweighted eigenvectors, compare it to the membership matrix G of the optimal conductance partition via an orthogonal alignment O, bound ||FO−G||_F (Theorem 4.1), then convert that into a clustering-cost bound using degree-weighted copies of each node, and finally into a misclustered-node count. The approximation-ratio α of K-means enters at the cost-

What would settle it

Run ISC on graphs with controlled degree heterogeneity and spectral gaps and compare true misclassification counts against the Theorem 4.5 bound; one instance with actual error above the bound refutes it. For the early-stage claim, fix ASCENT's hyperparameters on one set of benchmark graphs and evaluate on a held-out set; if the advantage disappears, the early-stopping conclusion is an artifact of tuning on the evaluation metric.

Watch

Extended reading notes

Core claim

The central result is Theorem 4.5. Given a graph G and a pre-set number of clusters K, let (Ŝ_1,...,Ŝ_K) be a partition achieving the minimal average conductance φ̄_K(G), and let (C_1,...,C_K) be the clustering produced by ISC — a degree-corrected spectral clustering method that uses the leading K+1 reweighted eigenvectors of the regularized Laplacian. If K-means has approximation ratio α, then the number of misclustered nodes is at most 160(1+α)(1+λ_1)^2 (μ_max/d_min) K Ψ_ISC, where Ψ_ISC = (1−λ_{K+2})^{-1}[1 − (d_min/(d_max+τ))(1−φ̄_K(G))]. The factor Ψ_ISC isolates two independent reasons a graph is hard to cluster: a small minimum-to-maximum degree ratio (degree heterogeneity) and a smal

Load-bearing premise

The empirical advantage of ASCENT rests on tuning its two hyperparameters with the same conductance metric used for evaluation, and the theoretical error bound becomes vacuous when the minimum degree d_min is small — either way, the practical guarantee is conditional.

Editorial extensions

If this is right

  • If the bound is correct, the quality of DCSC is predictable without fitting any generative model: two numbers, degree spread and spectral gap, certify an upper limit on misclassification.
  • The comparison framework gives a fair way to rank spectral methods: RSC can beat NJW when degree heterogeneity is high and the graph is not well-clustered; ISC always has a tighter bound than RSC with the same τ; ASCENT can beat ISC when its node-wise corrections align with communities.
  • ASCENT inherits the theoretical bound at essentially no extra cost — iterating the mean aggregator is O(|E|) per step — so the reported quality gains come with a matching analysis.
  • The bound is independent of the number of nodes N, so the error guarantee does not degrade as graphs scale to millions of nodes, unlike N-dependent probabilistic bounds.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The theoretical bound divides by d_min, so it is vacuous on graphs with isolated or near-isolated nodes; a natural extension is to normalize by something like the minimum cluster volume or to add a small universal regularization, which the paper does not address.
  • The paper's empirical claim that early stages before over-smoothing improve quality is untested against hyperparameters chosen on held-out data: θ and L are selected per dataset using the same average-conductance objective on which final quality is reported, so the measured advantage may shrink under a fully unsupervised protocol with a train/test split.
  • The same spectral-then-cost route is likely portable to other clustering objectives such as ratio cut or modularity, since the proof relies on conductance's relation to the normalized Laplacian; testing the bound on graphs with controlled degree distributions and spectral gaps would be a direct experimental check.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. This paper develops a deterministic, model-free analysis of degree-corrected spectral clustering (DCSC). It proves Theorem 4.5: for a graph G and a fixed number of clusters K, if (S_1,...,S_K) is the average-conductance-optimal partition and (C_1,...,C_K) is the clustering produced by ISC, then the number of misclustered nodes is at most 160(1+alpha)(1+lambda_1)^2 (mu_max/d_min) K Psi_ISC, with Psi_ISC = (1-lambda_{K+2})^{-1}[1 - (d_min/(d_max+tau))(1 - phi_bar_K(G))]. The proof is purely spectral and does not assume a stochastic block model or other generative model. The same framework is specialized to NJW, RSC, and SCORE+ in Table 4, and is extended to a new algorithm, ASCENT, which uses node-wise degree corrections iterated by a GNN mean aggregator. Experiments compare ASCENT with 13 baselines on synthetic and real graphs.

Significance. If proved, the ISC bound is a useful complement to SBM-based analyses: it is deterministic, applies to any graph, and explicitly exposes two interpretable degradation factors, degree heterogeneity (d_min/(d_max+tau)) and cluster-structure weakness (through 1-lambda_{K+2}), relative to the optimal average-conductance partition. The reduction of the bound to several spectral algorithms in Table 4 and the proposed ASCENT extension are natural and potentially of independent interest. The manuscript is transparent about the algorithmic steps and provides anonymous code. However, the ASCENT theorem as printed is inconsistent with its own proof in a load-bearing place, and the empirical validation is weakened by per-dataset tuning on the evaluation objective and the absence of variance reporting. The core ISC derivation appears sound, but the extension and the empirical claim require correction before the paper can be accepted.

major comments (3)
  1. [Section 5.2, Proposition 5.1 and Appendix E] Proposition 5.1 defines Psi_AST := (1+lambda_{K+2}^{AST})^{-1}[1 - (d_hat - phi_bar_K(G))], but Appendix E derives, via the same steps as Theorem 4.1, ||F_hat - G||_F^2 <= K(1 - lambda_{K+2})^{-1}[1 - (d_hat - phi_bar_K(G))], and the proof of Remark 5.2 also uses (1 - lambda_{AST}_{K+2})^{-1}. The two denominators cannot both be correct: since 1 - lambda_{K+2} is in (0,1) and 1 + lambda_{K+2} > 1, the printed formula is numerically tighter than the proof supports. Thus Proposition 5.1 as stated is unproved. This is not a local typo in isolation: the same denominator appears in the definition of Psi_AST and in the proof's final bound. Please correct the statement (or the proof) and re-check the derivation of Remark 5.2 under the corrected expression.
  2. [Theorem 4.5 and Table 4] The bound divides by d_min through mu_tilde := mu_max/d_min. For graphs with an isolated vertex, d_min = 0 and the bound is undefined; for graphs with very small minimum degree, the bound becomes disproportionately loose. The text after Theorem 4.5 claims the result does not rely on additional conditions; this is inaccurate without an explicit assumption d_min > 0. Please add the assumption and discuss the degenerate case. This does not invalidate the spectral argument itself, but it is a real input condition that should be stated.
  3. [Section 6.4, Table 10, and Section 6.2] ASCENT's hyperparameters theta and L are selected per dataset using the same unsupervised average-conductance objective on which the final quality is then reported. This is effectively test-set tuning: the advantage of ASCENT in Tables 7-8 may shrink for a user who must choose these parameters without access to the evaluation objective. In addition, Tables 7 and 8 report only means (over 100 generated graphs or 5 seeds) without standard deviations or significance tests. The empirical claim in the abstract that some early stages before over-smoothing 'can potentially result in better clustering quality' is therefore not yet established at the standard expected for a method comparison. Please provide a parameter-selection strategy that does not rely on the evaluation objective (e.g., fixed values, a validation split, or a separate model-selection criterion) and report variance or significa
minor comments (6)
  1. [Appendix C, proof of Lemma 4.4] The proof writes t != sigma(r) in two places where the context (and the rest of the proof) requires t != pi(r). This typo should be corrected.
  2. [Remark 4.6] The proof asserts 'Usually, lambda^{RSC}_{K+1} <= lambda^{NJW}_{K+1}' without proof or conditions. Since the comparison in this remark relies on this inequality, either prove it for the relevant Laplacians or state it explicitly as an assumption.
  3. [Section 4.1 and Section 5.2] The notation d_tilde is used in Section 4.1 for the ratio d_min/(d_max+tau), while Section 5.2 introduces d_hat as an average of such ratios. Rename one of them to avoid confusion.
  4. [Theorem 4.5 statement] The phrase 'where the optimal correspondence of C_r is S_hat_r' is imprecise because the optimal partition and the output partition have no intrinsic ordering. It should be clarified that one takes the best possible correspondence, or that the bound holds for the correspondence induced by the orthogonal transformation O in Theorem 4.1.
  5. [Figure 1] The color legend is not explained in the caption; it should state which colors correspond to which of the two karate-club clusters and how the normalized tau values are plotted.
  6. [Section 6.1] For the DGC baselines, the text says 'with the best quality metrics reported' when trying feature strategies. This is another form of test-set selection and should be disclosed or justified more carefully.

Circularity Check

1 steps flagged · score 2.0 of 10

Theoretical bound is self-contained; the only circular-adjacent element is empirical tuning of ASCENT's θ,L on the same conductance objective used for evaluation.

  1. fitted input called prediction [Section 6.4 (Table 10) and Section 6.1 'Evaluation Metrics']
    "We determined parameter settings of {θ,L} for ASCENT on all the datasets based on the unsupervised average conductance metric. ... Hyper-parameters of all the methods were tuned based on the unsupervised average conductance metric. ... For those without feasible ground-truth, we ... recorded the corresponding average conductance values."

    The same average-conductance objective is used both to select ASCENT's free parameters θ and L per dataset and to report ASCENT's clustering quality in Tables 7–8 (Cond rows). For the no-ground-truth datasets, the reported conductance improvement is therefore not an independent prediction: it is partly produced by the parameter search over that objective. The theoretical Theorem 4.5/Proposition 5.1 do not use these fitted values, so this is a mild empirical circularity, not a defect of the spectral derivation.

full rationale

The central theoretical derivation is self-contained. Theorem 4.1–4.5 and Appendices A–D bound ||FO−G||_F and then the mis-clustered node count using only eigen-decomposition identities of the regularized Laplacian and the definitions of Ψ_ISC, φ̄_K, d_min, d_max, and τ; no fitted parameter or external self-citation is reintroduced. Proposition 5.1/Appendix E applies the same proof scheme to ASCENT with cluster-wise corrections, but the main text's formula for Ψ_AST uses (1+λ_{K+2})^{-1} while Appendix E derives (1−λ_{K+2})^{-1}, an internal sign inconsistency that makes the printed ASCENT bound unproven; this is a correctness risk rather than circularity. Likewise, dividing by d_min without stating d_min>0 is an omitted degeneracy condition, not a circular step. The only circularity-adjacent element is empirical: ASCENT's θ and L are tuned on each dataset by the same average-conductance metric that is then reported as its quality advantage; this selection bias affects the empirical 'better clustering' claim but does not enter the theoretical bounds. Therefore the paper has no significant circularity beyond this minor empirical fit.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The theoretical bound uses no fitted constants: all quantities (λ, d_min/d_max, φ̄, μ_max) are graph-derived. The empirical performance claim depends on per-dataset hyperparameters θ,L and on the cited constant-factor KMeans approximation. No new physical or mathematical entity is postulated.

free parameters (3)
  • τ (degree-correction term) = τ = d̄ for RSC; δ·d_max and δ(d_min+d_max)/2 for SCORE+/ISC; θ·τ^(L) for ASCENT
    Algorithm design parameter; the theorem holds for any τ>0, so this is not fitted to make the bound work, but it is chosen by hand in the methods.
  • L (ASCENT iterations) = 1–60 per dataset (Table 10)
    Tuned per dataset on unsupervised conductance; the empirical 'early stage before over-smoothing' claim depends on choosing this value.
  • θ (ASCENT scale) = 1.0 down to 1e-3 per dataset (Table 10)
    Tuned per dataset on conductance; controls the magnitude of node-wise corrections.
assumptions (6)
  • standard math Spectral theorem and Rayleigh-quotient identities for the symmetric regularized Laplacian D_τ^{-1/2} A D_τ^{-1/2}.
    Invoked throughout Theorem 4.1 and Appendix A to expand G in the eigenbasis and bound the tail error.
  • domain assumption KMeans has approximation ratio α, which can be a constant [52].
    Used in Theorem 4.3 and Lemma 4.4 to turn the clustering-cost bound into a volume-mismatch bound; if α is not constant, the final constant c=160(1+α) is not universal.
  • domain assumption Definition 3.2: all d_i copies of spectral embedding of node v_i lie in one cluster, so COST reduces to standard KMeans distance.
    This modeling choice is stated in Section 3 and is required for the KMeans approximation-ratio argument in Lemma 4.4.
  • domain assumption Graph is undirected, unweighted, simple, with K given; clusters have positive volume and d_min>0 for the final node-count bound.
    Conductance is undefined for zero-volume sets; the theorem's final step divides by d_min, so isolated nodes make the bound vacuous.
  • standard math The normalized-vs-unnormalized embedding inequality from Lemma 1 in [23] holds with constant 4 (used in Appendix B).
    The bound in Lemma 4.2 depends on this cited inequality; the paper does not prove it inside the manuscript.
  • domain assumption ASCENT's GNN mean aggregation over-smooths: lim_{l→∞} τ_i^{(l)} = constant, so the method reduces to constant-τ DCSC.
    Used in Section 5.1 to connect ASCENT to conventional DCSC at large iteration counts; standard for connected graphs but not formalized here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Revisiting Degree-Corrected Spectral Clustering: a Condition-Free Spectral Analysis and Extension." pith.science (2026). https://pith.science/paper/K6JEOID3

@misc{pith2026260721435,
  author       = {Pith},
  title        = {Pith review of: Revisiting Degree-Corrected Spectral Clustering: a Condition-Free Spectral Analysis and Extension},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/K6JEOID3}},
  note         = {Machine review of arXiv:2607.21435}
}
read the original abstract

Spectral clustering is a representative graph clustering technique with strong interpretability and theoretical guarantees. Degree-corrected spectral clustering (DCSC) has emerged as the state-of-the-art for this technique. While prior studies have provided impressive theoretical insights for DCSC, their analyses typically depend on specific probabilistic frameworks (e.g., stochastic block models) and conditions. In this study, we explore an alternative condition-free analysis for the clustering quality of DCSC from a pure spectral view, without any random graph models. It gives bounds for the number of mis-clustered nodes w.r.t. the optimal partition of conductance minimization while involving quantities that indicate impacts of (\romannumeral1) degree heterogeneity and (\romannumeral2) weakness of clustering structures to the clustering quality. Inspired by graph neural networks (GNNs) and their over-smoothing effect, we propose ASCENT (Adaptive Spectral ClustEring with Node-wise correcTion), a simple yet effective extension of DCSC. Different from most DCSC methods with a constant degree correction, ASCENT follows a node-wise correction scheme. It can assign different corrections for nodes via a GNN mean aggregator. We demonstrate that (\romannumeral1) ASCENT reduces to conventional DCSC methods when encountering over-smoothing; (\romannumeral2) some early stages before over-smoothing can potentially result in better clustering quality.

Figures

Figures reproduced from arXiv: 2607.21435 by the authors.

Figure 1
Figure 1. {𝝉 (𝑙)} on the Zachary’s karate club graph, where each color denotes a cluster. with more common neighbors) to have close correction values. For instance, when 30 ≤ 𝑙 ≤ 70, nodes in the first cluster tend to have larger corrections than those in the second cluster. It is well-known that most GNNs suffer from over-smoothing [55], where node features converge to a constant as the number of layers increases. Similarly,… view at source ↗
Figure 2
Figure 2. Parameter analysis of 𝐿 on Caltech. 1 0.5 0.1 5e-2 1e-2 5e-3 1e-3 5e-4 1e-4 θ 62 64 66 68 70 72 NMI ↑ (a) NMI↑ 1 0.5 0.1 5e-2 1e-2 5e-3 1e-3 5e-4 1e-4 θ 74 76 78 80 82 84 AC ↑ (b) AC↑ 1 0.5 0.1 5e-2 1e-2 5e-3 1e-3 5e-4 1e-4 θ 48 48.5 49 49.5 50 50.5 Conductance ↓ (c) Conductance↓ [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Parameter analysis of 𝜃 on Caltech. weakness of clustering structures to the clustering quality of DCSC. Inspired by GNNs and their over-smoothing effect, we proposed ASCENT, a simple yet effective extension of DCSC. It follows a node-wise correction scheme that can assign nodes {𝑣𝑖 } with different corrections {𝜏𝑖 } via the GNN mean aggregation. In particular, ASCENT reduces to conventional DCSC methods when encoun… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Illustrations of 𝐻𝜋,𝑟Δ𝑆̂ 𝑟 , 𝐻𝜋,𝑡Δ𝑆̂ 𝑡 , 𝐻𝜋′ ,𝑟Δ𝑆̂ 𝑟 , and 𝐻𝜋′ ,𝑡Δ𝑆̂ 𝑡 denoted by red areas. Without loss of generality, we assume that max{𝜇(𝐶𝑎∖𝑆̂ 𝑟 ), 𝜇(𝐶𝑎∖𝑆̂ 𝑡 )} = 𝜇(𝐶𝑎∖𝑆̂ 𝑡 ). Since each iteration moves a selected set 𝐶𝑎 at most once, the total contribution of cas…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

77 extracted references · 4 linked inside Pith

  1. [1]

    Berahmand, E

    K. Berahmand, E. Nasiri, Y. Li, et al., Spectral clustering on protein-protein interaction networks via constructing affinity matrix using attributed graph embedding, Computers in Biology and Medicine 138 (2021) 104933

    2021

  2. [2]

    G.Qin,L.Gao,Spectralclusteringfordetectingproteincomplexesinprotein–proteininteraction(PPI)networks,MathematicalandComputer Modelling 52 (11-12) (2010) 2066–2074

    2010

  3. [3]

    L.Dai,B.Bai,Optimaldecompositionforlarge-scaleinfrastructure-basedwirelessnetworks,IEEETransactionsonWirelessCommunications (TWC) 16 (8) (2017) 4956–4969

    2017

  4. [4]

    M. Qin, K. Lei, B. Bai, G. Zhang, Towards a profiling view for unsupervised traffic classification by exploring the statistic features and link patterns, in: Proceedings of the 2019 ACM SIGCOMM Workshop on Network Meets AI & ML, 2019, pp. 50–56

    2019

  5. [5]

    A. Ng, M. Jordan, Y. Weiss, On spectral clustering: Analysis and an algorithm, in: Advances in Neural Information Processing Systems (NeurIPS), 2001, pp. 849–856

    2001

  6. [6]

    Jin, Fast community detection by SCORE, The Annals of Statistics 43 (1) (2015) 57–89

    J. Jin, Fast community detection by SCORE, The Annals of Statistics 43 (1) (2015) 57–89

    2015

  7. [7]

    T. Qin, K. Rohe, Regularized spectral clustering under the degree-corrected stochastic blockmodel, in: Advances in Neural Information Processing Systems (NeurIPS), 2013, pp. 3120–3128

    2013

  8. [8]

    J. Jin, Z. T. Ke, S. Luo, Improvements on score, especially for weak signals, Sankhya A (2021) 1–36

    2021

Show all 77 references
  1. [9]

    H.Qing,J.Wang,Animprovedspectralclusteringmethodforcommunitydetectionunderthedegree-correctedstochasticblockmodel,arXiv preprint arXiv:2011.06374 (2020)

    2011 arXiv

  2. [10]

    Zhang, K

    Y. Zhang, K. Rohe, Understanding regularized spectral clustering via graph conductance, in: Advances in Neural Information Processing Systems, 2018, pp. 10654–10663

    2018

  3. [11]

    Coja-Oghlan, Graph partitioning via adaptive spectral techniques, Combinatorics, Probability and Computing 19 (2) (2010) 227–284

    A. Coja-Oghlan, Graph partitioning via adaptive spectral techniques, Combinatorics, Probability and Computing 19 (2) (2010) 227–284

    2010

  4. [12]

    K.Chaudhuri,F.Chung,A.Tsiatas,Spectralclusteringofgraphswithgeneraldegreesintheextendedplantedpartitionmodel,in:Conference on Learning Theory, JMLR Workshop and Conference Proceedings, 2012, pp. 35–1

    2012

  5. [13]

    A. A. Amini, A. Chen, P. J. Bickel, E. Levina, Pseudo-likelihood methods for community detection in large sparse networks, The Annals of Statistics (2013) 2097–2122

    2013

  6. [14]

    Cucuringu, A

    M. Cucuringu, A. V. Singh, D. Sulem, H. Tyagi, Regularized spectral methods for clustering signed networks, Journal of Machine Learning Research (JMLR) 22 (264) (2021) 1–79

    2021

  7. [15]

    Joseph, B

    A. Joseph, B. Yu, Impact of regularization on spectral clustering, The Annals of Statistics 44 (4) (2016) 1765–1791

    2016

  8. [16]

    Dall’Amico, R

    L. Dall’Amico, R. Couillet, N. Tremblay, Revisiting the Bethe-Hessian: Improved community detection in sparse heterogeneous graphs, in: Advances in Neural Information Processing Systems (NeurIPS), 2019, pp. 4039–4049

    2019

  9. [17]

    Cohen-Addad, F

    V. Cohen-Addad, F. Mallmann-Trenn, D. Saulpic, Community recovery in the degree-heterogeneous stochastic block model, in: Conference on Learning Theory, PMLR, 2022, pp. 1662–1692

    2022

  10. [18]

    L. Ding, C. Li, D. Jin, S. Ding, Survey of spectral clustering based on graph theory, Pattern Recognition (2024) 110366

    2024

  11. [19]

    Condon, R

    A. Condon, R. M. Karp, Algorithms for graph partitioning on the planted partition model, Random Structures & Algorithms 18 (2) (2001) 116–140

    2001

  12. [20]

    Karrer, M

    B. Karrer, M. E. Newman, Stochastic blockmodels and community structure in networks, Physical Review E 83 (1) (2011) 016107

    2011

  13. [21]

    Von Luxburg, A tutorial on spectral clustering, Statistics & Computing 17 (2007) 395–416

    U. Von Luxburg, A tutorial on spectral clustering, Statistics & Computing 17 (2007) 395–416

    2007

  14. [22]

    1423–1455

    R.Peng,H.Sun,L.Zanetti,Partitioningwell-clusteredgraphs:Spectralclusteringworks!,in:ConferenceonLearningTheory,PMLR,2015, pp. 1423–1455

    2015

  15. [23]

    Mizutani, Improved analysis of spectral algorithm for clustering, Optimization Letters 15 (2021) 1303–1325

    T. Mizutani, Improved analysis of spectral algorithm for clustering, Optimization Letters 15 (2021) 1303–1325

    2021

  16. [24]

    14717–14742

    P.Macgregor,H.Sun,Atighteranalysisofspectralclustering,andbeyond,in:Proceedingsofthe2022InternationalConferenceonMachine Learning (ICML), 2022, pp. 14717–14742

    2022

  17. [25]

    J.R.Lee,S.O.Gharan,L.Trevisan,Multiwayspectralpartitioningandhigher-orderCheegerinequalities,JournaloftheACM(JACM)61(6) (2014) 1–30

    2014

  18. [26]

    F.Krzakala,C.Moore,E.Mossel,J.Neeman,A.Sly,L.Zdeborová,P.Zhang,Spectralredemptioninclusteringsparsenetworks,Proceedings of the National Academy of Sciences (PNAS) 110 (52) (2013) 20935–20940

    2013

  19. [27]

    Gulikers, M

    L. Gulikers, M. Lelarge, L. Massoulié, Non-backtracking spectrum of degree-corrected stochastic block models, in: Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017, pp. 44–1

    2017

  20. [28]

    Dall’Amico, R

    L. Dall’Amico, R. Couillet, N. Tremblay, Optimal Laplacian regularization for sparse spectral community detection, in: Proceedings of the 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2020, pp. 3237–3241. Wei Li et al.:Preprint s...

    2020

  21. [29]

    L.Dall’Amico,R.Couillet,N.Tremblay,Aunifiedframeworkforspectralclusteringinsparsegraphs,JournalofMachineLearningResearch (JMLR) 22 (217) (2021) 1–56

    2021

  22. [30]

    L.Dall’Amico,R.Couillet,N.Tremblay,NishimorimeetsBethe:aspectralmethodfornodeclassificationinsparseweightedgraphs,Journal of Statistical Mechanics: Theory and Experiment 2021 (9) (2021) 093405

    2021

  23. [31]

    A.Decelle,F.Krzakala,C.Moore,L.Zdeborová,Asymptoticanalysisofthestochasticblockmodelformodularnetworksanditsalgorithmic applications, Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 84 (6) (2011) 066106

    2011

  24. [32]

    Massoulié, Community detection thresholds and the weak Ramanujan property, in: Proceedings of the 46th Annual ACM Symposium on Theory of computing, ACM, 2014, pp

    L. Massoulié, Community detection thresholds and the weak Ramanujan property, in: Proceedings of the 46th Annual ACM Symposium on Theory of computing, ACM, 2014, pp. 694–703

    2014

  25. [33]

    L.Yue,X.Jun,Z.Sihang,W.Siwei,G.Xifeng,Y.Xihong,L.Ke,T.Wenxuan,L.X.Wang,etal.,Asurveyofdeepgraphclustering:Taxonomy, challenge, and application, arXiv:2211.12875 (2022)

    2022 arXiv

  26. [34]

    X.Su,S.Xue,F.Liu,J.Wu,J.Yang,C.Zhou,W.Hu,C.Paris,S.Nepal,D.Jin,etal.,Acomprehensivesurveyoncommunitydetectionwith deep learning, IEEE Transactions on Neural Networks & Learning Systems (TNNLS) (2022)

    2022

  27. [35]

    1293–1299

    F.Tian,B.Gao,Q.Cui,E.Chen,T.-Y.Liu,Learningdeeprepresentationsforgraphclustering,in:Proceedingsofthe28thAAAIConference on Artificial Intelligence, 2014, pp. 1293–1299

    2014

  28. [36]

    L. Yang, X. Cao, D. He, C. Wang, X. Wang, W. Zhang, Modularity based community detection with deep learning, in: Proceedings of the 25fth International Joint Conference on Artificial Intelligence (IJCAI), 2016, pp. 2252–2258

    2016

  29. [37]

    B. Deng, T. Wang, L. Fu, S. Huang, C. Chen, T. Zhang, THESAURUS: Contrastive graph clustering by swapping fused gromov-wasserstein couplings, in: Proceedings of the AAAI Conference on Artificial Intelligence, 2025, pp. 16199–16207

    2025

  30. [38]

    Devvrit, A

    F. Devvrit, A. Sinha, I. Dhillon, P. Jain, S3GC: Scalable self-supervised graph clustering, in: Advances in Neural Information Processing Systems (NeurIPS), 2022, pp. 3248–3261

    2022

  31. [39]

    Y. Liu, J. Li, Y. Chen, R. Wu, E. Wang, J. Zhou, S. Tian, S. Shen, X. Fu, C. Meng, et al., Revisiting modularity maximization for graph clustering: A contrastive learning perspective, in: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2024,...

    2024

  32. [40]

    M.E.Newman,Modularityandcommunitystructureinnetworks,ProceedingsoftheNationalAcademyofSciences(PNAS)103(23)(2006) 8577–8582

    2006

  33. [41]

    Bhowmick, M

    A. Bhowmick, M. Kosan, Z. Huang, A. Singh, S. Medya, DGCLUSTER: A neural framework for attributed graph clustering via modularity maximization, in: Proceedings of the 36th AAAI Conference on Artificial Intelligence, 2024, pp. 11069–11077

    2024

  34. [42]

    T.Zhang,R.Ramakrishnan,M.Livny,BIRCH:Anefficientdataclusteringmethodforverylargedatabases,in:Proceedingsofthe1996ACM SIGMOD International Conference on Management of Data, ACM, 1996, pp. 103–114

    1996

  35. [43]

    Wilder, E

    B. Wilder, E. Ewing, B. Dilkina, M. Tambe, End to end learning and optimization on graphs, in: Advances in Neural Information Processing Systems (NeurIPS), 2019, pp. 4672–4683

    2019

  36. [44]

    F. M. Bianchi, D. Grattarola, C. Alippi, Spectral clustering with graph neural networks for graph pooling, in: Proceedings of the 37th International Conference on Machine Learning (ICML), PMLR, 2020, pp. 874–883

    2020

  37. [45]

    A.Tsitsulin,J.Palowitch,B.Perozzi,E.Müller,Graphclusteringwithgraphneuralnetworks,JournalofMachineLearningResearch(JMLR) 24 (127) (2023) 1–21

    2023

  38. [46]

    D. Bo, X. Wang, C. Shi, M. Zhu, E. Lu, P. Cui, Structural deep clustering network, in: Proceedings of the 2020 Web Conference 2020, 2020, pp. 1400–1410

    2020

  39. [47]

    M. Qin, D. Jin, K. Lei, B. Gabrys, K. Musial-Gabrys, Adaptive community detection incorporating topology and content in social networks, Knowledge-Based Systems (KBS) 161 (2018) 342–356

    2018

  40. [48]

    X. Wang, M. Zhu, D. Bo, P. Cui, C. Shi, J. Pei, AM-GCN: Adaptive multi-channel graph convolutional networks, in: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020, pp. 1243–1253

    2020

  41. [49]

    M. Qin, K. Lei, Dual-channel hybrid community detection in attributed networks, Information Sciences 551 (2021) 146–167

    2021

  42. [50]

    M. Qin, C. Zhang, B. Bai, G. Zhang, D.-Y. Yeung, Towards a better trade-off between quality and efficiency of community detection: An inductive embedding method across graphs, ACM Transactions on Knowledge Discovery from Data (TKDD) (2023)

    2023

  43. [51]

    Y.Gao,M.Qin,Y.Ding,L.Zeng,C.Zhang,W.Zhang,W.Han,R.Zhao,B.Bai,RaftGP:Randomfastgraphpartitioning,in:Proceedingsof the 2023 IEEE High Performance Extreme Computing Conference (HPEC), IEEE, 2023, pp. 1–7

    2023

  44. [52]

    D. Choo, C. Grunau, J. Portmann, V. Rozhon, k-means++: Few more steps yield constant approximation, in: Proceedings of the 2020 International Conference on Machine Learning (ICML), 2020, pp. 1909–1917

    2020

  45. [53]

    1024–1034

    W.Hamilton,Z.Ying,J.Leskovec,Inductiverepresentationlearningonlargegraphs,in:AdvancesinNeuralInformationProcessingSystems (NeurIPS), 2017, pp. 1024–1034

    2017

  46. [54]

    W.W.Zachary,Aninformationflowmodelforconflictandfissioninsmallgroups,JournalofAnthropologicalResearch33(4)(1977)452–473

    1977

  47. [55]

    T. K. Rusch, M. M. Bronstein, S. Mishra, A survey on oversmoothing in graph neural networks, arXiv preprint arXiv:2303.10993 (2023)

    2023 arXiv

  48. [56]

    R. B. Lehoucq, D. C. Sorensen, C. Yang, ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, SIAM, 1998

    1998

  49. [57]

    Lancichinetti, S

    A. Lancichinetti, S. Fortunato, F. Radicchi, Benchmark graphs for testing community detection algorithms, Physical Review E 78 (4) (2008) 046110

    2008

  50. [58]

    V.Red,E.D.Kelsic,P.J.Mucha,M.A.Porter,Comparingcommunitystructuretocharacteristicsinonlinecollegiatesocialnetworks,SIAM Review 53 (3) (2011) 526–543

    2011

  51. [59]

    L. A. Adamic, N. Glance, The political blogosphere and the 2004 US election: Divided they blog, in: Proceedings of the 3rd International Workshop on Link Discovery, 2005, pp. 36–43

    2004

  52. [60]

    A.Grover,J.Leskovec,node2vec:Scalablefeaturelearningfornetworks,in:Proceedingsofthe22ndACMSIGKDDInternationalConference on Knowledge Discovery & Data Mining, 2016, pp. 855–864. Wei Li et al.:Preprint submitted to ElsevierPage 24 of 25 Revisiting Degree-Corrected Spectral Clust...

    2016

  53. [61]

    Stark, B.-J

    C. Stark, B.-J. Breitkreutz, T. Reguly, L. Boucher, A. Breitkreutz, M. Tyers, BioGRID: A general repository for interaction datasets, Nucleic Acids Research 34 (suppl_1) (2006) D535–D539

    2006

  54. [62]

    Szklarczyk, A

    D. Szklarczyk, A. L. Gable, D. Lyon, A. Junge, S. Wyder, J. Huerta-Cepas, M. Simonovic, N. T. Doncheva, J. H. Morris, P. Bork, et al., STRING v11: Protein–protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets...

    2019

  55. [63]

    J. Yang, J. Leskovec, Defining and evaluating network communities based on ground-truth, in: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, 2012, pp. 1–8

    2012

  56. [64]

    Leskovec, K

    J. Leskovec, K. J. Lang, A. Dasgupta, M. W. Mahoney, Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters, Internet Mathematics 6 (1) (2009) 29–123

    2009

  57. [65]

    W.-L.Chiang,X.Liu,S.Si,Y.Li,S.Bengio,C.-J.Hsieh,Cluster-GCN:Anefficientalgorithmfortrainingdeepandlargegraphconvolutional networks,in:Proceedingsofthe25thACMSIGKDDInternationalConferenceonKnowledgeDiscovery&DataMining,2019,pp.257–266

    2019

  58. [66]

    S. Pu, J. Wong, B. Turner, E. Cho, S. J. Wodak, Up-to-date catalogues of yeast protein complexes, Nucleic Acids Research 37 (3) (2009) 825–831

    2009

  59. [67]

    I. S. Dhillon, Y. Guan, B. Kulis, Weighted graph cuts without eigenvectors a multilevel approach, IEEE Transactions on Pattern Analysis & Machine Intelligence (TPAMI) 29 (11) (2007) 1944–1957

    2007

  60. [68]

    2218–2225

    E.Y.Chan,D.-Y.Yeung,Aconvexformulationofmodularitymaximizationforcommunitydetection,in:Proceedingsofthe22ndInternational Joint Conference on Artificial Intelligence (IJCAI), 2011, pp. 2218–2225

    2011

  61. [69]

    A. V. Knyazev, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method, SIAM Journal on Scientific Computing 23 (2) (2001) 517–541

    2001

  62. [70]

    M. E. Newman, A. Clauset, Structure and inference in annotated networks, Nature Communications 7 (1) (2016) 11863

    2016

  63. [71]

    3950–3957

    D.Bo,X.Wang,C.Shi,H.Shen,Beyondlow-frequencyinformationingraphconvolutionalnetworks,in:ProceedingsoftheAAAIConference on Artificial Intelligence, 2021, pp. 3950–3957

    2021

  64. [72]

    Y.Dong,K.Ding,B.Jalaian,S.Ji,J.Li,AdaGNN:Graphneuralnetworkswithadaptivefrequencyresponsefilter,in:Proceedingsofthe30th ACM International Conference on Information & Knowledge Management (CIKM), 2021, pp. 392–401

    2021

  65. [73]

    2350–2361

    M.Qin,J.Liu,I.King,Efficientddentityandpositiongraphembeddingviaspectral-basedrandomfeatureaggregation,in:Proceedingsofthe 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, 2025, pp. 2350–2361

    2025

  66. [74]

    M. Qin, W. Li, J. Cui, S. Pei, InfraredGP: Efficient graph partitioning via spectral graph neural networks with negative corrections, in: Proceedings of the 2025 IEEE High Performance Extreme Computing Conference (HPEC), IEEE, 2025, pp. 1–7

    2025

  67. [75]

    Q. Chen, W. Li, M. Qin, J. Hou, A spectral theory of normalized corrected GNN propagation, arXiv preprint arXiv:2606.23572 (2026)

    2026 arXiv

  68. [76]

    M.Qin,C.Zhang,Y.Gao,W.Zhang,D.-Y.Yeung,Pre-trainandrefine:Towardshigherefficiencyin𝑘-agnosticcommunitydetectionwithout qualitydegradation,in:Proceedingsofthe30thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,2024,pp.2467–2478

    2024

  69. [77]

    M. Qin, C. Zhang, Y. Gao, Y. Ding, W. Jiang, W. Zhang, W. Han, B. Bai, Towards faster graph partitioning via pre-training and inductive inference, in: Proceedings of the 2024 IEEE High Performance Extreme Computing Conference (HPEC), IEEE, 2024, pp. 1–7. Wei Li et al.:Preprint...

    2024

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.