Hierarchical Structure Construction on Hypergraphs

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

Exploring the hierarchical structure of graphs presents notable advantages for graph analysis, revealing insights ranging from individual vertex behavior to community distribution and overall graph stability. This paper studies hierarchical structures within hypergraphs, where a hyperedge can connect multiple vertices. We observed that directly extending hierarchical frameworks from pairwise graphs to hypergraphs overlooks high-order interactions and can result in either high computational complexity or sparse hierarchy structure. To address this challenge, we introduce a dual-layer hypergraph hierarchy consisting of a primary hierarchy and a secondary hierarchy, enabling the construction of a refined hypergraph hierarchy in linear time. The dual-layer hierarchy establishes a global hierarchy based on vertex cohesion, utilizing vertex-induced subhypergraphs, and a local hierarchy based on hyperedge containment, employing edge-induced subhypergraphs. The combination of global and local hierarchy mitigates the homogeneity and sparsity issues inherent in single-layer hierarchies, allowing more effective modeling of high-order interactions. Furthermore, we propose an efficient hierarchical construction algorithm by leveraging a novel hyperedge-based disjoint set to identify connected subhypergraphs. Additionally, to optimize the local hierarchy further and prevent the emergence of excessively redundant levels, we introduce a compact local hierarchy by defining a restricted subgraph metric to eliminate redundancy caused by large-sized hyperedges. Empirical studies on real-world hypergraphs demonstrate the effectiveness of our approach.

Author Affiliations

@inproceedings{qi2024hierarchical,
  title = {Hierarchical Structure Construction on Hypergraphs},
  author = {Luo, Qi and Zhang, Wenjie and Yang, Zhengyi and Wen, Dong and Wang, Xiaoyang and Yu, Dongxiao and Lin, Xuemin},
  series = {CIKM '24},
  url = {http://dx.doi.org/10.1145/3627673.3679765},
  doi = {10.1145/3627673.3679765},
  booktitle = {Proceedings of the 33rd ACM International Conference on Information and Knowledge Management},
  publisher = {ACM},
  year = {2024},
  month = Oct,
  pages = {1597-1606},
  collection = {CIKM '24}
}