Rethinking Degree-Corrected Spectral Clustering: a Pure Spectral Analysis & Extension

Dear Reviewer hGxZ,

We sincerely thank you for summarizing the strengths of our paper. In addition, we have also tried our best to make a major revision according to your comments and suggestions on the weaknesses.

---

W1. The paper's notation is dense and at times difficult to follow ...

Response to W1: We are sorry for the presentation issue regarding notations. During the revision, we have adopted your suggestion to give separate definitions for $E(S, V \backslash S)$ and $\mu (S)$ before Definition 1. Moreover, we have given the definition of $m_K$ just after it is first used in (5). In the analysis of the main paper, we have used $\Psi_{\rm{ISC}}$ and $\Psi_{\rm{AST}}$ to denote the $\Psi$ quantities of ISC and ASCENT, respectively. Moreover, we have further extended our analysis to a series of spectral clustering algorithms in Appendix F, where we used the subscripts (or superscripts) of 'NJW', 'RSC', 'SC+', 'ISC', and 'AST' to denote corresponding variables of NJW, RSC, SCORE+, ISC, and ASCENT, respectively.

We hope that our revisions can help you better follow the analysis.

---

W2. Some parts of the derivations, especially in Section 3, appear redundant ...

Response to W2: We are sorry for the redundant presentation. However, Reviewer g4ng also suggested to add some more explanations in Section 3 (e.g., the high-level sketch in Fig. 1 of the revised paper), in addition to the redundant presentation you mentioned. In this sense, some redundant derivations and explanations may be necessary for those who lack related backgrounds to follow the logical flows of our theoretical analysis.

We really hope that you can understand our difficulties in reaching a presentation appropriate for readers with different backgrounds.

---

W3. As previously mentioned, the ASCENT algorithm and its node-wise correction scheme should be the highlight of this paper. However, the theoretical results in Section 4 don’t convincingly showcase the advantages of ASCENT ... I recommend replacing Theorem 10 with a result that ties more directly to the ASCENT algorithm, or alternatively, presenting a simpler explanation in text form.

Response to W3: Thank you for your comments regarding our analysis of ASCENT. During the revision, we have adopted your suggestion to replace Proposition 9 and Theorem 10 with an improved analysis (cf. Proposition 9 in the revised paper) and given the corresponding proof in Appendix E. Instead of simply replacing the constant $\tau$ with the maximum correction $\tau_{\max}$ of ASCENT (i.e., our previous analysis), the upper bounds in our improved analysis are related to the maximum correction $\hat\tau_r$ among nodes in each cluster $\hat S_r$. Since different nodes $\{ v_i \}$ may have different corrections $\{\tau_i\}$, different clusters $\{ \hat S_r\}$ may have different $\{\hat \tau_r\}$ and thus the upper bounds of $\mu (C_r \Delta \hat S_r)$ and $\phi (C_r)$ are determined by cluster-wise corrections $(\hat \tau_1, \cdots, \hat \tau_K)$. As demonstrated in Fig. 2 (of the revised paper), ASCENT can force nodes $\{ v_i\}$ in the same cluster to have close corrections $\{ \tau_i \}$. Based on this property, we believe that the improved analysis with cluster-wise corrections $(\hat \tau_1, \cdots, \hat \tau_K)$ can better demonstrate the advantages of ASCENT, compared with the previous version with $\tau_{\max}$.

Moreover, based on our extended analysis in Appendix F, we have further tried to answer the question: When can ASCENT potentially outperform ISC? It further verifies that under certain conditions, it is possible for ASCENT to outperform some conventional DCSC algorithms (e.g., ISC).

We really hope that our revisions and explanations can help you better understand the advantages of our method and address your concerns.

W4. Selecting suitable values for parameters $(\theta, L, K)$ could be challenging in practice ... a more adaptive approach or further guidance on parameter selection for real-world datasets would be helpful.

Q2. The range of $\theta$ values tested in the experiments seems broad. Could you discuss whether the algorithm is sensitive to the choice of $\theta$?

Response to W4 and Q2: Please note that for most graph clustering methods (including ASCENT and other baselines in our experiments), $K$ is assumed to be given, as described in the 2nd paragraph of Section 2. Hence, we usually do not need to select $K$ in practice.

From the perspective of machine learning, $(\theta, L)$ are hyper-parameters for ASCENT, just like the number of GNN layers in some deep graph clustering baselines (e.g., GAP, SDCN, MinCutPool, DMoN, and DGCluster in our experiments). Moreover, the constant correction $\tau$ in RSC, SCORE+, and ISC can also be considered as a tunable hyper-parameter. Since graph clustering is a typical unsupervised task, one can tune hyper-parameters of a method using the unsupervised conductance metrics. Concretely, we can compute conductance metrics w.r.t. clustering results given by different hyper-parameter settings and then select the one with minimum conductance.

As described in Appendix I of the revised paper, we recommend to adjust $\theta \in \{ 0.01, 0.05, 0.1, 0.5, 1\}$ for ASCENT. According to the parameter analysis results in Fig. 4 of the revised paper, the clustering quality of ASCENT is sensitive to $\theta$.

We believe that ASCENT is a good beginning to consider node-wise corrections $\{ \tau_i \}$ for DCSC, even though we still manually set $\{ \tau_i \}$ by adjusting $\{ \theta, L\}$. As summarized in Appendix J of the revised paper, we intend to consider a more advanced setting with learnable $\{ \tau_i \}$ instead of manually adjusting $\{ \theta, L\}$ in our future work.

---

W5. The paper contains several typographical errors, and a thorough proofreading is recommended ...

Response to W5: We are sorry for the errors you mentioned. During the revision, we have corrected them with the corresponding revisions highlighted in blue text. For instance, we have (1) changed '(iii) degree heterogeneity and (iv) weakness of clustering structures' to '(i) degree heterogeneity and (ii) weakness of clustering structures', (2) changed '$1 > \lambda_1 \le \lambda_2 \cdots$' to '$1 > \lambda_1 \ge \lambda_2 \cdots \lambda_N$', (3) completed the sentence to 'example analysis results of $\theta$ on Caltech are visualized in Fig. 3', and (4) replaced 'eigenvalue decomposition' with 'eigen-decomposition'. Besides, we have also tried our best to find some other potential errors and correct them.

---

Q1. What is the rationale for selecting $K \in \{ 2, 8, 32\}$ in the experiments?

Response to Q1: Please note that in our previous version, we have already explained why we set $K \in \{ 2, 8, 32\}$ for Airport, Wiki, BlogCatalog, and ogbn-Protein in the last paragraph of Section 5.1 and Appendix H.

In our experiments, CalTech, Simmons, PolBlogs, and BioGrid are widely-used datasets that provide explicit clustering ground-truth w.r.t. our problem statement but with relatively small scales. Therefore, we could directly set $K$ according to their ground-truth (e.g., $K = 8$ for CalTech as summarized in Table 3) while using NMI and AC to measure the correspondence between (i) the clustering result given by a method and (ii) the ground-truth.

To further test the efficiency and scalability of ASCENT, we also used additional datasets (i.e., Airport, Wiki, BlogCatalog, and ogbn-Protein) with relatively larger scales. However, as described in Appendix H of the revised paper, these four datasets do not provide ground-truth w.r.t. our problem statement (i.e., disjoint graph clustering without attributes). Concretely, the original ground-truth of Wiki and BlogCatalog is overlapping but not disjoint. Airport and ogbn-Protein are attributed graphs. It is unclear that their ground-truth is dominated by graph topology or attributes due to the complicated correlations between the two sources described in Section 2. In this sense, we could not directly use their ground-truth for evaluation but had to manually set $K \in \{ 2, 8, 32\}$ for them and compared their corresponding conductance values. It is also a widely-used strategy for graph clustering (community detection) when ground-truth is unavailable [1-2].

[1] Dhillon et al. Weighted Graph Cuts without Eigenvectors: A Multilevel Approach.

[2] Chan et al. A Convex Formulation of Modularity Maximization for Community Detection.

Dear Reviewer hGxZ,

We sincerely appreciate your positive feedbacks regarding our responses and revisions.

We are sorry for the dense presentation of our paper. As we can check, Reviewer VrzY gave positive feedbacks regarding the presentation of previous version. Reviewer g4ng further suggested to added some more explanations regarding theoretical analysis. It indicates that people with different backgrounds may have different opinions about the presentation of a paper with rigorous theoretical analysis. We have tired our best to make a compromise among all the reviewers' comments.

We really hope that you can understanding our difficulties in reaching a presentation appropriate for readers with different backgrounds while following the page limit of main paper.

Q3. It would be useful to define over smoothing more rigorously, especially in the context of ASCENT which is pretty different from GNN?

Response to Q3: Thank you for your suggestion regarding the definition of over-smoothing. Despite the strict page limit of main paper, during the revision, we have still tried our best to give a brief but formal definition of the over-smoothing effect of ASCENT in Section 4. Concretely, we have $\mathop {\lim }\limits_{l \to \infty } \tau _i^{(l)} = c, \forall {v_i} \in V$, with $c$ as a constant.

---

Q4. The paper also notes that, after enough iterations, ASCENT effectively reduces to a conventional DCSC method with a global, constant correction term ... Is there a convergence guarantee in the strict mathematical sense? Are there possible guarantees against oscillations?

Response to Q4: Please note that ASCENT reduces to a conventional DCSC algorithm with a constant correction $\tau$, due to the over-smoothing issue of the GNN mean aggregator. Since ASCENT adopts the typical mean aggregator (e.g., same as that of GraphSAGE-mean), any convergence guarantees regarding the over-smoothing of this aggregator also hold for ASCENT. To the best of our knowledge, there is some rigorous theoretical analysis regarding the convergence of over-smoothing (cf. Theorem 1 and Corollary 1 in [1]). Our toy example in Fig. 2 of the revised paper also justified this effect.

[1] Keriven et al. Not Too Little, Not Too Much: a Theoretical Analysis of Graph (Over)smoothing.

---

Q5. Maybe give more intuition on crucial parameters like $\Psi$.

Response to Q5: As highlighted before Theorem 3 of the revised paper, $\Psi$ is an auxiliary quantity that can measure impacts of (i) degree heterogeneity and (ii) weakness of clustering structures. Concretely, $\Psi$ includes two variables (i.e., $h$ and $m_K$), where (i) a small $h$ indicates high degree heterogeneity and (ii) a small lower bound of $m_K$ indicates weak clustering structures.

Since $\Psi$ is inversely proportional to $h$ and $m_K$, high degree heterogeneity and weak clustering structures may result in a large value of $\Psi$.

Furthermore, the upper bounds of mis-clustered volume $\mu (C_r \Delta \hat S_r)$ and conductance $\phi (C_r)$ given by Theorem 8 are directly proportional to $\Psi$. Therefore, (i) higher degree heterogeneity and (ii) weak clustering structures result in higher upper bounds of $\mu (C_r \Delta \hat S_r)$ and $\phi (C_r)$, indicating lower clustering quality.

In this setting, $\Psi$ enables our main theoretical results in Theorem 8 to quantitatively reveal the impacts of (i) degree heterogeneity and (ii) weakness of clustering structures to the clustering quality measured by $\mu (C_r \Delta \hat S_r)$ and $\phi (C_r)$.

We really hope that our explanations can help you better understand the motivation and intuition of introducing $\Psi$.

Dear Reviewer 2rdr,

We sincerely thank you for summarizing the strengths of our paper. Besides, we have also tried our best to make a major revision according to your concerns and suggestions on the weaknesses.

---

W1. Over-Smoothing Control: Although ASCENT attempts to mitigate over-smoothing, the choice of the parameter L (number of correction iterations) is critical ...

Q1. Can you effectively do cross validation to find L?

Response to W1 & Q1: Please note that $L$ is a hyper-parameter of ASCENT, like the number of GNN layers in some deep graph clustering approaches (e.g., GAP, SDCN, MinCutPool, DMoN, and DGCluster in our experiments). Since graph clustering is a typical unsupervised task, one cannot use the cross-validation designed for supervised tasks to tune $L$. Instead, we can use the unsupervised conductance metric to tune $L$, as spectral clustering is an approximated algorithm for conductance minimization. Concretely, we can compute conductance metrics w.r.t. clustering results given by different settings of $L$ and select the $L$ that has the minimum conductance. Such a strategy is also adopted by other baselines in our experiments to tune their hyper-parameters.

We believe that ASCENT is a good beginning to consider node-wise corrections for DCSC. As summarized in Appendix J of the revised paper, we intend to extend ASCENT to a setting with learnable node-wise corrections $\{ \tau_i \}$ in our future work, instead of manually setting $\{ \tau_i \}$ by adjusting $\{ \theta, L\}$.

---

W2. Complexity and Scalability: Although ASCENT aims to address high degree heterogeneity and weak clustering structures, node-wise correction might increase computational complexity, especially on large-scale graphs with millions of nodes ...

Q2. How would you consider scaling the algorithm to big graphs?

Response to W2 & Q2: Thank you for your comment and question regarding the complexity and scalability of ASCENT. During the revision, we have provided complexity analysis in Appendix G, where the derivation of node-wise corrections $\{ \tau_i\}$ will not increase the overall complexity of ASCENT. Namely, ASCENT has the same complexity with most existing DCSC algorithms.

We have also conducted additional efficiency analysis for all the methods in Appendix I. Our results (cf. Tables 27-30) demonstrate that spectral clustering methods (including ASCENT) can achieve significantly better efficiency and scalability than deep graph clustering baselines. Moreover, eigen-decomposition is the major bottleneck for all the spectral clustering algorithms and the derivation of $\{ \tau_i\}$ would not significantly increase the overall runtime of ASCENT.

To further improve the scalability of ASCENT, we need to first improve its bottleneck (i.e., eigen-decomposition). One can speed up eigen-decomposition using the efficient LOBPCG solver, which also has parallel implementations. As summarized in Appendix J, we plan to consider this improvement in our future work.

---

W3. Initialisation in ASCNET: ... In graphs with degree heterogeneity, initial corrections may differ widely, and ASCENT’s iterative process may need more iterations to bring node corrections to a stable, locally consistent state, or possibly oscillate?

Response to W3: One of our contributions is that ASCENT can derive node-wise corrections $\{ \tau_i \}$ (i.e., different nodes may have different corrections) before it reduces to the case with a constant correction $\tau$ due to over-smoothing. Our experiments also demonstrate that ASCENT can potentially obtain better clustering quality than conventional DCSC methods with a constant $\tau$ in some early steps of iteration before over-smoothing.

In this sense, it does not matter that ASCENT may need more iterations to bring node corrections to a stable state as you mentioned. We really hope that our explanations can help you better understand our contributions of ASCENT.

---

W4. The presentation is a bit dense and it could useful to try to re-organize a bit the paper to make it more more reader-friendly.

Response to W4: We are sorry for the dense presentation of main paper, due to some redundant explanations about theoretical analysis. However, Reviewer g4ng still suggested to added some more interpretations regarding the analysis in Section 3 (e.g., the high-level sketch in Fig. 1 of the revised paper), in addition to the previous presentation. In this sense, some redundant derivations and explanations may be necessary for those who lack related backgrounds to follow the logical flows of our theoretical analysis.

We really hope that you can understand our difficulties in reaching a presentation appropriate for readers with different backgrounds while following the page length of the conference (i.e., at most 10 pages for the main paper).

Q5. he authors should justify the use of the mean aggregation operation in the computation of the node-wise parameters ...

Response to Q5: Please note that most existing DCSC methods use the 'average/mean' of degrees as their constant correction $\tau$ (e.g., $\tau := \bar d$ and $\delta (d_{\min} + d_{\max})/2$ for RSC and ISC as summarized in Table 1). In this sense, the constant $\tau$ can be considered as a global average of degrees. Based on this interpretation of $\tau$, it is interesting to consider local average of degrees w.r.t. the local topology of each node, which can be computed by the GNN mean aggregation defined in (12).

Also as justified by the toy example in Fig. 2 of the revised paper, (i) $\tau_i$ of each node $v_i$ is initialized by $d_i$ and (ii) the mean aggregation forces nodes $\{ v_i \}$ with dense linkage (e.g., in the same cluster) to have similar corrections $\{ \tau_i \}$ (i.e., the local average degrees). Finally, for a large number of iterations (e.g., $L=50$ in Fig. 2), corrections $\{ \tau_i \}$ of all the nodes converge to a constant, which can be considered as a special global average degree, and thus reduces to a conventional DCSC method (e.g., ISC) with a constant $\tau$.

In summary, the basic motivation of using the GNN mean aggregation operation is that it can compute the local average w.r.t. the local topology of each node, which serves as a special case of the global average in conventional DCSC methods with a constant $\tau$.

We really hope that our explanations can help you better understand the motivation of using mean aggregation.

Q2. The theoretical bound for the mis-clustered volume is derived based on the solution of minimal conductance, which is an unconventional approach in network clustering analysis. It would be helpful to explain whether this mis-cluster rate is valid in practical applications.

Response to Q2: It is well known that spectral clustering adopts a relaxed version of the NP-hard combinatorial optimization objective of conductance minimization. From the perspective of combinatorial optimization, the optimal solution $(\hat S_1, \cdots, \hat S_K)$ to conductance minimization corresponds to the ground-truth you mentioned, in an ideal case.

Please also note that the mis-clustered volume $\mu (C_r \Delta {\hat S}_r)$ in Theorem 8 is consistent with the accuracy metric of graph clustering. Following the same renumbering of $(C_1, \cdots, C_K)$ in Theorem 8, the clustering accuracy is defined as $\sum\nolimits_{r = 1}^K {|{C_r} \cap {{\hat S}_r}|} /N$. In particular, we have ${C_r} \cap {\hat S_r} = {C_r} \cup {\hat S_r} - {C_r}\Delta {\hat S_r} \le V - {C_r}\Delta {\hat S_r}$ and thus lower mis-clustered volume $\mu (C_r \Delta {\hat S}_r)$ indicates higher clustering accuracy.

To the best of our knowledge, to provide bonds regarding the feasible solution given by an algorithm (e.g., $(C_1, \cdots, C_K)$ of ISC) w.r.t. the optimal solution (e.g., $(\hat S_1, \cdots, \hat S_K)$ of conductance minimization) is a widely-used and conventional strategy in the analysis of many combinatorial optimization problems on graphs. For instance, we have $\rm{OBJ} \le \gamma {\rm{OPT}}$ (i.e., $\gamma$-approximation) for some well-known algorithms of traveling salesman problem (TSP) based on minimum spanning tree [1,2], with OBJ and OPT as objective values of (i) feasible solution given by the algorithm and (ii) optimal solution. Since spectral clustering is an approximated algorithm for the NP-hard conductance minimization problem, it is straightforward to adopt this strategy for our analysis of DCSC. Some early studies on vanilla spectral clustering (e.g., Peng et al. and Mizutani et al. in our paper) also follow this strategy. Our analysis can be considered as a unified extension of these early studies.

We really hope that the aforementioned explanations can help you better understand that our analysis follows a conventional strategy in the analysis of combinatorial optimization and is valid in practical applications.

[1] Pop et al. A Comprehensive Survey on the Generalized Traveling Salesman Problem.

[2] Arora et al. Approximation Schemes for NP-hard Geometric Optimization Problems: a Survey

---

Q4. The authors should provide an analysis of the computational complexity of the proposed method ASCENT. Additionally, a comparison of ASCENT with other existing approaches in terms of runtime would be beneficial.

Response to Q4: During the revision, we have adopted your suggestion to add complexity analysis for ASCENT in Appendix G and conduct further efficiency analysis (in terms of runtime) for all the methods in Appendix I, with corresponding results reported in Tables 27-30. According to our analysis, we can reach the following conclusions.

• The derivation of node-wise corrections $\{ \tau_i \}$ will not increase the overall complexity of ASCENT. Therefore, ASCENT has the same complexity with most conventional DCSC algorithms.
• For all the spectral clustering algorithms (including ASCENT), eigen-decomposition is the major bottleneck in their runtime, while the derivations of $\{ \tau_i \}$ would not significantly increase the overall runtime of ASCENT.
• All the spectral clustering methods (including ASCENT) have significantly better efficiency than other deep graph clustering baselines.

Q1. In Theorem 8, the assumption of an upper bound on $\Psi$ is made without providing any justification. It would be beneficial to offer an intuitive explanation for this assumption ...

Response to Q1: We are sorry for the insufficient explanations regarding the condition of $\Psi$ in Theorem 8. During the revision, we have adopted your suggestion to give additional explanations for this condition at the end of Section 3.

Concretely, to ensure that the condition $\Psi \le 1/[132(1+\lambda_1)^2\alpha {\tilde \mu} K]$ holds, we need small $\bar \phi_K (G) / (1 - \lambda_{K+2})$ and large $d_{\min} / [(d_{\max + \tau}) (1 - \lambda_{K+2})]$. In some early studies on vanilla spectral clustering (e.g., Peng et al. and Mizutani et al. in our paper), a graph is defined to be well-clustered if $\bar \phi_K(G) / (1 - \lambda_{K+1})$ is sufficiently small. It is consistent with that $\bar \phi_K (G) / (1 - \lambda_{K+2})$ is small. The well-clustered assumption adopted by Peng et al. and Mizutani et al. indicates that the optimal solution $(\hat S_1, \cdots, \hat S_K)$ (i.e., clustering ground-truth in real applications) describes an explicit clustering structure of $G$. Our analysis can be considered as a unified extension of these early studies. Moreover, large $d_{\min} / [(d_{\max + \tau}) (1 - \lambda_{K+2})]$ indicates that the degree heterogeneity should not be very high. In summary, the condition in Theorem 8 implies an implicit assumption that (i) $G$ is well-clustered and (ii) the degree heterogeneity is not so high.

During the revision, we have also considered your suggestion to verify this condition on both synthetic and real graphs. However, we encountered the following difficulties in exactly computing $\Psi$ and its upper bound. Please note that this condition includes variables (e.g., $\bar \phi_K (G)$, $\mu_{\min}$, and $\mu_{\max}$) associated with the optimal solution to conductance minimization. It is well-known that conductance minimization is an NP-hard combinatorial optimization problem, so we could not expect a polynomial-time algorithm to obtain its optimal solution. It is intractable to get the optimal solution using the brute-force algorithm with a complexity of $O(N^K)$. Although we can still 'approximately' treat the ground-truth of a dataset as the optimal solution, we also found that the upper bound includes the approximation ratio $\alpha$ of KMeans, which depends on the concrete algorithm we use and is usually not an exact number (e.g., $\alpha = O(log K)$ for KMeans++). In summary, we could not exactly compute $\Psi$ and its upper bound to verify the condition. We really hope that you can understand the difficulties we encountered.

Also as summarized in Appendix J of the revised paper, we plan to further improve this condition by extending some new theoretical results on the combinatorial optimization problem of graph-cut minimization (e.g., conductance minimization in this paper) to DCSC.

W2. The paper provides insufficient detail regarding the tuning of the parameter $\theta$, lacking a clear explanation of how it was chosen during the data analysis process ... the experimental results in Section 5.1 show only a slight improvement over the baseline methods.

Q3. The limitation on the number of iteration steps in the ASCENT model is introduced to address over-smoothing issues ... The original degree-corrected spectral clustering (DCSC) method already performs well, and the proposed approach shows only slight improvements by adding two extra parameters $L$ and $\theta$.

Response to W2 & Q3: Thank you for your comments regarding the parameter setting and quality improvement of ASCENT.

From the perspective of machine learning, $(\theta, L)$ are hyper-parameters for ASCENT, just like the number of GNN layers in some deep graph clustering baselines (e.g., GAP, SDCN, MinCutPool, DMoN, and DGCluster in our experiments). Moreover, the constant correction $\tau$ in RSC, SCORE+, and ISC can also be considered as a tunable hyper-parameter. Since graph clustering is a typical unsupervised task, one can tune hyper-parameters of a method (e.g., ASCENT and other graph clustering baselines) using the unsupervised conductance metrics. Concretely, we computed the conductance metrics w.r.t. the clustering results given by different hyper-parameter settings and then selected the setting with minimum conductance. During the revision, we have added the aforementioned details in the last paragraph of Section 5.1. We have further provided results of parameter analysis in Fig. 3 and Fig. 4.

Please also note that our ASCENT method can achieve significant improvement in some cases, e.g., improvement of more than ~3% on LFR-2 and ~5% on ogbn-Protein as highlighted in Table 5 and Table 8. Our main purpose of the extension of node-wise corrections (i.e., ASCENT) is to explore whether it can potentially achieve better clustering quality, which has not been considered by most existing methods. To some extent, our experiments validate such a possibility and provide some interesting phenomena as you mentioned in S3.

Therefore, we believe that ASCENT is a good beginning to consider node-wise corrections $\{ \tau_i \}$ for DCSC. As summarized in Appendix J, we plan to consider an advanced extension with learnable $\{ \tau_i \}$, instead of manually setting them by adjusting $\{ \theta, L\}$ in our future work.

Dear Reviewer VrzY,

We sincerely thank you for summarizing the strengths of our paper. In addition, we have also tried our best to make a major revision of our paper according to your concerns and suggestions on the weaknesses.

---

W1. The theoretical results on the mis-clustered volume (i.e. Theorem 3 and Theorem 8) are nearly identical to Theorem 1 and Theorem 5 in the paper Fangmeng Liu et al. ... it would benefit from further clarification on how it advances the existing literature.

Response to W1: Thank you for providing a related work on RSC. After checking the paper you mentioned, we conclude that our analysis is more generic than this work. As summarized at the beginning of Section 3, we adopt ISC as an example for analysis, which has a more generic formate than RSC. During the revision, we have further provided a new upper bound for conductance $\phi (C_r)$ in Theorem 8, besides that of mis-clustered volume $\mu (C_r \Delta {\hat S}_r)$. In contrast, the paper you mentioned only does not include such analysis.

To demonstrate the generality of our analysis, we have also provided further analysis on DCSC in Appendix F, where we reduced our main theoretical results to NJW, RSC, and SCORE+. In this sense, our analysis serves as a unified framework involving a series of spectral clustering algorithms. Based on this framework, we further try to answer three questions. (i) Why can ISC potentially outperform RSC? (ii) When can a DCSC algorithm (e.g., RSC) potentially outperform vanilla spectral clustering (i.e., NJW)? (iii) When can ASCENT potentially outperform ISC?

To the best of our knowledge, most existing studies (including the paper you mentioned) do not include the aforementioned generic analysis. During the revision, we have adopted your suggestion to cite the paper you mentioned in Section 1 and highlighted the aforementioned contributions beyond it.

Please also note that in addition to our analysis, we also proposed ASCENT, an extension of DCSC with node-wise corrections $\{ \tau_i \}$ and explored its potential to achieve better clustering quality. To the best of our knowledge, we are the first to consider DCSC with node-wise corrections $\{ \tau_i \}$ determined by the mean aggregation mechanism of GNNs. In particular, ASCENT reduces to existing DCSC methods (e.g., ISC) when encountering the over-smoothing of mean aggregation.

We really hope that you can re-evaluate our paper by comprehensively considering our contributions, including the unified analysis and the extension of DCSC (i.e., ASCENT).

Dear Reviewer VrzY,

We sincerely appreciate your feedbacks regarding our responses and revisions.

Please note that Theorem 8 is the analysis on ISC (i.e., a conventional method with a constant $\tau$) but not on ASCENT (i.e., our extension with node-wise corrections). Therefore, we do not expect that Theorem 8 can interpret the benefits of ASCENT with node-wise corrections.

Instead, we have provided an improved analysis for ASCENT with node-wise corrections in Proposition 9 (of the revised paper), where we define $\hat \tau_r := {\max}\{ \tau_i | v_i \in \hat S_r \}$ for each cluster $\hat S_r$. Since different nodes $\{ v_i \}$ may have different $\{ \tau_i \}$, different clusters $\{ \hat S_r \}$ may further have different $\{ \hat \tau_i\}$. More importantly, based on Proposition 9, we further tried to answer the question: when can ASCENT potentially outperform ISC? in Appendix F and showed that it is possible for ASCENT to outperform ISC. In this sense, we strongly believe that our analysis can help interpret the benefits of node-wise corrections.

Regarding the condition and assumption of Theorem 8, we would kindly highlight that almost all the theoretical studies on DCSC (including those based on random graph models like DCSBM) have very similar conditions. For instance, the well-known DCSBM-based analysis on RSC [1] should first satisfy $[K\ln (4N/\varepsilon )/(\delta + \tau )] \le {\lambda _K}/(8\sqrt 3 )$ for a sufficiently large number of nodes $N$. It may also be rather strict to satisfy this condition as you mentioned, especially for a sufficiently large $N$. However, this paper was still accepted by a top-tier venue and has become a very famous work with high citations.

In summary, we strongly believe that our paper is a good beginning for its spectral-based analysis on DSCC and extension with node-wise corrections. Also as summarized in Appendix J, some new theoretical results on the combinatorial optimization problem of graph-cut minimization can help relax the assumption.

We really hope that you can re-evaluate our paper by comprehensively considering our (i) unified theoretical analysis for a series of spectral clustering algorithms (i.e., NJW, RSC, SCORE+, ISC, and ASCENT) in Appendix F and (ii) novel extension of DCSC with node-wise corrections (i.e., ASCETN), instead of just focusing on the condition on $\Psi$ in one theorem.

[1] Qin et al. Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel.

Q4. The paper states that the upper bound depends on a quantity that indicates the weak clustering structure. However, this is not convincing to me, especially using a relatively loose upper bound for $\Psi$ to explain this ... From the definition of $\Psi$, it only depends on $1 - \lambda_{K+2}$, and I don't think we can infer that $1 - \lambda_{K+2}$ is comparable to $1 - \lambda_{K+1} / \lambda_K$.

Response to Q4: Thank you for your question regarding the physical meaning of $m_K$ in $\Psi$ (i.e., how the impact of the weakness of clustering structures is considered in our analysis). Please note that by using the properties of eigenvalues (i.e., $1 > {\lambda_K} \ge {\lambda_{K+1}} \ge {\lambda_{K+2}}$), we can rigorously ensure that $(1 - \lambda_{K+2}) \ge (1 - \lambda_{K+1} / \lambda_K)$. In this sense, it is comparable.

In our main theoretical results (i.e., Theorem 8), we have $\Psi : = {(1 - {\lambda _{K + 2}})^{ - 1}}[1 - {d_{\min }}(1 - {{\bar \phi }_K}(g))/({d_{\max }} + \tau )]$.

Let $\Psi ': = {(1 - {\lambda _{K + 1}}/{\lambda _K})^{ - 1}}[1 - {d_{\min }}(1 - {{\bar \phi }_K}(g))/({d_{\max }} + \tau )]$.

The upper bound in Theorem 8 can then be formulated as

$\mu ({C_r}\Delta {\hat S_r}) \le {\rm{sth}} \cdot\Psi \le {\rm{sth}}\cdot \Psi'$,

where $\Psi'$ is directly related to the weakness of clustering structures. In particular, weaker clustering structures will result in a smaller value of ${\rm{sth}}\cdot \Psi'$ and thus will restrict ${\rm{sth}}\cdot \Psi$ to a smaller value (i.e., lower upper bound of $\mu (C_r \Delta \hat S_r)$). In this sense, our analysis can reveal the impact of the weakness of clustering structures to the clustering quality measured by $\mu ({C_r}\Delta {\hat S_r})$.

We really hope that the aforementioned interpretations can help you better understand how the impact of the weakness of clustering structures is considered in our analysis.

---

Q5. In Lemma 4, why are the eigenvectors compared to the columns of the orthogonal matrix ${\bf{O}}$? shouldn't they be compared to the columns in ${\bf{G}}$, as they are in Theorem 3?

Response to Q5: Please note that Lemma 4 is derived based on the clustering cost (2) and Eq. (8), as highlighted in Fig. 1 of the revised paper. In particular, Eq. (8) is a rewritten form of the first term of (7) in Theorem 3, which replaces each element ${\bf{G}}_{ir}$ of ${\bf{G}}$ with $[d_i / \mu (\hat S_r) ]^{0.5}$. Therefore, we do not need to include ${\bf{G}}$ in Lemma 4. Instead, $({\bf{o}}_1, \cdots, {\bf{o}}_K)$ from the orthogonal matrix ${\bf{O}}$ can be considered as cluster centers in KMeans clustering. In contrast, ${\bf{G}}$ is used to encode the optimal solution of conductance minimization but not the cluster centers of KMeans.

We really hope that our revisions and explanations can help better understand the key ideas of Lemma 4.

Q1. Is it possible to consider alternative optimization objectives other than conductance minimization, which might yield an optimal solution that is closer to the output of ISC? Additionally, if we were to use SCORE+ instead of ISC, would this result in a very different upper bound?

Response to Q1: To the best of our knowledge, spectral clustering is an algorithm for a relaxed version of several graph-cut objectives, e.g., conductance minimization (or equivalently normalized cut minimization) and ratio-cut minimization, as summarized in [1]. Different objectives have different (matrix) representations ${\bf{G}}$ for the optimal solution.

For instance, we have ${\bf{G}}_{ir} = [d_i / \mu (\hat S_r)]^{0.5}$ if $v_i \in \hat S_r$

and ${\bf{G}}_{ir} = 0$ otherwise for conductance minimization in our paper.

In contrast, we have ${\bf{G}}_{ir} = 1/ |\hat S_r|$ if $v_i \in \hat S_r$

and ${\bf{G}}_{ir} = 0$ otherwise for ratio-cut minimization.

Despite such a difference, we believe that our analysis can be easily extended to another graph-cut objective (e.g., ratio-cut) with a different definition of ${\bf{G}}$, because the key idea of our analysis (e.g., Theorem 3) is to reformulate ${\bf{G}}$ using the linear combination of orthogonal eigenvalues $\{ {\bf{u}}_i \}$. As demonstrated in [2], there are also some relations between the graph-cut minimization and modularity maximization objectives. For instance, normalized cut minimization (or equivalently conductance minimization) is equivalent to a normalized form of modularity maximization. Therefore, our analysis can also be easily extended to modularity maximization by using this relation. We plan to consider these extensions in our future work as summarized in Appendix J.

During the revision, we have also reduced our analysis on ISC to SCORE+ in Appendix F. As summarized in Table 9 (of the revised paper), SCORE+ has bounds (w.r.t. $\mu (C_r \Delta \hat S_r)$ and $\phi (C_r)$) very similar to those of ISC. In this sense, SCORE+ does not result in very different upper bounds.

[1] Luxburg et al. A Tutorial on Spectral Clustering.

[2] Yu et al. Network Community Discovery: Solving Modularity Clustering via Normalized Cut.

---

Q2. Is it correct to select the first eigenpairs of the Laplacian matrix when the eigenvalues are ordered in a decreasing order? ...

Response to Q2: Please not that our analysis follows the original standard procedure of a DCSC algorithm (e.g., ISC). Namely, using the leading largest eigenvalues is the original design of the algorithm we analyze. Thank you for pointing out such a potential limitation regarding eigenvalues, which may be a common limitation for most existing spectral clustering approaches.

Please note that our extension of DCSC (i.e., ASCENT) focuses on the assignment of node-wise corrections and follows the standard steps of an existing DCSC algorithm (i.e., eigen-decomposition, spectral embedding arrangement, normalization, and KMeans clustering of ISC). In this sense, any possible solution to this limitation of an existing DCSC algorithm (e.g., considering the absolute values of eigenvalues) can also be a solution to ASCENT. We plan to address this potential limitation in our future work.

---

Q3. I don't understand why the clustering cost function include $d_i$ in front of $|{\bf{\tilde F}}_i - {\bf{w}}_r|$. It seems more intuitive to consider simply sum of $|{\bf{\tilde F}}_i - {\bf{w}}_r|$, which aligns with the K-means objective. Additional explanation of this choice would be helpful.

Response to Q3: To help you better understand why we used $d_i |{\bf{\tilde F}}_{i,:} - {\bf{w}}_r|$, we have given the full proof of Lemma 4 in Appendix C of the revised paper.

The major reason is that for the matrix representation $\bf{G}$ of the optimal solution, we have ${\bf{G}}_{ir} = (d_i / \mu(\hat S_r))^{0.5}$ if $v_i \in {\hat S}_r$. In the 3rd line from the bottom of Appendix C, we can (i) eliminate the $d_i$ in $\bf{G}$

and further (ii) extract $\mu (\hat S_r)$ from ${\bf{G}}$ by using the $d_i$ in $d_i |{\bf{\tilde F}}_{i,:} - {\bf{w}}_r|$, in order to complete the proof of Lemma 4 based on Theorem 3 and Eq. (8).

As highlighted in Definition 2, by assuming that for each node $v_i \in V$, all the $d_i$ copies of ${\bf{\tilde F}}_{i,:}$ are contained in one of $\{ S_1, \cdots, S_K \}$, this cost function reduces to the standard KMeans cost.

Another advantage of this cost is that it can be directly used to formulate overlapping graph clustering, where each node may belong to multiple clusters. In general, disjoint graph clustering (considered in this paper) is a special case of overlapping graph clustering.

We really hope that our revisions and explanations can help you better understand the reason of using $d_i |{\bf{\tilde F}}_{i,:} - {\bf{w}}_r|$.

W4. Regarding the ASCENT algorithm, the motivation behind iteratively updating the degree correction term for each node is unclear ... it remains unclear what the number of iteration should be in practice, and the accuracy is only slightly improved as shown in Figure 2 ...

Response to W4: Thank you for your comments regarding the motivation, parameter setting (e.g., $L$), and quality improvement of ASCENT.

Please note that as described in the 1st paragraph of Section 4, most existing DCSC methods use the 'average/mean' of degrees as their constant correction $\tau$ (e.g., $\tau := \bar d$ and $\delta (d_{\min} + d_{\max})/2$ for RSC and ISC as summarized in Table 1). In this sense, the constant $\tau$ can be considered as a global average of degrees. Based on this interpretation of $\tau$, it is interesting to consider a local average of degrees w.r.t. the local topology of each node, which can be computed by iteratively applying the GNN mean aggregation defined in (12). In summary, the motivation of iteratively updating degree corrections via the mean aggregation is that it can compute the local average w.r.t. the local topology of each node, which serves as a special case of the global average in conventional DCSC methods with a constant $\tau$.

From the perspective of machine learning, $(\theta, L)$ are hyper-parameters for ASCENT, just like the number of GNN layers in some deep graph clustering baselines (e.g., GAP, SDCN, MinCutPool, DMoN, and DGCluster in our experiments). Moreover, the constant correction $\tau$ in RSC, SCORE+, and ISC can also be considered as a tunable hyper-parameter. Since graph clustering is a typical unsupervised task, one can tune hyper-parameters of a method (e.g., ASCENT and other graph clustering baselines) using the unsupervised conductance metrics. Concretely, we computed the conductance metrics w.r.t. the clustering results given by different hyper-parameter settings and then selected the setting with minimum conductance. During the revision, we have added the aforementioned details about hyper-parameters tuning in the last paragraph of Section 5.1.

Please also note that ASCENT can achieve significant improvement in some cases, e.g., improvement of more than ~3% on LFR-2 and ~5% on ogbn-Protein as highlighted in Table 5 and Table 8. Our main purpose is to consider an extension of node-wise corrections (i.e., ASCENT) and explore whether it can potentially achieve better clustering quality, which has not been considered by most existing methods. To some extent, our experiments validate such a possibility and provide some interesting phenomena. Therefore, we believe that ASCENT is a good beginning to consider node-wise corrections $\{ \tau_i \}$ for DCSC. As summarized in Appendix J, we plan to consider an advanced extension with learnable $\{ \tau_i \}$, instead of manually setting them by adjusting $\{ \theta, L\}$ in our future work.

W3. I am concerned that the condition required for in Theorem 8 might be too stringent and challenging to satisfy for high degree heterogeneity case...

Q6. In Theorem 8, the upper bound holds when $\Psi \le 1/[132(1+\lambda_1)^2\alpha K {\tilde\mu}]$ ... In this case, if $n{{\bar \theta }^2} \to \infty$ or $\bar d \to \infty$, then ${\lambda _{K + 2}} = O(1)$ and $\Psi \approx 1$. Given these, I am concerned about whether the condition can be satisfied under high degree heterogeneity.

Response to W3 & Q6: To the best of our knowledge, node degrees in most real-world graphs follow the typical power-law distributions, where only a very few nodes have large degrees and most nodes have relatively small degrees. In this sense, it is very extreme and rare that $\bar d \to \infty$ even for high degree heterogeneity (i.e., large $d_{\max}$ and small $d_{\min}$). For instance, we have $(d_{\min}, d_{\max}, {\bar d}) = (1, 28754, 5.3)$ and $(1, 14815, 17.35)$ for Youtube and LiveJournal, which are famous large-scale graphs from SNAP. The statistics of datasets in our experiments as summarized in Table 3 and some studies on large-scale complex systems (e.g., World Wide Web [1,2]) also verify this phenomenon. Therefore, your concern about $\bar d \to \infty$ may be rare in real applications.

We are sorry for the insufficient explanations regarding the condition of $\Psi$ in Theorem 8. During the revision, we have adopted your suggestion to provide additional explanations at the end of Section 3. In fact, the condition of $\Psi$ indicates an implicit assumption of our analysis that (i) $G$ is well-clustered and (ii) the degree heterogeneity is not so high.

In some early studies on vanilla spectral clustering (e.g., Peng et al. and Mizutani et al. in our paper), a graph is defined to be well-clustered if $\bar \phi_K(G) / (1 - \lambda_{K+1})$ is sufficiently small. The well-clustered assumption adopted by Peng et al. and Mizutani et al. indicates that the optimal solution $(\hat S_1, \cdots, \hat S_K)$ (i.e., clustering ground-truth in real applications) describes an explicit clustering structure of $G$. Our analysis can be considered as a unified extension of these early studies.

It is still possible that this condition may not hold when the degree heterogeneity is very high. To the best of our knowledge, most related analysis on spectral clustering cannot avoid including similar conditions that may not always hold. For instance, the well-known DCSBM-based analysis on RSC [3] should first satisfy $[K\ln (4N/\varepsilon )/(\delta + \tau )] \le {\lambda _K}/(8\sqrt 3 )$ for a sufficiently large number of nodes $N$. It may also be stringent and challenging to satisfy this condition, especially for a sufficiently large $N$.

Please also note that $\tau$ in DCSC can help resist the impact of high degree heterogeneity to the condition:

$\Psi \le 1/[132(1+\lambda_1)^2\alpha K {\tilde\mu}]$,

$\Psi := {(1 - {\lambda _{K + 2}})^{ - 1}}[1 - \tilde d(1 - {{\bar \phi }_K}(G))]$,

with $\tilde d: = {d_{\min }}/({d_{\max }} + \tau )$.

A larger $\tau$ can result in smaller eigenvalues $\lambda_{K+2}$ and $\lambda_1$, which can further let the left part of the inequality become smaller and the right part become larger. In this case, this inequality is more likely to hold.

Also as summarized in Appendix J of the revised paper, we plan to further improve this condition by extending some new theoretical results on the combinatorial optimization problem of graph-cut minimization (e.g., conductance minimization in this paper) to DCSC.

[1] Kleinberg et al. The Web as a Graph: Measurements, Models, and Methods.

[2] Barabási et al. Emergence of Scaling in Random Networks.

[3] Qin et al. Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel.

Dear Reviewer g4ng,

We sincerely thank you for summarizing the strengths of our paper. In addition, we have also tried our best to make a major revision according to your comments and suggestions on the weaknesses.

---

W1. The theoretical contributions of the paper could be presented more clearly ... I suggest adding a high-level overview of the theorems and lemmas to clarify their roles in the analysis before diving into the details.

Response to W1. Thank you for your suggestion regarding the presentation of our analysis. During the revision, we have adopted your suggestion to add an overview about the logical flow from Theorem 3 to Theorem 8 in Fig. 1 and briefly introduce the key idea of proof after introducing a theorem or lemma in Section 3. For instance, the key idea to prove Theorem 3 is to reformulate the matrix representation ${\bf{G}}$ of the optimal solution using the linear combination of orthogonal eigenvectors $\{ {\bf{u}}_i\}$. Theorem 7 is proved by contradiction using the upper and lower bounds given by Theorem 5 and Theorem 7, respectively. We really hope that our revisions can help you better understand the logical flow of our analysis.

---

W2. I am uncertain how useful the main result (Theorem 8) since the recovery accuracy by spectral clustering without a model assumption is still unknown.

Response to W2. It is well known that spectral clustering adopts a relaxed version of the NP-hard combinatorial optimization objective of conductance minimization. To the best of our knowledge, to provide bonds regarding the feasible solution given by an algorithm (e.g., $(C_1, \cdots, C_K)$ of ISC) w.r.t. the optimal solution (e.g., $(\hat S_1, \cdots, \hat S_K)$ of conductance minimization) is a widely-used strategy in the analysis of many combinatorial optimization problems on graphs. For instance, we have $\rm{OBJ} \le \gamma {\rm{OPT}}$ (i.e., $\gamma$-approximation) for some well-known algorithms of traveling salesman problem (TSP) based on minimum spanning tree [1,2], with OBJ and OPT as objective values of (i) feasible solution given by the algorithm and (ii) optimal solution. Since spectral clustering is an approximated algorithm for the NP-hard conductance minimization problem, it is straightforward to adopt this strategy for our analysis of DCSC. Some early studies on vanilla spectral clustering (e.g., Peng et al. and Mizutani et al. in our paper) also follow this strategy. Our analysis can be considered as a unified extension of these early studies.

Please also note that the mis-clustered volume $\mu (C_r \Delta {\hat S}_r)$ in Theorem 8 is consistent with the accuracy metric of graph clustering. Following the same renumbering of $(C_1, \cdots, C_K)$ in Theorem 8, the clustering accuracy is defined as $\sum\nolimits_{r = 1}^K {|{C_r} \cap {{\hat S}_r}|} /N$. In particular, we have ${C_r} \cap {\hat S_r} = {C_r} \cup {\hat S_r} - {C_r}\Delta {\hat S_r} \le V - {C_r}\Delta {\hat S_r}$ and thus lower mis-clustered volume $\mu (C_r \Delta {\hat S}_r)$ indicates higher clustering accuracy.

During the revision, we have also reduced our analysis to NJW, RSC, AND SCORE+ in Appendix F. It extends our analysis to a unified framework involving a series of spectral clustering. Based on this framework, we further tried to answer the following questions. (i) Why can ISC potentially outperform RSC? (ii) When can a DCSC algorithm (e.g., RSC) potentially outperform vanilla spectral clustering (i.e., NJW)? (iii) When can ASCENT potentially outperform ISC? This extension can also be considered as a significant contribution of our analysis. In contrast, most existing analysis only focuses on one specific algorithm (e.g., RSC).

We really hope the aforementioned explanations can help you better understand that our analysis is useful, especially from the perspective of combinatorial optimization.

[1] Laporte et al. The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms.

[2] Pop et al. A Comprehensive Survey on the Generalized Traveling Salesman Problem.

W2. Since $\Psi$ needs to be lower than $\mu_{\min}/(132 (1+\lambda_{1})^2 \alpha K \mu_{\max})$, when this is satisfied? ... the analysis of heterogeneity carries this assumption ... you still have some assumptions for the graph. Thus, you need to clarify what this assumption is.

Response to W2: We are sorry for the insufficient explanations regarding the condition of $\Psi$ in Theorem 8. During the revision, we have adopted your suggestion to give additional explanations regarding the assumption it implies at the end of Section 3.

Concretely, to ensure that the condition $\Psi \le 1/[132(1+\lambda_1)^2\alpha {\tilde \mu} K]$ holds, we need small $\bar \phi_K (G) / (1 - \lambda_{K+2})$ and large $d_{\min} / [(d_{\max + \tau}) (1 - \lambda_{K+2})]$. In some early studies on vanilla spectral clustering (e.g., Peng et al. and Mizutani et al. in our paper), a graph is defined to be well-clustered if $\bar \phi_K(G) / (1 - \lambda_{K+1})$ is sufficiently small. It is consistent with that $\bar \phi_K (G) / (1 - \lambda_{K+2})$ is small. The well-clustered assumption adopted by Peng et al. and Mizutani et al. indicates that the optimal solution $(\hat S_1, \cdots, \hat S_K)$ (i.e., clustering ground-truth in real applications) describes an explicit clustering structure of $G$. Our analysis can be considered as a unified extension of these early work. Moreover, large $d_{\min} / [(d_{\max + \tau}) (1 - \lambda_{K+2})]$ indicates that the degree heterogeneity should not be very high. In summary, the condition in Theorem 8 implies an implicit assumption that (i) $G$ is well-clustered and (ii) the degree heterogeneity is not so high.

Also as summarized in Appendix J of the revised paper, we plan to further improve this condition by extending some new theoretical results on the combinatorial optimization problem of graph-cut minimization (e.g., conductance minimization in this paper) to DCSC.

We really hope that the aforementioned explanations and our revisions can help you better understand the implicit assumption of our main theoretical results (i.e., Theorem 8).

---

Additional Rebuttal: Please note that in addition to our unified analysis on DCSC, we also proposed ASCENT, an extension of DCSC with node-wise corrections $\{ \tau_i \}$, and explored its potential to achieve better clustering quality. To the best of our knowledge, we are the first to consider DCSC with node-wise corrections $\{ \tau_i \}$ determined by the mean aggregation mechanism of GNNs. In particular, ASCENT reduces to existing DCSC methods (e.g., ISC) when encountering the over-smoothing of mean aggregation.

We really hope that you can re-evaluate our paper by comprehensively considering our contributions, including the unified analysis mentioned in our response to W1 and the extension of DCSC (i.e., ASCENT).

Dear Reviewer YKQp,

We sincerely thank you for summarizing the strengths of our paper. Besides, we have also tried our best to make a major revision according to your comments on the weaknesses.

---

W1. It is not clear how the bound is useful/non-trivial. How large the coefficient is? ... Can you say your bound is not trivial?

Response to W1: As highlighted in Theorem 8, the clustering quality measured by the mis-clustered volume $\mu (C_r \Delta \hat S_r)$ and conductance $\phi (C_r)$ is related to (i) degree heterogeneity and (ii) weakness of clustering structures. In this sense, our analysis can quantitatively reveal impacts of these two properties to the clustering quality of DCSC. It is useful, since it is consistent with the fact that the quality of a graph clustering algorithm should be affected by the several inherent properties of the graph to be partitioned (e.g., degree heterogeneity and weakness of clustering structures).

It is well known that spectral clustering adopts a relaxed version of the NP-hard combinatorial optimization objective of conductance minimization. To the best of our knowledge, to provide bonds regarding the feasible solution given by an algorithm (e.g., $(C_1, \cdots, C_K)$ of ISC) w.r.t. the optimal solution (e.g., $(\hat S_1, \cdots, \hat S_k)$ of conductance minimization) is a widely-used strategy in the analysis of many combinatorial optimization problems on graphs. For instance, we have $\rm{OBJ} \le \gamma {\rm{OPT}}$ (i.e., $\gamma$-approximation) for some well-known algorithms of traveling salesman problem (TSP) based on minimum spanning tree [1,2], with OBJ and OPT as objective values of (i) feasible solution given by the algorithm and (ii) optimal solution. Since spectral clustering is an approximated algorithm for the NP-hard conductance minimization problem, it is straightforward to adopt this strategy for our analysis of DCSC. Some early studies on vanilla spectral clustering (e.g., Peng et al. and Mizutani et al. in our paper) also follow this strategy. Our analysis can be considered as a unified extension of these early studies.

During the revision, we have also reduced our analysis to NJW, RSC, AND SCORE+ in Appendix F. It extends our analysis to a unified framework involving a series of spectral clustering. Based on this framework, we further tried to answer the following questions. (i) Why can ISC potentially outperform RSC? (ii) When can a DCSC algorithm (e.g., RSC) potentially outperform vanilla spectral clustering (i.e., NJW)? (iii) When can ASCENT potentially outperform ISC? This extension can also be considered as a significant contribution of our analysis. In contrast, most existing analysis (including the work you mentioned) only focuses on one specific algorithm (e.g., RSC).

We really hope that the aforementioned explanations can help you better understand that our analysis is useful, especially from the perspective of combinatorial optimization.

[1] Laporte et al. The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms.

[2] Pop et al. A Comprehensive Survey on the Generalized Traveling Salesman Problem.

During the rebuttal period, we have also taken a great amount of efforts to give responses and revise our papers according to suggestions and concerns of all the reviewers. The major revisions to address reviewers' concerns are summarized as follows.

• New Theoretical Results to Demonstrate the Advantages of Node-Wise Corrections (in ASCENT). We have replaced Proposition 9 and Theorem 10 in the previous version with an improved analysis (cf. Proposition 9 in the revised paper) using cluster-wise corrections $\{ \hat \tau_i \}$. Since different nodes $\{ v_i \}$ in ASCENT may have different corrections $\{ \tau_i \}$, different clusters $\{ \hat S_r \}$ have also have different $\{\hat \tau_i\}$. We have also answered the question: when can ASCENT potentially outperform ISC in Appendix F and showed that it is possible for ASCENT (with node-wise corrections) to outperform ISC (with a constant correction). Most reviewers did not raise further concerns about this revision. However, it seems that Reviewer VrzY ignored this revision and simply reached a conclusion that 'there is no substantial difference from the previous work'.

• Further Complexity and Efficiency Analysis to Show the Impact of Node-Wise Corrections Derivation. We have provided additional complexity analysis in Appendix G and efficiency analysis in Appendix I, which demonstrate that the derivation of node-wise corrections will not increase the overall complexity and is also not the bottleneck of ASCENT. Reviewers did not raise further concerns about this revision.

• Further Explanations about the Condition of $\Psi$ in Main Theoretical Results. We have given further explanations about the condition of $\Psi$ and corresponding assumptions in Section 3 (after Theorem 8). Some reviewers have raised further concerns that this condition of $\Psi$ is strict. We would kindly highlight that almost all the theoretical studies on DCSC have very similar conditions. Some of these papers were still accepted by top-tier venues and have achieved high citations. We really hope that you can understand that it is extremely difficult or even impossible to avoid any conditions in a theoretical analysis. We have also adopted the suggestion of some reviewers to discuss some future directions to improve this condition in Appendix J.

• Compromise about the Presentation. We have also comprehensively adopted suggestions from all the reviewers to adjust the presentation of our paper. We really hope that people with different backgrounds may have different opinions about the presentation of a paper with rigorous theoretical analysis. We have tried our best to make a compromise among all the reviewers' comments regarding the presentation.

Our responses to clarify the misunderstanding of reviewers are summarized as follows.

• Motivations of Using GNN Mean Aggregation for Node-Wise Corrections. We have highlighted that existing DCSC algorithms use the global average node degree to set the constant correction \tau&. In contrast, ASCENT adopts *local average degrees w.r.t. local topology of each node* via the GNN mean aggregation to set node-wise corrections \tau_i$. As the number of iterations increases, local average degrees will finally reduce to the global average degree due to over-smoothing. Reviewers did not raise further concerns about this revision.

• Quality Improvement of ASCENT. We have highlighted that ASCENT can achieve significant quality improvement (e.g., more than ~3% on LFR-2 and ~5% on ogbn-Protein as in Table 5 and Table 8) compared with conventional DCSC baselines in some cases. Reviewers did not raise further concerns about this revision.

---

In summary, we believe that our revisions and responses have addressed most of the concerns. However, it seems that some reviewers just simply ignore most of our contributions, responses, and revisions, especially our efforts in the rebuttal peroid, lacking a comprehensive evaluation of our paper.