Active Learning in the Geometric Block Model

Eli Chien, Antonia Maria Tulino, Jaime Llorca

Abstract

The geometric block model (GBM) is a generative model for random graphs that captures inherent geometric properties and transitivity in community detection problems. While unsupervised motif-counting algorithms have shown promise, they fail in certain parameter regimes where community connection densities are too similar. This work introduces active learning to the GBM, demonstrating that querying a vanishingly small, sub-linear fraction of node labels is sufficient for exact community recovery in these challenging regimes. We propose two algorithms combining motif-counting with strategic label queries and validate their performance on synthetic and real-world datasets.

Introduction: The Challenge of Transitivity

Community detection is fundamental to network analysis. While the Stochastic Block Model (SBM) is a traditional benchmark, it fails to account for transitivity—the "friends of friends" property common in social networks. The Geometric Block Model (GBM) addresses this by embedding nodes in a latent geometric space, where connection probability depends on both community membership and spatial proximity.

However, GBM is mathematically more complex than SBM. In many practical scenarios, the density difference between intra-community and inter-community edges is insufficient for unsupervised methods to achieve exact recovery. Recent advances in motif-counting have improved the unsupervised bounds, as shown in Figure 1, but a significant gap remains where community structure is unrecoverable without additional information.

Comparison of the minimum $\theta_1$ required for exact recovery between the proposed unsupervised bound and previous results.

Methodology: Hybrid Active Learning

We propose a two-phase framework to bridge this gap and achieve exact recovery:

  1. Phase 1: Unsupervised Motif-Counting. Leveraging the geometric nature of GBM, we count triangles associated with each edge. In a GBM, edges within the same community typically participate in significantly more triangles than cross-community edges. This allows for an initial pruning of the graph to remove suspected inter-community connections.
  2. Phase 2: Active Querying. We introduce two policies to resolve remaining ambiguities:
  3. Algorithm 1 (Motif-counting with $S^2$): Applies the $S^2$ algorithm—a minimax optimal graph-based active learning method—to the pruned graph to identify and query the most informative nodes for labeling.
  4. Algorithm 2 (Aggressive Edge Removal): Uses a stricter pruning threshold to isolate clean components, then queries exactly one node from each component to propagate labels.

Experimental Results and Query Complexity

Our theoretical analysis and numerical simulations confirm that exact recovery is possible with a query complexity of $O(n^{1-\epsilon})$, meaning the number of queries grows much slower than the total number of nodes $n$. As shown in Figure 6, even when the model parameters $\theta_1$ fall below the unsupervised threshold, the number of queries required remains sub-linear relative to the total number of nodes.

Query complexity ($\log_n Q$) as a function of $\theta_1$ for $\theta_2 = 4$, illustrating the sub-linear query regime.

On real-world datasets, the hybrid approach shows significant gains:

  • Political Blogs: Accuracy improved from 0.78 (unsupervised) to 0.93 with only 3.7% of nodes queried.
  • LiveJournal: Achieved 0.91 accuracy with less than 1% (0.88%) of nodes queried.
  • Efficiency: Compared to using the $S^2$ algorithm alone, our hybrid motif-counting approach requires approximately 10 times fewer queries to reach the same accuracy levels.

Discussion and Future Directions

While our algorithms provide a robust path to exact recovery, several challenges remain. Algorithm 2's efficiency depends on accurate knowledge of model parameters ($\theta_1, \theta_2$), which may be unknown in practice. Furthermore, our current analysis focuses on two equal-sized communities in a 2D torus space. Future work will explore extensions to multi-community settings, varying cluster sizes, and higher-dimensional latent spaces to better model the complexities of real-world networks.

Summary updated

Abstract

The geometric block model is a recently proposed generative model for random graphs that is able to capture the inherent geometric properties of many community detection problems, providing more accurate characterizations of practical community structures compared with the popular stochastic block model. Galhotra et al. recently proposed a motif-counting algorithm for unsupervised community detection in the geometric block model that is proved to be near-optimal. They also characterized the regimes of the model parameters for which the proposed algorithm can achieve exact recovery. In this work, we initiate the study of active learning in the geometric block model. That is, we are interested in the problem of exactly recovering the community structure of random graphs following the geometric block model under arbitrary model parameters, by possibly querying the labels of a limited number of chosen nodes. We propose two active learning algorithms that combine the use of motif-counting with two different label query policies. Our main contribution is to show that sampling the labels of a vanishingly small fraction of nodes (sub-linear in the total number of nodes) is sufficient to achieve exact recovery in the regimes under which the state-of-the-art unsupervised method fails. We validate the superior performance of our algorithms via numerical simulations on both real and synthetic datasets.
BibTeX
@inproceedings{chien2020active,
  author = {Eli Chien and Antonia Maria Tulino and Jaime Llorca},
  title = {{Active Learning in the Geometric Block Model}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=Hw3rR_24hZ9},
}
Figure