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.
Methodology: Hybrid Active Learning
We propose a two-phase framework to bridge this gap and achieve exact recovery:
- 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.
- Phase 2: Active Querying. We introduce two policies to resolve remaining ambiguities:
- 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.
- 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.
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