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@google.... 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, JYL 1
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.....Ai 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 L < 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 +
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(k--)
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-neighborhoood (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(v; G(), F) & (u; 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 enformation-hhooretiaalll 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
Acc
M max
(A(u; =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 of 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 (i(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()) ) (
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- Jueoo (.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
StreemBe StreamBP
StreamBP StreamBP
StreamB
0.8
0.8
StreemBB
OracleOP
Orecle0P
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- ASS1171162 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-4611 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 2513,, 2019.
13


Reviews:
[{"review_id": "V2EZgL4ZvaQ", "reviewer": "Reviewer_QSCc", "summary": "A streaming Stochastic Block Model (SBM) is proposed as null model to analyze streaming community detection algorithms on growing graphs.\nA 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.\n", "questions": "", "limitations": "", "rating": 5, "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": "Community detection based on relational data is a common problem and streaming algorithms that scale to large networks could be highly valuable.\nThe 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.\nMy 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.\nDetailed comments follow below.\n\nStrengths:\n+ Proposal of a null model for streaming community detection algorithms, which is based on the Stochastic Block Model (SBM) \n+ 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.\n+ Theoretical insights:\n  * proof that, in the absence of side information, no local streaming algorithm can achieve non-trivial community membership reconstruction\n  * STREAMBP achieves the same accuracy as offline BP in case of available side information (assuming a simple SBM with only two communities)\n+ Conjectures of optimality for STREAMBP follow naturally from the theoretical insights. \n+ Experiments on synthetic and real world data provide evidence for the utility of the proposed algorithms. \n\nWeaknesses:\n- The network growth model (streaming SBM) does not seem to be appropriate in most real world applications:\n* Only one node arrives randomly at each time point.\n* 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).\n* 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.\n* The SBM is neither degree corrected or allows for multiple community memberships. This makes it an unrealistic description of most real world graphs.\n- 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.\n- The availability of side information in the introduced form seems to be a lot to ask for in applications.\n- 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).\n- Theoretical results apply only to the simple SBM with two groups with intra-community connection probability a and inter-community detection probability b. \n- Also the algorithm STREAMBP is only introduced for this simplistic case.\n- 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?!\nThis 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.\n- No code has been shared.\n- A discussion is missing.\n\nPoints of minor critique:\n- The notation delta over = should be introduced.\n- 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?\n- A detailed explanation how multiple communities (k>2) are handled in the experiments is missing.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "K3Ahl2IR84", "reviewer": "Reviewer_WcZo", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "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.\n\nThey propose a streaming version of belief propagation and a more robust version that reduces the effect of longer cycles by considering only \"bounded\" information.\n\nTheoretical 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.\n\nI 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:\n* First, the discussion of the experimental results\n  * 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!\n\n  * 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.\n\n  * 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?\n\nI 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)\n\n* Second, the conclusion (or rather the lack of it)\nThe 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.\n\n\n* Finally, missing references \nThe 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:\n  *  Aslak, Ulf, Martin Rosvall, and Sune Lehmann. \"Constrained information flows in temporal networks reveal intermittent communities.\" Physical Review E 97.6 (2018): 062312.\n  * Zhu, Peican, et al. \"Community detection in temporal networks via a spreading process.\" EPL (Europhysics Letters) 126.4 (2019): 48001.\n  * 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.\n  * Gao, Xubo, et al. \"Temporal network pattern identification by community modelling.\" Scientific reports 10.1 (2020): 1-12.\n\n### Minor Remarks\n* Typo in line 45: The ' after the stop should be removed\n* The sentence before (2) lacks some object. We define... Let us define...\n* The normalization proposed in Sec. 5.1 is pretty standard. Why is it not used for StreamBP?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Partly.\n\nYes, 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Iqv6bp07at2", "reviewer": "Reviewer_N5WW", "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.\n\nThe 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.\n\nIn 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. \n\nThose 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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "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.\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nBoth 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.\n\nFinally, 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.\n\nMinor remarks:\n- Lines 128 - 129: I found the expression \"information from [...] is pulled\" quite unclear; maybe consider replacing it by \"pulled together\" or \"merged\"\n- Above line 269: I didn't find the definition for $\\hat{\\mathbb E}}$, is it simply an averaging over several runs ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "4OuZTUIjnB-", "reviewer": "Reviewer_Y4Hw", "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\nis not available to a system. Instead, more and more information becomes available to the system as time progresses.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "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\nis not available to a system. Instead, more and more information becomes available to the system as time progresses.\n\nSections 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,\ni.e. V(t) \\subset V(t+1) and so on.\n\nHowever, it's not quite clear from the experiment description how was the data being supplied to the Streaming BP model proposed.\nSince experiments are conducted on complete graphs, I believe the information about the graph was partially fed in.\nMore 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\nthat 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.\nHow would the streaming BP algorithm do if the partial information being available is of that nature?\n\nMoreover, 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.\n\nI think the paper needs to compare their streaming-BP results with some other incremental retraining approaches like employing graph convolutional networks etc.       \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

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)