Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The problem of community detection in a complex network (unsupervised learning) is by now very well-established. The last decade and a half have seen great breakthroughs in computing thresholds for various instances of the problem as well as devising algorithms which work well (optimally) over networks sampled from the graph stochastic block model (SBM); more recently, the studies have extended to hypergraphs, as they encode more complex relationships between a set of points through ``hyperedges". The regime of exact recovery of communities has been one of the first for which a threshold was proved (originally by Abbe and Sandon in 2014-15, followed shortly by a different method by Yun and Proutiere), in a general graph case and depending on the newly defined Chernoff-Hellinger divergence. Since then, various results have been shown for different generalizations to uniform and non-uniform models.   Together with my student Haixiao Wang, we have been able to prove an information-theoretic threshold (given through a generalized Chernoff-Hellinger divergence) for the non-uniform hypergraph SBM, and provide two-stage algorithms that achieve exact recovery above the threshold. We have examined the problem both agnostically (with minimal assumptions on parameter knowledge) and with full knowledge of the set of parameters, and also shown that our algorithms also produce an ``optimal" recovery of the communities involved below the threshold.