Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a Belief-Propagation algorithm to effectively solve the problem of online community detection, i.e., in cases where the complete information about the network
is not available to a system. Instead, more and more information becomes available to the system as time progresses.

main_review: The paper proposes a Belief-Propagation algorithm to effectively solve the problem of online community detection, i.e., in cases where the complete information about the network
is not available to a system. Instead, more and more information becomes available to the system as time progresses.

Sections 2-4 are quite well written. In Section 2, it is understood that the vertex and edge sets at time t, namely V(t) and E(t) are subsets of those at time t+1,
i.e. V(t) \subset V(t+1) and so on.

However, it's not quite clear from the experiment description how was the data being supplied to the Streaming BP model proposed.
Since experiments are conducted on complete graphs, I believe the information about the graph was partially fed in.
More details about the settings need to be included about how the initial graph G(1) was chosen. In practice, G(t) growing radially it may actually happen
that a separate connected component of G becomes available, i.e., there is minimal or no connection between V(t+1)-V(t) and V(t), or in other words |V(t+1)-V(t) \cap V(t)| could be small.
How would the streaming BP algorithm do if the partial information being available is of that nature?

Moreover, it's a bit strange to see why weren't more recent approaches for community detection being applied as baselines, e.g. the graph convolutional approaches like SAGE (“Inductive representation learning on large graphs,” in NIPS, 2017), or say even shallow dense vector based approach like retraining node2vec/deepwalk on each G(t) as and when they become available and classifying the test set nodes threafter.

I think the paper needs to compare their streaming-BP results with some other incremental retraining approaches like employing graph convolutional networks etc.       

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: A streaming Stochastic Block Model (SBM) is proposed as null model to analyze streaming community detection algorithms on growing graphs.
A online algorithm based on Belief Propagation (BP) is proposed to estimate community membership in this setting. It is proven to achieve the same accuracy as its offline variant BP in a simplified setting.

main_review: Community detection based on relational data is a common problem and streaming algorithms that scale to large networks could be highly valuable.
The provided theoretical insights and proposed algorithms could make a valuable contribution to the field. Yet, the limitations are not clearly discussed and important related information is scattered between different sections, which makes it difficult to assess the validity of some of the claims.
My biggest concern is that theoretical insights and algorithms are limited to a simplistic Stochastic Block Model that consists of only two communities, for which the connection probabilities are assumed to be known. This is quite detached from possible application scenarios.
Detailed comments follow below.

Strengths:
+ Proposal of a null model for streaming community detection algorithms, which is based on the Stochastic Block Model (SBM) 
+ Proposal of streaming versions of BP, STREAMBP and STREAMBP*, that achieve optimal estimation accuracy (in relation to global BP) in case of the simple two community SBM.
+ Theoretical insights:
  * proof that, in the absence of side information, no local streaming algorithm can achieve non-trivial community membership reconstruction
  * STREAMBP achieves the same accuracy as offline BP in case of available side information (assuming a simple SBM with only two communities)
+ Conjectures of optimality for STREAMBP follow naturally from the theoretical insights. 
+ Experiments on synthetic and real world data provide evidence for the utility of the proposed algorithms. 

Weaknesses:
- The network growth model (streaming SBM) does not seem to be appropriate in most real world applications:
* Only one node arrives randomly at each time point.
* This node will be disconnected from the current graph G_{t-1} with high probability because it will likely be connected to other nodes in the large full graph, which have not been arrived yet. This is in stark contrast to the common intuition of network growth models that create connected components (e.g. via preferential attachment or other attachment mechanisms).
* The motivation to model temporal networks does not seem to fit the growth model, as the parameters of the SBM are all static. Nodes just arrive in a random order. The time order does not even depend on a process.
* The SBM is neither degree corrected or allows for multiple community memberships. This makes it an unrealistic description of most real world graphs.
- The streaming SBM might still be interesting to study online algorithms. Yet, I would expect that also streaming algorithms perform better if they explore not uniformly at random arriving nodes but nodes that are connected to the currently available graph.
- The availability of side information in the introduced form seems to be a lot to ask for in applications.
- Is the definition of V^t_v correct on page 4? It is unclear to me why the neighborhoods should not be symmetric for symmetric graphs G(n). V^t_v seem to form connected components that contain v(t).
- Theoretical results apply only to the simple SBM with two groups with intra-community connection probability a and inter-community detection probability b. 
- Also the algorithm STREAMBP is only introduced for this simplistic case.
- The definition of the BP update (Eq. (5)) seems to assume the knowledge of the probabilities a and b? How can this be? Don't the need to be estimated as well?! Shouldn't proofs also cover possible errors in their estimation?!
This problem seems to be acknowledged in the experiments section but it is not clear how the estimates are obtained without the knowledge of the communities Vi to start with.
- No code has been shared.
- A discussion is missing.

Points of minor critique:
- The notation delta over = should be introduced.
- It is surprising that the presence of cycles that hampers STREAMBP (see Sec. 5.1) does not create difficulties in the proof. What is the intuition behind that?
- A detailed explanation how multiple communities (k>2) are handled in the experiments is missing.

limitations_and_societal_impact: A discussion at the end of the paper is completely missing. At least the limitations introduced by focusing only on simple SBMs with two communities and the missing parameter estimation procedure should be addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider a streaming stochastic block model and propose a streaming variant of belief propagation for this dynamical scenario. They show that the proposed version asymptotically performs as good as offline belief propagation.
main_review: This paper tackles the problem of community detection in dynamical networks. The problem is studied in the context of the streaming stochastic block model with the assumptions of (i) bounded degree graphs and (ii) available side information.

They propose a streaming version of belief propagation and a more robust version that reduces the effect of longer cycles by considering only "bounded" information.

Theoretical guarantees are derived that show "optimality" of streamingBP in that it asymptotically achieves the same accuracy as the offline version. The algorithms are also evaluated on a range of synthetic and (limited) real-world scenarios.

I have reviewed an earlier version of this paper and I must admit that the authors did a good job in overhauling the presentation of the work. In the current form, the paper is much clearer and more accessible. Nonetheless, I am certainly surprised that the authors did not address certain aspects that were central points of criticism in the last round of reviews.  In case of acceptance, I would highly encourage the authors to take this points into account. These are:
* First, the discussion of the experimental results
  * The results in Section 5.3 (and in Appendix A/B) show certain aspects regarding the behavior of the algorithms that are not discussed sufficiently. In particular, we can see that StreamBP often does better than its offline version (for a fixed radius $R$). I found this surprising and the paper does not discuss this consistently. E.g., in the Intro it is stated that StreamBP does not outperform offline BP whereas Theorem 2 states that StreamBP performs at least as good as offline BP. I assume that this discrepancy stems from the difference of comparing the algorithm for a fixed radius vs. unbounded radius. If so, this should definitely be clarified!

  * There is some erratic behavior of StreamBp e.g., in Fig. 4a and 4c or in Fig. 7. The brief discussion in Sec. 5.1 does not explain the precise reasons for this behavior or which of the underlying assumptions is violated. Clearly, the optimality of Theorem 2 does not apply in this setting.

  * Also why is it that StreamBP* usually performs worse than StreamBP (and strictly worse than OracleBP) but does a very good job in precisely those scenarios where StreamBP fails?

I would suggest that the authors summarize the main insights of the experiments (also for the additional experiments in the Appdx.) in a couple of sentences (see next point)

* Second, the conclusion (or rather the lack of it)
The lack of conclusion is definitely not optimal as the paper abruptly ends after the experiments. It would definitely help to discuss how the experiments connect to the theory and how they substantiate the claims.


* Finally, missing references 
The studied problem is closely related to community detection in temporal networks. Besides a brief mention of a single paper, the authors fail to reference this line of work and to distinguish their work from the recent progress in temporal networks. I suggest the following references again:
  *  Aslak, Ulf, Martin Rosvall, and Sune Lehmann. "Constrained information flows in temporal networks reveal intermittent communities." Physical Review E 97.6 (2018): 062312.
  * Zhu, Peican, et al. "Community detection in temporal networks via a spreading process." EPL (Europhysics Letters) 126.4 (2019): 48001.
  * He, Jialin, and Duanbing Chen. "A fast algorithm for community detection in temporal network." Physica A: Statistical Mechanics and its Applications 429 (2015): 87-94.
  * Gao, Xubo, et al. "Temporal network pattern identification by community modelling." Scientific reports 10.1 (2020): 1-12.

### Minor Remarks
* Typo in line 45: The ' after the stop should be removed
* The sentence before (2) lacks some object. We define... Let us define...
* The normalization proposed in Sec. 5.1 is pretty standard. Why is it not used for StreamBP?

limitations_and_societal_impact: Partly.

Yes, the proposed algorithm  performs asymptotically the same as offline BP. Yet it does this in fewer iterations, which might make it more applicable to certain scenarios for which offline BP does not scale well enough. Clustering in particular might have detrimental societal effects when applied to social networks (polarization of society, targeted advertising,...)
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper tackles a streaming version of community detection, where the vertices of a graph generated with the classical stochastic block model are revealed sequentially, in a random order.

The authors restrict themselves to what they call $R$-local algorithms, wherein the new information brought by the arrival of a vertex is only propagated at distance at most $R$ of this revealed vertex.

In the absence of side information (i.e. additional information correlated with the ground truth community of each vertex), they show that this class of algorithms is unable to yield meaningful reconstruction when $n$ goes to infinity. In contrast, when side information is present, they provide an algorithm (StreamBP) for community detection, and show that this algorithm matches the performance of the classical belief propagation algorithm (OfflineBP) on the whole graph. 

Those results are complemented by experiments on both synthetic and real-world datasets, comparing the StreamBP and OfflineBP algorithms, as well as several alternatives : simple voting algorithms, and a modified version of StreamBP (StreamBP*), modified to better deal with real-world datasets while enjoying the same theoretical guarantees as the original algorithm.
main_review: This paper establishes strong results on the defined streaming SBM, which is a natural extension of the SBM to dynamic data. This model is justified by the need to study efficient algorithms that work on evolving networks, which is a fairly recent line of work but is gaining more and more traction.

The authors present a very comprehensive view of the topic : they show a strong impossibility result in the absence of side information, and their StreamBP algorithm matches the performance of classical BP while operating in the $R$-local framework. Since classical BP is conjectured to achieve optimal reconstruction in the SBM, this makes it a strong positive result.

The exposition of the article is quite clear, although it assumes some familiarity with BP algorithms : equations (5) and (6) are tersely justified, and the generalization to non-symmetric SBM may not be "immediate" to non-expert readers. Similarly, the StreamBP* could use a bit more justification, maybe in the form of a small appendix section.

The main technical argument of this paper is Theorem 1, which states that $R$-local algorithms in the sense of streaming data are "local" on another sense: each vertex only gets information from vertices that are at a bounded distance from him. This entails directly the impossiblity result, and allows using the classical Galton-Watson tree coupling arguments for the study of the StreamBP algorithm, which uses classical arguments from thereon.

Both proposed algorithms are quite thoroughly tested, on a large variation of synthetic and real-world data. A very interesting phenomenon, which (as far as I could read) is glossed over in the paper, is the fact that StreamBP is more efficient that OfflineBP, especially for small/medium R; this could be worth ponting out/explaining. Those experiments are complemented by another wealth of graphs in the appendix, where in particular the authors study the variation of performance with respect to the estimates of the parameter $a$: the need for for perfect information of the model parameters being one of the drawbacks of BP algorithms, this is a particularly interesting study.

Finally, for lack of space, the authors relegated the study of what they call "Local streaming algorithms with summary statistics" to the supplementary material. This is an extension of $R$-local algorithms where vertices are allowed to share restricted information outside of their $R$-neighbourhood. They show that Corollary 1 also holds in this case, i.e. no such algorithm can achieve non-trivial reconstruction. This is a nice extension of the local algorithms studied previously, and the gist of the (technical) proofs of this section is explained clearly.

Minor remarks:
- Lines 128 - 129: I found the expression "information from [...] is pulled" quite unclear; maybe consider replacing it by "pulled together" or "merged"
- Above line 269: I didn't find the definition for $\hat{\mathbb E}}$, is it simply an averaging over several runs ?
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper considers streaming/dynamic version of the stochastic block model, and provides theoretical guarantee. However, as is evident from multiple reviews, the paper writing is suboptimal. The dynamic version of SBM can be defined in multiple ways. Therefore, the authors need to do a better job in motivating the usefulness of their model, discuss the parameter estimation, and provide a more thorough experimental analysis.
Decision: Accept (Poster)