TITLE:  Convex Relaxation for Community Detection

ABSTRACT: 

Cluster structures are ubiquitous for large data, and community detection has recently attracted much research attention in applied physics, sociology, computer science and statistics due to its broad applicability in various network datasets. A variety of approaches distinct in essence have thus been proposed, among which convex relaxation have not been extensively explored due to the lack of knowledge of its statistical advantages over other methods, either theoretical or empirical. In this talk, I will focus on explaining the benefits of convex community detection in two aspects: robustness against adversarial nodes and efficacy in networks with heterogeneous degrees. For the robustness, I will show that convex relaxation is able to detect the hidden communities in presence of a portion of arbitrary or even adversarial nodes with strong theoretical guarantees, while standard spectral clustering may fail due to a small fraction of outliers; For networks with heterogenous degrees, I will show that a convex optimization enjoys desirable theoretical properties under the degree-corrected stochastic block model as well as competitive empirical performances compared to the state-of-the-art tractable methods in the literature. The talk consists of my collaborative works with T. Tony Cai, Yudong Chen, and Jiaming Xu.

BIO: Dr. Xiaodong Li is an assistant professor in the statistics department at UC Davis. Prior to that, he worked in the statistics department of Wharton School at University of Pennsylvania for two years. He got Ph.D of mathematics at Stanford University in 2013, and BS at Peking University in 2008. He works on theory and methods in in the intersection of statistics, applied math and machine learning, with current research interests including dimension reduction, randomized algorithms, network data, convex and nonconvex optimization, etc. He has published a series of papers regarding low-rank recovery, matrix completion, phase retrieval and community detection in various journals of statistics, mathematics and engineering such as JACM, IEEE TIT, AoS, ACHA, FOCM, etc.