Research Projects

Hypergraphs are generalisations of graphs (a simple undirected graph being just a 2-uniform hypergraph) and are very useful for modelling higher-order interactions in complex networks. In particular, hypergraphs have been used for community detection in networks [Ghoshdastidar and Dukkipati, 2014, Ghoshdastidar and Dukkipati, 2017, Pal and Zhu, 2021, Dumitriu et al., 2021, Dumitriu and Wang, 2023], in biology [Tian et al., 2009, Michoel and Nachtergaele, 2012], for modelling chemical reactions [Skvortsova et al., 2014, Flamm et al., 2015, Mann and Venkatasubramanian, 2023], in modelling citation networks [Ji and Jin, 2016], in recommendation systems [Bu et al., 2010] and for processing image data [Govindu, 2005], among other areas. Therefore, developing statistical inference procedures for hypergraphs with provable guarantees is an important problem with a host of potential applications. In this project, we will mainly focus on the problem on community recovery on hypergraphs and other related statistical inference questions. Community detection on graphs is by now quite well-understood (see Abbe (2018) for a comprehensive survey). Hypergraphs present a number of mathematical and algorithmic challenges. Extensions of algorithms for graphs that work on the adjacency tensor of hypergraphs have been developed. However, these algorithms all suffer from a "curse of dimensionality" due to the adjacency tensor having a polynomially large (polynomial of degree equal to the order of the tensor) number of entries in the number of nodes. In this project, we expect to develop information theoretically optimal algorithms (especially spectral ones) for hypergraph community recovery based on hypergraph adjacency matrices (which are contractions of adjacency tensors) or transforms thereof (e.g., Laplacian, Bethe-Hessian, graph projection, etc.). These matrices only store a quadratic number of entries, and as such algorithms based on them are much more computationally efficient than those based on full adjacency tensors. In the course of our endeavour towards understanding the theoretical underpinnings of such algorithms, we expect to obtain a detailed picture of the limiting spectral behaviour of the aforementioned matrices, and tensor contractions in general, from the point-of-view of random matrix theory. Random-matrix-theoretic results would be key towards a rigorous mathematical understanding of a host of statistical inference techniques (e.g., outlier eigenvalue tests, model selection techniques, spectral clustering, semi-definite-programming-based algorithms, etc.) for hypergraphs based on HAMs. We also expect to develop scalable divide-and-conquer-type algorithms based on HAMs and provide rigorous theoretical guarantees on their performance. Such algorithms would be very useful for scaling up computationally expensive algorithms such as semi-definite programs or variational inference to large hypergraphs.