Streaming, Memory Limited Algorithms for Community Detection
In this paper, we consider sparse networks consisting of a finite number of nonoverlapping communities, i.e. disjoint clusters, so that there is higher density within clusters than across clusters. Both the intra-and inter-cluster edge densities vanish when the size of the graph grows large, making the cluster reconstruction problem nosier and hence difficult to solve. We are interested in scenarios where the network size is very large, so that the adjacency matrix of the graph is hard to manipulate and store. The data stream model in which columns of the adjacency matrix are revealed sequentially constitutes a natural framework in this setting. For this model, we develop two novel clustering algorithms that extract the clusters asymptotically accurately. The first algorithm is offline, as it needs to store and keep the assignments of nodes to clusters, and requires a memory that scales linearly with the network size. The second algorithm is online, as it may classify a node when the corresponding column is revealed and then discard this information. This algorithm requires a memory growing sub-linearly with the network size. To construct these efficient streaming memory-limited clustering algorithms, we first address the problem of clustering with partial information, where only a small proportion of the columns of the adjacency matrix is observed and develop, for this setting, a new spectral algorithm which is of independent interest.
The paper describes two related algorithms for finding clusters under the stochastic block model assumption when there is partial information (in the sense that only a fraction of the columns of the adjacency matrix are revealed) or in a data streaming setting (where fewer than the size of the input bits are retained to perform the computation).Pros: Another contribution to an area of recent interest, both with respect to data-constrained computation, clustering matrices, etc.The main algorithm splits the problem into two steps, which is probably the correct way to do streaming clustering under model assumptions like this stochastic block model.  Making that explicit highlights both important points.Cons:The algorithm is of theoretical interest, as it makes unrealistically strong assumptions for realistic networks of even moderate size and since it doesn't work at important "boundaries" of edge density, e.g., extremely sparse graphs.Claims with respect to how this work fits into the streaming and community literature are very much overstated, as mentioned below.The description of the algorithm seems to not make clear what I think is going on: that under the stochastic block model with large blocks, then input has very nice structure, and so the main goal of the algorithm is to make sure that the sampling doesn't overly concentrate certain quantities in the "empirical" estimates.  For example, I think that is what the trimming step is doing, and I think that is similar to what Feige and others, Montaneri and others, and probably others have done.  A few other comments.  (1) The problem as stated is unrealistic for what most people would consider community detection in realistic networks.  For example, the clusters don't overlap, and the results don't go through when the graphs are extremely sparse (which is typical) or extremely dense (which may arise occasionally).  Thus, they are best viewed as contributing to the recent work on spectral-like algorithms for stochastic block (which also suffer from similar drawbacks) and related models under various computational constraints (which is of interest).(2) No empirical evaluation.  This isn't necessarily a bad thing, since if there were it would likely be trivial (in the sense that they would simply show a phase transition which they establish) or overly-idealized (i.e., they would have to "simulate" memory limitations, since dealing with realistic memory management is very nontrivial).(3) The columns are revealed one by one.  This is a rather strong assumption in terms of motivations, and it means that it is much easier to obtain much stronger results than if elements or blocks are revealed.  For example, much stronger results are obtained in low-rank matrix approximation when columns are sampled than when elements are sampled.  More formal data streaming models, e.g., in the theoretical computer science literature consider other data presentation formats.(4) Finally, if the authors don't know of other related work on clustering or partitioning or community finding, it is for lack of effort.  For example, a few quick web searches find many papers, including the following papers:FENNEL: Streaming Graph Partitioning for Massive Scale Graphs, by Tsourakaki, et al.Online Analysis of Community Evolution in Data Streams, by Aggarwal and YuStreaming Graph Partitioning for Large Distributed Graphs, by Stanton and KliotSparse Cut Projections in Graph Streams, by Das Sarma, Gollapudi and PanigrahyThese papers are all sufficiently different than the present paper that there is novelty in the present paper and no overlap.  But they illustrate that it much more accurate to describe the present paper as an interesting but relatively minor improvement on recent work on stochastic blockmodeling under various well-motivated memory constraints than as the first community detection algorithms in the data stream model or as a paper that introduces the problem of community detection with partial information, both of which are claimed but neither of which is correct.