EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Hypergraph decomposition with intersection bounds

Qi Luo, Zhengyi Yang, Wenjie Zhang, Alexander Zhou, Dongxiao Yu, Xiuzhen Cheng, Xuemin Lin, Song Guo

The VLDB Journal · 2026-07 · 35 (4)

DOI: 10.1007/s00778-026-00985-5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The VLDB Journal, online erschienen am 24.06.2026. Verfasst von Qi Luo und 7 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 69 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: University of New South Wales.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Hypergraph decomposition is a fundamental problem in hypergraph analysis which breaks down hypergraphs into cohesive subgraphs and functional units with dense interactions. Hyperedge intersections and overlaps capture the unique property of shared elements (vertices) between groups (hyperedges) in hypergraphs, revealing cohesive substructures not apparent when focusing solely on individual connections. Despite the significance of hyperedge overlap as a measure of hypergraph cohesiveness, existing models for hypergraph decomposition fail to capture this feature. In this paper, we study the problem of hypergraph decomposition with intersection bounds. We propose the ( k , s )-core, a new cohesive subgraph model incorporating both a vertex degree constraint k and a hyperedge intersection constraint s . This model includes two types: (1) strong ( k , s )-cores, where connected hyperedges share at least s vertices, enforcing strong hyperedge overlap, and (2) weak ( k , s )-cores, where hyperedges are connected through s -walks, allowing for a looser overlap. We prove that our definition of ( k , s )-cores exhibits uniqueness and hierarchical properties. Based on the properties, we develop two decomposition algorithms: a bottom-up algorithm for strong ( k , s )-cores, which uses a heuristic hyperedge removal mechanism to maintain consistent decomposition results and employs a union-find data structure for efficient connectivity identification, and a top-down algorithm for weak ( k , s )-cores that preserves the subgraph containment relationship. Our algorithms achieve traversal efficiency by processing each hyperedge in the hypergraph only once. Additionally, all ( k , s )-cores can be efficiently stored with minimal memory overhead. Comprehensive experiments and case studies show that the ( k , s )-core model outperforms existing methods in capturing cohesive subgraphs with overlaps in hypergraphs. Furthermore, the proposed algorithms demonstrate high efficiency and scalability, making them well-suited for real-world hypergraphs.

Förderung

  • University of New South Wales

Zitieren

APA

Luo, Q., Yang, Z., Zhang, W., Zhou, A., Yu, D., Cheng, X., Lin, X., & Guo, S. (2026). Hypergraph decomposition with intersection bounds. The VLDB Journal, 35(4). https://doi.org/10.1007/s00778-026-00985-5

Vancouver

Luo Q, Yang Z, Zhang W, Zhou A, Yu D, Cheng X, et al. Hypergraph decomposition with intersection bounds. The VLDB Journal. 2026;35(4). doi:10.1007/s00778-026-00985-5

BibTeX
@article{Luo2026,
  author = {Luo, Qi and Yang, Zhengyi and Zhang, Wenjie and Zhou, Alexander and Yu, Dongxiao and Cheng, Xiuzhen and Lin, Xuemin and Guo, Song},
  title = {Hypergraph decomposition with intersection bounds},
  journal = {The VLDB Journal},
  year = {2026},
  volume = {35},
  number = {4},
  doi = {10.1007/s00778-026-00985-5}
}
Kostenlos starten →