Efficient indexing and searching of constrained core in hypergraphs

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

Hypergraphs are generalized graph models that capture high-order relationships through hyperedges that contain arbitrary vertices. In large-scale hypergraphs, it is common to observe global sparsity and local density, which makes identifying the dense substructures a fundamental task in graph mining. This paper introduces a framework called (k, p)-PoolCore for searching constrained cohesive subgraphs in hypergraphs, with k representing the degree constraint of vertices and p indicating the size constraint of hyperedges. We theoretically analyze the monotonicity and hierarchical properties of (k, p)-PoolCore. To capitalize on these properties, we propose a tree-based PoolCore index that organizes all (k, p)-PoolCores within trees to facilitate efficient queries. Furthermore, we optimize this index to establish a list-based PoolCore index, which offers O(1) query time complexity in most cases without additional space complexity in large-scale hypergraphs. Our extensive experiments and case studies on real-world hypergraphs demonstrate the advantages of (k, p)-PoolCore in hypergraph decomposition and modeling cohesiveness substructures. The proposed tree-based PoolCore index achieves a remarkable 10^6 speedup compared to the basic computation method. Additionally, the optimized list-based PoolCore index further accelerates querying by at least 100x while maintaining space-complexity efficiency and scalability in real-world hypergraphs.

Author Affiliations

@article{luo2025efficient,
  title = {Efficient indexing and searching of constrained core in hypergraphs},
  author = {Luo, Qi and Zhang, Wenjie and Yang, Zhengyi and Yu, Dongxiao and Lin, Xuemin and Wang, Liping},
  journal = {The VLDB Journal},
  year = {2025},
  month = {Apr},
  day = {22},
  volume = {34},
  number = {3},
  pages = {34},
  issn = {0949-877X},
  doi = {10.1007/s00778-025-00915-x},
  url = {https://doi.org/10.1007/s00778-025-00915-x}
}