High-Order Local Clustering on Hypergraphs

RAIDS Lab Authors

Zhengyi Yang

(corresponding author)

Director

Details

Research Area

Tags

Resources

Abstract

Graphs are a commonly used model in data mining to represent complex relationships, with nodes representing entities and edges representing relationships. However, graphs have limitations in modeling high-order relationships. In contrast, hypergraphs offer a more versatile representation, allowing edges to join any number of nodes. This capability empowers hypergraphs to model multiple relationships and capture high-order information present in real-world applications. We focus on the problem of local clustering in hypergraphs, which computes a cluster near a given seed node. Although extensively explored in the context of graphs, this problem has received less attention for hypergraphs. Current methods often directly extend graph-based local clustering to hypergraphs, overlooking their inherent high-order features and resulting in low-quality local clusters. To address this, we propose an effective hypergraph local clustering model. This model introduces a novel conductance measurement that leverages the high-order properties of hypergraphs to assess cluster quality. Based on this new definition of hypergraph conductance, we propose a greedy algorithm to find local clusters in real time. Experimental evaluations and case studies on real-world datasets demonstrate the effectiveness of the proposed methods.

Author Affiliations

@article{wei2024high,
  title = {High-Order Local Clustering on Hypergraphs},
  author = {Wei, Jingtian and Yang, Zhengyi and Luo, Qi and Zhang, Yu and Qin, Lu and Zhang, Wenjie},
  volume = {11},
  url = {https://publications.eai.eu/index.php/sis/article/view/7431},
  doi = {10.4108/eetsis.7431},
  number = {6},
  journal = {EAI Endorsed Transactions on Scalable Information Systems},
  year = {2024},
  month = Nov
}