Zihe Zhou

Home / Research / Highway

Highway

Scalable overlapping community detection through sparse structural backbones.

Zihe Zhou, Samin Aref · ASONAM 2026 (Springer proceedings) · Accepted

Paper (arXiv) Benchmark & code cdlib Talk Slides Cite

The problem

Overlapping community detection lets a node belong to several communities at once — realistic, but expensive. Most methods run inference on the full graph, repeatedly updating each node's memberships along every edge. As networks grow large or dense, these cascading updates become the scalability bottleneck, forcing a hard trade-off between detection quality and speed.

Highway starts from a different assumption: the community signal travels through a small set of structurally informative edges. If we keep only those, we can infer overlapping communities on a much sparser structure — without discarding the information that matters.

Highway across several networks: full graph, sparse backbone, and recovered overlapping communities
From full network to sparse backbone to overlapping communities — Highway across several networks.

Core idea — four steps

Highway keeps the pathways that carry community signal, then propagates a few anchor memberships over that reduced structure.

1

Backbone construction

Score every edge by a hybrid importance — a modularity-inspired term that discounts links explained by high degree, plus a Jaccard neighbourhood-overlap term that favours locally coherent regions — and keep only the informative edges as a sparse backbone.

2

Anchor-based initialization

Select anchor nodes on the full graph with a greedy degree-cover strategy so no two anchors crowd the same local region, and seed each anchor with a unit membership signal.

3

Neighbor-only propagation

Spread anchor memberships across the backbone under a neighbour-only rule: a node's membership is set solely by its backbone neighbours (no self-reinforcement), with degree-normalized weights, keeping the strongest few anchors per node.

4

Anchor-preserving calibration

Nodes that retain the same set of anchors form a "pattern"; each pattern's structural reliability (internal density and boundary concentration) is scored and calibrated into the final overlapping community assignments.

Key results

1.13M
nodes / 2.99M edges — largest real network handled
7.34×
faster on the largest instance
300s
the only method finishing all three real SNAP networks within the limit

Runtime — Amazon 3.7s · DBLP 3.8s · YouTube 23.3s; up to 7.34× faster than the strongest competitor, and ~60× vs COPRA on the largest instance.

Quality — ~3,000 synthetic graphs (LFR, ABCD+o²) against 10 methods across 5 metrics (Q_ov, FRI, Dice, F*, ONMI); rank 1 in Q_ov on ABCD+o² (+18.9%).

Why it matters

Highway suggests that much of the structure needed for overlapping-community inference can be preserved in a carefully chosen sparse backbone — so quality and scalability need not trade off as sharply as prior methods imply. The backbone is not just a speed-up; it is a hypothesis about which edges actually carry community signal.

Cite

@misc{zhou2026highway,
  title         = {Overlapping Network Community Detection Using Sparse Backbones},
  author        = {Zihe Zhou and Samin Aref},
  year          = {2026},
  eprint        = {2607.14531},
  archivePrefix = {arXiv},
  primaryClass  = {cs.SI},
  url           = {https://arxiv.org/abs/2607.14531}
}