Optimal hypothesis testing for stochastic block models with growing degrees

Abstract: In this talk, we discuss optimal hypothesis testing for distinguishing a stochastic block model from an Erdos–Renyi random graph when the average degree grows to infinity with the graph size. We show that linear spectral statistics based on Chebyshev polynomials of the adjacency matrix can approximate signed cycles of growing lengths when the graph is sufficiently dense. The signed cycles have been shown by Banerjee (2018) to determine the likelihood ratio statistic asymptotically. In this way one achieves sharp asymptotic optimal power of the testing problem within polynomial time complexity. Time permitting, we will also discuss how linear spectral statistics of a weighted non-backtracking matrix can be used to approximate the likelihood ratio. The talk is based on joint work with Debapratim Banerjee.

Biography: Dr.Zongming Ma is an Associate Professor of Statistics of the Wharton School at the University of Pennsylvania. He received his PhD in Statistics from Stanford University in 2010 and has since then been on the faculty of the Wharton Statistics Department. Dr.Ma’s research interests include high-dimensional statistical inference, non-parametric statistics, network data analysis, and their applications in biomedical data analysis. He is a recipient of a Sloan Research Fellowship and an NSF CAREER Award.