Active Community Detection with Maximal Expected Model Change

Friday, November 6, 2020 - 1:25pm - 2:25pm
Dan Kushnir (Nokia Bell Labs)

We present a novel active learning algorithm for community detection on networks. Our proposed algorithm uses a Maximal Expected Model Change (MEMC) criterion for querying network nodes label assignments. MEMC detects nodes that maximally change the community assignment likelihood model following a query. Our work is inspired by detection in the benchmark Stochastic Block Model (SBM), where we provide  sample complexity analysis and empirical study with SBM and real network data for binary as well as for multi-class settings. We also cover the most challenging case of sparse degree and below-detection-threshold SBMs, where we observe a super-linear error reduction. MEMC is shown to be superior to the random selection baseline and other state-of-the-art active learners.

Dan Kushnir is a distinguished member of technical staff at Bell Laboratories Data Science group where he has been since 2012. Before that he held the Gibbs assistant professor position at Yale University's Applied Math Program from 2008 to 2012. He obtained his PhD at the Weizmann Institute of Science on the subject of Multiscale Tools for Data Analysis in 2008. He hold BsC in Computer Science from the Hebrew University in Jerusalem. His Current Interests Include Active Learning, efficient Sampling, Harmonic Analysis, Numerical Analysis and Randomized methods.