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

Authors: ling Cheng, Jiashu Pu, Ruicheng Liang, Qian Shao, Hezhe Qiao, Feida Zhu
Primary area: learning on graphs and other geometries & topologies
Keywords: Semi-supervised Community Detection, Clique, Annealing, Crystallization Kinetics

Abstract:
Semi-supervised community detection methods are widely used for identifying specific communities due to the label scarcity. Existing semi-supervised community detection methods typically involve two learning stages \ie, learning in both initial identification and subsequent adjustment, which often starts from an unreasonable community core candidate.
Moreover, these methods encounter scalability issues because they depend on reinforcement learning and generative adversarial networks, leading to higher computational costs and restricting the selection of candidates. 
To address these limitations, we draw a parallel between crystallization kinetics and community detection to integrate the spontaneity of the annealing process into community detection.
Specifically, we liken community detection to identifying a crystal subgrain (core) that expands into a complete grain (community) through a process similar to annealing. Based on this finding, we propose CLique ANNealing (CLANN), which applies kinetics concepts to community detection by integrating these principles into the optimization process to strengthen the consistency of the community core. Subsequently, a learning-free Transitive Annealer was employed to refine the first-stage candidates by merging neighboring cliques and repositioning the community core, enabling a spontaneous growth process that enhances scalability.
Extensive experiments on diverse community detection datasets demonstrate that CLANN outperforms state-of-the-art methods across multiple real-world datasets, showcasing its exceptional efficacy and efficiency in community detection.

Decision: reject
Reviewer scores: 6, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1730287860749

thread_type:
official_review

<thread_object>
creator: reviewer_omjd

<content>
summary:
This manuscript introduces CLANN, a new community detection method motivated by the kinetics crystallization process. It integrates the Nucleus Proposer to learn to detect community cores and Transitive Annealer for spontaneous growth. Extensive experiments with various settings highlight the excellence of CLANN.

strengths:
S1: The design of the method is inspired by the kinetics of the crystallization process, which provides strong motivation.

S2: Detailed formulas are used to express the approach more rigorously and scientifically.

S3: Extensive experiments are conducted to validate the method.

weaknesses:
W1: I have two key concerns about the design of the loss functions

W1.1: In equation 7, the formulation of Integrity-Based Loss is used to guide the prediction of the state of undergrown, equilibrium, and overgrown states. It is modeled as a classification problem. However, the loss function used seems not to align with the Binary Cross Entropy. 

The binary cross-entropy loss is:

$
\text{BCE}(y, \hat{y}) = - \frac{1}{N} \sum_{i=1}^N \left( y_i \log(\hat{y}_i) + (1 - y_i) \log(1 - \hat{y}_i) \right)
$

where:
- \( y_i \) is the true label (0 or 1),
- \( \hat{y}_i \) is the predicted probability of the positive class,
- \( N \) is the total number of samples. 

while the authors seem to mix up the order in the bracket:

$
\sum_{g=1}^3 \left( (y_g^k - 1) \log(\hat{y}_g^k) - y_g^k \log(1 - \hat{y}_g^k) \right)
$

W1.2: In the design of the integrity-based method, the overflow states are predefined, which limits the inclusion of many promising patterns, such as:
$(a_2 + \check{a}_2)$

===============

W2: I have two key concerns about the training process.

W2.1: A two-stage training method is used here: first, the Energy-Based Loss, Consistency-Based Loss, and Interface-Based Loss are trained together, followed by training the Integrity-Based Loss separately. This approach to multi-loss training is relatively unusual and lacks clear motivation. Won't the second loss disrupt the model trained in the first stage? How are these losses aligned?

W2.2: As seen in Figure 5, when Loss Amplification approaches 0, performance on many datasets actually improves, indicating that this loss does not enhance training and may even reduce performance (e.g., Consistency-Based Loss and Interface-Based Loss). Strangely, in the ablation study in Table 4, these losses appear to be beneficial.

===============

W3: Some claims and typos can be improved.

W3.1: The authors argue that previous reinforcement-learning-based methods face scalability issues (Line 017), and that the proposed method has better scalability compared to these approaches. CLARE itself is also a reinforcement learning-based method (Line 984). As shown in Figure 4, NP and CLANN demonstrate poorer scalability compared to CLARE. In the DBLP and LiveJournal datasets, NP and CLANN even exhibit faster growth in runtime.

W3.2: Line 157, "Propose" => "Proposer"

questions:
Given that some losses do not statistically significantly improve performance (e.g., Integrity-Based Loss), would it be possible to reduce certain losses to make the model simpler and emphasize the more effective components?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730627122154

thread_type:
official_review

<thread_object>
creator: reviewer_pfe6

<content>
summary:
The paper proposes a novel approach for semi-supervised community detection, named CLique ANNealing (CLANN), which integrates principles from crystallization kinetics with community detection. To address the issues with scalability and core selection inconsistency, CLANN introduces two main components Nucleus Proposer and Transitive Annealer, draws an analogy between community detection and crystallization, treating communities as grains growing from smaller, well-defined "clique" cores. Experiments conducted on datasets show that CLANN outperforms state-of-the-art methods in both efficacy and efficiency.

strengths:
S1: The approach of using crystallization principles, especially the spontaneous annealing process, provides a compelling and physics-informed basis for community formation.
S2: The learning-free Transitive Annealer circumvents computational issues tied to reinforcement learning, showing superior scalability over existing methods.
S3: Empirical results indicate that CLANN consistently achieves higher performance across diverse datasets, particularly excelling in detecting distinct community structures within hybrid graphs.

weaknesses:
W1: The CLANN model assumes high network density and consistency by analogizing community detection to crystallization growth. In practice, however, many graph networks (e.g., social networks, literature citation networks, etc.) may contain highly heterogeneous connectivity structures and low degree of node density, which could lead to difficulties for the annealing process to efficiently identify core or stable structures. In sparse or non-uniform networks, the use of an annealing process may lead to difficulties in forming coherent communities in the model, affecting the detection accuracy.
W2: CLANN pre-screens the candidate set by a filtering mechanism when initializing candidate community cores to improve efficiency. However, on large-scale datasets, this mechanism still requires a lot of computational resources to traverse and filter the candidate cores. Especially in real-time application scenarios, the initialization process may be too slow, affecting the application efficiency of the algorithm.
W3: For hyperparameters such as Transitive Threshold $\theta$, Temperature Prob. $P_{temp}$, further analysis is required.

questions:
Q1: Eq. 9 is not the same as the loss in Algo. 1? I think this needs more explanation. Also, at the same time the $ \gamma _G$ should be performing a parameter sensitivity analysis.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730636421856

thread_type:
official_review

<thread_object>
creator: reviewer_hnzb

<content>
summary:
In community detection, semi-supervised methods are widely used to identify specific communities; however, existing methods often rely on high-cost models like Generative Adversarial Networks (GAN) or reinforcement learning, resulting in suboptimal initial community cores and limited scalability. There are two main issues with these methods: first, community core inconsistency, as growth-based methods often start from random nodes or k-hop ego networks, which do not accurately represent the structural characteristics of the community; and second, poor growth scalability, as using GAN or reinforcement learning to increase community core candidates is computationally intensive and fails to efficiently leverage existing information, limiting the number of core candidates. To address these issues, the authors propose a community detection model, CLANN, based on annealing and crystallization kinetics. This model comprises two key components: the Nucleus Proposer, which selects completely connected subgraphs (i.e., cliques) as community cores and integrates four crystallization principles to enhance core consistency; and the Transitive Annealer, which uses a learning-free annealing mechanism to merge adjacent cliques into final communities, thereby reducing computational cost and improving scalability. Experimental results show that CLANN outperforms existing community detection methods in terms of accuracy and efficiency across multiple real-world datasets, demonstrating its effectiveness and adaptability in diverse network analysis scenarios.

strengths:
1.Innovative Approach: The paper creatively relates community detection to crystallization kinetics, introducing an annealing mechanism to enhance community core consistency and scalability with the novel CLANN model.

2.Scalability Improvement: The unsupervised Transitive Annealer significantly reduces computational complexity compared to GANs and reinforcement learning, improving performance on large-scale datasets.

3.Significant Performance Gains: Experiments show that CLANN outperforms existing methods in accuracy and efficiency across various real-world datasets, highlighting its broad applicability.

weaknesses:
1.Questionable Validity of Physical Analogy: The analogy between community detection and crystallization kinetics is debatable, particularly regarding the relevance of energy minimization in community detection.

2.Insufficient Explanation of Crystallization Dependency: The paper does not adequately clarify how the introduced crystallization principles apply to community detection and their role in model optimization.

3.Limited Adaptability to Different Network Structures: CLANN’s effectiveness on non-clique structures or noisy communities is not thoroughly assessed, raising doubts about its generalizability.

4.Lack of Theoretical Analysis: The method lacks in-depth theoretical validation, such as proofs of convergence and complexity for the Transitive Annealer, along with insufficient sensitivity analyses for hyperparameters.

questions:
1.Applicability of Physical Analogy: The analogy between community detection and crystallization lacks theoretical validation. Please clarify how crystallization principles (e.g., "stability," "cohesion") apply and impact core consistency and scalability.

2.Theoretical Support for CLANN: The model lacks theoretical analysis on convergence and complexity. Please provide complexity proof or detailed time complexity analysis, particularly for large datasets.

3.Parameter Sensitivity Analysis: The paper lacks a systematic sensitivity analysis of key hyperparameters (e.g., annealing temperature, loss weights). Please describe how performance varies with these parameters.

4.Applicability to Non-Clique Structures: CLANN’s reliance on cliques as cores raises questions about its adaptability to non-clique or noisy networks. Please test on such datasets to verify its general applicability.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730646831745

thread_type:
official_review

<thread_object>
creator: reviewer_4nxw

<content>
summary:
The manuscript presents a novel method for community detection called CLANN. This method addresses challenges in semi-supervised community detection, particularly issues with community core consistency and scalability. The authors draw an analogy between community formation and crystallization kinetics, introducing two main components: the Nucleus Proposer and the Transitive Annealer. These components use cliques as starting points and leverage physics-based principles to optimize and expand communities effectively. The paper claims that CLANN surpasses existing state-of-the-art methods in accuracy and efficiency based on extensive experiments across various datasets.

strengths:
1:The analogy with crystallization kinetics introduces a novel physics-grounded perspective for community detection, enriching the field with fresh conceptual insights.

2:Empirical evaluations show that CLANN outperforms established methods in both single and hybrid dataset scenarios, demonstrating its robustness and superior scalability.

3:The integration of the Nucleus Proposer and Transitive Annealer simplifies the growth process without relying on computationally heavy methods like GANs or reinforcement learning.

4:The paper provides extensive tests, including ablation studies and adaptability analyses, solidifying the validity of its contributions.

weaknesses:
1:While the physics-based analogy is intriguing, it may be difficult for readers without a background in crystallization kinetics to grasp fully. More simplified explanations or visual aids could make this clearer.

2:Although the method improves scalability over GAN-based approaches, the process of clique enumeration can still be computationally expensive, potentially limiting applicability to extremely large graphs.

3:The experiments, though diverse, may benefit from including more real-world networks with varying characteristics to generalize the method's effectiveness further.

4:The paper does not thoroughly discuss the practical implementation details, such as computational resources required for different dataset sizes, which may affect the adoption of the model in real-world applications.

questions:
1:Can you provide more intuitive examples or visual explanations of how crystallization kinetics translate to the community detection process? 

2:How does CLANN compare with simpler heuristic-based community detection methods in terms of performance and resource consumption?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732343980117

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response (Part 1)

comment:
Dear all reviewers, thank you very much for the time and effort in reviewing our paper, and for the constructive and positive comments. Our rebuttal consists of two parts: **Global Response** where we address the shared concerns from two or more reviewers and **Individual Response** where we provide a detailed one-to-one response to address your questions/concerns individually.

---
> ## **1. Analogy Rationale Between Crystallization Kinetics and Community Detection**

Applying energy minimization principles from physics to network community detection has proven to be valid and effective [Ref1, Ref2, Ref3]. Specifically, in [Ref3], the modularity function is shown to be equivalent to the Hamiltonian (energy function) of a Potts spin glass model, establishing a direct connection between modularity optimization and energy minimization. Maximizing modularity corresponds to finding a configuration of communities that minimizes the system's energy, leading to a more stable and natural partitioning of the network. In our study, we link our energy-based loss functions to modularity, demonstrating that optimizing these loss functions aligns with modularity optimization to achieve a reasonable community configuration (Page 14-15, Section A).

As outlined in the introduction (Line 50 - 72), core consistency refers to the embedding similarity between a community core and the corresponding complete community. Stability and cohesion principles, reflected in the Energy-Based Loss and Consistency-Based Loss, incorporate diverse information during community formation—such as size, misplacement, and shape—into the embeddings. This ensures that the community core embedding aligns closely with the complete community embedding. In contrast, previous methods neglect the community formation process, focusing solely on nodes or k-hop structures, which leads to inconsistent core embeddings.

For scalability, the principles of spontaneous growth and equilibrium status embed the natural community formation process directly into the model. This enables the community core to grow autonomously, eliminating the need for a second-stage, computationally expensive training process involving RL or GANs. These principles collectively enhance both the consistency and scalability of the model while maintaining efficiency and accuracy in community detection.

To help reader to understand crystallization process better, we upload our source code and a visualization video to an anonymous GitHub repository at https://anonymous.4open.science/r/CLANN_ICLR2025-51D0/README.md

**References**:  
[Ref1] Pang, Y., & Li, K. (2013). An Energy Model for Network Community Structure Detection. *In Advanced Data Mining and Applications: 9th International Conference*.  
[Ref2] Pang, Y., Bai, L., & Bu, K. (2015). An energy model for detecting community in PPI networks. *In International Conference on Data Management in Cloud, Grid and P2P Systems*.  
[Ref3] Reichardt, J., & Bornholdt, S. (2006). Statistical mechanics of community detection. *Physical Review E—Statistical, Nonlinear, and Soft Matter Physics*.

---
> ## **2. Experiments on More Datasets**

In our original submission, we evaluated CLANN's performance on **non-clique** structures as shown in Appendix Section K. By replacing cliques with scatter-based cores, we tested the model on **6 bipartite datasets** (collaboration and co-purchase networks). These results demonstrate our robust performance under non-clique conditions. Additionally, experiments on **15 datasets** across three scenarios (**Non-Clique**, **Sparse**, and **Noisy**) further validate CLANN's effectiveness.
- **scatter datasets**, communities were generated with tree-structures to ensure **non-clique** structures.
- **Barabási-Albert datasets** are scale-free sparse networks with **fewer than 300 cliques**, simulating natural community growth.
- **NoisyDBLP datasets** introduced 10% edge perturbation for DBLP datasets while preserving community connectivity.

Altogether, CLANN was tested on **43 networks**, demonstrating its robustness in diverse and challenging conditions. Detalied results and analysis are presented in Appendix Section K (colored by blue).

```
Table 1. CLANN's F1 Performance Across 3 New Scenarios
```
|Dataset|S 1K|S 2K|S 3K|S 4K|S 5K|B 1K|B 2K|B 3K|B 4K|B 5K|N 1K|N 2K|N 3K|N 4K|N 5K|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|#Node|64,020|100,000|100,000|100,000|100,000|100,000|100,000|100,000|100,000|100,000|25,968|47,318|70,425|97,270|215,912|
|#Edge|66,665|200,000|200,000|200,000|200,000|200,000|200,000|200,000|200,000|200,000|88,949|181,547|280,586|397,201|829,877|
|CLARE|0.1929|0.1522|0.1904|0.2153|0.2394|0.1291|0.1871|0.216|0.2458|0.2589|0.3308|0.3608|0.366|0.3753|0.2837|
|CLANN|0.31|0.1567|0.2824|0.298|0.3011|0.1922|0.2513|0.2992|0.33|0.3307|0.4157|0.4475|0.4742|0.4398|0.3539|

These results demonstrate that CLANN adapts effectively to non-clique, sparse, and noisy structures while maintaining superior performance.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732345993832

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response (Part 2)

comment:
> ## **3. Sensitivity Analyses of Hyperparameters**
1. Existing Sensitivity 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. As shown in **Figure 5**, we normalized these losses to the same magnitude and varied their weights across a wide range of values (0.01, 0.1, 1, 10, 100). The results demonstrate that the model’s performance remains stable, highlighting its robustness to changes in loss weights. In **Appendix I**, we studied the impact of the **candidate size rate** to analyze the quality of candidates selected by Nucleus Proposer. 

2. For annealing temperature and transtive threshold in Algorithm 2: In the real deployment, we try to avoid overusing many hyperparameters to improve model's generalizability,
- **Annealing Temperature Threshold**: In the deployment, it is set to be a temperature probability function as $P_{\text{temp}}(|S_i^c|) = \Phi\left( \frac{|S_i^c| - \mu}{\sigma} \right)$. It represents a cumulative distribution function of a normal distribution where $\mu$ is the mean and $\sigma$ is the standard deviation of the training community size. In this case, this threshold can dynamically adapt to different datasets. 
- **Transitive threshold**: As explained in Section 5.3, we just simply check whether the integrity score of the newly merged clique is higher than that of the previous state, making the transitive threshold unnecessary. 

Consider the generalizability and to avoid confusion, in the revised version, we have removed both parameters from Algorithm 2, and added illustration before euqation (13).


---
> ## **4. Computational Efficiency**
1. **Scalability of Clique Enumeration**:  
As detailed in **Appendix C and Appendix F**, we avoid traversing the entire graph to enumerate all cliques $\(O(3^{N/3})\)$, instead, we extract maximum cliques from 1-hop ego networks for the pre-selected node. We only check the clique for this node among its 1-hop ego network, reducing complexity to $\(O(N^2)\)$. In the real deployment, after optimizing our source code, we achieved faster speed and less RAM requirement compared to the runtime reported in our original version. The source code and datasets are provided in the anonymous GitHub repository mentioned in the previous Global Response.

2. **Theoretical Validation**:  
For complexity and convergence, we provide a detailed complexity analysis in **Appendix C**, breaking down the computational steps for the **Preliminary Core Filter**, **Nucleus Proposer**, and **Transitive Annealer**. The Transitive Annealer is guaranteed to terminate within \(M\) iterations, as confirmed by empirical results in **Section 6.4**, where most cases converge in fewer than 3 iterations (**Figure 6**).  

3. **Efficiency of the Candidate Filtering Mechanism**:  
- **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.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Overall, the paper seems difficult for the machine learning community to understand. The reviewers reported multiple issues, which unfortunately the rebuttal did not address. I cannot accept the paper at this stage. The authors should put more effort into communicating with the machine learning community by modifying the paper for this audience.