Clustering of vertices in random hypergraphs

Zoom Link

Fast algorithms for recovering a latent community structure from an observed hypergraph are usually based on the spectral decomposition of a matrix associated with the hypergraph. Their statistical accuracy can be evaluated by analysing expected error rates for randomly generated hypergraphs with a given community structure, such as the hypergraph stochastic block model (HSBM). Fast and provably exact community recovery algorithms are usually based on aggregating the observed adjacency tensor into a similarity matrix, the entries of which describe the number of hyperedges indicent to a particular node pair. Unfortunately, the mapping of the adjacency tensor to a similarity matrix loses information, and in some cases this information loss may be statistically significant. Therefore, it still remains unknown whether a fast and exact community recovery algorithm exists in the general setting. Instead of the similarity matrix, an alternative is to apply linear-algebraic techniques to a wide matrix obtained by lossless flattening the adjacency tensor. In this presentation I discuss ongoing research on the analysis of a community recovery algorithm based on flattening the observed hypergraph adjacency tensor. In particular, the approach yields a strongly consistent estimator for recovering communities in d-regular hypergraphs with n >> 1 nodes, for which the average hyperedge density is of order at least n^{-d/2}. In still sparser regimes, community recovery is known to be possible but there are no known fast algorithms. These findings suggest that community recovery from d-uniform hypergraphs with d ≥ 3 may be much harder than what one might expect based on analogous theoretical results for graphs (d=2).

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.