Source-linked AI summary
CommunityGAN: Community Detection with Generative Adversarial Nets
Yuting Jia, Qinqin Zhang, Weinan Zhang, Xinbing Wang
TL;DR
Community detection with learned graph embeddings remains difficult when communities overlap densely, because common clustering algorithms cannot represent such memberships. CommunityGAN jointly learns membership-strength embeddings and optimizes them with motif-level adversarial learning; the paper reports gains over state-of-the-art methods across community detection and clique prediction.
Problem
Conventional graph embeddings do not encode community membership, and clustering algorithms cannot handle the dense overlap found in some real-world networks.
Source: §1 · p. 1Method
CommunityGAN jointly learns vertex-community membership-strength embeddings and optimizes them through a minimax game between a motif-level generator and discriminator.
Source: §1 · pp. 1–2Results
7.9% to 21.0%: CommunityGAN improves F1-Score for community detection and reaches AUC scores of at least 0.990 and 0.956 for 3-clique and 4-clique prediction.
Source: §1 · p. 2Takeaways & Limitations
The paper reports that CommunityGAN maintains performance as overlap increases and that properly sized motifs can improve community structures over edge-level optimization.
Source: §5.7 · p. 8
Abstract
from arXiv · showhide
Community detection refers to the task of discovering groups of vertices sharing similar properties or functions so as to understand the network data. With the recent development of deep learning, graph representation learning techniques are also utilized for community detection. However, the communities can only be inferred by applying clustering algorithms based on learned vertex embeddings. These general cluster algorithms like K-means and Gaussian Mixture Model cannot output much overlapped communities, which have been proved to be very common in many real-world networks. In this paper, we propose CommunityGAN, a novel community detection framework that jointly solves overlapping community detection and graph representation learning. First, unlike the embedding of conventional graph representation learning algorithms where the vector entry values have no specific meanings, the embedding of CommunityGAN indicates the membership strength of vertices to communities. Second, a specifically designed Generative Adversarial Net (GAN) is adopted to optimize such embedding. Through the minimax competition between the motif-level generator and discriminator, both of them can alternatively and iteratively boost their performance and finally output a better community structure. Extensive experiments on synthetic data and real-world tasks demonstrate that CommunityGAN achieves substantial community detection performance gains over the state-of-the-art methods.
1 INTRODUCTION
CommunityGAN addresses the difficulty of detecting dense overlapping communities with conventional graph embeddings and clustering. It jointly learns community membership representations and optimizes them through motif-level adversarial learning.
1 INTRODUCTION
- Conventional embedding vectors lack membership meaning, and clustering can fail when vertices belong to many overlapping communities.The paper notes that vertices in some real-world datasets may belong to tens of communities simultaneously.Source: §1 · p. 1
- CommunityGAN jointly learns graph representations and overlapping communities, with each vertex’s vector encoding its membership strengths across communities.This design is modeled after AGM’s vertex-community membership factors.Source: §1 · p. 1
- A motif-level generator proposes vertex subsets for a specified motif, while a discriminator judges whether subsets are real motifs in a minimax game.The competition is described as driving the generator toward the true connectivity distribution.Source: §1 · p. 2
- The contributions combine AGM’s direct membership representation with GAN learning, analyze motif distributions, and introduce an efficient, graph-aware Graph AGM motif generator.The paper also reports synthetic experiments on dense overlap and motif-level generation and discrimination.Source: §1 · p. 2
- 7.9% to 21.0%: CommunityGAN improves F1-Score for community detection and reaches AUC scores of at least 0.990 and 0.956 for 3-clique and 4-clique prediction.The paper reports these gains across real-world tasks and states that performance relies on the joint advantages of its embedding design, adversarial learning, and motif-level optimization.Source: §1 · p. 2
2 RELATED WORK
Related work spans community-quality measures, generative and matrix-factorization models, graph representation learning, and unified embedding-community frameworks. The section identifies limits in pair reconstruction, dense-overlap handling, and scalability or clustering requirements.
2 RELATED WORK
- Community detection methods optimize quality measures, fit generative graph models, or factorize adjacency matrices; pair-reconstruction models can limit performance.The cited matrix-factorization methods often address dense overlap but are described as restricted by bilinear pair reconstruction.Source: §2 · p. 2
- General graph representation methods learn vertex embeddings, but community detection still requires clustering, which cannot handle dense overlap; CommunityGAN outputs memberships directly.The section describes random-walk, proximity-preserving, and adversarial embedding approaches.Source: §2 · p. 2
- Unified frameworks include a matrix-factorization approach limited on million-vertex graphs and a joint embedding framework that still infers communities through clustering.The latter is described as retaining the dense-overlap problem.Source: §2 · p. 2
3 EMPIRICAL OBSERVATION
This section analyzes the relationship between motifs and communities, describing the datasets before presenting empirical observations.
3.1 Datasets
- Table 1 reports five networks’ vertex, edge, triangle, community, and per-vertex membership counts.The networks are LiveJournal, Orkut, YouTube, DBLP, and Amazon.Source: Table 1 · p. 3, §3.1 · p. 3
3.2 Empirical Observations
- Within-community samples have much higher average 2-, 3-, and 4-clique occurrence probabilities than samples drawn from the whole network.The study repeatedly sampled vertices from communities and compared clique occurrence with the whole-network rate.Source: §3.2 · p. 3, Table 2 · p. 3
- As the number of shared communities rises, 3- and 4-clique probability increases overall, supporting extension of AGM from edge to clique generation.This trend accords with the AGM assumption that vertices in overlapping communities are more densely connected than vertices in a single community.Source: §3.2 · p. 3, Figure 2 · p. 3
4 METHODOLOGY
CommunityGAN learns overlapping community affiliations by training a motif generator and discriminator together, then uses graph-aware generation and membership post-processing to produce communities. Its method develops this framework from a minimax objective through motif-specific models and practical initialization and selection procedures.
4.1 CommunityGAN Framework
- The generator approximates the distribution of real motifs covering a center vertex, while the discriminator estimates whether a vertex subset is a real motif.The paper focuses on cliques and trains the two models in a minimax game.Source: §4.1 · pp. 3–4
4.2 CommunityGAN Optimization
- The discriminator learns from positive real motifs and negative generated subsets, while policy gradients update the generator under the discriminator’s guidance.The two models are trained alternatively to make generated motifs harder to distinguish from true motifs.Source: §4.1 · p. 4, §4.2 · p. 4
4.3 A Naive Implementation of D and G
- The naive generator builds a motif as a vertex sequence, conditioning each new vertex on all previously selected vertices to keep the subset likely to form a clique.Conditioning only on the immediately preceding vertex could add a vertex from a different community and yield a low-probability clique.Source: §4.3 · p. 4
4.4 Graph AGM
- Graph AGM addresses dense-overlap, all-vertex softmax, and ignored-proximity limitations by making generator vectors encode community affiliations and using graph-aware generation.The generator treats a virtual vertex as connected to the union of the selected vertices’ neighborhoods and uses a random walk to choose generated vertices.Source: §4.4 · p. 5
- AGM-style motif scoring models a clique’s probability from the entrywise product of member affiliation vectors, and defines the discriminator using nonnegative vertex representations.The discriminator takes the form 1 − exp(−⊙(d_v1, d_v2, …, d_vm)).Source: §4.4 · p. 5
- The graph-aware walk selects generated vertices through neighbor-based relevance probabilities, favoring paths relevant to the virtual root.The relevance probability is a softmax over the root’s neighbors.Source: §4.4 · p. 5
4.5 Other Issues
- The authors initialize generator and discriminator representations from an AGM fit, choosing it over locally minimal neighborhoods because the latter performed somewhat worse.Locally minimal neighborhoods can save AGM training time, but the reported efficiency analysis includes pre-training time.Source: §4.5 · p. 6
- Hard memberships threshold the learned representations, while the number of communities is selected by link-prediction score on a reserved validation set.The procedure reserves 20% of links for validation and chooses the community count with the maximum prediction score.Source: §4.5 · p. 6
5 SYNTHETIC DATA EXPERIMENTS
Synthetic experiments test CommunityGAN on graphs with dense overlapping communities and assess whether motif-level generation and discrimination improve detection. The reported results show strong performance across overlap levels and identify clique sizes 4 or 5 as most effective.
5.1 Evaluation Metric
- The evaluation uses average F1-Score, matching detected and ground-truth communities in both directions before averaging the best-match scores.Higher F1-Score indicates more accurate detected communities.Source: §5.1 · p. 7
5.2 Datasets
- The synthetic graphs vary in overlap: all communities overlap, and average memberships per vertex rise as the generator’s β1 and β2 decrease.The CKB Graph Generator produces graphs with ground-truth communities; the experiment varies β1 and β2 across six settings.Source: §5 · p. 6, §5.2 · p. 7, Table 4 · p. 7
5.5 Ability of CommunityGAN to Solve Dense Overlapping Problem
- CommunityGAN significantly outperforms all baselines across the synthetic graphs, including ckb-267, where MMSB and AGM decline.The comparison evaluates eight methods using average F1-Score; CommunityGAN also improves on its AGM pre-training method.Source: Figure 6 · p. 7, §5.5 · p. 8
5.3 Comparative Methods
- Seven baselines span traditional overlapping-community methods, graph representation learning, and a joint representation-learning and detection method.The compared methods are MMSB, CPM, AGM, node2vec, LINE, GraphGAN, and ComE.Source: §5.3 · p. 7
5.4 Experiment Setup
- Training uses stochastic gradient descent at learning rate 0.001, with five positive and five negative vertex subsets per vertex and three updates of G and D per iteration.For embedding-only baselines, K-means uses the ground-truth community count and is repeated five times; other baselines use default hyperparameters.Source: §5.4 · p. 7
5.6 Efficacy of Motif-Level Generation and Discrimination
- Clique sizes 4 or 5 generally perform best; size 6 often performs worse as its cliques cover fewer vertices.The reported explanation is that fewer covered vertices yield fewer positive training samples; Table 5 reports clique and vertex coverage statistics.Source: Figure 7 · p. 8, §5.6 · p. 8, Table 5 · p. 8
5.7 Discussion
- CommunityGAN maintains performance as overlap increases, improves on AGM through minimax competition, and benefits from motif-level optimization with proper motif sizes.The discussion contrasts its stability with baseline methods and states that motif-level optimization can improve community structure over edge-level optimization.Source: §5.7 · p. 8
6 REAL-WORLD SCENARIOS
Real-world experiments evaluate community detection, clique prediction, and training time across five datasets. CommunityGAN outperforms baselines on community detection and on 3- and 4-clique prediction, while its training time is described as acceptable despite not being fastest.
6.1 Datasets
- The three community-detection datasets have ground-truth memberships; because some baselines take longer to train, the experiments sample subgraphs with 100 ground-truth communities.The study also uses datasets without ground-truth communities for its other real-world scenario.Source: §6 · p. 8, §6.1 · pp. 8–9
6.2 Community Detection
- CommunityGAN outperforms all baselines on three community-detection networks, improving F1-Score by 7.9% (on Youtube) to 21.0% (on Amazon) and NMI by at most 34.3% (on Amazon).The reported results are in Table 6; the evaluation uses F1-Score and NMI.Source: Table 6 · p. 9, §6.2 · p. 9
- The generator performs strongly after convergence, while the discriminator’s performance may fall slightly or rise initially before falling.Figure 8 displays relative score increases because F1-Score differs substantially across the three datasets.Source: Figure 8 · p. 9, §6.2 · pp. 9–10
6.3 Clique Prediction
- On arXiv-GrQc, CommunityGAN gains 0.40% to 74.52% in 3-clique prediction and 4.60% to 79.03% in 4-clique prediction.It outperforms all baselines on 3- and 4-clique prediction, but does not always score highest for 2-clique prediction.Source: Table 7 · p. 10, §6.3 · p. 10
6.4 Efficiency analysis
- CommunityGAN is not the fastest model, but its training time is described as acceptable while its performance significantly outperforms faster models.Its reported training time includes pre-training; the comparison uses 16 threads where supported.Source: Figure 9 · p. 10, §6.4 · p. 10
7 CONCLUSION
The conclusion presents CommunityGAN as a joint approach to overlapping community detection and graph representation learning, with membership-strength embeddings optimized through motif-level adversarial training. Experiments on synthetic graphs and five real-world datasets show substantial gains over baselines across the reported experiments.
7 CONCLUSION
- CommunityGAN jointly addresses overlapping community detection and graph representation learning, with embeddings that encode vertex membership strength and motif-level adversarial optimization.The conclusion reports synthetic experiments on dense overlap and motif generation, plus real-world experiments in two scenarios across five datasets.Source: §7 · p. 10