Jingtian Wei, University of New South Wales
Graphs serve as a commonly used model to represent complex relationships for data mining, where vertices represent entities and edges represent relationships. However, limitations arise with graphs in modelling high-order relationships. In contrast, hypergraphs provide a more versatile representation, allowing edges to join any number of vertices. This empowers hypergraphs with the ability to model n-ary relationships and high-order information present in real-world applications. This project studies the problem of local clustering in hypergraphs, which computes a cluster near a given seed node. While extensively explored in the context of graphs, this problem has received little attention for hypergraphs. Current methods extend graph-based local clustering directly 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. It introduces a novel conductance measurement that leverages the high-order properties of hypergraphs to assess the quality of a cluster. Based on this new definition of hypergraph conductance, we propose an algorithm for local clustering in hypergraphs. Additionally, a greedy algorithm is introduced to provide real-time approximations of local clusters. Experimental evaluations on real-world datasets showcase the effectiveness and efficiency of the proposed methods.