Co-Clustering Exchangeable Array and Graph Data

• Activity Number: 223
• Type: Topic Contributed
• Date/Time: Monday, August 4, 2014 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): David S. Choi*+ and Patrick Wolfe
• Companies: Carnegie Mellon and University College London
• Keywords: network ; consistency ; community detection ; clustering ; stochastic blockmodel ; nonparametric

Abstract

We analyze the problem of partitioning a 0-1 array or bipartite graph into subgroups (also known as co-clustering), under a relatively mild assumption that the data is generated by a general nonparametric process. This problem can be thought of as co-clustering under model misspecification; we show that the additional error due to misspecification can be bounded by O(n^(-1/4)). Our result suggests that under certain sparsity regimes, community detection algorithms and stochastic blockmodeling may be robust to modeling assumptions, and that their usage is analogous to the usage of histograms in exploratory data analysis.