Convex Relaxation for Community Detection

Seminar | August 30 | 4-5 p.m. | 1011 Evans Hall

 Xiaodong Li, University of California, Davis

 Department of Statistics

Cluster structures might be 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 had not been extensively
explored since its statistical advantages over other methods have seldom been shown, either

theoretically or empirically. In this talk, I will focus on explaining the benefits of convex com-
munity 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 optimiza-
tion method 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.