Nonbacktracking spectral clustering of nonuniform hypergraphs
This work addresses clustering in hypergraph data, which is important for analyzing complex interactions in fields like social networks or biology, but it is incremental as it builds on existing spectral and stochastic blockmodel frameworks.
The authors tackled the challenge of spectral clustering for nonuniform hypergraphs by introducing a method based on the hypergraph nonbacktracking operator, proving computational improvements and demonstrating benefits over graph-based methods in experiments with real and synthetic data.
Spectral methods offer a tractable, global framework for clustering in graphs via eigenvector computations on graph matrices. Hypergraph data, in which entities interact on edges of arbitrary size, poses challenges for matrix representations and therefore for spectral clustering. We study spectral clustering for nonuniform hypergraphs based on the hypergraph nonbacktracking operator. After reviewing the definition of this operator and its basic properties, we prove a theorem of Ihara-Bass type which allows eigenpair computations to take place on a smaller matrix, often enabling faster computation. We then propose an alternating algorithm for inference in a hypergraph stochastic blockmodel via linearized belief-propagation which involves a spectral clustering step again using nonbacktracking operators. We provide proofs related to this algorithm that both formalize and extend several previous results. We pose several conjectures about the limits of spectral methods and detectability in hypergraph stochastic blockmodels in general, supporting these with in-expectation analysis of the eigeinpairs of our studied operators. We perform experiments in real and synthetic data that demonstrate the benefits of hypergraph methods over graph-based ones when interactions of different sizes carry different information about cluster structure.