MSHC: a multi-stage hypergraph clustering algorithm

Abstract

As a high-dimensional extension of ordinary graphs, hypergraphs can more flexibly reflect high-order complex relationships between nodes. Hypergraph clustering aims to discover complex high-order correlations in powerful hypergraph structures. In response to challenges faced by current hypergraph clustering algorithms, such as extremely high complexity, unstable clustering results, and the tendency to fall into local optima, a multi-stage hypergraph clustering algorithm denoted as MSHC is proposed based on the idea of hypergraph partitioning. This algorithm divides the hypergraph clustering process into three stages: hypergraph reduction, hypergraph initial clustering, and optimization migration. In the first stage, a fast reduction method that preserves the hypergraph structure is proposed to reduce the complexity of subsequent algorithms. In the second stage, a similarity measurement method between hypergraph nodes based on set pair analysis theory is introduced, and hierarchical clustering algorithm is applied for initial clustering. Four different cluster merging strategies are employed to increase the diversity of clustering schemes. In the final stage, the genetic algorithm is applied to obtain the optimal hypergraph clustering scheme. Comparative experiments are conducted with two traditional hypergraph clustering algorithms on three data sets with different sizes. Experimental results show that the hypergraph modularity index of the MSHC algorithm is improved by 0.079 and 0.077on the Songs_genres and Papers_keywords datasets respectively, and is only reduced by 0.006 on the Movies_genres dataset.

Keywords

• data processing
• hypergraph clustering
• genetic algorithm
• set pair analysis theory
• hypergraph reduction
• multi-stage clustering
• hypergraph modularity