Exact Blind Community Detection From Signals on Multiple Graphs

IEEE Transactions on Signal Processing, vol. 68, pp. 5016–5030

Abstract

Networks and data supported on graphs have become ubiquitous in the sciences and engineering. This paper studies the `blind' community detection problem, where we seek to infer the community structure of a graph model given the observation of independent graph signals on a set of nodes whose connections are unknown. We model each observation as filtered white noise, where the underlying network structure varies with every observation. These varying network structures are modeled as independent realizations of a latent planted partition model (PPM), justifying our assumption of a constant underlying community structure over all observations. Under certain conditions on the graph filter and PPM parameters, we suggest simple algorithms for determining (i) the number of latent communities and (ii) the associated partitions of the PPM. We then prove statistical guarantees in the asymptotic and non-asymptotic sampling cases. Numerical experiments on real and synthetic data demonstrate the efficacy of these algorithms.

Authors 4

1. T. Mitchell Roddenberry

   Rice University

   Affiliation as printed

   Department of Electrical and Computer Engineering, Rice University, Houston, USA

2. Michael T. Schaub Aachen Department of CS

   University of Oxford · RWTH Aachen University

   Affiliation as printed

   Department of CS, RWTH Aachen University, Aachen, Germany

   Department of ES, University of Oxford, Oxford, U.K

3. Hoi-To Wai

   Chinese University of Hong Kong

   Affiliation as printed

   Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, Hong Kong

4. Santiago Segarra

   Rice University

   Affiliation as printed

   Department of Electrical and Computer Engineering, Rice University, Houston, USA