Overlapping community detection aims to identify nodes that participate in multiple communities simultaneously, a common structure in social, collaboration, and information networks. In this talk, we present Highway, a scalable algorithm for overlapping community detection using sparse backbones. The work is motivated by Triad, our optimization-based framework that models overlapping assignments through node-level memberships, edge-level coherence, and community-level regularization, but is limited by the computational cost of quadratically constrained programming.

Highway addresses this scalability bottleneck by shifting from dense full-graph inference to backbone-guided signal propagation. It first constructs a sparse backbone using a hybrid edge score that combines a modularity-inspired global signal with a local neighborhood-overlap signal. It then selects distributed anchor nodes and propagates anchor memberships through the backbone using a neighbor-only update rule. Finally, propagated anchor patterns are calibrated through pattern-level and neighbor-level consensus to produce overlapping communities.

We evaluate Highway on LFR and ABCD+o² overlapping benchmark networks under increasing mixing parameter values. Compared with ten existing methods, Highway provides a favorable accuracy–efficiency trade-off, maintaining competitive detection quality while achieving stable runtime growth on larger instances.