Streaming Belief Propagation for Community Detection
Authors: Yuchen Wu
Jakab Tardos
Mohammadhossein Bateni
André Linhares
Filipe Miguel Goncalves de Almeida
Andrea Montanari
Ashkan Norouzi-Fard
Venue: NeurIPS 2021 Poster (2021)
Keywords: community detection
stochastic block model
streaming algorithm
local algorithm

Abstract: The community detection problem requires to cluster the nodes of a network into a small number of well-connected ‘communities’. There has been substantial recent progress in characterizing the fundamental statistical limits of community detection under simple stochastic block models.  However, in real-world applications, the network structure is typically dynamic, with nodes that join over time. In this setting, we would like a detection algorithm to perform only a limited number of updates at each node arrival. While standard voting approaches satisfy this constraint, it is unclear whether they exploit the network information optimally. We introduce a simple model for networks growing over time which we refer to as streaming stochastic block model (StSBM). Within this model, we prove that voting algorithms have fundamental limitations.  We also develop a streaming belief-propagation (STREAMBP)  approach, for which we prove optimality in certain regimes. We validate our theoretical findings on synthetic and real data

Streaming Belief Propagation for Community Detection
Yuchen Wu Stanford University wuyc14@stanford. edu
Jakab Tardos EPFL jakab. tikab.tardos@epll.co ch
MohammadHossein Bateni Google Research bateni@google com
André Linhares
Filipe Miguel Gonçalves de Almeida
Google Research
Google Research filipea@googlee... google.com
1 iinhares@oogle.ccom com
Andrea Montanari
Ashkan Norouzi-Fard
Stanford University montanari cettinarrttttafforoo
Google Research
Sahbannorouzzi@googlee.
Abstract
The community detection problem requires to cluster the nodes of a network into a small number of well-connected 'communities'. There has been substantial recent progress characterizing the fundamental statistical limits of community detection under simple stochastic block models. However, in real-world applications, the network structure typically dynamic, with nodes that join over time. this setting, would like detection algorithm to perform only limited number updates at each node arrival. While standard voting approaches satisfy this constraint, it is unclear whether they exploit the network information optimally. We introduce a simple model for networks growing over time which we refer to streaming stochastic block model (StSBM). Within this model, we prove that voting algorithms have fundamental limitations. We also develop a streaming peopaf-propagation (STREAMBP) approach, for which prove optimality in certain regimes. We validate our theoretical findings on synthetic and real data.
Introduction
Given single realization of a network = (V,E), E), the community detection problem requires to find partition of its vertices into small number of clusters or 'communities' [GN02, MO04, JTZ04, For10, PKVS12, J
Numerous methods have been developed for community detection on static networks (GN02, CNM04, GA05, RCC+04, L.009, VLBB08, WZCX18] However, the network structure evolves time in most applications. For instance, in social networks new users can join the network; in online commerce new products can be listed; see [WGKM18, GLZ08, KvB+ + 14] for other examples. In such dynamic settings, it is desirable to have algorithms that perform only a limited number of operations each time node joins leaves, possibly revising the labels of nodes in a neighborhood of the new node. (These notions will be formalized below.) Several groups have developed algorithms of this type in the recent past [HS12, CSG16, ZWCY19, MKV 20]. The present paper aims at characterizing the fundamental statistical limits of community detection in the dynamic setting, and proposing algorithms that achieve those limits.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

As usual, establishing fundamental statistical limits requires introducing a statistical model for the network G (V,E), In the case of static networks, precise characterizations have only been achieved recently, and almost uniquely for a simple network model, namely the stochastic block model (SBM) [HILL83, ABFX08, KN11, RCY+ 11 DKMZ11, 1, Mas14, 14, ABH15, AS15, MNS18). In this paper we build on these recent advances and study a dynamic generalization of the SBM, which we refer to as streaming SBM (SISBM).
The SBM can be defined as follows. Each vertex is given a label r(o) drawn independently from a fixed distribution over the set [k] {1. 2, .......... k). Edges are conditionally independent given vertex labels. Two vertices u, V are connected by an edge with probability W (w))))r())- The analyst is given realization of the graph and required to estimate the labels r. We will assume in addition that the analyst has access to some noisy version of the vertex labels, denoted by F = (f(e))nEV. This is a mathematically convenient generalization: the special case in which no noisy observations are available can be captured by letting 7 be independent of r. Further, such a generalization is useful to model cases in which covariate information available at the nodes [MX16].
Informally, the streaming SBM (SISBM) is a version of SBM in which nodes are revealed one at time in random order (see below for formal definition). In order to model the notion that only a limited number of updates is performed each time a new node joins the network, we introduce a class of 'local streaming algorithms.' These encompass several algorithms in earlier literature. e.g. IZGL033 CSG16]. Our definition is inspired and motivated by the more classical definition of local algorithms for static graphs. Local algorithms output estimates for one vertex based only on a small neighborhood around it, and thus scale well to large graphs; see [Suo]] 13] for a survey. A substantial literature studies the behavior of local algorithms for sparse graphs [GT12, HLS114, GS14, Mon15, MX16, FM17].
Our results focus on the sparse regime in which the graph's average degree is bounded. This is the most challenging regime for the SBM, and it also relevant for real-world applications where networks are usually sparse. We present the following contributions:
Fundamental limitations of local streaming algorithms. We prove that, in the absence of side informa- tion, in streaming symmetric SBM (introduced in Section 2), local streaming algorithms (introduced in Section 3) do not achieve any non-trivial reconstruction: their accuracy is asymptotically the same as random guessing; see Corollary 1. This holds despite the fact that there exist polynomial time non-local algorithms that achieve significantly better accuracy. From practical viewpoint, this indicates that methods with a small 'locality radius' (the range over which the algorithm updates its estimates) are ineffective at aggregating information: they perform poorly unless strong local side information is available.
Optimality of streaming belief propagation. On the positive side, in Section 4 we define streaming version of belief propagation (BP), a local streaming algorithm that we call STREAMBP, parame- terized by locality radius R. We prove that, for any non-vanishing amount of side information, STREAMBP achieves the same reconstruction accuracy as offline BP; see Theorem 2. The latter is in turn conjectured to be the optimal offfine polynomial-time algorithm [DKMZI1, Abb17, HS17J. Under this conjecture, there is no loss of performance in restricting to local streaming algorithms as long (1) local side information is available; (2) the locality radius is sufficienlly large; and (3) information is aggregated optimally via STREAMBP.
Let us emphasize that we do not claim (nor do we expect) STREAMBP to outperform offline BP. We use offline BP as an 'oracle' benchmark (as it has the full graph information available, and is not constrained to act in a streaming fashion).
Implementation and numerical experiments. In Section 5 and Appendix A-C, we validate our results both on synthetic data, generated according to the StSBM, and on real datasets. Our empirical results are consistent with the theory; in particular, STREAMBP substantially outperforms simple voting methods. However, we observe that it can behave poorly with large locality radius R. In order to overcome this problem, we introduce a 'bounded distance' version of STREAMBP, called STREAMBP* which appears to be more robust. (STREAMBP* can be shown to enjoy the same theoretical guarantees as STREAMBP.)
2

---

2 Streaming stochastic block model
In this section we present formal definition of the proposed model. The streaming stochastic block model is probability distribution (tS k, p, W, a) over triples (T, F, G) where E [k]" is a vector of labels (here [k] & {l.....Au k)), F [M] are noisy observations of the labels т, and
G (G(O), G(I), ... G[n)) a sequence of undirected graphs. Here G(t) (V) E()) is graph over [V(I]== = / vertices and, for each 0 S < n We will assume, without loss of generality, that ((n) = [n], and interpret (()) as the label associated
V(t) S V( and E(() S E. + 1).
to vertex v E [n). For each 0 S t I n 1, G(t) is the subgraph induced in G(t + 1) by V(t); cquivalently, all edges in Eit + 1) Et) are incident to the unique vertex in V +1)
The distribution SISBM(n, P. a, parameterized
scalar a E [0, - probability vector p = (pi..... .p)) E 4₁ - {a E 10, 1Js, (x, = 1). and a symmetric matrix E [0, _]a*k, We draw the coordinates of 7 independently with distribution p. and set F(u) =(e) with probability 1 a, and F(u) ~ Unif([k] (T(1))) otherwise, independently across vertices:
((f(v) = 31 r(O) = =sp) = -(0700 ---
if $1 = 30:
P(T(v) =
Ps
aa(kk-1
if 81 # 80.
We then construct G(n) by generating conditionally independent edges, given (r, 7), with
(((u,)) E(n)) T, (r()),(()-
Note that the labels provide noisy 'side information' about the true labels T. This information is conditionally independent of the graph G(n) given т. Finally we generate the graph sequence G by choosing a uniformly random permutation of the vertices (o(1), v()). v(n)) and setting ((t) {.(1). ................................ ... u(t)} and G(t) to the graph induced by V(t). If v = v(t), then we define t the arrival order of vertex v. Note that, for each t, G(t) is distributed according to standard SBM with t vertices: G(t) SBM(t, k p, W).
An equivalent description is that (conditional on t, +) StSBM k: p. W, defines Markov chain over graphs. The new graph G(t + 1) is generated from G(t) by drawing the vertex u(t + 1) uniformly at random from [n]] (t), and then the edges (u, o(t + 1)), u V(t), independently with probabilities given by Equation (1).
We are interested in the behavior of large graphs with bounded average degree. In order to focus on this regime, will consider n oc and W W()) 0 with ((n) Wo/n n for matrix 1xk independent of Wo E 20
A case of special interest is the streaming symmetric SBM, StSSBM(n, k a, 6, a), which corresponds to taking p (1/k,...,, 1/k) and Wo having diagonal elements a and non-diagonal elements b. Finally, the case = (k- 1)/k corresponds pure noise F: in this case drop 7 from the observations and we will drop a from the distribution parameters.
Figure I: Evolving process of StSBM.
2.1 Definitions and notations
For two nodes v, o' (tt,, we denote by de(v, v') their graph distance in G(t), i.e., the length of the shortest path in G(t) connecting v and v', with de(u, v') co if no such path exists, We also write d(v, v') d, (v, o') for the graph distance in G(n). For o (nn) and R N+, let (z) (V)(),
denote the ball of radius R in G(t) centered at i.e., the subgraph induced in G(t) by nodes Vi(()) A {v' (t) de(v, v') R} and edges (2) e E(t) with
3

---

E (u). Furthermore, let ((()) _ fo' E V(t): d(e,v') RJ. Throughout the paper, unless otherwise stated, we assume (V), U2) is an undirected edge.
We consider an algorithm A that takes as input the graph G(n) and side information f, and for each (nn) outputs A(e; G(n), f) E [k] as an estimate for r(r). Note that we always assume the arrival orders of vertices are observed (i.e., by observing v E [n] we also observe the unique ł E [n] such that e (t)), thus G(n) contains the arrival order of its vertices. We define the estimation
accuracy of algorithm A as
1 ())
(A E
max TEBx Ti
(EV(
Here G₁ is the group of permutations over [k] and the expectation is with respect to G(n), 7; and the randomness of the algorithm (if A is randomized).
3 Local streaming algorithms
In this section we introduce local streaming algorithms, which are generalization of local algorithms in the dynamic network setting. An R-local streaming algorithm is an algorithm that at each vertex keeps some information available to that vertex. As new vertex v(t) joins, information within the R-neighborhoodd (v(t)) is pulled. An estimate for r(e) is constructed based on information available to In order to accommodate randomized algorithms we assume that random variables (G))ogV(n) Unif(O, 1J), independent of the graph, are part of the local information available to the algorithm.
As an example, we can consider a simple voting algorithm. At each step t, this algorithm keeps in memory the current estimates f(u) E [k] for all E (t).. As new vertex v(t) joins, its estimated label determined according
+(v(()) = argmax,e[k) (s)
Tイ(x) =
== 6
+ E f()=) (v()),))EE(()
(3)
In words, the estimated label at v(t) is the winner of voting procedure, where the neighbors of v(l) contribute one vote each, while the side information at v(l) contributes votes.
For (nn) and E [n]. we denote the subgraph accessible to at time t by G (V,, E,), with initialization go ({v), 0). At time t, we conduct the following updates:
U
V4-1
for U E VH(((()),
V
('EV(((()) D
for v & V&(((t)).
We let G. be the subgraph induced in G(l) by V and denote by Ø (Vi, 8 the corresponding labeled graph with vertex labels and randomness Ç. Namely Di e {(v', f(v'),vv) o' Vt Et A Et. At time all nodes in the R neighborhood of u(t) share the same updated subgraph Pitt) while the rest of the subgraphs stay unchanged. Let us emphasize that the 'neighborhoods' G are not symmetric, in the sense that we can have v1 Gt, but 02 & Gt,
Definition 1 (R-local streaming algorithm). An algorithm A is R-local streaming algorithm if at each time t and for each vertex E (t), it outputs an estimate of (v) denoted by A'(x; G(t), e [k], which is a function uniquely of G
Note that this class includes as special cases voting algorithms (which correspond to R 1) but also a broad class of other approaches. We will compare R-local streaming algorithms with R-local algorithms (non-streaming). In order to define the latter, given a neighborhood (2)()), we define the corresponding labeled graph as (v) A (V)()), (k(v)), with (v(()) & (.))) o' (=))))
Definition 2 (R-local algorithm). An algorithm A is an R-local algorithm if. at each time and for each vertex v (t), outputs an estimate of T (v) denoted by ( G(I), E [k), which is function uniquely of (v).

---

For simplicity, define the final output of an algorithm A by A(u; G(), F) & ("; G(n). F). The next theorem states that, under StSSBM, any local streaming algorithm with fixed radius behaves asymptotically as local algorithm. Here we focus on StSSBM extension to asymmetric cases is straightforward
Theorem 1. Let G be distributed according to StSSBM (n, k; a, b, a), and vo Unif([n)) be vertex chosen independently of G. Then, for any e >> O, there exist ne E *N such that for every n, with probability least 1- E, the following properties hold: (1) 9%, is subgraph B, (vo): and (2) to does not belong to 9 for any v V(n))VV...o))
Under the symmetric SBM, local algorithms without side information cannot achieve non-trivial estimation accuracy as defined in (2) [KMS16]. Therefore we have the following corollary of the first part of Theorem 1.
Under StSSBM(n, k; a, b) with no side information, no R-local streaming algorithm A can achieve non-trivial estimation accuracy. That is, limm-+00 (A()) = 1/k.
Corollary 1.
Remark 1. Corollary does not hold if side information is available. As we will see below, an arbitrarily small amount of side information (any a < (k 1)/k) can be boosted ideal accuracy using R-local streaming algorithmss with sufficiently large R. On the other hand, for fixed small R, a small amount of side information has only limited impact on accuracy. Our numerical simulations illustrate this for voling algorithmss which are R-local for R = 1: they do not provide substantial boost over the use of only side information (ie., the estimated label i (v) = F(v) at all vertices).
Remark 2. In practice we can imagine keeping small memory containing global information and updating it each time a new vertex joins. This global information would be available at each node. For example, we could keep track of the estimated size of each community. For suitable class of algorithms of this type, it can be shown that they cannot achieve non-trivial reconstruction in the symmetric model StSSBM(n, k, o, b) either. Due to space constraints we do not present this result here. Interested readers are referred to Section G in the appendix.
4 Streaming belief propagation
In this section we focus on the symmetric model StSSBM. Notice that this model makes community detection more difficult compared to the asymmetric model, as in the latter case average degrees for vertices are different across communities, and one can obtain non-trivial estimation accuracy by simply using the degree of each vertex. For the symmetric model StSSBM (n, k; a, b, a),, we proved that local streaming algorithms cannot provide any non-trivial reconstruction the true labels no side information is provided, i.c., if a (k- 1)/k. We also comment that, for fixed (small) R. accuracy achieved by any algorithm is continuous in a, and hence a small amount of side information will have small effect.
In contrast, for any non-vanishing side information a < (k- 1)/k, we conjecture that information- theoretically optimal reconstruction is possible using local streaming algorithm, under two condi- tions: (i) the locality radius Rt is large enough; and (ii) the following Kesten-Stigum (KS) condition is met:
(a b)2
1.
(4)
a (k 1)6
We will refer to À as to the 'signal-to-noise ratio' (SNR).
We provide evidence towards this conjecture by proposing a streaming belief propagation algorithm (STREAMBP) and showing that it achieves asymptotically the same accuracy as the standard offline BP algorithm. The latter is believed to achieve cetmmatioon-thoreticaeee the KS threshold [DKMZ11, 1, MNS14J. We will describe STREAMBP in the setting of the symmetric model StSSBM(n, kt a, b, oz), but its generalization to the asymmetric case is immediate.
optimal reconstruction above
The algorithm has a state which is given by a vector of messages indexed by directed edges in G(t), m {m m (u,v) v) E(t)). Note that G(t) is an undirected graph, and each edge (u, v) corresponds to two messages indexed by u + v and v + u. Each message is probability distribution over [k:]
My-oe (mu-s (1), mans (2), mm (k)) AE.
5

---

Figure 2: Update schedule of STREAMBP. Upon the arrival of a new vertex (shown in the leftmost figure), STREAMBP performs the belief propagation updates corresponding to the blue edges in the three other figures, in the order from left to right.
The BP update is a map BP (Ax)* [k] + AR, where (Ax)* denotes the finite sequences of elements of Ax:
BP((m: (s) = (P)(F)(s)
[I (b (a-)mm))(sss))
(5)
Z
1=1
Here (s) & ( (4- 1) and the constant 7 7= =-7(mm is f)
defined implicitly by the normalization condition >>e(m) BP((m;: : is ()))(ss)) = 1. When
message v + u updated, we compute new value by applying the function (5) to the incoming messages into vertex v, with the exception of u v imon-backtracking property):
Ma-+a BP((m E dv \ fu));
Here de denotes the set of neighbors of vertex e in the current graph. When a new vertex v(() joins at time i, the above rule to: (1) update all the messages incoming into v(t), i.e., -> v(),, for w neighbor of vtt) in G(t), and (2) update all messages at distance 1 < R from v(t) in G(t), along paths outgoing from (t). in order of increasing distance L. The pscudocode for STREAMBP is given in Algorithm 1, and an illustration in Figure 2. For the sake of simplicity, we analyze this algorithm in the two-group symmetric model SISSBM(n, 2, a, b, a). We believe that the extension of this analysis to other cases is straightforward, but we leave it out of this presentation.
Our main result is that STREAMBP achieves asymptotically at least the same accuracy as of- fline BP, as originally proposed in [DKMZ11] and analyzed, e.g., in [MX16]. Offline BP per- forms the updates via Equation (6) in paral-
Algorithm Streaming R-local belief propagation
1: for = 1,2...., n do
lel on all the edges of G'nn) for R - 1 itera- tions, and then computes vertex estimates us- ing m. + BP (B((mmyxuJvvaau F(u)). fu)) == arg m m. (s). Note that, for each R, this defines an R-local algorithm, and hence we will refer R as its radius.
2:
11 Update the incoming messages:
3:
for w E Di(w(())) do
4:
mw-+v(t) (P( u u dw {v(t)):((w) end for
5:
6:
// Update the outgoing messages:
Theorem 2. For U E V(n). le Arel;; F) F) E [k] be the estimate of T(U) given by Algorithu (STREAMBP), and (e F) E [k] be the estimate given by offline BP with radius R (equivalently, BP with parallel updates, stopped after R itera- tions). Under the model StSSBM(n, 2, a, b, a). STREAMBP performs at least as well as offline BP:
7:
for r = 1,2..... .. do
.....R for E D (u(t)) do
8:
9:
Let E D((v) on a shortest path connecting and v(t).
10:
my + BP ( : u E Ov' \ (u))i
11:
end for end for 13: end for
for do
inf (Q (A)) 20. O. n00
15: m. + BP -Pe(mm F(u))
Output F(u) == arg max,e(k) m, (s) as an estimate for r(u).
17: end for
conjectured that, in the presence of side information, i.e., for a < (k 1)/k, offline BP optimal among all polynomial-time algorithms [DKMZI1] (provided R can be taken arbitrarily

---

large). Whenever this is the case, the above theorem implies that STREAMBP is optimal as well. In the case of the symmetric model, it is also believed that under the KS condition (Equation 4), and for < (k- - 1)/k, offline BP does indeed achieve the claim has been proven in certain cases by [MX16] we can use the results of [MX16] in conjunction with Theorem 2 to obtain conditions under which STREAMBP is information enformationtheooretiallll theoretically optimal.
optimal accuracy. This
Corollary 2. Suppose one of the following conditions holds (for a sufficiently large absolute constant C)) in the two-group symmetric model StSSBM(n, k = 2, a, b, a): (1) la - bl < 2 and 1/2); (2) (a - b)2 > C(a + b) and 1/2); or (3) a E (0, 10)) Then Algorithm achieves optimal estimation accuracy:
lim sup sup (Rn(An)) sup Sup R-+00 n-020
0.
A
(Here the supremum is taken over all algorithms, not necessarily local or online.)
5 Empirical evaluation
In this section, we compare the empirical performance of two versions of our streaming belief propagation algorithm (Algorithm 1) with some baselines. We consider the following streaming algorithms:
STREAMBP:
proposed algorithm in this work with radius R, outlined in Algorithm 1.
proposed algorithm in this work, which is a STREAMBP. It is described in more detail in Section 5.1, and its pseudocode is given in Algorithm 2.
STREAMBP":
version of
VOTE1X, VOTE2X, VOTE3X: simple plurality voting algorithms that give weight 5 the side information, as defined in Equation (3) (the numbering corresponds to E (1, 2,,,23)) 3}). Despite looking somewhat naïve, voting algorithms are common in industrial applications.
We also compare the streaming algorithms above with ORACLEBP, which is the offline belief propagation algorithm, parameterized by its radius (number of parallel iterations) R. Note that in contrast to the streaming algorithms, to which we reveal one vertex at time (along with its side information and the edges connecting it to previously revealed vertices), ORACLEBP has access to the entire graph and the side information of all the vertices from the beginning.
Our experiments based both on synthetic datasets (Section 5.2) and real-world datasets (Sec- tion 5.3). Because the model considered in this paper assumes undirected graphs, in a preprocessing step convert the input graphs of the real-world datasets into undirected graphs by simply ignoring edge directions. Table shows statistics of the datasets used (after making the graphs undirected); the values used for and b for the real-world datasets are discussed in Section 5.3.
IV
E
Citeseer 3,264
4,536
11.47
0.89
Cora
2,708
5,278
7
17.62
0.90
Polblogs 1,490
16,715
2
40.69
4.23
Synthetic [10,000-50,000] [20,000--000000]
[2-5]
[2.5-18)
[0.05-1]
Table 1: Statistics of the synthetic and real-world datasets. For the synthetic datasets, various experiments with range of parameters are performed.
As the measure of accuracy, we use the empirical fraction of labels correctly recovered by each algorithm, that is
M max Acc
(A(e; =xxo()
T n
(EV(N)
In synthetic data we observe that, as soon as a < (k: 1)/k, k,, the maximization over π not necessary (as expected from theory), and hence drop it.
7

---

5.1 Bounded-distance streaming BP
In our experimental results presented below, we observed that the simple implementation in Algo- rithm exhibits undesirable behaviors for certain graphs. We believe this is caused by two factors. First, unlike ORACLEBP, do not have upper bound on the radius of influence of each vertex in STREAMBP; it may indeed use long paths. Second, the number cycles in the graph increases as a, b grow. Large values of a and b can result many paths being cycles, which negatively affects the performance of the algorithm.
In order to overcome these problems, we use two modifications. The first one is standard: we constrain messages so that ma-+o (s) E [e, = for some fixed small E >> 0 (we essentially constrain the log- likeliiid ratios to be bounded).
The second modification defines variant, presented in Algorithm 2, which we call STREAMBP". Here the estimate at node is guaranteed to depend only on the graph structure and side information within (v), and not on the information outside this ball. This constraint can be implemented in prsssage-passing fashion, by keeping, on each edge, R + 1 distinct messages m mnt""... m corresponding to different locality radii.
5.2 Synthetic datasets
Figure 3 illustrates the effect of the radius on the performance of the algorithms." 1 We use various settings for k, 6, We observe that voting al- gorithms do not perform significantly better than the baseline! 1 - (dashed line). This is due both to the very small radius R = of these algo- rithms, and to the specific choice of the update rule. For R = 1, STREAMBP and STREAMBP perform significantly better than voting, showing that their update rule is preferable. Their accuracy improves with R, and is often close to the opti- mal accuracy (i.e. the accuracy of ORACLEBP for large R) already for R x 5.
Algorithm 2 STREAMBP". Bounded-distance streaming BP
for = 1,2,...,, n
2:
for E (v((()) do
3:
m (-))1(1) + 1/k
4:
for = 1,2, R do
5:
m v-
BP((m
end for end for
7:
8:
for U. E Di(v(t) do
In Figure 4, we study the effect of the SNR pa- rameter x, defined in Equation (4), on the perfor- mance of the BP algorithms. The accuracy the algorithms improves as À increases. It is close to the baseline 1 - a when the SNR is close to the KS threshold À 1, and then it improves for large A. This is a trace of the phase transition the KS threshold which is blurred because of side information. For large values of R, the ac- curacy of our streaming algorithms STREAMBP and STREAMBP nearly matches that of the op- timal offline algorithm ORACLEBP.
9:
m v(()+v f- 1/k
10:
for i = 1.2...., R do
11:
m ((t)+v
BP((m) (0()) ) (0
1-1
12:
end for end for
13:
14:
for 2,3, R do
15:
for D (v(t)) do
16:
Let o' E (D) on a shortest path
connecting and vt).
17:
for 1,2, R do
18:
m +0 BP( BP((m (m. u- boeoo (.1
Further experiments on synthetic datasets are re- ported in Appendix A. We then present in Ap- pendix B the result of experiments where no side
19:
end for
20:
end for
information is provided to the algorithms. We ob-
21:
end for
serve that in the streaming setting, and for small
22: end for
radius (ft), neither STREAMBP nor PT achieves high accuracy (above 1/k) in the ab- sence of side information, suggested by our theoretical results.
23: // Compute the estimates:
24: for u E V do
25: m.
Rt " F(u))
26: Output f(u) == arg max, (s)
27: end for
Notice that the three voting algorithms do not depend on the radius, resulting in horizontal lines in the diagram.
8

---

5.3 Real-world datasets
We further investigate the performance of our algorithms on three Citeseer [RA15], and Polblogs [AGO5]. Cora and Citeseer are academic citation networks: vertices represent scientific publications partitioned into represent citations of publication by another. The Polbiogs dataset represents the structure of the political blogosphere in the United States around its 2004 presidential election: vertices correspond to political blogs, and directed edges represent the existence of hyperlinks from one blog to another. The blogs are partitioned into = classes based on their political orientation (liberal or conservative).
datasets: Cora [RA15],
and k classes respectively; directed edges
As mentioned in the beginning of Section 5, in preprocessing step we convert the input graphs of the real-world datasets into undirected graphs by simply ignoring edge directions. Also, since the graphs do not stem from the models of Section 2, we use oracle estimates of parameters a and obtained by matching the density of intra- and inter-community edges with those in the model S1SSBM(n, k ã, b, ar). Namely, for graph G = (V, E), letting Vi...., V& S V be the ground-truth communities, we set
à [V] EvEra) E(u,)EE 1 (u, V.) Eie(M] (v
i -I- E())e(?)) E(unee fu E Vi, E Vi} EmenE) [VI]]
For each dataset, we run the streaming algorithms STREAMBP and STREAMBP" using the parameters à and b = b. Notice that these estimates cannot be implemented in practice because we do not know the communities VG to start with. However, the performances appear not to be too sensitive to these estimates; we provide empirical evidence of this in Appendix A.
Figure 5 shows the accuracy of different algorithms these datasets, for selected values of Although the graphs in these datasets are not random graphs generated according to StSBM, the empirical results generally align with the theoretical results we proved for that model. Specifically, see that our streaming algorithm STREAMBP is approximately as accurate as the ofline algorithm ORACLEBP, and significantly better than the voting algorithms. STREAMBP produces high-quality results for Cora and Citeseer datasets, but behaves erratically on the Polblogs dataset. As Polblogs is relatively dense compared with Cora and Citeseer thus contains more cycles, such phenomenon likely due to the issues discussed in Section 5.1.
Appendix C provides additional details these experiments, well results for other values of
0.8
0.9
Vote1X
Accuracy
Accuracy
Vote2X
Vote3X
0.7
0.8
StreamBP
StreamBP*
0.6
0.7
OracleBP
Radius (R)
Radius (R)
(a) 1: = 2, a
3, b .1. 4.
(b) k = 2, 5, b
.5, 3.
0.7
Accuracy
0.7
Accuracy
0.6
0.6
0.6
0.5
0.5
0.4
0.5
0.4
0.3
2
8
10
2
4
8
10
2
4
6 8 10
Radius (R)
Radius (R)
Radius (R)
(c) l/ = 3, 4, 05,
55.
(d) k: = 0, 3, 11
-6.
(e) h: 5, a 8, 11 .7.
Figure 3: Results of the experiments synthetic datasets with 50,000 vertices. The black dashed line represents the accuracy of the noisy side information (without using the graph at all), namely a.

---

1.0
Accuracy
Accuracy
Accuracy
0.9
0.9
0.9
StreamBe StreamBP
StreamBP StreamBP Orecle0P
StreamB
0.8
0.8
StreemBB
OracleOP
GracleOP
1.0
2.0
2.5
3.0
(A)
(A)
SNR
(a) R
(b) R
(c)
Figure 4: Results of the experiments on synthetic datasets with 50,000 vertices, with k 2, a bb 8, - 0.2, as we increase the ratio À from 1.0 to 3.0. The black dashed line represents the accuracy of the noisy side information (without using the graph at all), namely 1 a.
0.8
Vote1X
Accuracy
0.7
Accuracy
0.88
Vote3X
0.6
StreamBP
0.6
0.4
OracleBP
Radius (R)
Radius (R)
Radius (R)
(a) Cora (k 7), 0.6.
Citeseer (k- 6), 0.6.
(c) Polblogs (k 2), 0.3.
Figure 5: Results of experiments on real-world datasets. The black dashed line represents the accuracy of the noisy side information (without using the graph at all), namely a.
Acknowledgments and Disclosure of Funding
A.M. and Y.W. were partially supported by NSF grants CCF-2006489, IIS- ASS-171162 and the ONR grant N00014-18-1-2720
J.T. has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No 759471).
10

---

References
[Abb17] Emmanuel Abbe. Community detection and stochastic block models: recent develop- ments. The Journal of Machine Learning Research, 18(1):6446 6531, 2017.
[ABFX08] Edoardo Maria Airoldi, David M Blei, Stephen E Fienberg, and Eric Xing. Mixed membership stochastic blockmodels. Journal of machine learning research, 2008.
[ABH15] Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall. Exact recovery in the stochastic block model. IEEE Transactions on Information Theory, 62(1):471-487, 2015.
[AG05] Lada A. Adamic and Natalie S. Glance. The political blogosphere and the 2004 u.s. election: divided they blog. In LinkKDD, pages 36-43, 2005.
[AS15] Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 670-688. IEEE, 2015.
[CNM04] Aaron Clauset, Mark EJ Newman, and Cristopher Moore. Finding community structure in very large networks, Physical review E, 70(6):06611) 11, 2004.
[CSG16] Mário Cordeiro, Rui Portocarrero Sarmento, and Joao Gama. Dynamic community detection evolving networks using locality modularity optimization. Social Network Analysis and Mining, 6(1):15, 2016.
[DKMZ11] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymp- totic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):066100 106, 2011.
[FM17] Zhou Fan and Andrea Montanari. How well do local algorithms solve semidefinite programs? In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 604 614, 2017.
[For10] Santo Fortunato. Community detection in graphs. Physics reports, 486(3-5):55-17, 2010.
[GA05] Roger Guimera and Luis A Nunes Amaral. Functional cartography of complex metabolic networks. nature, 433(7028):895-990) 2005.
[GLZ08] Andrew B. Goldberg, Ming Li, and Xiaojin Zhu. Online manifold regularization: A new learning setting and empirical study. Machine Learning and Knowledge Discovery in Databases, European Conference, ECML/KKDD, volume 5211 of Lecture Notes in Computer Science, pages 393-407. Springer, 2008
[GNO2] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821-7826, 2002.
[GS14] David Gamarnik and Madhu Sudan. Limits of local algorithms over sparse random graphs. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 369-376, 2014.
[GT12] Shayan Oveis Gharan and Luca Trevisan. Approximating the expansion profile and almost optimal local graph clustering. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 187-196. IEEE, 2012.
[HLL83] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
[HLS14] Hamed Hatami, László Lovász, and Balázs Szegedy. Limits of locally-globally conver- gent graph sequences. Geometric and Functional Analysis, 24(1):269-296, 2014.
[HS12] Petter Holme and Jari Saramäki. Temporal networks. Physics reports, 519(3)997-125, 2012.
11

---

[HS17] Samuel B Hopkins and David Steurer. Efficient bayesian estimation from few samples: community detection and related problems. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 379-390. IEFE, 2017.
[JTZ04] Daxin Jiang, Chun Tang, and Aidong Zhang. Cluster analysis for gene expression data: a survey. IEEE Transactions on knowledge and data engineering, 16(11): 16(11):1370-1388 2004.
[JYL+18] Muhammad Aqib Javed, Muhammad Shahzad Younis, Siddique Latif, Junaid Qadir, and Adeel Baig. Community detection in networks: A multidisciplinary review. Journal of Network and Computer Applications, 108:87-111, 2018.
[KMS16] Varun Kanade, Elchanan Mossel, and Tselil Schramm. Global and local informa- tion in clustering labeled block models. IEEE Transactions on Information Theory, 62(10)):500-599) 5917, 2016.
[KNI1] Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1):016107, 2011.
[KyB+14] Georg Krempl, Indre Žliobaite, Dariusz Brzeziúski, Byke Hüllermeier, Mark Last, Vincent Lemaire, Tino Noack, Ammar Shaker, Sonja Sievi, Myra Spiliopoulou, and Jerzy Stefanowski. Open challenges for data stream mining research. SIGKDD Explor. Newsl., 16(1):1-10, September 2014.
[LF09] Andrea Lancichinetti and Santo Fortunato. Community detection algorithms: com- parative analysis. Physical review E, 80(5):056117, 2009.
[LP17] Russell Lyons and Yuval Peres. Probability on trees and networks, volume 42, Cam- bridge University Press, 2017.
[Mas14] Laurent Massoulié, Community detection thresholds and the weak ramanujan property. In Proceedings of the forty-sixth annual ACM symposium Theory of computing. pages 694-703, 2014.
[MKV+20] L-E Martinet, MA Kramer, W Viles, LN Perkins, E Spencer, CJ Chu, SS Cash, and ED Kolaczyk. Robust dynamic community detection with applications to human brain functional networks. Nature communications, 11(1):1-13, 2020.
[MNS14] Elchanan Mossel, Joe Neeman, and Allan Sly. Belief propagation, robust reconstruction and optimal recovery of block models. In Conference on Learning Theory, pages 356-370, 2014.
[MNS15] Elchanan Mossel, Joe Neeman, and Allan Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162(3-4):431-461, 2015.
[MNS18] Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. Combinatorica, 38(3):665-708, 2018
[MO04] Sara C Madeira and Arlindo L Oliveira. Biclustering algorithms for biological data anal- ysis: survey. IEEE/ACM transactions on computational biology and bioinformatics, 1(1):24 45, 2004.
[Mon15] Andrea Montanari. Finding one community in a sparse graph. Journal of Statistical Physics, (2)(2)2733299, 2015.
[MX16] Elchanan Mossel and Jiaming Xu. Local algorithms for block models with side information. In Proceedings the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 71-80, 2016.
[PKVS12] Symeon Papadopoulos, Yiannis Kompatsiaris, Athena Vakali, and Ploutarchos Spyri- donos. Community detection in social media. Data Mining and Knowledge Discovery, 24(3):515-555 2012. 2012.
12

---

[RA15] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization, AAAI, 2015.
[RCC+04] Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and Domenico Parisi. Defining and identifying communities in networks. Proceedings of the national academy of sciences, 101(9):2658 211226668-666,, 2004.
11C++11] Karl Rohe, Sourav Chatterjee, Bin Yu, et al. Spectral clustering and the high- dimensional stochastic blockmodel. Annals of Statistics, 39(4):1878- 1915, 2011.
[Suo13] Jukka Suomela. Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2):1- 40, 2013.
[Ver18] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[VLBB08] Ulrike Von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. The Annals of Statistics, pages 555-586, 2008.
[WGKM18] Tal Wagner, Sudipto Guha, Shiva Prasad Kasiviswanathan, and Nina Mishra. Semi- supervised learning on data streams via temporal label propagation. In Proceedings of the 35th International Conference Machine Learning, ICML, volume 80 of Proceedings of Machine Learning Research, pages 5082-5091. PMLR, 2018.
[WZCX18] Feifan Wang, Baihai Zhang, Senchun Chai, and Yuanqing Xia. An extreme learning machine-bard based community detection algorithm in complex networks. Complexity, 2018, 2018.
[ZGL03] Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty. Semi-supervice learning using gaussian fields and harmonic functions. Tom Fawcett and Nina Mishra, editors, Machine Learning, Proceedings of the Twentieth International Conference ICML, pages 912-919, AAAI Press, 2003.
[ZWCY19] Xiangxiang Zeng, Wen Wang, Cong Chen, and Gary Yen. consensus community- based particle swarm optimization for dynamic community detection. IEEE transactions on cybernetics, 5066):25022255 2213,, 2019.
13


Reviews:
[{"review_id": "yh3jvIoyXVX", "reviewer": "Reviewer_LCrq", "summary": "This paper proposes to do community detection in a variant of the stochastic block model for which nodes arrive in a streaming fashion, and there may exists noisy estimates of the real labels. They prove that if the noise render the side information uninformative, a local streaming algorithm is equivalent to a local algorithm, which cannot achieve non-trivial accuracy. If the side information is informative, they provide a belief propagation algorithm in the streaming setting which achieves comparable accuracy to offline BP asymptotically. Offline BP has been conjectured to be optimal, so their algorithm would also be optimal if the conjecture is proven (it is in special cases). They also provide another algorithm which is in practice more consistent than StreamBP.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "#################################################################### \n\n                  DISCLAIMER                                                \n####################################################################\n\nI'm not an expert on community detection nor on the stochastic block model, and only have basic knowledge of it. I therefore cannot vouch for the novelty of their algorithm/proof techniques or the originality of the work. I did check their proofs and did not notice errors, but similarly I'm not sure I would have noticed if there was any.\n\n####################################################################\n\n                  OVERALL                                                \n####################################################################\n\nI liked this paper.\n1. The writing is excellent. \n2. While the algorithm seems intuitive, the proofs appear (to me, a non-expert) technically strong.\n3. The results are interesting and powerful if that conjecture holds.\n4. The experimental section is convincing, with experiments on synthetic and real-life networks.\n5. Too often, when a paper is technically strong, the experiments seem like an afterthought to show it's not terrible in practice. Here, it seems the chaotic behavior of StreamBP informed the design of StreamBP*, which in turn got its own analysis, which I appreciate.\n\n\n####################################################################\n\n                  POSITIVE COMMENTS                                                \n####################################################################\n+ The authors provides many insights and intuition throughout the paper (e.g. \"An equivalent description is that[...] defines a Markov chain\nover graphs\", \"one can obtain non-trivial estimation accuracy by simply using the degree of each vertex\" etc.). This makes I very easy to follow the proof. It was excellent writing.\n+ The results appear strong. There is a negative result when there is no side information, and an (up to a conjecture) optimal algorithm when there exists enough information.\n+ Their algorithm is simple.\n+ I was surprised online algorithms compared with offline SOTA in this setting.\n\n####################################################################\n\n                  NEGATIVE COMMENTS                                                \n####################################################################\n- I may have missed it, but it seems $a$ and $b$ are known for the message passing algorithm. This seems like a strong assumption, and I would have liked to see it discussed.\n- Similarly, we would intuitively expect that the number of communities could grow when we add nodes. A comment on the fact that this is not the setting considered and why could improve the paper.\n\nMinor comments:\n- line 139, adding a line saying \"all nodes connected to each nodes in the neighborhood R of $v$ are now connected through $v$ while the rest of the graph stays unchanged\" would help understanding the following lines faster, since the notation is heavy.\n- line 142, \"Let us emphasize that the ‘neighborhoods’ Gt are not symmetric\" could be explained further, for instance stating that neighborhood are updated only up to depth $R$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5h"}, "extra_text": {}}, {"review_id": "dsOHQyljlNj", "reviewer": "Reviewer_y2ff", "summary": "The paper considers the problem of recovering the communities in a streaming version of\nstochastic block models, using information within a bounded radius. The main technical\nresults are the limits of recovery with no side information, and a streaming version of\nbelief propagation which has the same reconstruction accuracy as the offline BP\nalgorithm using side information. The algorithms are evaluated on synthetic and real\nnetworks, and show good performance.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There has been a lot of work on stochastic block models, and\npaper studies a problem of reconstructing an SBM in which nodes appear in a sequence.\nThe main result showing that side information gives the same performance as the \noffline algorithm is quite intereesting.\nThe paper is technically quite involved. The experiments match the theoretical results.\nThe notion of streaming and the specific variation of SBM considered here\nis a bit confusing--- the algorithms are not streaming in the standard models,\nand the motivation for the graph model is not very clear.\n\nThe presentation could be improved quite a bit to make it more readable. There is quite\na bit of notation, which needs some work, and a table can be helpful.\n\nAdditional comments:\n\nlines 88-91: it would be useful to give some more motivation for the noisy labels\n\\tilde{\\tau}. Is the specific model here relevant in some application? It is not\nclear if \"side information\" is the right name for this\n\neqn (2): shouldn't it be \\tau\\circ\\pi, instead of the other way around? The permutation\nis on the nodes, not the labels\n\nLines 118-122: if we can assume that the arrival order is known, then the accuracy metric\nfor the algorithm in (2) is not clear. Wouldn't the permutation \\pi be fixed in that case?\n\nThe streaming aspect of the StSBM model is confusing. Looks like the edges and labels\nare defined independent of the node ordering\n\nIt would be useful to explain the implication of Theorem 1 a bit more in the remarks.\nFor instance, how large does r_{\\epsilon} have to be?\n\nsection 4 talks about a contrast with the assymetric model, which hasn't been defined\nso far.\n\nThe use of the term \"streaming\" is a bit confusing, considering the standard notion of\nstreaming algorithms. For instance, Algorithm 1 is not implemented in the standard\nstreaming model.\n\nsection 5.3: are the parameters k=7 and k=6 good fit for the Cora and Citeseer networks?\nThey also have skewed degree distributions, so is an SBM an approprate model to\nconsider for them?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no discussion on this", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "BTWCJcfF2DQ", "reviewer": "Reviewer_YnVr", "summary": "This paper studies a dynamic version of the stochastic block model, named as streaming stochastic block model (StSBM). The authors consider a sparse regime and analyze the asymptotic behavior of the model. In particular, the authors show that without some side information about the node labels, recovery of the true labels through a R-local streaming algorithm is no better than random guessing (Corollary 1). The authors also propose a streaming R-local belief propagation algorithm (StreamBP), and show their streaming algorithm perform as good as the offline version algorithm (Theorem 2). Empirical evaluations using synthetic and real-world datasets are provided in the paper.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThe problem considered in the paper is well motivated. To me the proposed results are novel. For the StSBM, the proposed algorithm StreamBP uses only local information and achieves an accuracy asymptotically as good as that of the offline algorithm. This is shown both theoretically and empirically. Although the authors only focus on the symmetric version of the model with k = 2, it seems the proof is extendable. In the experiment section it is shown that for k > 2, the proposed algorithm is still as good as the offline algorithm. \n\nThe paper is well written and organized for most of the time. The model is clearly defined in the preliminary section.\n\nWeakness:\nI am not sure technically how much the proof in this paper is different from that in [MX16]. Despite of the streaming vs. offline change, it seems that the proof of Theorem 2 is similar to that in [MX16].\n\nInstead of predicting the true cluster label of each node, what can be said about StreamBP if one is interested in identifying just the cluster membership, i.e., recovery up to permutation of clusters? The latter is a more common objective in SBM literature (e.g., [Abb17, ABH15]). In such case one does not need access to side information.\n\nThere are some notations that are not clearly defined by the time of their first appearance:\n- Neighborhood B_R^t (Line 129)\n- What does \\Xi do (Line 131)?\nFurthermore, it will be helpful if the authors can provide some example figures explaining StSBM in Section 2. A simple way to do so would be showing the evolution of a network for several t's. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretic work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Each reviewer has a positive opinion of this submission, which deals with a relevant problem. I recommend acceptance.
Decision: Accept (Poster)