Effective and Efficient Community Search over Large-Scale Hypergraphs

Yu Liu, Qi Luo, Yanwei Zheng, Wenjie Zhang, Xuemin Lin, Dongxiao YuEDBT 2025 · OpenReview

TL;DR

This paper introduces the $(k, s)$-HCore model, a hyperedge-centric approach to community search that captures higher-order group interactions more accurately than traditional vertex-centric models. To find the most relevant results, the authors define the Hyperedge-Centric Minimum Community Search (HMCS) problem and provide an optimized branch-and-bound algorithm (OBBAB) that achieves up to a $10^4$ speedup over baseline methods.

What Problem Does This Paper Address?

Community Search (CS) aims to find a cohesive group of vertices containing a specific query vertex. While well-studied in simple graphs (pairwise relationships), traditional CS fails in hypergraphs, where a single "edge" (hyperedge) can connect any number of vertices (e.g., a research paper with five authors).

Comparison of graph representations: (a) DBLP network, (b) pairwise graph, (c) bipartite graph, (d) s-line graph, and (e) hypergraph.

The authors identify two major gaps in existing hypergraph CS:

  1. Ignoring Hyperedge Overlap: Most models are "vertex-centric," focusing on how many neighbors a vertex has. This ignores the "strength" of group interactions—how much different hyperedges overlap and share members.
  2. Excessive Community Size: Existing methods often return massive communities that are difficult to interpret. Finding the minimum cohesive community is a more useful but computationally harder (NP-Hard) problem.

Methods

The researchers propose a two-pronged solution involving a new structural model and an efficient search algorithm.

1. The $(k, s)$-HCore Model

Instead of looking at vertex degrees, this model focuses on hyperedge interactions:

  • Interaction Engagement ($k$): A hyperedge must intersect with at least $k$ other hyperedges.
  • Intersection Strength ($s$): Those intersections must share at least $s$ vertices. By combining these, the $(k, s)$-HCore identifies sub-hypergraphs where groups are tightly "locked" together through significant shared membership.

2. The OBBAB Algorithm

Finding the minimum sub-hypergraph that satisfies the $(k, s)$-HCore constraint is NP-Hard. The authors develop an Optimized Branch-and-Bound (OBBAB) algorithm featuring three key techniques: candidate set pruning, lower bound pruning, and strategic branching.

The workflow comparison between the baseline Branch-and-Bound (BAB) and the Optimized Branch-and-Bound (OBBAB), showing how pruning reduces the search space.
  • Candidate Set Pruning: Systematically eliminates hyperedges that cannot possibly be part of a valid $(k, s)$-HCore based on their local connectivity.
  • Lower Bound Pruning: Uses a greedy estimation to predict the minimum possible size of a community in a specific search branch. If that estimate exceeds the size of the best community found so far, the branch is discarded.
  • Strategic Branching: Instead of picking edges at random, the algorithm uses "connectivity scores" to prioritize hyperedges that are most likely to lead to a small, cohesive community quickly.

Key Results

The study evaluates the model on 10 real-world datasets across six domains, including pharmaceutical, Q&A networks, and academic collaboration (e.g., AMiner with ~27 million edges).

  • Cohesion: Communities found by the $(k, s)$-HCore model exhibited twice the "overlapness" (average hyperedges per vertex) compared to traditional $k$-core or $CoCore$ models.
  • Efficiency: The OBBAB algorithm outperformed the baseline Branch-and-Bound (BAB) by 2 to 4 orders of magnitude.
  • Scalability: While the baseline BAB's runtime increased exponentially with dataset size, OBBAB demonstrated near-linear scalability, making it viable for massive datasets.
  • Application Success: Case studies in influence spreading showed that vertices within a $(k, s)$-HCore are more effective "seeds" for information dissemination than those identified by vertex-centric measures.

Limitations and Future Work

Despite massive speedups, the underlying problem remains NP-Hard. Future work could explore attributed hypergraphs or adapt these minimum search techniques to dynamic hypergraphs that evolve over time.

Summary updated

BibTeX
@inproceedings{liu2025effective,
  author = {Yu Liu and Qi Luo and Yanwei Zheng and Wenjie Zhang and Xuemin Lin and Dongxiao Yu},
  title = {{Effective and Efficient Community Search over Large-Scale Hypergraphs}},
  booktitle = {EDBT},
  year = {2025},
  url = {https://openreview.net/forum?id=mU0ChiVBtG},
}
Figure