New Recipe for Semi-supervised Community Detection: Clique Annealing under Crystallization Kinetics

W1.1+Q2. Loss function order mix-up and typo.

We appreciate your observation regarding the order mix-up error. We have rectified the error and the typo in the revised manuscript with blue color.

W1.2. Concern about missing promising patterns.

Thanks for your thoughtful feedback on the predefined overflow states and their potential limitations in accommodating promising patterns. Below, we provide clarification to address this concern.

1. Definition of Overflow States: The undergrown, equilibrium, and overgrown states are not arbitrarily predefined by our method. Instead, they are derived directly from the labeled communities, which represent expert-labeled classifications of community growth dynamics and are therefore grounded in the structure and semantics of the labeled dataset. By using these states as references, the model aligns well with real-world patterns observed in the training data.

2. Role of the Integrity-Based Loss: The Integrity-Based Loss leverages these labeled states to train a classifier that predicts the growth status of subgraphs. This approach ensures that the model's predictions are consistent with the expert-labeled community structures and allows for robust guidance during the Transitive Annealer process.

3. Handling Patterns like $a + \breve{a}$: Suppose node-1 is the community core of $a$, while node-2 is the core of a community that covers $a + \breve{a}$. For the growth process starting from node-1, $a + \breve{a}$ can be classified as an overgrown state. However, for growth starting from node-2, it is considered as an equilibrium state, our model can thus include these promising candidates by considering different start points during the annealing process.

W2.1. Two-stage training scheme.

After training the Energy-Based, Consistency-Based, and Interface-Based loss functions, we fix the graph encoder parameters. The Integrity-Based Loss training does not disrupt the learned representations. The Integrity-Based Loss is specifically designed to optimize a separate classifier that takes subgraph embeddings as input and outputs their growth status. This loss is not directly connected to the optimization of the graph encoder but instead focuses on facilitating decision-making during the Transitive Annealer stage. Training the Integrity-Based Loss separately can avoid additional constraints or conflicting objectives on the graph encoder during the first stage.

W2.2+Q1. Loss Contribution.

Thank you for highlighting this point. The interaction of the three losses during joint training contributes to the observed result. These losses interact dynamically, and their combined contribution to the final performance is not a linear sum of individual ones. When the three losses are trained together, adjustments to one loss's weight can lead to performance fluctuations due to these interactions, we thus can hardly conclude that one loss function is entirely invalid or dominant.

As mentioned before, the Integrity-Based Loss, while not directly optimizing representation quality, serves a specialized role in guiding the stopping criteria during the growth process of the Transitive Annealer. This loss ensures robust and consistent growth of community structures by providing a clear indicator for terminating growth states. Its contribution lies in improving interpretability and the overall scalability of the annealing process, rather than directly enhancing network representation. Removing or simplifying these losses may inadvertently compromise this robustness, particularly in datasets with diverse community characteristics.

W3.1. Statement about superior scalability.

Thank you for highlighting this issue. Since the Clique Preparation phase is the most time-intensive part of CLANN, we focused on optimizing its efficiency. After thoroughly reviewing the code, we introduced a preprocessing step to eliminate unnecessary operations, significantly enhancing the efficiency of the clique preparation module. We also replaced the result in the revised version. The new source code can be found in an anonymous GitHub repository at https://anonymous.4open.science/r/CLANN_ICLR2025-51D0/README.md.

Here we provide the runtime improvement based on our new code:

Table 1. Runtime Improvement

Could please acknowledge and respond to the rebuttal.

We appreciate the your insightful comment regarding the validity of physical analogy, adaptability, and sensitivity analysis. Please see our detailed one-by-one responses below.

W1+Q1. Questionable Validity of Physical Analogy

Energy minimization principles from physics have been effectively applied to network community detection. In previous reference in Global Response1, maximizing modularity corresponds to minimizing system energy for stable community partitioning. Our study extends this link by showing that optimizing energy-based loss functions aligns with modularity optimization, resulting in reasonable community configurations (Page 14-15, Section A). Please refer to our reply in Global Response 1 for more detailed explanation.

W2. Insufficient Explanation of Crystallization Dependency

Inspired by the analogy between crystallization and community detection, we leverage crystallization principles in CLANN to address two key challenges: community core inconsistency and growth scalability. Specifically, among the four crystallization principles:

1. The stability principle ensures that cores remain compact and representative;
2. The cohesion principle promotes strong internal connections within communities;
3. The growth analogy helps overcome barriers to meaningful expansion;
4. The equilibrium principle prevents overgrowth or fragmentation.

These principles are seamlessly integrated into CLANN's loss functions, such as an energy-based loss to encourage cohesive embeddings and an interface-based loss to regulate expansion. This approach achieves enhanced consistency and scalability in community detection without relying on complex mechanisms like GANs or reinforcement learning. Moreover, we provide a crystallization video in an anonymous GitHub repository in Global Response 1.

W3+Q4. Limited Adaptability to Different Network Structures and Non-Clique Structures

We employed extra network datasets to demonstrate our CLANN's effectiveness. Concretely, we conducted experiments on 43 (7(Section 6 - Setting 1) + 15(Section 6 - Setting 2) + 6 (6 Bipartite Networks without Cliques) + 15 (Non-clique, Sparse, Noisy Networks)) different networks. Here we also provide the results of CLANN's performance on newly introduced Non-Clique, Sparse, and Noisy networks as shown below. The detailed results and analysis can be found in the common response Global Response 2.

Table 1. CLANN's F1 Performance Across 3 New Scenarios

W4+Q2+Q3. Lack of Theoretical Analysis and insufficient sensitivity analyses for hyperparameters, detailed time complexity analysis

Thanks for your valuable feedback. We agree that convergence proofs and complexity analyses for the Transitive Annealer, as well as sensitivity analyses for hyperparameters, are critical for a comprehensive understanding of the method. Here we provide brief explanation, for more detailed responses, please refer to our reply in Global Response 3 and 4 .

• For Complexity Analysis: We have included a detailed complexity analysis in Appendix C, showing that the time complexity of the entire framework is $O(N^2)$. The analysis breaks down the computational steps of the Preliminary Core Filter, Nucleus Proposer, and Transitive Annealer, demonstrating their efficiency in large-scale settings.
• For Convergence: Regarding convergence, the Transitive Annealer is designed to terminate in at most $M$ steps, where $M$ is the maximum number of iterations. Empirical results in Section 6.4 confirm that the annealer converges within 3 iterations in the vast majority of cases. This is supported by the case visualizations in Figure 6.
• For Hyperparameter Analysis: In Section 6.5, we have conducted a sensitivity analysis of the 3 loss weights for the energy-based, interface-based, and consistency-based losses. In Appendix I, we studied the impact of the candidate size rate to analyze the quality of candidates selected by Nucleus Proposer.

Could please acknowledge and respond to the rebuttal.

Dear Reviewer hnzb:

We would like to express our sincere gratitude for your time in reviewing our paper and your valuable comments.

Since the revision submission period is nearing its end, we are wondering whether our response has sufficiently addressed your questions. If you have any additional suggestions, we are more than willing to engage in further discussions and make necessary improvements to the paper.

Thank you once again for dedicating your time to enhancing our paper!

All the best,

Authors

Dear Reviewer hnzb,

Since the End of author/reviewer discussions is coming in ONE day, may we know if our response addresses your main concerns? If so, we kindly ask for your reconsideration of the score. Should you have any further advice on the paper and/or our rebuttal, please let us know and we will be more than happy to engage in more discussion and paper improvements.

Thank you so much for devoting time to improving our paper!

Thank you very much for the constructive comments and questions. We are grateful for the positive comments on the novelty of design and empirical justification. Please see our detailed one-by-one responses below.

W1+Q1. More simplified explanations or visual aids of analogy

To help reader to understand crystallization process better, we upload a visualization video to an anonymous GitHub repository in Global Response (Part 1). This video shows taht the crystallization process starts from some specific points (community cores in our case). By growing and merging (merging cliques in our case), the sub-grains grow into bigger crystalline structures (final communities in our case).

W2. Expensive computational of clique enumeration and limited applicability to extremely large graphs.

Thanks for the constructive comments. To validate the our model's efficiency, we conducted detailed computational complexity analysis in Appendix Section C, and runtime analysis in Section 6.4 and Appendix Section J. Also, please refer to our reply in Global Response 4 about Computational Efficiency for more detailed response.

W3. More real-world networks with varying characteristics may benefit the generalization.

Thank you very much for the constructive comments. To validate the effectiveness, we conducted extra network datasets to demonstrate our CLANN's effectiveness. Concretely, we conducted experiments on 43 (7(Section 6 - Setting 1) + 15(Section 6 - Setting 2) + 6 (6 Bipartite Networks without Cliques) + 15 (Non-clique, Sparse, Noisy Networks)) different networks. The detailed results and analysis can be found in the Global Response 2.

W4. Lack of some implementation details.

Thanks for pointing out this problem. Most of the implementation detail are provided in Appendix H**. As noted, all experiments were conducted on an AMD EPYC 7763 64-core Processor with 256GB of memory and a single NVIDIA RTX A5000 GPU (24GB memory). The overall size of the model (104,783 parameters, 424KB checkpoint size) and the average runtime for datasets of varying scales (reported in Table 6 and Figure 10) indicate the model’s computational efficiency.

Q2. How does CLANN compare with simpler heuristic-based community detection methods in terms of performance and resource consumption?

In the original submission, we provide the performance comparison with traditional unsupervised methods in Table 13 (Setting 1), and 15 (Setting 2). In the revised version, we also provide the runtime comparison in Table 14 (colored by blue). We put the performance and runtime comparison under Setting 1 here.

Table 1: F1 Score Compared with Unsupervised Methods under Setting 1

• For Spectral clustering methods, the best results among DBSCAN, HDBSCAN, and OPTICS are presented.
• Est. α: Estimated α value of the degree power-law fit.
• N/A: Did not converge within 2 days.

Table 2: Runtime (in Seconds) Comparison with Unsupervised Methods under Setting 1

CLANN consistently outperforms heuristic-based methods like Louvain and Label Propagation, achieving the highest F1 scores across diverse datasets. For instance, on the Amazon dataset, CLANN scores 0.9055, significantly higher than Louvain's 0.8226. Its advantage is even more pronounced on hybrid datasets like "A/D," where it achieves 0.6578 compared to Louvain's 0.1206, showcasing its ability to handle complex community structures with superior accuracy and robustness.

Although CLANN requires more computation time, its consistant better performance justifies the trade-off. On the Amazon dataset, it achieves far better results in 112.1 seconds compared to Louvain's 0.3 seconds. Features like the Nucleus Proposer and Transitive Annealer enable efficient refinement of community structures, making CLANN an ideal choice when accuracy outweighs runtime considerations.

Could please acknowledge and respond to the rebuttal.

Dear Reviewer 4nXW:

We would like to express our sincere gratitude for your time in reviewing our paper and your valuable comments.

Since the revision submission period is nearing its end, we are wondering whether our response has sufficiently addressed your questions. If you have any additional suggestions, we are more than willing to engage in further discussions and make necessary improvements to the paper.

Thank you once again for dedicating your time to enhancing our paper!

All the best,

Authors

Dear Reviewer 4nXW,

Since the End of author/reviewer discussions is coming in ONE day, may we know if our response addresses your main concerns? If so, we kindly ask for your reconsideration of the score. Should you have any further advice on the paper and/or our rebuttal, please let us know and we will be more than happy to engage in more discussion and paper improvements.

Thank you so much for devoting time to improving our paper!

W1. The difficulties in dealing with heterogeneous connectivity structures and low degree of node density.

Thanks for your constructive comments. To demonstrate the effectiveness of CLANN in handling heterogeneous structures and low node density, we first conducted experiments on non-clique structures, focusing specifically on bipartite graphs, as shown in Appendix Section K. By replacing cliques with scatter-based cores, we tested the model on 6 datasets (3 collaboration and 3 co-purchase networks). These experiments further indicate that CLANN retains robust performance under non-clique and noisy network scenarios.

Moreover, we conducted experiments on 15 datasets (3 scenarios with 5 datasets in each) to further justify CLANN's (with scatter cores) effectiveness in diverse situations (Non-Clique, Sparse, and Noisy). Here we also provide the results of CLANN's performance on newly introduced Non-Clique, Sparse, and Noisy networks as shown below. The detailedresults and analysis can be found in the common response Global Response 2.

Table 1. CLANN's F1 Performance Across 3 New Scenarios

W2. Traverse and filter the candidate cores may require large computational resources on large datasets.

We appreciate the reviewer’s valuable feedback on the computational overhead of the candidate filtering mechanism, especially in large-scale datasets and real-time application scenarios. We would like to clarify the following points to address this concern:

• Efficiency of the Preliminary Core Filter: The Preliminary Core Filter pre-selects candidate community cores by only leveraging a lightweight classifier (input vector dimension is only 5). The standard augment feature for this filter only involves simple operations (degree calculation), which are computationally lightweight and can be performed in near real-time. This approach ensures the filtering mechanism remains efficient and scalable, even in real-time or streaming scenarios.

• Real-Time Adaptation for New Nodes: For dynamic graphs where new nodes are added, the computational requirement is further minimized. When a new node comes in, instead of recomputing all existing nodes, we only update very basic standard augment feature for the related neighbor nodes (degree-based features, Page 6 Line 272-273), because the new node only connects to a few existing nodes, which will not change the standard augment feature of most unconnected nodes.

W3. More analysis on the hyperparameters

Thanks for the constructive comments. In the real deployment, to improve model's generalizability, we do not need to set the annealing temperature threshold and transitive threshold manually. Please refer to our reply in Global Response 3 in the Global Response section above for this concern.

Q1. More explanation on Eq.9 and sensitivity analysis on $\gamma_{G}$.

Reply: We appreciate the reviewer’s observation regarding the inconsistency between Eq. 9 and the loss function in Algorithm 1. Below, we clarify this issue and explain the reasoning behind our design choices.

1. Rectification of Algorithm 1: We acknowledge the inconsistency and have rectified Algorithm 1 to align it with the explanation in the main text. Specifically, $\gamma_{G}$, which corresponds to the Integrity-Based Loss, has been removed from Algorithm 1. This adjustment reflects the fact that the Integrity-Based Loss is optimized independently and not during the main training process for the graph encoder.

2. Separate Optimization of the Integrity-Based Loss: As noted in our response to Reviewer oMJD W2.1, the Integrity-Based Loss is specifically designed to optimize a separate classifier. This classifier takes subgraph embeddings as input and outputs the growth status (undergrown, equilibrium, or overgrown). By optimizing this loss separately:

• We avoid introducing additional hyperparameters ($\gamma_{G}$) that would complicate the optimization of the graph encoder.
• The graph encoder focuses solely on optimizing the Energy-Based Loss, Consistency-Based Loss, and Interface-Based Loss, which are critical for learning robust subgraph embeddings.

Could please acknowledge and respond to the rebuttal.

Dear Reviewer pfE6:

We would like to express our sincere gratitude for your time in reviewing our paper and your valuable comments.

Since the revision submission period is nearing its end, we are wondering whether our response has sufficiently addressed your questions. If so, we would greatly appreciate it if you could consider updating the score to reflect this. If you have any additional suggestions, we are more than willing to engage in further discussions and make necessary improvements to the paper.

Thank you once again for dedicating your time to enhancing our paper!

Best regards,

Authors

Dear Reviewer pfE6,

Since the End of author/reviewer discussions is coming in ONE day, may we know if our response addresses your main concerns? If so, we kindly ask for your reconsideration of the score. Should you have any further advice on the paper and/or our rebuttal, please let us know and we will be more than happy to engage in more discussion and paper improvements.

Thank you so much for devoting time to improving our paper!