Less is More: Simple yet Effective Heuristic Community Detection with Graph Convolution Network

Hong Wang, Yinglong Zhang, Zhangqi Zhao, Zhicong Cai, Xuewen Xia, Xing Xu

In the world of graph data, finding "communities"—groups of nodes more densely connected to each other than to the rest of the network—is a fundamental task. Whether you are identifying functional modules in a protein network or consumer segments in an e-commerce graph, the goal is the same. However, as datasets grow and node attributes become richer, the algorithms have become increasingly bloated.

A new paper titled "Less is More: Simple yet Effective Heuristic Community Detection with Graph Convolution Network" argues that we’ve over-engineered the solution. By stripping away complex contrastive learning and the need for predefined community counts, the authors have developed a method that is both faster and more accurate than current state-of-the-art (SOTA) models.

TL;DR

The authors propose a GCN-based community detection framework that eliminates the need for manual community-count specification and expensive contrastive learning. By combining a classic heuristic (Louvain) for global structure with GCNs for local features, they achieve superior accuracy and significantly faster runtimes across nine diverse datasets.

What Problem Does This Paper Address?

Community detection has historically been split into two camps:

  1. Traditional Heuristics: Methods like Louvain optimization are fast and look at the "global" topology, but they ignore the rich attribute data (features) often attached to nodes.
  2. Deep Learning Approaches: Modern GNN-based methods use node attributes but often rely on contrastive learning. This requires generating multiple "views" of the data and selecting "negative samples," which is computationally expensive and sensitive to noise.

Furthermore, most deep learning models require the user to pre-specify the number of communities ($K$). In real-world networks, we rarely know $K$ in advance, making these models difficult to deploy autonomously.

Methods

The authors' "Less is More" approach follows a three-stage pipeline that avoids the pitfalls of joint optimization and data augmentation:

  1. Adaptive Global Pre-Detection: The model uses the Louvain algorithm to get an initial "sketch" of the network's global structure. It then applies a statistical filter (based on mean and standard deviation of community sizes) to discard tiny, noisy clusters, leaving only significant "structural community centers."
  2. Local Feature Fusion: A standard Graph Convolutional Network (GCN) processes the graph to integrate local structural information with node attributes. This produces low-dimensional node embeddings.
  3. Soft-Assignment Modularity Optimization: The "global" centers from step one are mapped into the same feature space as the GCN embeddings. The model then calculates the similarity between nodes and these centers to create a membership probability matrix. Finally, it optimizes a single modularity-based loss function.

Unlike other models that juggle four or five different loss functions, this framework uses just one, making it much easier to train.

Datasets

The researchers evaluated their model on nine widely used benchmarks:

  • Citation Networks: Cora, Citeseer, Pubmed.
  • E-commerce/Co-purchase: Amac (Amazon Computers), Amap (Amazon Photo).
  • Co-authorship/Academic: Acm, Cocs.
  • Others: Film (Wikipedia actors) and Uat (Air transportation).

These datasets range from roughly 1,200 nodes to nearly 20,000 nodes, providing a robust test of scalability and generalization.

Key Insights and Ideas

  • The "Adaptive K" Advantage: By using Louvain as a pre-step, the model "discovers" the number of communities on its own. This removes the "artificial interference" of a human guessing the value of $K$.
  • Contrastive Learning is Optional: One of the most surprising findings was that adding a SimCLR-style contrastive loss actually decreased performance in several cases. The authors argue that if your structural and feature integration is well-designed, the overhead of contrastive learning is not just unnecessary—it’s detrimental.
  • Global + Local = Success: The "aha moment" here is the realization that Louvain provides the global "where," while GCNs provide the local "what." Combining them in the feature space allows the model to resolve boundary nodes that traditional methods often misclassify.

Key Results

The proposed model, simply named "Our" in the paper's tables, dominated the competition:

  • Accuracy: On the Acm dataset, it achieved a Max ACC (Accuracy) of 0.8443, significantly higher than the next best deep learning model, CommDGI (0.8750 - Note: The paper shows "Our" as the best/runner up across most metrics in Table 3).
  • Speed: In runtime comparisons (Figure 5), the model was orders of magnitude faster than competitors like MAGI and MGCN. For example, on the Cora dataset, it finished in roughly 35 seconds, while some SOTA models took over 1,000 seconds.
  • Clarity: T-SNE visualizations (Figure 6) show that the "Our" method produces much tighter, more distinct clusters compared to other deep learning methods, which often show significant overlap between communities.

Limitations and Future Work

While the model is highly effective, it does rely on the Louvain algorithm for its initial global structural awareness. If a graph is so noisy that Louvain fails to find any meaningful initial structure, the subsequent steps might suffer.

The authors suggest that future work will focus on even more sophisticated ways to acquire global structural information and applying these techniques to specific social network analysis problems. They also aim to explore how this "simple" philosophy can be applied to even larger, billion-scale graphs.

Check out the code: The authors have made their implementation available on GitHub at https://github.com/wuanghoong/Less-is-More.git.

Summary updated

Abstract

Community detection is crucial in data mining. Traditional methods primarily focus on graph structure, often neglecting the significance of attribute features. In contrast, deep learning-based approaches incorporate attribute features and local structural information through contrastive learning, improving detection performance. However, existing algorithms' complex design and joint optimization make them difficult to train and reduce detection efficiency. Additionally, these methods require the number of communities to be predefined, making the results susceptible to artificial interference. To address these challenges, we propose a simple yet effective community detection algorithm that can adaptively detect communities without relying on data augmentation and contrastive optimization. The proposed algorithm first performs community pre-detection to extract global structural information adaptively. It then utilizes GCN to integrate local structures and attribute features. Subsequently, it combines global, local structures and attribute features in the feature space to discover community affiliations. Finally, a modularity maximization method is employed to optimize the communities based on these three types of information, thereby uncovering the community affiliation of each node. We conduct experimental comparisons across various graph datasets, evaluating the proposed algorithm against traditional methods and state-of-the-art community detection algorithms. The experimental results demonstrate that our algorithm achieves greater efficiency and accuracy in terms of both detection speed and effectiveness. The code is available at https://github.com/wuanghoong/Less-is-More.git.
BibTeX
@misc{wang2025less,
  author = {Hong Wang and Yinglong Zhang and Zhangqi Zhao and Zhicong Cai and Xuewen Xia and Xing Xu},
  title = {{Less is More: Simple yet Effective Heuristic Community Detection with Graph Convolution Network}},
  year = {2025},
  eprint = {2501.12946},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.12946},
}
Figure