summaries: A streaming Stochastic Block Model (SBM) is proposed as null model to analyze streaming community detection algorithms on growing graphs. A online algorithm based on Belief Propagation (BP) is proposed to estimate community membership in this setting. It is proven to achieve the same accuracy as its offline variant BP in a simplified setting.  This paper tackles a streaming version of community detection, where the vertices of a graph generated with the classical stochastic block model are revealed sequentially, in a random order.  The authors restrict themselves to what they call $R$-local algorithms, wherein the new information brought by the arrival of a vertex is only propagated at distance at most $R$ of this revealed vertex.  In the absence of side information (i.e. additional information correlated with the ground truth community of each vertex), they show that this class of algorithms is unable to yield meaningful reconstruction when $n$ goes to infinity. In contrast, when side information is present, they provide an algorithm (StreamBP) for community detection, and show that this algorithm matches the performance of the classical belief propagation algorithm (OfflineBP) on the whole graph.   Those results are complemented by experiments on both synthetic and real-world datasets, comparing the StreamBP and OfflineBP algorithms, as well as several alternatives : simple voting algorithms, and a modified version of StreamBP (StreamBP*), modified to better deal with real-world datasets while enjoying the same theoretical guarantees as the original algorithm. 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. The paper considers the problem of recovering the communities in a streaming version of stochastic block models, using information within a bounded radius. The main technical results are the limits of recovery with no side information, and a streaming version of belief propagation which has the same reconstruction accuracy as the offline BP algorithm using side information. The algorithms are evaluated on synthetic and real networks, and show good performance. 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.
abstractText: 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.
authors.name: Yuchen Wu
references.authors: Emmanuel Abbe
references.title: Community detection and stochastic block models: recent developments
references.venue: The Journal of Machine Learning Research,
references.authors: Edoardo Maria Airoldi David M Blei Stephen E Fienberg Eric P Xing
references.title: Mixed membership stochastic blockmodels
references.venue: Journal of machine learning research,
references.authors: Emmanuel Abbe Afonso S Bandeira Georgina Hall
references.title: Exact recovery in the stochastic block model
references.venue: IEEE Transactions on Information Theory,
references.authors: Lada A. Adamic Natalie S. Glance
references.title: The political blogosphere and the 2004 u.s. election: divided they blog
references.venue: In LinkKDD,
references.authors: Emmanuel Abbe Colin Sandon
references.title: Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery
references.venue: In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science,
references.authors: Aaron Clauset Mark EJ Newman Cristopher Moore
references.title: Finding community structure in very large networks
references.venue: Physical review E,
references.authors: Mário Cordeiro Rui Portocarrero Sarmento Joao Gama
references.title: Dynamic community detection in evolving networks using locality modularity optimization
references.venue: Social Network Analysis and Mining,
references.authors: Aurelien Decelle Florent Krzakala Cristopher Moore Lenka Zdeborová
references.title: Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
references.venue: Physical Review E,
references.authors: Zhou Fan Andrea Montanari
references.title: How well do local algorithms solve semidefinite programs
references.venue: In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing,
references.authors: Santo Fortunato
references.title: Community detection in graphs
references.venue: Physics reports,
references.authors: Roger Guimera Luis A Nunes Amaral
references.title: Functional cartography of complex metabolic
references.venue: networks. nature,
references.authors: Andrew B. Goldberg Ming Li Xiaojin Zhu
references.title: Online manifold regularization: A new learning setting and empirical study. In Machine Learning and Knowledge Discovery in Databases, European Conference, ECML/PKDD, volume
references.authors: Michelle Girvan Mark EJ Newman
references.title: Community structure in social and biological networks
references.venue: Proceedings of the national academy of sciences,
references.authors: David Gamarnik Madhu Sudan
references.title: Limits of local algorithms over sparse random graphs
references.venue: In Proceedings of the 5th conference on Innovations in theoretical computer science,
references.authors: Shayan Oveis Gharan Luca Trevisan
references.title: Approximating the expansion profile and almost optimal local graph clustering
references.venue: In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science,
references.authors: Hamed Hatami László Lovász Balázs Szegedy
references.title: Limits of locally–globally convergent graph sequences
references.venue: Geometric and Functional Analysis,
references.authors: Samuel B Hopkins David Steurer
references.title: Efficient bayesian estimation from few samples: community detection and related problems
references.venue: IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS),
references.authors: Daxin Jiang Chun Tang Aidong Zhang
references.title: Cluster analysis for gene expression data: a survey
references.venue: IEEE Transactions on knowledge and data engineering,
references.authors: Muhammad Aqib Javed Muhammad Shahzad Younis Siddique Latif Junaid Qadir Adeel Baig
references.title: Community detection in networks: A multidisciplinary review
references.venue: Journal of Network and Computer Applications,
references.authors: Varun Kanade Elchanan Mossel Tselil Schramm
references.title: Global and local information in clustering labeled block models
references.venue: IEEE Transactions on Information Theory,
references.authors: Brian Karrer Mark EJ Newman
references.title: Stochastic blockmodels and community structure in networks
references.venue: Physical review E,
references.authors: Georg Krempl Indre Žliobaite Dariusz Brzeziński Eyke Hüllermeier Mark Last Vincent Lemaire Tino Noack Ammar Shaker Sonja Sievi Myra Spiliopoulou Jerzy Stefanowski
references.title: Open challenges for data stream mining research
references.venue: SIGKDD Explor. Newsl.,
references.authors: Andrea Lancichinetti Santo Fortunato
references.title: Community detection algorithms: a comparative analysis
references.venue: Physical review E,
references.authors: Russell Lyons Yuval Peres
references.title: Probability on trees and networks, volume 42
references.authors: Laurent Massoulié
references.title: Community detection thresholds and the weak ramanujan property
references.venue: In Proceedings of the forty-sixth annual ACM symposium on Theory of computing,
references.authors: L-E Martinet MA Kramer W Viles LN Perkins E Spencer CJ Chu SS Cash ED Kolaczyk
references.title: Robust dynamic community detection with applications to human brain functional networks
references.venue: Nature communications,
references.authors: Elchanan Mossel Joe Neeman Allan Sly
references.title: Belief propagation, robust reconstruction and optimal recovery of block models
references.venue: In Conference on Learning Theory,
references.authors: Elchanan Mossel Joe Neeman Allan Sly
references.title: Reconstruction and estimation in the planted partition model
references.venue: Probability Theory and Related Fields,
references.authors: Elchanan Mossel Joe Neeman Allan Sly
references.title: A proof of the block model threshold
references.venue: conjecture. Combinatorica,
references.authors: Sara C Madeira Arlindo L Oliveira
references.title: Biclustering algorithms for biological data analysis: a survey
references.venue: IEEE/ACM transactions on computational biology and bioinformatics,
references.authors: Andrea Montanari
references.title: Finding one community in a sparse graph
references.venue: Journal of Statistical Physics,
references.authors: Elchanan Mossel Jiaming Xu
references.title: Local algorithms for block models with side information
references.venue: In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science,
references.authors: Symeon Papadopoulos Yiannis Kompatsiaris Athena Vakali Ploutarchos Spyridonos
references.title: Community detection in social media
references.venue: Data Mining and Knowledge Discovery,
references.authors: Ryan A. Rossi Nesreen K. Ahmed
references.title: The network data repository with interactive graph analytics and visualization
references.venue: In AAAI,
references.authors: Filippo Radicchi Claudio Castellano Federico Cecconi Vittorio Loreto Domenico Parisi
references.title: Defining and identifying communities in networks
references.venue: Proceedings of the national academy of sciences,
references.authors: Karl Rohe Sourav Chatterjee Bin Yu
references.title: Spectral clustering and the highdimensional stochastic blockmodel
references.venue: Annals of Statistics,
references.authors: Roman Vershynin
references.title: High-dimensional probability: An introduction with applications in data science, volume 47
references.authors: Ulrike Von Luxburg Mikhail Belkin Olivier Bousquet
references.title: Consistency of spectral clustering
references.venue: The Annals of Statistics,
references.authors: Tal Wagner Sudipto Guha Shiva Prasad Kasiviswanathan Nina Mishra
references.title: Semisupervised learning on data streams via temporal label propagation
references.venue: In Proceedings of the 35th International Conference on Machine Learning, ICML,
references.authors: Feifan Wang Baihai Zhang Senchun Chai Yuanqing Xia
references.title: An extreme learning machine-based community detection algorithm in complex
references.authors: Xiaojin Zhu Zoubin Ghahramani John D. Lafferty
references.title: Semi-supervised learning using gaussian fields and harmonic functions
references.venue: Machine Learning, Proceedings of the Twentieth International Conference ICML,
references.authors: Xiangxiang Zeng Wen Wang Cong Chen Gary G Yen
references.title: A consensus communitybased particle swarm optimization for dynamic community detection
references.venue: IEEE transactions on cybernetics,
sections.heading: 1 Introduction
sections.text: Given a single realization of a network G = (V,E), the community detection problem requires to find a partition of its vertices into a small number of clusters or ‘communities’ [GN02, MO04, JTZ04, For10, PKVS12, JYL+18].
  Numerous methods have been developed for community detection on static networks [GN02, CNM04, GA05, RCC+04, LF09, VLBB08, WZCX18]. However, the network structure evolves over 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 a node joins or 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 (NeurIPS 2021).
  As usual, establishing fundamental statistical limits requires introducing a statistical model for the networkG = (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) [HLL83, ABFX08, KN11, RCY+11, DKMZ11, Mas14, 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 (StSBM).
  The SBM can be defined as follows. Each vertex v is given a label τ(v) 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τ(u),τ(v). The analyst is given a realization of the graph and required to estimate the labels τ . We will assume in addition that the analyst has access to some noisy version of the vertex labels, denoted by τ̃ = (τ̃(v))v∈V . This is a mathematically convenient generalization: the special case in which no noisy observations τ̃ are available can be captured by letting τ̃ be independent of τ . Further, such a generalization is useful to model cases in which covariate information is available at the nodes [MX16].
  Informally, the streaming SBM (StSBM) is a version of SBM in which nodes are revealed one at a time in random order (see below for a 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, [ZGL03, 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 [Suo13] for a survey. A substantial literature studies the behavior of local algorithms for sparse graphs [GT12, HLS14, 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 is 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 information, 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 a 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 a streaming version of belief propagation (BP), a local streaming algorithm that we call STREAMBP, parameterized by a 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 offline polynomial-time algorithm [DKMZ11, Abb17, HS17]. Under this conjecture, there is no loss of performance in restricting to local streaming algorithms as long as (1) local side information is available; (2) the locality radius is sufficiently 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.)
sections.heading: 2 Streaming stochastic block model
sections.text: In this section we present a formal definition of the proposed model. The streaming stochastic block model is a probability distribution StSBM(n, k, p,W, α) over triples (τ, τ̃,G) where τ ∈ [k]n is a vector of labels (here [k] , {1, . . . , k}), τ̃ ∈ [k]n are noisy observations of the labels τ , and G = (G(0), G(1), . . . , G(n)) is a sequence of undirected graphs. Here G(t) = (V (t), E(t)) is a graph over |V (t)| = t vertices and, for each 0 ≤ t ≤ n− 1, V (t) ⊆ V (t+ 1) and E(t) ⊆ E(t+ 1). We will assume, without loss of generality, that V (n) = [n], and interpret τ(v) as the label associated to vertex v ∈ [n]. For each 0 ≤ t ≤ n − 1, G(t) is the subgraph induced in G(t + 1) by V (t); equivalently, all edges in E(t+ 1) \ E(t) are incident to the unique vertex in V (t+ 1) \ V (t).
  The distribution StSBM(n, k, p,W, α) is parameterized by a scalar α ∈ [0, k−1k ], a probability vector p = (p1, . . . , pk) ∈ ∆k , {x ∈ [0, 1]k, 〈x, 1〉 = 1}, and a symmetric matrix W ∈ [0, 1]k×k. We draw the coordinates of τ independently with distribution p, and set τ̃(v) = τ(v) with probability 1− α, and τ̃(v) ∼ Unif([k] \ {τ(v)}) otherwise, independently across vertices:
  P ( τ(v) = s ) = ps, P (τ̃(v) = s1 | τ(v) = s0) = { 1− α if s1 = s0, α/(k − 1) if s1 6= s0.
  We then construct G(n) by generating conditionally independent edges, given (τ, τ̃), with P ( (u, v) ∈ E(n) | τ, τ̃ ) = Wτ(u),τ(v). (1)
  Note that the labels τ̃ provide noisy ‘side information’ about the true labels τ . 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 (v(1), v(2), . . . , v(n)) and setting V (t) = {v(1), . . . , v(t)} and G(t) to the graph induced by V (t). If v = v(t), then we define t as the arrival order of vertex v. Note that, for each t, G(t) is distributed according to a standard SBM with t vertices: G(t) ∼ SBM(t, k, p,W ). An equivalent description is that (conditional on τ, τ̃ ) StSBM(n, k, p,W, α) defines a Markov chain over graphs. The new graph G(t + 1) is generated from G(t) by drawing the vertex v(t + 1) uniformly at random from [n] \ V (t), and then the edges (u, v(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, we will consider n → ∞ and W = W (n) → 0 with W (n) = W0/n for a matrix W0 ∈ Rk×k≥0 independent of n.
  A case of special interest is the streaming symmetric SBM, StSSBM(n, k, a, b, α), which corresponds to taking p = (1/k, . . . , 1/k) and W0 having diagonal elements a and non-diagonal elements b. Finally, the case α = (k − 1)/k corresponds to pure noise τ̃ : in this case we can drop τ̃ from the observations and we will drop α from the distribution parameters.
  hhnni矗 鸞
  ag.ci
  Nine
  nazis
  hdnet
  矗tanto 䎖矗趱
  tanto
  engin
  tanto
sections.heading: 2.1 Definitions and notations
sections.text: For two nodes v, v′ ∈ V (t), we denote by dt(v, v′) their graph dista ce in G(t), i.e., the length of the shortest path in G(t) connecting v and v′, with dt(v, v′) = ∞ if no such path exists. We also write d(v, v′) = dn(v, v′) for the graph distance in G(n). For v ∈ V (n) and R ∈ N+, let BtR(v) = (V t R(v), E t R(v)) denote the ball of radius R in G(t) centered at v, i.e., the subgraph induced in G(t) by nodes V tR(v) , {v′ ∈ V (t) : dt(v, v′) ≤ R} and edges (v1, v2) ∈ E(t) with
  3
  v1, v2 ∈ V tR(v). Furthermore, let DtR(v) , {v′ ∈ V (t) : d(v, v′) = R}. Throughout the paper, unless otherwise stated, we assume (v1, v2) is an undirected edge.
  We consider an algorithm A that takes as input the graph G(n) and side information τ̃ , and for each v ∈ V (n) outputs A(v;G(n), τ̃) ∈ [k] as an estimate for τ(v). Note that we always assume the arrival orders of vertices are observed (i.e., by observing v ∈ [n] we also observe the unique t ∈ [n] such that v = v(t)), thus G(n) contains the arrival order of its vertices. We define the estimation accuracy of algorithm A as
  Qn(A) , E max π∈Sk 1 n ∑ v∈V (n) 1 (A(v;G(n), τ̃) = π ◦ τ(v)) . (2) Here Sk is the group of permutations over [k] and the expectation is with respect to G(n), τ, τ̃ , and the randomness of the algorithm (if A is randomized).
sections.heading: 3 Local streaming algorithms
sections.text: In this section we introduce local streaming algorithms, which are a 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 a new vertex v(t) joins, information within the R-neighborhood BtR(v(t)) is pulled. An estimate for τ(v) is constructed based on information available to v. In order to accommodate randomized algorithms we assume that random variables (ξv)v∈V (n)
  iid∼Unif([0, 1]), 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 τ̂(v) ∈ [k] for all v ∈ V (t). As a new vertex v(t) joins, its estimated label is determined according to
  τ̂(v(t)) = argmaxs∈[k] πt(s) πt(s) = δ 1(s = τ̃(v(t))) + ∑
  (v(t),u)∈E(t)
  1(s = τ̂(u)) . (3)
  In words, the estimated label at v(t) is the winner of a voting procedure, where the neighbors of v(t) contribute one vote each, while the side information at v(t) contributes δ votes.
  For v ∈ V (n) and t ∈ [n], we denote the subgraph accessible to v at time t by Gtv = (Vtv, Etv), with initialization G0v = ({v}, ∅). At time t, we conduct the following updates:
  Vtv ,  ⋃ v′∈V tR(v(t)) Vt−1v′ for v ∈ V tR(v(t)),
  Vt−1v for v /∈ V tR(v(t)).
  We let Gtv be the subgraph induced in G(t) by Vtv, and denote by Ḡtv = (V̄tv, Ētv) the corresponding labeled graph with vertex labels τ̃ and randomness ξ. Namely V̄tv , {(v′, τ̃(v′), ξv′) : v′ ∈ Vtv}, Ētv , Etv. At time t, all nodes in the R neighborhood of v(t) share the same updated subgraph Gtv(t) while the rest of the subgraphs stay unchanged. Let us emphasize that the ‘neighborhoods’ Gtv are not symmetric, in the sense that we can have v1 ∈ Gtv2 but v2 6∈ G t v1 . Definition 1 (R-local streaming algorithm). An algorithm A is an R-local streaming algorithm if, at each time t and for each vertex v ∈ V (t), it outputs an estimate of τ(v) denoted by At(v;G(t), τ̃) ∈ [k], which is a function uniquely of Ḡtv .
  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 BtR(v), we define the corresponding labeled graph as B̄tR(v) , (V̄ t R(v), E t R(v)), with V̄ t R(v) , {(v′, τ̃(v′), ξv′) : v′ ∈ V tR(v(t))}. Definition 2 (R-local algorithm). An algorithm A is an R-local algorithm if, at each time t and for each vertex v ∈ V (t), it outputs an estimate of τ(v) denoted by At(v;G(t), τ̃) ∈ [k], which is a function uniquely of B̄tR(v).
  For simplicity, define the final output of an algorithm A by A(v;G(n), τ̃) , An(v;G(n), τ̃). The next theorem states that, under StSSBM, any local streaming algorithm with fixed radius behaves asymptotically as a 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, α), and v0 ∼ Unif([n]) be a vertex chosen independently of G. Then, for any > 0, there exist n , r ∈ N+, such that for every n ≥ n with probability at least 1− , the following properties hold: (1) Gnv0 is a subgraph of B n r (v0); and (2) v0 does not belong to Gnv for any v ∈ V (n)\V nr (v0).
  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. Corollary 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, limn→∞Qn(A) = 1/k. Remark 1. Corollary 1 does not hold if side information is available. As we will see below, an arbitrarily small amount of side information (any α < (k − 1)/k) can be boosted to ideal accuracy using R-local streaming algorithms with sufficiently large R. On the other hand, for a fixed small R, a small amount of side information has only limited impact on accuracy. Our numerical simulations illustrate this for voting algorithms, which are R-local for R = 1: they do not provide substantial boost over the use of only side information (i.e., the estimated label τ̂(v) = τ̃(v) at all vertices). Remark 2. In practice we can imagine keeping a 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 a 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, a, b) either. Due to space constraints we do not present this result here. Interested readers are referred to Section G in the appendix.
sections.heading: 4 Streaming belief propagation
sections.text: 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, α), we proved that local streaming algorithms cannot provide any non-trivial reconstruction of the true labels if no side information is provided, i.e., if α = (k − 1)/k. We also comment that, for a fixed (small) R, accuracy achieved by any algorithm is continuous in α, and hence a small amount of side information will have a small effect.
  In contrast, for any non-vanishing side information α < (k − 1)/k, we conjecture that informationtheoretically optimal reconstruction is possible using a local streaming algorithm, under two conditions: (i) the locality radius R is large enough; and (ii) the following Kesten-Stigum (KS) condition is met:
  λ , (a− b)2
  a+ (k − 1)b > 1 . (4)
  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 information-theoretically optimal reconstruction above the KS threshold [DKMZ11, MNS14]. We will describe STREAMBP in the setting of the symmetric model StSSBM(n, k, a, b, α), but its generalization to the asymmetric case is immediate.
  The algorithm has a state which is given by a vector of messages indexed by directed edges in G(t), mt = {mtu→v,mtv→u : (u, 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 a probability distribution over [k]:
  mu→v = (mu→v(1),mu→v(2), . . . ,mu→v(k)) ∈ ∆k .
  The BP update is a map BP : (∆k)∗ × [k] → ∆k, where (∆k)∗ denotes the finite sequences of elements of ∆k:
  BP({mi}i≤`; τ̃)(s) := BP0(τ̃)(s)
  Z
  ∏̀ i=1 ( b+ (a− b)mi(s) ) . (5)
  Here BP0(τ̃)(s) , ( α + (k − 1 − kα)1τ̃=s ) /(k − 1) and the constant Z = Z({mi : i ≤ `}; τ̃)
  is defined implicitly by the normalization condition ∑ s∈[k] BP({mi : i ≤ `}; τ̃)(s) = 1. When a message v → u is updated, we compute its new value by applying the function (5) to the incoming messages into vertex v, with the exception of u→ v (non-backtracking property):
  mv→u ← BP({mw→v : w ∈ ∂v \ {u}}; τ̃(v)) . (6)
  Here ∂v denotes the set of neighbors of vertex v in the current graph. When a new vertex v(t) joins at time t, we use the above rule to: (1) update all the messages incoming into v(t), i.e., w → v(t), for w a neighbor of v(t) in G(t), and (2) update all messages at distance 1 ≤ ` ≤ R from v(t) in G(t), along paths outgoing from v(t), in order of increasing distance `. The pseudocode 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 StSSBM(n, 2, a, b, α). We believe that the extension of this analysis to other cases is straightforward, but we leave it out of this presentation.
  Algorithm 1 Streaming R-local belief propagation
  1: for t = 1, 2, . . . , n do 2: // Update the incoming messages: 3: for w ∈ Dt1(v(t)) do 4: mw→v(t) ← BP({mu→w : u ∈ ∂w \ {v(t)}}; τ̃(w)) 5: end for 6: // Update the outgoing messages: 7: for r = 1, 2, . . . , R do 8: for v ∈ Dtr(v(t)) do 9: Let v′ ∈ Dt1(v) on a shortest path
  connecting v and v(t). 10: mv′→v ← BP({mu→v′ : u ∈
  ∂v′ \ {v}}; τ̃(v′)) 11: end for 12: end for 13: end for 14: for u ∈ V do 15: mu ← BP({mv→u}v∈∂u; τ̃(u)) 16: Output τ̂(u) := arg maxs∈[k]mu(s) as an estimate for τ(u). 17: end for
  Our main result is that STREAMBP achieves asymptotically at least the same accuracy as offline BP, as originally proposed in [DKMZ11] and analyzed, e.g., in [MX16]. Offline BP performs the updates via Equation (6) in parallel on all the edges of G(n) for R − 1 iterations, and then computes vertex estimates using mu ← BP({mv→u}v∈∂u; τ̃(u)), τ̂(u) := arg maxs∈[k]mu(s). Note that, for each R, this defines an R-local algorithm, and hence we will refer to R as its radius. Theorem 2. For v ∈ V (n), let AR(v;G(n), τ̃) ∈ [k] be the estimate of τ(v) given by Algorithm 1 (STREAMBP), and AoffR (v;G(n), τ̃) ∈ [k] be the estimate given by offline BP with radius R (equivalently, BP with parallel updates, stopped after R iterations). Under the model StSSBM(n, 2, a, b, α), STREAMBP performs at least as well as offline BP:
  lim inf n→∞
  ( Qn(AR)−Qn(AoffR ) ) ≥ 0.
  It is conjectured that, in the presence of side information, i.e., for α < (k − 1)/k, offline BP is optimal among all polynomial-time algorithms [DKMZ11] (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 information-theoretically optimal accuracy. This 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-theoretically optimal. 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, α): (1) |a− b| < 2 and α ∈ (0, 1/2); (2) (a− b)2 > C(a+ b) and α ∈ (0, 1/2); or (3) α ∈ (0, 1/C). Then Algorithm 1 achieves optimal estimation accuracy:
  lim sup R→∞ lim sup n→∞
  ( Qn(AR)− sup
  A Qn(A)
  ) = 0.
  (Here the supremum is taken over all algorithms, not necessarily local or online.)
sections.heading: 5 Empirical evaluation
sections.text: 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. • STREAMBP∗: proposed algorithm in this work, which is a ‘bounded-distance’ version of
  STREAMBP. It is described in more detail in Section 5.1, and its pseudocode is given in Algorithm 2. • VOTE1X, VOTE2X, VOTE3X: simple plurality voting algorithms that give a weight δ to the
  side information, as defined in Equation (3) (the numbering corresponds to δ ∈ {1, 2, 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 a 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 are based both on synthetic datasets (Section 5.2) and on real-world datasets (Section 5.3). Because the model considered in this paper assumes undirected graphs, in a preprocessing step we convert the input graphs of the real-world datasets into undirected graphs by simply ignoring edge directions. Table 1 shows statistics of the datasets used (after making the graphs undirected); the values used for a and b for the real-world datasets are discussed in Section 5.3.
  As the measure of accuracy, we use the empirical fraction of labels correctly recovered by each algorithm, that is
  Acc = Ê max π∈Sk 1 n ∑ v∈V (n) 1 (A(v;G(n), τ̃) = π ◦ τ(v)) . In synthetic data we observe that, as soon as α < (k−1)/k, the maximization over π is not necessary (as expected from theory), and hence we drop it.
sections.heading: 5.1 Bounded-distance streaming BP
sections.text: In our experimental results presented below, we observed that the simple implementation in Algorithm 1 exhibits undesirable behaviors for certain graphs. We believe this is caused by two factors. First, unlike ORACLEBP, we do not have an 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 in 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 mu→v(s) ∈ [ε, 1− ε] for some fixed small ε > 0 (we essentially constrain the log-likelihood ratios to be bounded).
  The second modification defines a variant, presented in Algorithm 2, which we call STREAMBP∗. Here the estimate at node v is guaranteed to depend only on the graph structure and side information within BnR(v), and not on the information outside this ball. This constraint can be implemented in a message-passing fashion, by keeping, on each edge, R+ 1 distinct messages m0u→v, . . . ,m R u→v, corresponding to different locality radii.
  5.2 Synthetic datasets
  Algorithm 2 STREAMBP∗: Bounded-distance streaming BP
  1: for t = 1, 2, . . . , n do 2: for v ∈ Dt1(v(t)) do 3: m0v→v(t) ← 1/k 4: for i = 1, 2, . . . , R do 5: miv→v(t) ← BP({mi−1v′→v}v′∈∂v\{v(t)}; τ̃(v)) 6: end for 7: end for 8: for v ∈ Dt1(v(t)) do 9: m0v(t)→v ← 1/k
  10: for i = 1, 2, . . . , R do 11: miv(t)→v ← BP({mi−1v′→v(t)}v′∈∂v(t)\{v}; τ̃(v(t))) 12: end for 13: end for 14: for r = 2, 3, . . . , R do 15: for v ∈ Dtr(v(t)) do 16: Let v′ ∈ Dt1(v) on a shortest path connecting v and v(t). 17: for i = 1, 2, . . . , R do 18: miv′→v ← BP({mi−1u→v′}u∈∂v′\{v}; τ̃(v′)) 19: end for 20: end for 21: end for 22: end for 23: // Compute the estimates: 24: for u ∈ V do 25: mu ← BP({mRv→u}v∈∂u; τ̃(u)) 26: Output τ̂(u) := arg maxsmu(s) 27: end for
  Figure 3 illustrates the effect of the radius on the performance of the algorithms.1 We use various settings for k, a, b, α. We observe that voting algorithms do not perform significantly better than the baseline 1−α (dashed line). This is due both to the very small radius R = 1 of these algorithms, 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 optimal accuracy (i.e. the accuracy of ORACLEBP for large R) already for R ≈ 5. In Figure 4, we study the effect of the SNR parameter λ, defined in Equation (4), on the performance of the BP algorithms. The accuracy of the algorithms improves as λ increases. It is close to the baseline 1 − α when the SNR is close to the KS threshold at λ = 1, and then it improves for large λ. This is a trace of the phase transition at the KS threshold which is blurred because of side information. For large values of R, the accuracy of our streaming algorithms STREAMBP and STREAMBP∗ nearly matches that of the optimal offline algorithm ORACLEBP.
  Further experiments on synthetic datasets are reported in Appendix A. We then present in Appendix B the result of experiments where no side information is provided to the algorithms. We observe that in the streaming setting, and for small radius (R), neither STREAMBP nor STREAMBP∗ achieves high accuracy (above 1/k) in the absence of side information, as suggested by our theoretical results.
  1Notice that the three voting algorithms do not depend on the radius, resulting in horizontal lines in the diagram.
sections.heading: 5.3 Real-world datasets
sections.text: We further investigate the performance of our algorithms on three real-world datasets: Cora [RA15], Citeseer [RA15], and Polblogs [AG05]. Cora and Citeseer are academic citation networks: vertices represent scientific publications partitioned into k = 7 and k = 6 classes respectively; directed edges represent citations of a publication by another. The Polblogs 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 k = 2 classes based on their political orientation (liberal or conservative).
  As mentioned in the beginning of Section 5, in a 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 b, obtained by matching the density of intra- and inter-community edges with those in the model StSSBM(n, k, ã, b̃, α). Namely, for a graph G = (V,E), letting V1, . . . , Vk ⊆ V be the ground-truth communities, we set ã = |V | · ∑ i∈[k]
  ∑ (u,v)∈E 1{u, v ∈ Vi}∑ i∈[k] (|Vi| 2 ) , b̃ = |V | · ∑ {i,j}∈([k]2 ) ∑ (u,v)∈E 1{u ∈ Vi, v ∈ Vj}∑ {i,j}∈([k]2 ) |Vi||Vj | .
  For each dataset, we run the streaming algorithms STREAMBP and STREAMBP∗ using the parameters a = ã and b = b̃. Notice that these estimates cannot be implemented in practice because we do not know the communities Vj 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 on 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, we see that our streaming algorithm STREAMBP∗ is approximately as accurate as the offline 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 is likely due to the issues discussed in Section 5.1.
  Appendix C provides additional details on these experiments, as well as results for other values of α.
  Acknowledgments and Disclosure of Funding
  A.M. and Y.W. were partially supported by NSF grants CCF-2006489, IIS-1741162 and the ONR grant N00014-18-1-2729.
  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).
title: Streaming Belief Propagation for Community Detection