Bayesian Hierarchical Community Discovery
We propose an efficient Bayesian nonparametric model for discovering hierarchical community structure in social networks. Our model is a tree-structured mixture of potentially exponentially many stochastic blockmodels. We describe a family of greedy agglomerative model selection algorithms that take just one pass through the data to learn a fully probabilistic, hierarchical community model. In the worst case, Our algorithms scale quadratically in the number of vertices of the network, but independent of the number of nested communities. In practice, the run time of our algorithms are two orders of magnitude faster than the Infinite Relational Model, achieving comparable or better accuracy.
The authors propose a generalization of the Bayesian 
      nonparamtric stochastic block model to the hierarchical setting, in order 
      to infer a hierarchy rather than a flat clustering of entities when 
      conditioned on observed links between entities. They propose a learning 
      algorithm based on agglomerative clustering to select a tree which 
      represents valid possible partitions of the entities. They then present 
      empirical results from two corpuses of social connectivity data and 
      conclude that their method is both faster and more accurate than the 
      Infinite Relational Model (IRM), a widely-used model for tasks of this 
      kind. I believe this paper tackles an interesting issue that a 
      significant fraction of the NIPS audience will be interested in. On the 
      technical side, Bayesian nonparametric methods, while attractive from a 
      conceptual point of view, are often quite slow in practice. On the proble 
      domain side, social scientsits are increasingly using sophisticated 
      Bayesian models for analyzing data and so a hierarchical extension to a 
      popular network-discovery model should be appreciated. This paper touches 
      on both those issues. The key insight is that by restricting 
      allowed partitions to conform to a tree structure, the marginal likelihood 
      of the data can be computed efficiently. The IRM must essentially consider 
      the exponential number of possible partitions of the data. However, I was 
      left somewhat confused on how the learning procedure of the trees relates 
      to the generative story behind the Bayesian model. Since it is greedy, I 
      do not think it can be seen as performing true posterior inference over a 
      distribution of trees or finding some kind of point MAP or ML estimate. 
      But I may have misunderstood. I would recommend that the authors try to 
      improve the clarity of Section 4. I found the results to be 
      impressive. In terms of several performance measures (AUC, predictive llh, 
      accuracy), the proposed method performed comparably or slightly better 
      than the IRM, the closest competitor. While the asymptotic improvements in 
      these scores are perhaps not that impresive in absolute terms, the claimed 
      runtime is orders of magnitude faster than IRM inference. I think 
      the overall clarity and writing quality could be improved. First, there 
      are a series of distracting spelling and grammar errors (eg line 126). 
      Second, the prose is sometimes hard to understand. Line 47-50 in the 
      introduction has some vague phrasing (what are 'local changes' in this 
      setting? What are the 'iterations' referring to? Iterations of an MCMC 
      algorithm?), for instance. The authors do not clearly describe the content 
      of the datasets they train on (Monastery networks and NIPS authorship), 
      which could confuse readers who are not already familiar with them. I 
      occasionally found the math somewhat obtuse and unnecessary, such as Eq. 
      5. I also found Figure 3 confusing. Being unfamiliar with the monastery 
      dataset, it is visually unclear which method is performing the best. 
      Perhaps a dataset that more readers will be familiar with would be 
      helpful. Section 4, which presents the core novel contribution of the 
      paper, required several readings to understanding. If these issues 
      could be remedied, however, I believe the proposed approach has enough 
      novelty and the results are strong enough to warrant publication. The 
      authors propose a novel model of graph edge structure that can be seen as 
      a Bayesian version of agglomerative clustering inspired by the IRM. I 
      found the core learning algorithm to be insightful and the experimental 
      results to be strong, but the quality of writing in need of improvement.