Clustering Hypergraphs via the MapEquation

Abstract

A hypergraph is a generalization of a graph in that the restriction of pairwise affinity scores is lifted in favor of affinity scores that can be evaluated between an arbitrary number of inputs. Hypergraphs clustering is the process of finding groups in which members of a given hypergraph exhibit a high similarity and dissimilarity with members outside their group. In this paper, we generalize the well-known MapEquation, an optimization equation used in the clustering of nonhypergraphs, for hypergraphs. We develop an agglomerative algorithm, Hypergraph Random Walks (HRW), to find an approximate solution to the generalized MapEquation. Our algorithm requires neither hyperparameter setting nor any restriction on the underlying hypergraph. We show that our algorithm has a strong theoretical performance on the newly defined ring of hyper cliques and demonstrate that our algorithm scales to hypergraphs with large edge sets.

Keywords

• Hypergraph clustering
• random walks
• MapEquation
• hyper cliques