PaperlayerView exact revision on arXiv

Source-linked AI summary

Overlapping Community Detection with Graph Neural Networks

Oleksandr Shchur, Stephan Günnemann

arXiv:1909.12201v1cs.LGcs.SIstat.ML

TL;DR

Community-detection methods using deep learning have largely addressed disjoint rather than overlapping communities. The paper proposes NOCD, a GNN-based model for overlapping community detection, and reports strong recovery performance alongside scalability and robustness evidence. The authors conclude that deep learning for graphs merits more attention for this task.

  • Problem

    Existing deep-learning approaches for community detection focus on disjoint communities, despite overlapping communities being common in real networks.

  • Method

    NOCD is a GNN-based model for overlapping community detection, evaluated alongside neural embedding baselines and established methods.

  • Results

    NOCD methods achieve the highest recovery score on 9 of 10 datasets, and the model is trained on 63K nodes and 810K edges in 3 minutes using 750MB of GPU RAM.

  • Takeaways & Limitations

    The results provide strong evidence that deep learning for graphs deserves more attention as a framework for overlapping community detection.

  • Takeaways & Limitations

    The authors identify inductive performance and using NOCD-X and NOCD-G to quantify attribute relevance as follow-up questions.

Abstract

from arXiv · show

Community detection is a fundamental problem in machine learning. While deep learning has shown great promise in many graphrelated tasks, developing neural models for community detection has received surprisingly little attention. The few existing approaches focus on detecting disjoint communities, even though communities in real graphs are well known to be overlapping. We address this shortcoming and propose a graph neural network (GNN) based model for overlapping community detection. Despite its simplicity, our model outperforms the existing baselines by a large margin in the task of community recovery. We establish through an extensive experimental evaluation that the proposed model is effective, scalable and robust to hyperparameter settings. We also perform an ablation study that confirms that GNN is the key ingredient to the power of the proposed model.

1 INTRODUCTION

Existing deep-learning approaches for community detection largely address disjoint communities, despite real networks commonly containing overlaps. The paper responds with an end-to-end GNN model for overlapping community detection and evaluates its accuracy, speed, and GNN component.

  • Deep-learning methods for community detection have received relatively little attention compared with other graph tasks.
  • Existing approaches focus on disjoint communities, although communities in real networks are known to overlap.
  • The paper proposes an end-to-end GNN model capable of detecting overlapping communities.
  • The model introduces a GNN-based approach, four benchmark datasets, and an evaluation of speed and accuracy against established methods.

2 BACKGROUND

Overlapping community detection assigns nodes to potentially multiple communities, often by inferring affiliations that explain graph structure. NOCD combines probabilistic and representation-learning perspectives to learn those affiliations end-to-end with a GNN.

  • Overlapping community detection represents assignments with a non-negative affiliation matrix F, allowing nodes to belong to multiple communities or none.
  • A community is generally treated as a node group whose members are more likely to connect with one another than with other nodes.
  • Community detection can be formulated as inferring the unobserved affiliation matrix F from an observed graph under a generative model p(G|F).
  • The affiliation matrix can also be viewed as a graph-structure-preserving node embedding.
  • Simply combining existing node embeddings with overlapping K-means does not produce satisfactory results.
  • NOCD combines probabilistic and representation-learning perspectives to learn community affiliations end-to-end with a graph neural network.

3 THE NOCD MODEL

NOCD generates non-negative community affiliations with a GNN and trains them using a balanced Bernoulli–Poisson negative log-likelihood. The formulation supports graph-structure-aware predictions, feature integration, and efficient training through caching and edge/non-edge sampling.

  • NOCD combines GNNs with the Bernoulli–Poisson model, which supports overlapping communities and diverse community topologies.
  • In the Bernoulli–Poisson model, nodes sharing more communities are more likely to be connected by an edge.
  • Instead of optimizing F directly, NOCD generates it with a GNN and applies a ReLU output to ensure non-negativity.
  • The training objective is a balanced negative log-likelihood because graph sparsity otherwise makes the non-edge term dominate the loss.
  • The GNN encourages similar affiliation vectors for neighboring nodes, incorporates node features when available, and can support inductive prediction.
  • Caching reduces loss and gradient computation from O(N^2) to O(N + M), while mini-batching edges and non-edges approximately reduces training-objective gradients to O(S).
  • NOCD uses the full adjacency matrix inside the GNN and was trained on a graph with 800K+ edges in 3 minutes on one GPU.

4 EVALUATION

The evaluation tests NOCD on real-world overlapping-community datasets, compares it with established methods and simpler neural baselines, and examines recovery, scalability, hyperparameter sensitivity, and the role of graph structure.

  • Datasets: Four newly collected co-authorship datasets extend evaluation beyond small Facebook ego-networks, with research areas as communities and paper keywords as node attributes.The datasets cover Chemistry, Computer Science, Medicine, and Engineering; larger graphs with reliable overlapping-community ground truth and attributes were otherwise not openly available.
  • Baselines: The evaluation compares NOCD with probabilistic, matrix-factorization, heuristic, and neural graph-embedding baselines, including DeepWalk/NEO and Graph2Gauss/NEO.All methods receive the true number of communities, while other hyperparameters use recommended values.
  • Recovery: Either NOCD-X or NOCD-G achieves the highest NMI on 9 of 10 datasets, and reconstruction loss identifies the better variant without supervision.NOCD-G outperforms NOCD-X in NMI exactly when it has lower reconstruction loss.
  • Hyperparameter sensitivity: The same configuration tuned only on Computer Science performs well across datasets ranging from Facebook graphs with 150 nodes to a Computer Science graph with 22K nodes.The reported Computer Science configuration has N = 22K, M = 96.8K, D = 7.8K, while Facebook 414 has N = 150, M = 1.7K, D = 16.
  • Scalability: NOCD trains on Medicine’s 63K-node, 810K-edge graph in 3 minutes using 750MB of GPU memory, while several baselines fail to scale or take substantially longer.EPM, SNetOC, and CDE do not scale to larger datasets; CESNA takes 2 hours on Medicine, and NEO-K-Means exceeds several hours on large datasets.
  • GNN ablation: On adjacency inputs, the GNN model always outperforms MLP, while attribute-only MLP can win when features are strong but performs extremely poorly on some Facebook datasets.These comparisons use the same objective and evaluate NMI across all 11 datasets.

5 RELATED WORK

Prior community-detection research largely addresses non-overlapping communities, while existing deep-learning approaches either cannot model overlap or omit graph structure. The paper positions its GNN as an end-to-end alternative for overlapping community detection.

  • Existing community detection: Traditional overlapping-community methods include non-negative matrix factorization, probabilistic inference, and heuristics, while most community-detection studies focus on non-overlapping communities.These categories summarize the established approaches discussed in the related work.
  • Deep learning for graphs: Deep graph-learning methods include graph neural networks and node embeddings, but embedding approaches are described as unsuitable for overlapping community detection.GNNs operate directly on graph-structured data, whereas embedding methods learn node vectors for downstream tasks.
  • Prior neural methods: Several neural community-detection methods cannot handle overlapping communities, while another deep-belief-network approach omits graph structure and relies on MCMC, limiting scalability.A supervised GNN for community detection is related but addresses a different setting.

6 DISCUSSION & FUTURE WORK

NOCD is a GNN model for overlapping community detection that the experiments find accurate, flexible, and scalable. The results support greater attention to deep learning for graphs in this task, while leaving attribute relevance and inductive performance for future study.

  • NOCD is a graph neural network model for overlapping community detection.
  • The experimental evaluation confirms that NOCD is accurate, flexible, and scalable.
  • Future work will examine whether NOCD-X and NOCD-G can quantify attribute relevance to community structure and assess NOCD’s inductive performance.
  • The results provide strong evidence that deep learning for graphs deserves more attention for overlapping community detection.

A DATASETS

Table 3 presents dataset statistics, with K denoting 1000.

  • Table 3 summarizes dataset statistics and uses K to denote 1000.

B.1 Architecture

The architecture section compares the GNN-based model with alternative architectures and describes the configuration choices used for the models. Hyperparameters and architecture selection were based on NMI performance on the Computer Science dataset.

  • Architecture and hyperparameters for all three models were selected using NMI performance on the Computer Science dataset, without additional tuning on other datasets.
  • The GNN model uses a two-layer graph convolutional network with hidden size 128 and output size equal to the number of communities.
  • Jumping Knowledge Network and GraphSAGE architectures produced lower NMI scores than the selected architecture on the Computer Science dataset.
  • The MLP model performed best with the same regularization, hidden size, dropout, and batch-normalization configuration as the GCN model.
  • The free-variable model compared locally minimal-neighborhood initialization with initialization from an untrained GCN, and the former consistently performed better.

B.2 Training

The models use Adam optimization with early stopping, while the free-variable model additionally projects its affiliation matrix to remain non-negative. Baseline implementations and experiments were run under specified software, hardware, and single-GPU conditions.

  • The GNN and MLP models use Adam with learning rate 10^-3 and stop after 5000 epochs or 500 iterations without loss improvement.
  • The free-variable model uses Adam with learning rate 5 · 10^-2 and projects its affiliation matrix after each step to preserve non-negativity.
  • Table 4 provides an overview of the baselines and refers to separate discussion of CESNA’s scalability.
  • BigCLAM and CESNA use the authors’ reference C++ implementations with default parameter settings, while SNMF was implemented in Python.
  • Experiments used Ubuntu 16.04LTS, specified CPU and GPU hardware, and a single GPU at a time for training and inference.

E CONVERGENCE OF THE STOCHASTIC SAMPLING PROCEDURE

The paper tests whether stochastic edge and non-edge sampling converges to the same objective as full-batch training. Training is stable, with larger batch sizes closely matching full-batch convergence.

  • Stochastic training samples S edges and S non-edges uniformly instead of using all node pairs to compute each gradient.The procedure tests whether this sampling strategy reaches the same result as the full objective.
  • The experiment compares full-batch optimization with stochastic gradient descent across multiple batch sizes from the same initialization.The full loss is measured over iterations on the Computer Science dataset.
  • The plot compares batch sizes S ∈{1000, 2500, 5000, 10000, 20000} with full-batch training against adjacency-matrix access.Each stochastic iteration accesses 2S entries, while full-batch training accesses 2N + 2M entries using caching.
  • For S = 10K and S = 20K, stochastic training converges very closely to the loss achieved by full-batch training.This is the reported evidence that the stochastic procedure is stable.

F QUANTIFYING AGREEMENT BETWEEN OVERLAPPING COMMUNITIES

The section examines agreement metrics for overlapping communities and identifies a failure mode in symmetric F1 and Jaccard scores. It recommends overlapping NMI because it handles the demonstrated degenerate assignment correctly.

  • Symmetric agreement scores compare ground-truth and predicted overlapping communities using a set-similarity measure such as F1-score or Jaccard similarity.The score combines similarities between ground-truth and predicted communities in both directions.
  • Frequently used agreement measures can assign arbitrarily high scores to completely uninformative community assignments.The section demonstrates this problem with an assignment that places all nodes in one predicted community.
  • A single predicted community containing all nodes receives symmetric F1-score 2K N+K and symmetric Jaccard similarity K N despite being uninformative.The ground truth contains two communities of K nodes each, while the prediction assigns every node to one community.
  • The paper suggests overlapping normalized mutual information (NMI), which assigns degenerate cases like this a score of 0.NMI is presented as a more robust alternative for evaluating overlapping community recovery.
Loading 1909.12201v1…