Thinned random measures for sparse graphs with overlapping communities
Authors: Federica Zoe Ricci
Michele Guindani
Erik B. Sudderth
Venue: NeurIPS 2022 Accept (2022)
Keywords: bayesian nonparametrics
network analysis
stochastic blockmodels
generalized gamma process
completely random measures

Abstract: Network models for exchangeable arrays, including most stochastic block models, generate dense graphs with a limited ability to capture many characteristics of real-world social and biological networks. A class of models based on completely random measures like the generalized gamma process (GGP) have recently addressed some of these limitations. We propose a framework for thinning edges from realizations of GGP random graphs that models observed links via nodes' overall propensity to interact, as well as the similarity of node memberships within a large set of latent communities. Our formulation allows us to learn the number of communities from data, and enables efficient Monte Carlo methods that scale linearly with the number of observed edges, and thus (unlike dense block models) sub-quadratically with the number of entities or nodes. We compare to alternative models for both dense and sparse networks, and demonstrate effective recovery of latent community structure for real-world networks with thousands of nodes.

Thinned random measures for sparse graphs with overlapping communities
Federica Zoe Ricci Department of Statistics
Michele Guindani Department of Biostatistics
University of Califomia,, Irvine, CA, USA sericci@uci.cem
University of California, Los Angeles, CA, USA mguindani ucla. aalla.dde edu
Erik B. Sudderth
Departments of Computer Science and Statistics University of California, Irvine, CA, USA sudderth@uci.co
Abstract
Network models for exchangeable arrays, including most stochastic block models, generate dense graphs with a limited ability to capture many characteristics of real-world social and biological networks. A class of models based on completely random measures like the generalized gamma process (GGP) have recently ad- dressed some of these limitations. We propose a framework for thinning edges from realizations of GGP random graphs that models observed links via nodes' overall propensity to interact, as well as the similarity of node memberships within large of latent communities. Our formulation allows us learn the number of communities from data, and enables efficient Monte Carlo methods that scale linearly with the number of observed edges, and thus (unlike dense block models) sub-qu uub-quadratically with the number of entities or nodes. We compare to alternative models for both dense and sparse networks, and demonstrate effective recovery of latent community structure for real-world networks with thousands of nodes.
Introduction
Given observations of (often binary) relationships Yij between pairs of nodes entities (i,j), many relational models [I] seek to uncover an underlying set of communities. Classic stochastic blockmodels [2] generalize mixture models for clustering non-relational data by assigning each entity to one K communities (clusters). The infinite relational model (IRM) [3] instead uses Dirichlet process prior [4] partition entities into single communities. While the IRM allows the number of communities to be inferred from data, later work has shown that real-world social networks are better captured by models which allow nodes participate in multiple communities [5], including applications of the hierarchical Dirichlet process (HDP) [6] to relational data [7]. Node relationships may also be modeled by shared features [8, 9] learned via the Indian Buffet Process [10], by combination of node and interaction factors [11], or by proximity in latent space [12, 13].
There is extensive literature descriptive statistics of biological and social networks [14, 15] including degree distributions, path distances and "small world" phenomena [16], community struc- tures and modularity, and notions of centrality and causality. In particular, sparsity is a ubiquitous phenomenon real-world networks [14, 15]: as network size grows, the number of edges grows more slowly than the quadratic number of node pairs. However, the IRM and HDP relational models (and large literature of related models [1]) generate dense graphs where the number of edges scales quadratically with the number of nodes. In fact, classic representation theorem [17, 18] shows
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

that any generative model that regards graphs as exchangeable adjacency matrices, meaning arrays whose distribution invariant to permutations of node indices, generates dense graphs. Most existing probabilistic network models, which generate an adjacency matrix by sampling edges from inde- pendent Bernoulli distributions given latent node-specific parameters, have this limitation. Another important property of many real-world networks is assortative mixing [19, 20, 21], that is the presence of more popular or sociable nodes to which other nodes are more likely to connect. Models with degree-correction mechanisms [22, 23, 24] account for this phenomenon.
By representing graphs as a latent process (a completely random measure), Caron and Fox [25] showed that it is possible to formulate generative models that capture the sparsity of real-world networks as well as assortative mixing. Related models, including certain infinite limits of graphs called graphons. have been studied by several authors [26, 27]. However, these models mostly produce homogeneous graphs with sparsity and heavy-tailed degree distributions, but lacking the community structure of real networks. Two notable exceptions are work by Herlau et al. [28] and Todeschini et al. [29] that augment random- measure models [25] with latent community structure. Alternative approaches to sparse networks regard edges, rather than nodes, as the core of the generative process [30, 31, 32]. Another approach to simultaneously capture local density and global sparsity models graphs as a collection of cliques [33].
In this paper, we propose a novel random graph model that efficiently thins edges from sparse homogeneous graphs to reveal community structure while maintaining sparsity. Unlike [28], we allow entities to have membership in multiple communities. Unlike [29], we allow completely flexible specification of the hierarchical Bayesian prior on latent community memberships; importantly, this enables the network- specific learning of the appropriate number of latent communities. We further develop an efficient Monte Carlo inference algorithm that, unlike nearly all dense block models, scales linearly with the number of observed edges and thus sub-quadratically with the number of entities. Experiments show recovery of communities for networks with thousands of nodes.
2
Background: Stochastic Blockmodels for Dense and Sparse Networks
An undirected binary network with N nodes and E edges may be represented by symmetric NN x N adjacency matrix Y. If there is an edge (link) between nodes i a j then Y.j = 1, otherwise Yi, = 0.
2.1 Mixed Membership Stochastic Blockmodels
Stochastic blockmodels (SBMs) [2] assume that each node belongs to one of K latent communities, and that the probability of edge depends on how strongly their communities are connected. The community E (1.....K K} of node i follows a categorical distribution q; ind Cat(.3), where , (BI,..., 3x) so that 3% controls the relative size of community k. Edges are sampled independently as Yi ind Bernoulli (T..e). where Tık Teck is the probability of an edge between nodes in communities ind and These interaction probabilities are often assigned conjugate beta priors, Tik Beta(ta, Tb).
Mixed membership stochastic blockmodees (MMSBs) [5] extend SBMs to allow nodes to be members of multiple communities. Let म. ( T(k) denote K K-dimensional probability vector representing the strength of affiliation of node i to each of K communities. For every pair of nodes ind Cat(mT;), Gya ind Cat(TT))
(i,j), the communities governing their interaction are sampled as Gi.
Then, like standard SBMs, edges are sampled independently as Yi, ind Bernoull((neees)) Community memberships are typically assigned a hierarchical prior, such as
g ind Dirichlet((S)....... (3K))
Dirichlet (2.... K" 2
(1)
The concentration parameter Ç controls the polarization of n; and its variation around 8, with smaller values of Ç inducing more polarized community memberships that place significant probability on only a few communities, and larger values of Ç inducing community memberships that differ very little from 3. When fitting this model to data, we can treat K as an upper bound to the number of communities (that is, larger than the maximum number of communities that we expect to be necessary to model the network), fix 7 & K and let Ç be small. In this way, the hierarchical Dirichlet formulation allows network-speciffcc learning of the number of communities by favoring sparse

---

O
O O
0 0
100000
Figure I: Generation of an adjacency matrix from the GGP model of Caron and Fox [25] (top) and via thinning via our proposed model with K" = 3 communitics (bottom). Rows and columns correspond to nodes in all plots, ordered by decreasing sociability w; Left: Latent directed multigraphs underlying the observed graphs on the right. Darker cells correspond to higher Poisson rates: w; wy for the GGP, and w,wy Σ TuyT for the thinned GGP, Red zeros indicate thinned edges. Right: Binary adjacency matrix of the observed graph for the GGP (top) and thinned GGP (bottom) models. For the thinned GGP, edges colored according the community that generated them. Gray cells mark nodes whose edges the latent multigraph were all thinned, and are thus observed under the GGP but unobserved under the thinned GGP. GGP hyperparameters were set as 1/3),
o = 0.1, = 1, a 10, and community memberships were sampled given 3 = (1/3, 1/3,1
community frequency vectors B = (BI....; 3x) with elements Bn h E {1,..., "i....:K) K} [34]. The hierarchical Dirichlet process [6, is the limit of this prior as K approaches infinity [35].
2.2 Sparse Network Models via Completely Random Measures
For any fixed community frequencies 3 and interaction probabilities n, the SBM and MMSB may only generate dense graphs where the number edges scales quadratically with the number of nodes [18]. In contrast, many real-world networks appear to be sparse [15]. Heuristics
often used to fit (mixed membership) SBMs to large but sparse networks, such as fixing (rather than learning) The Re 0 for & * f; for example Kim et al. [7] fix
30 We seek to build models that capture mixed memberships and sparsity simultaneously without needing to rely on such heuristics.
Completely Random Measures. By representing the graph as a point process on the plane, Caron and Fox [25] showed that it is possible to generate sparse graphs by appropriately choosing the mean measure of the point process. According to their model, for + j.
Yi Wi, Wj ind
Bernoulli (1- exp (-2w,wy)).
where w; > 0 represents the sociability of node i: nodes with higher ws have higher probability to interact with other nodes, and hence greater expected degree. Differently from the (mixed membership) SBMs, where all parameters governing nodes' interactions are sampled independently. here nodes" sociabilities are generated altogether using the jumps completely random measure (CRM) [36]. Each node is also independently associated to real-valued location E, uniformly

---

distributed on the real line, and then set of potential nodes is defined by restricting to sociabilities with a sampled location in the interval [0, ai,
Wac { fwo 4 [0,
(3)
Here a > O controls the (random) number of nodes N₂. in the network by determining the size of the interval in which jumps are included. Depending on the distribution of the jumps, the model can capture both sparse and dense graphs. Intuitively, detailed in Sec. 5.1 of [25], for sparse networks the distribution of the jumps needs to place almost all of its mass near zero.
This model requires CRMs for which the sum Wa 2 [0.o] wi of the jumps in [0, a]] is finite. A simple undirected network is then generated via binary projection of an underlying directed multigraph, where the total number of edges naj from node to node j is independently distributed as
Paj W3y Wj ind Poisson(w;;1))
(4)
An edge is present in the undirected network if there is at least one directed edge in the latent directed multigraph, that is Y,, (nay + nij 2 1) for nodes * j. Because the sum of independent Poisson random variables is Poisson, Eq. (4) implies P(ny + ny 0) exp(-2u,wy Myy J. from which Eq. (2) follows. The number N of nodes in the observed network then equals the number No of nodes that have at least one edge in the underlying multigraph. This construction of the binary matrix from a multigraph [25] visualized in Fig. ((to)).
The sum cum-roopetyy of the Poisson distribution also implies that, given Wa. the total number of edges Da in the multigraph has a Poisson Pois distribution. Since n4 has high probability of being 0 for most node pairs (i, it is more efficient to first sample D. and then independently assign each edge pair of nodes based on their sociabilities. In more detail, Eq. (4) is equivalent
Da Ti = 1z i))((e2 = j), (5)
W; W
Do Wa ~ Poisson(W:)) P(zev = | =
where Ten E {1.2....} for v = 1,2 indicates the nodes sampled for edges e E (1...., D...
Caron and Fox [25] propose the generalized gamma process (GGP) [37, 38, 39] as a flexible but tractable CRM for Wa. with parameters
(0, oo), and a E (-o0, 0) for dense graphs or E (0, 1) for sparse graphs. Fig. 2 (black component) provides a visual summary of the generative process underlying the construction of a GGP random graph, using directed graphical model that highlights the conditional dependencies (and independencies) between its variables. Fig. 3a shows network sampled from the GGP model by means of a node-edge diagram.
Sparse Block Models. A limitation of the framework described above is that it does not model the community (block) structure of the network- well-recognized feature of complex networks. Herlau et al. [28] generalized the approach in [25] to accommodate networks with community structure. Specifically, they introduce a latent discrete variable &; E {1...., K} to indicate the assignment of node i to one of K communities, like in the SBMs. A bivariate CRM incorporates both the sociability weights and a set of parameters, denoted by Mecey capturing the interaction strength between two communities c; and ej in the underlying multigraph. For their formulation, the total ind number of edges nij from node i to node are independently distributed as nayl Mij/c,, Cj. Ws; wy Poisson(Neee, w; w and the likelihood from Eq. (2) of the observed nodes is modified as Yep I
c, Cjj, W;, Wj ind Bernoulli - -2 We refer to this approach as the stochastic block model generalized gamma process (SBM-GGP).
Sparse Mixed Membership. The SBM-GGP models sparse and dense networks with community structure, but does not capture overlapping community structures; it induces networks whose nodes partitioned into disjoint communities. In follow-up work, Todeschini et al. [29] extended the CRM-based framework discussed above by associating vector (wai..., w;k) of sociabilities to each node i, to represent different levels of affiliation of nodes to the K latent communities. A node may have high levels of affiliation to more than a community, leading to the formation of edges across multiple communities. The vectors of node sociabilities are distributed according to a compound CRM [40]; specifically, their implementation uses a compound generalized gamma process (CGGP). The likelihood function is modified accordingly, by independently sampling undirected edges as ind Ygg w/, wy Bernoulli1 exp(-2 k==1 W.xWFK... }). The latent community weights are modeled

---

22
YiS
K
NXN
Do
Figure 2:
Directed graphical model representing the GGP random graphs of Caron and Fox [25] (black), and the additional variables (blue) in our thinned GGP. For GGP hyperparametens that induce sparse graphs (a > 0) there is an infinite number of potential nodes, with sociabilities wy and community memberships Tİ
as Waak = Woo where Wio are sampled from a GGP as in Eq. (3), and thas are camma-distributed random variables the Gamma (ok by) whose shape ag and rate by may be inferred from data.
ind
As [29] point out, the CGGP model exploits an (unconstrained) non-negative matrix factorization to define the Bernoulli probability link. Our results in Sec. 5.1 suggest that this lack of constraints affects the ability the CGGP model to recover the true community structure of the network. Better regularized approaches non-negative matrix factorization, like the one we propose, may improve the identifiability of latent community structures and network parameters [41].
3 The Thinned GGP Network Model
We now add overlapping community memberships to the GGP network model [25] via vectors of probabilities sampled from a hierarchical Dirichlet distribution. Unlike the formulation of Todeschini et al. [29], our model enables learning the number of communities from data (see Secs. 2.1 and 4). By using probability vectors rather than unconstrained non- negative values to model community memberships, our model provides a regularized approach to inference in the GGP model, which in simulations (Sec. 5.1) provides substantial increase in community detection accuracy.
Let each node have both a sociability parameter ui from the GGP as in (3), and vector of probabilities = (M41...., Tak) T.k drawn from a hierarchical Dirichlet distribution as in (1). Moreover, let the number of potential edges between nodes i and in the latent multigraph depend only on their sociabilities, in (4). For each of the nij potential edges, node independently samples community from Ca,( and node samples a community from C, these community assignments match, the edge is retained; otherwise, it is thinned (i.e., discarded). See Figs. 1 and 3 for examples. More formally, let ñnj be the number multigraph edges between a pair of nodes i, that is retained (not thinned). Edges E (1...., Da) in the GGP multigraph stochastically thinned follows:
Gel Fel, (TI, .2....) Cat(Tra))
Ce2 Fe2s (2, ind Cat(Tzza);
(6)
Ds Σ
ñij =
1(x.1 i, j, c22),
Yi 1 (fi + + 2 1).
Here Zee (1,2,... for 1,2 indicate the nodes associated with edge e as in Eq. (5). An edge Yú is then present in the undirected graph if and only if at least one multigraph edge is not thinned. Equivalently, Eq. (7) implies that the observed undirected graph a binary projection the multigraph edges that are retained after the thinning process.
To determine the distribution of YıJ, note that the probability that nodes i and are assigned to the same community (marginalizing across communities) equals P(cer = cej) = Ei= Ti There- ind Poisson (w ΣK mwaTK).
fore, marginalizing over the latent multigraph, ñ4 Wi, W/ Tis TT The likelihood of the observed network thus equals
Yú
W; wy
Bernoulli
1 -
--eepp- exp
-2w;w;
Σ Tk
Unlike the MMSB and GGP models, our thinned generalized gammu process (TGGP) model favors edges between nodes that have both large sociabilities and similar community memberships. The TGGP model is summarized graphically in Fig. 2 and illustrated in Figs. and 3.
5

---

(a) Potential edges
(b) Unthinned edges
(c) Thinned edges
Figure 3: Visualization of networks simulated via (thinned) GGP with 15, 0.2, (a) Before thinning, potential edges are proposed according to nodes' sociabilities as in [25]. (b) After thinning. unthinned edges have colors (blue/red) corresponding to their assignment to バ = 2 communities. (c) The thinned edges (gray) are those for which the connected nodes were assigned to different communitics. In both (b) and (c), node colors represent their true community memberships, where lighter colors indicate more balanced memberships. Node sizes proportional to betweenness centrality, and layout determined by Gephi's Force Atlas 2 [42].
Monte Carlo Posterior Inference
In our TGGP model, the latent (unthinned) multigraph has a distribution (Eq. (5)) that depends only on the node sociability parameters w. The thinning process (Eqs. (6) and (7)) then depends only on the community membership vectors m, As can be deduced from the Markov properties of the directed graphical model in Fig. 2. given these latent multigraphs, the posterior distributions of (wi, W2, ...) and 1T1, ......) are conditionally independent. This design simplifies posterior inference, and in particular allows us to apply Theorem of [25] to derive the posterior of nodes' sociabilities, provided condition the (latent) multigraph. We thus implement a Gibbs sampling strategy for posterior inference where we sample both thinned and retained edges in the latent multigraph, as well as their community assignments, allow for efficient updates of other variables'
Some steps in the sampler are straightforwardly derived, considering that we can rely on the approach described in [25] to update node sociabilities and GGP hyperparameters (see the Appendix for detailed outline). However, the implementation of the sampler requires some additional careful development which we detail below to sample the latent multigraph, due to the unobserved thinning process. Multigraph sampling is made more computationally efficient via model properties that are unique to sparse, opposed to dense, stochastic block models. Letting (filled dot) ñ. denote the number of unthinned multigraph edges as in (7), and (empty dot) fug = T4j ñuy denote the number of thinned multigraph edges, we sample the latent multigraph follows.
Sampling of i:j: From Eq. (7), there exists an edge in the observed graph if and only if there is at least one unthinned edge between nodes and in the latent multigraph. Thus rather than considering each pair j. we only need to sample ñue when Yú, 1, an operation with cost linear in the number of observed (undirected) edges. Conversely, Yış implies ñu = nij = Since there must be at least one unthinned edge when Yij 1, the posterior follows zero-truncated Poisson distribution:
Yij 1, wx, Wj, n. Zero-TTrucc-Poisee 2wITU (nuy + (ijs))
TT
R=1
For each unthinned edge we sample single community assignment, since by definition these are the edges whose nodes have been assigned to the same communities. We can sample the community assignment of an unthinned edge between and j easily as a draw from Cat( Ta ".,,..., Tik (T))-
Sampling fizz By construction, since thinned edges are unobserved, all pairs of nodes (i,j) may have edges that are thinned. These edges are auxiliary variables necessary to obtain the full conditional posterior distribution of W.. Also, to update community memberships and global frequencies, is necessary to assign every thinned edge to a pair of discordant (non-matching) communities. Thanks
'Code be found the first author's website https: http:::///ederrczzee..ieeg wttp:r/ac......iu.....ooo.

---

1300
Maraoon
No
1.5-
0.2
1.0-
0.3
0.0
0.0
True value lower than 0.1
True value greater than 0.1
Figure 4: Validation of the MCMC sampler on graph with K = 15 communities, and N 386 observed nodes, simulated from the TGGP. Top: Traceplots of Na, Ot, 0, and r. Red, blue, and green indicate three distinct MCMC chains. Black horizontal lines mark the true values for the simulated graph. Bottom: True simulated values (red) and 95% credible intervals for the sociability parameters ue of randomly selected nodes.
to the properties of Poisson processes, we do not need to sample ñij for all node pairs; we can develop more efficient sampler that exploits the thinned model construction. We first sample proposed total number of thinned edges Dp Poisson (2 meaws) We then assign each of these independently to a pair of nodes according to their sociabilities as in Eq. (5), and subsequently to pair of commmunities given the memberships of the assigned nodes in Eq. (6). Finally, determine îug from the number of edges that were assigned to discordant communities.
Sampling unobserved nodes: As illustrated in Figs. and the total number of nodes Na with at least one edge in the unthinned multigraph is likely to be different from the total number of nodes with at least one edge after thinning and as a consequence from the total number of nodes N in the observed binary graph Y. There is thus some latent number N. N 2 0 of nodes whose edges with the observed nodes have all been thinned. In order to learn this number, our MCMC sampler includes an approximate update of N,, according to the mean ratio /a/N from graphs simulated from the GGP prior given the latest samples of the hyperparameters ax a, T. We found that this approximate method leads to convergence of the empirical MCMC-based estimate of N. across all simulated and real data that we considered (see Fig. 4). Sampling of the thinned edges from these unobserved nodes introduces some additional complications that efficiently resolve as detailed in the Appendix.
Sampling community memberships and global frequencies 3: From the conjugacy of Dirich- let priors to categorical likelihoods, node community memberships n; have closed-form Dirichlet
posteriors Ti M,, ind Dirichlet({331 + Ma........ [BK + M.K). where Ma equals the number of edges that node à participated in while being assigned to community k. Given community assignments of nodes in the latent multigraph, the global community frequencies 3 may be efficiently resampled using auxiliary-varrible methods developed for the hierarchical Dirichlet process [6] (see Appendix). By learning (8, node community memberships π, become sparse, placing significant probability mass only on a data-dependent subset of the full set of communities allocated in Eq. (1).
Computational complexity: For a K --oomunntyy TGGP model of a graph with E observed edges, resampling the latent multigraph requires O(EK) operations. (The thinned multigraph has fewer edges, and thus its resampling increases costs by a small constant.) Closed-form resampling of community memberships is faster, requiring only O(NK) operations for an Nonode graph. The CGGP model [29] uses Hamiltonian Monte Carlo proposals with similar cost, but empirically the CGGP sampler mixes slower and has inferior performance (see experiments). By exploiting sparse matrices and parallelization, both samplers may be scaled to networks with tens of thousands of nodes; very-large networks may require alternative approximate inference algorithms.
MCMC sampler validation: We evaluate the proposed posterior inference method on graph with 15 communities simulated from the TGGP model. The simulated graph had 1571 undirected, unthinned edges, N 386 observed nodes (i.e., with at least one unthinned edge), and N.- -N 192
7

---

190
350
713
232
150
193
750
V.
13/8
750
10:01
75
V4
1.5
230
250
257
730
732
300
2003
100
1083
(a) Adjacency Matrix
(b) True Blocks
(c) Estimated, TGGP
(d) Estimated, CGGP [29]
Figure 5: Results on two simulation experiments: a graph generated with the CGGP [29] (top) and a graph simulated with the proposed TGGP (bottom). Column (a) shows the true adjacency matrices, sorting nodes into blocks according the strongest community membership: (b) shows the relative edge density in the true blocks, sorting blocks by intensity. Columns (c) and (d) show the blocks estimated, respectively, with TGGP and the CGGP. In both simulations, we generate data setting a 250, 0 = 0.1, 7 = 1, and the CGGP we set = 1/K and bą = 1; for the TGGP we set 3 = (1/K, .... 1/K) and Ç 1. Inference uses the true number of communities for the CGGP, while our TGGP is given loose upper bound of K = 50, y 10, 0.2. The TGGP closely approximates the community structure, while the CGGP consistently underestimates the true number of communities.
15, For
unobserved nodes (i.e., with only thinned or self edges). Fig. 4 (top) shows traceplots from three separate MCMC chains, each of which was run for 20,000 iterations. The traceplot of the total number of nodes (observed + unobserved) N,, shows all values sampled since initialization to demonstrate that even very different initializations led the three MCMC chains quickly concentrate around the same (true) value of N.- The traceplots of the GGP hyperparameters or, a, and show samples after convergence (which took roughly 1000 iterations) and demonstrate that the posterior distribution effectively concentrated around the true values of these hyperparameters. Fig. 4 (bottom) shows summaries of the posterior distributions of nodes' sociabilities for 40 randomly selected nodes spanning from low to relatively large sociability, suggesting that the TGGP model also effectively recovers nodes' sociability parameters.
Experimental Results
5.1 Simulation
We discuss a simulation study where we investigated the performance of our proposed TGGP model, and the CGGP model of [29], based on simulated data generated from either model.
First, we present the results from sparse graph with 15 communities, simulated from our TGGP model by setting = 250, a 0.1, T = 1 for the distribution of node sociabilities and 7 10, <= 0.2 for the distribution of node community memberships. The adjacency matrix of the resulting undirected graph is shown in Figure 5(a, bottom). Figure 5(b, bottom) sorts the simulated nodes into blocks according their main membership and plots the density of edges each block, demonstrating that the simulated graph has a clear block structure. We then run our MCMC sampler for 50,000 iterations, discarding the first 40,000 samples as burn-in. For our model fitting, we let 50 be the upper bound to the number of communities and we set y = 10 and number of communities. From qualitative comparison of the (b) and (c) bottom panes in Figure we see that the community memberships recovered from our model are close to the underlying truth. In contrast, the CGGP model [29] struggles to recover the true community structure of the network (Fig. 5(d bottom)), despite being fitted with the number of communities K = 15 set to match the truth. We also simulated graph from the CGGP model of [29] with parameters as 1/K, by = chosen to induce community membership prior similar to our TGGP We fit both the CGGP model
0.5 to allow for learning the
8

---

we de- & Σn d(wi, 4b:) where the distance is the L1 total variation d(vi, th:) 2k-1 Wia Vaa Fig. 6 confirms that the TGGP more accurately recovers community member- and the TGGP model to the generated data. When fitting with the CGGP we still set the number of communities equal to the truth (K' 15). The results plotted in Fig. 5(d) indicate that the block structures learned by our (misspecified)) TGGP model are nevertheless closer to truth than those recovered by the CGGP. Additional results (shown in Appendix B) suggest that the parameters that represent the relative size of communities across the network are also more difficult to identify in the CGGP than in our TGGP formulation.
To quantify the superior community recovery of our TGGP model, recall that for each ob- served node the CGGP estimates a K K-dim. pos- itive real vector of community-specife sociabil- ities (WaI.... w,k), while our TGGP infers K-dim. probability vector of community mem- berships (Za1..... ). For quantitative com- parison, we standardize true and inferred so- ciability vectors by dividing each wis by the K
of and astmared memberanps
0.8-
model
TGGP
DBGP
0.6-
data
0.5-
TOGP
sum hi=1 Win- Also, since the TGGP model
CROP
was fitted with K set to an upper-bound of 50 0.4-
rather than the true number of communities, when analyzing TGGP results we pad the true vectors of community memberships (for TGGP- simulated data) and sociabilities (for CGGP- simulated data) with zeros. For estimated param- eters, community indices are then permuted to maximize similarity with true parameters. Let- ting t and di be, respectively, true and inferred community membershiips/sociaiiitc fine similarity
300
500
included nodes fhighest to lowest degree)
Figure 6: Plot of similarity between true and inferred community memberships for networks simulated (data) and fitted (model) with the TGGP and CGGP [29]. Our TGGP model uniformly achieves higher similarities.
ships for both networks, and for nodes of both high and low degree.
5.2 Real network data
We compare the performance of our TGGP framework for adding overlapping communities to the GGP model with the approaches detailed in Sec. 2.2 and 2.1: the CGGP (sparse with mixed memberships) [29], the SBM-GGP model (sparse with single memberships) [28], and the more classical SBM (dense with single membership) [2] and MMSB (dense with mixed memberships) [5]. We run 50,000 iterations of the five models' MCMC on four real-world networks; see Appendix for data sources and pre-processing. Fach model was fit to fully observed data to learn node-specific parameters (c.g.. sociabilities and community memberships) and community innerrtctiintrriiionnni probabilities, using the values from the last MCMC iteration. Two different measures of posterior predictive accuracy [43] were then used to assess the goodness of model fit.
For the first evaluation measure, we randomly selected 5% of the entries equal to 1 in the adjacency matrix and set them to O. We then compute the probability of being 1 of all entries that are equal to 0 in the modified adjacency matrix to assess how well each model can distinguish the entries that should in fact be 1. This edge-retrieval measure is motivated by common applications of network analysis to recommendation tasks (suggesting which edges that are not observed should be present). Fig. 7 (top) plots recall (proportion of ones recovered) on the horizontal axis, and F-score (geometric mean of recall and precision, which is the proportion of ones correctly predicted among all entries predicted as ones) on the vertical axis. This retrieval task is very challenging because, for sparse networks, the missing edges are a tiny proportion of all zero entries in the modified adjacency matrix.
For the second evaluation measure, we randomly obscure 5% of all entries in the adjacency matrix to assess how well each model can recover whether an entry is equal to 0 or to 1. Fig. (bottom) plots the receiver operating characteristic (ROC) curves, where false positive rate (number of zeros predicted as ones divided by the number of zeros) is on the horizontal axis, and true positive rate (proportion of ones correctly predicted as ones divided by the number of ones) is on the vertical axis. This second task has been used many prior papers but not as hard as the first one, because for a model to score well it suffices to learn small interaction probabilities, since almost all of the randomly

---

smagi
0.16
0.09
F-score
0.10
0.08
0.00
0.5
0.0
0.5
recal
smagt
1.00
0.75
1108
0.00
10 0.
0.5
10
0.
10
talse positive rate
COOP
SEM-GOP
9BM
Figure 7: F-score versus recall retrieval missing edges (top), and ROC curves (bottom) for prediction of missing adjacency matrix entries, for four real-world networks of varying sparsity. Our TGGP uniformly outperforms the CGGP [29]. SBM-GGP [28]. MMSB [5], and SBM [2].
selected entries are Fig. shows that our TGGP model does consistently better than all baseline methods for all networks considered, according to both evaluation measures.
Discussion
We have proposed framework for the analysis of binary network data that extends the GGP-based model of Caron and Fox [25] by allowing for overlapping community structures, depending both the overall sociability of the nodes and the similarity of their community memberships. Our generative model uses a novel latent multi-graph framework where nodes can connect within the same across different communities, but the edges formed across different communities hidden (thinned) in the projection giving rise to the observed network. In contrast with alternative extensions of the original GGP network model [28, 29], our thinned generalized gamma process (TGGP) enables mixed memberships and facilitates regularization of the community distributions for each node, resulting in improved inference and reconstruction of the latent community structures. Also, our model allows for learning the number of communities directly from the data, by encouraging recovery of set of non-empty communities smaller than specified upper bound.
Monte Carlo inference for the TGGP scales linearly with the number of observed edges, and thus sub- quadratically with the number of nodes in sparse graphs. This leads to strong edge prediction performance for social and biological networks of moderate size. However, further inference innovations may be needed scale to vary- networks with hundreds of thousands of nodes.
The proposed TGGP model amenable to further extensions. As the adopted mixed membership satchlet-multioomia specification, the vast literature
framework relies the well-studied hierarchical Dirichlet mixtures can be leveraged to capture more complex networks. It is possible to include additional node covariates metadata to guide the allocation of nodes to communities. Finally, distributional and asymptotic properties of our model can be investigated by exploiting results related to finite mixtures and mixtures of finite mixtures [see, e.g., 34, 44, 45, 35].
Acknowledgments and Disclosure of Funding
This research supported in part by NSF CAREER Award No. IIS1758028, and by the HPI Research Center in Machine Learning and Data Science at UC Irvine.
10

---

References
[1] Anna Goldenberg, Alice X Zheng, Stephen Fienberg. Edoardo M Airoldi, et al. A survey of statistical network models. Foundations and Trends in Machine Learning 2(2):129-23 2010.
[2] Yuchung J Wang and George Y Wong. Stochastic blockmodels for directed graphs. Journal of the American Statistical Association, 82(397):8-19, 1987.
[3] Charles Kemp, Joshua B Tenenbaum, Thomas L Griffiths, Takeshi Yamada, and Naonori Ueda. Learning systems of concepts with an infinite relational model. In AAAI, volume 3, page 2006.
[4] David Blackwell and James B MacQueen. Ferguson distributions via pólya um schemes. The Annals of Statistics, 1(2):353-355, 1973.
[5] Edo M. Airoldi, David Blei, Stephen Fienberg, and Eric Xing. Mixed membership stochastic blockmodels. Advances in Neural Information Processing Systems, 21, 2008
[6] Yee Teh, Michael Jordan, Matthew Beal, and David Blei. Hierarchical Dirichlet processes. Journal of the American Statistical Association, 101(466) December 2006.
[7] Dae Kim, Prem K Gopalan, David Blei, and Erik B. Sudderth. Efficient online inference for Bayesian nonparametric relational models. Advances in Neural Information Processing Systems, 26, 2013.
[8] Kurt Miller, Michael Jordan, and Thomas Griffiths. Nonparametric latent feature models for link prediction. Advances Neural Information Processing Systems, 22, 2009.
[9] Konstantina Palla, David A. Knowles, and Zoubin Ghahramani. An infinite latent attribute model for network data. Proc. 29th Int. Conf. Machine Learning, page 395-402, 2012.
[10] Zoubin Ghahramani and Thomas Griffiths. Infinite latent feature models and the Indian buffet process. Advances in Neural Information Processing Systems, 18, 2005.
[11] Peter Hoff. Multiplicative latent factor models for description and prediction of social networks. Computational and Mathematical Organization Theory, 1544)2261-272, 2009.
[12] Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association, 974460):1000-1095 2002.
[13] Pavel N Krivitsky, Mark S Handcock, Adrian E Raftery, and Peter D Hoff. Representing degree distributions, clustering, and homophily social networks with latent cluster random effects models. Social Networks, (1(:):204 213, 2009.
[14] Steven H Strogatz. Exploring complex networks. Nature, 010(4455:222228-227777 2001.
[15] Mark Newman. Networks. Oxford University Press, 2018.
[16] Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world' 'small-world'neeworkks 39346684):440-442, 1998.
networks. Nature,
[17] David Aldous. Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 11(4):581-598 1981.
[18] Peter Orbanz and Daniel M Roy. Bayesian models of graphs. arrays and other exchangeable random structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(2): 437-461, 2014.
[19] Mark EJ Newman. Assortative mixing in networks. Physical Review Letters, 20800700 2002.
[20] Hawoong Jeong, Zoltan Néda, and Albert-L.ász6ó Barabási. Measuring preferential attachment in evolving networks. EPL (Europhysics Letters), 61(4):567, 2003.
11

---

[21] Fragkiskos Papadopoulos, Maksim Kitsak, M Serrano, Marián Boguná, and Dmitri Krioukov. Popularity versus similarity in growing networks. Nature, 489(7417):537-554, 2012.
[22] Prem K Gopalan, Chong Wang, and David Blei. Modeling overlapping communities with node popularities. Advances in Neural Information Processing Systems, 26, 2013.
[23] Brian Ball, Brian Karrer, and Mark EJ Newman, Efficient and principled method for detecting communities in networks. Physical Review E, 84(3):031003, 2011.
[24] Mingyuan Zhou. Infinite edge partition models for overlapping community detection and link prediction. In Artificial Intelligence and Statistics, pages 1135-1 143. PMLR, 2015.
[25] François Caron and Emily B Fox. Sparse graphs using exchangeable random measures. Journal of the Royal Staristical Sociery: Series B (Statistical Methodoloyy), 79(5):125--1366 2017.
[26] Christian Borgs, Jennifer Chayes, Henry Cohn, and Nina Holden. Sparse exchangeable graphs and their limits via graphon processes. arXiv preprint
2016.
[27] Victor Veitch and Daniel M Roy. Sampling and estimation for (sparse) exchangeable graphs. The Annals of Statistics, 47(6):3274 3299, 2019.
[28] Tue Herlau, Mikkel N Schmidt, and Morten Mørup. Completely random measures for modelling Mlock-structured sparse networks. Advances in Neural Information Processing Systems, 29, 2016.
[29] Adrien Todeschini, Xenia Miscouridou, and François Caron. Exchangeable random measures for sparse and modular graphs with overlapping communities. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(2):487-55) 2020.
[30] Sinead A Williamson. Nonparametric network models for link prediction. The Journal of Machine Learning Research, 17(1):7102-7121, 2016.
[31] Diana Cai, Trevor Campbell, and Tamara Broderick. Edge-exchangeable graphs and sparsity. Advances in Neural Information Processing Systems, 29, 2016.
[32] Harry Crane and Walter Dempsey. Edge exchangeable models for interaction networks. Journal of the American Statistical Association, 1131623):1311-1126, 2018
[33] Sinead A Williamson and Mauricio Tec. Random clique covers for graphs with local density and global sparsity. In Uncertainty in Artificial Intelligence, pages 228-238. PMLR, 2020.
[34] Sylvia Crühhirth-Schhatte and Gertraud Malsiner-Wail From here to infinity: sparse finite versus dirichlet process mixtures model-based clustering. Advances in Data Analysis and Classification, 13(1):33-64, 2019.
[35] Hemant Ishwaran and Mahmoud Zarepour. Dirichlet prior sieves in finite normal mixtures. Statistica Sinica, pages 941 941-963, 2002.
[36] Olav Kallenberg. Probabilistic symmetries and invariance principles, volume 9, Springer, 2005.
[37] Philip Hougaard. Survival models for heterogeneous populations derived from stable distribu- tions. Biometrika, 73(2)3387-366, 1986.
[38] Lancelot F James. Poisson process partition calculus with applications to exchangeable models and bayesian nonparametrics. arXiv preprint math/0205093, 2002.
[39] Antonio Lijoi, Ramsés H Mena, and Igor Prünster. Controlling the reinforcement in bayesian non-parametrie mixture models. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 69(4):715-744 2007.
[40] Jim E Griffin and Fabrizio Leisen. Compound random measures and their use in bayesian non-parane parameramsssics. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 79(2):525-545, 2017.
12

---

[41] Patrik O Hoyer. Non-nege Von-negative matrix factorization with sparseness constraints. arXiv [cs.LG). 5:1457-1469, 2004.
[42] Mathieu Bastian, Sebastien Heymann, and Mathieu Jacomy. Gephi: an open source software for exploring and manipulating networks. In Proceedings of the International AAAI Conference on Web and Social Media, volume 3, pages 361-362, 2009.
[43] Andrew Gelman, Xiao-Li Meng, and Hal Stern. Posterior predictive assessment of model fitness via realized discrepancies. Statistica Sinica, pages 733-760, 1996.
[44] Jeffrey W Miller and Matthew T Harrison. Mixture models with a prior on the number of components. Journal of the American Statistical Association, 1130526) 2018.
[45] Subhashis Ghosal and Aad van der Vaart. Fundamentals of Nonparametric Bayesian Inference. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2017.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sec. 4 and 6.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [No] Some steps of our MCMC inference method are taken directly from cited prior work, including [25, 6].
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes] Code will be available on the first author's website datasets publicly available at the links provided in the Appendix.
htaps://feeericazoe github.io/) and
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Sections 4, 5, and the Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [Yes] For smaller datasets where this computationally feasible, in Figure 4.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] We used an internal cluster and do have detailed record computation times, but they were not substantial (at most a few days for each evaluated model).
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Appendix C.
(b) Did you mention the license of the assets? [Yes] See Appendix C.
(c) Did you include any new assets either the supplemental material or as URL? [Yes] Code will be released the first author's website: https://federicee io/
github.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] We used data that was already published and freely available. See cited sources for issues of consent.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No] We used data that was already published and freely available. See data sources for issues of de-identification.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "PD8WAaebJMv", "reviewer": "Reviewer_oHB1", "summary": "The authors propose the thinned generalized gamma process (TGGP) for generating sparse graphs with mixed-membership block structure. It builds upon the GGP-based model of Caron and Fox \\[12\\] and recent extensions to incorporate block structure. The TGGP thins potential edges from a GGP by removing edges where the community assignments for two nodes do not match. The authors claim that their TGGP is superior to the compound GGP approach of Todeschini et al. \\[17\\], and empirical results support this claim.", "questions": "1. I don't understand the first task in the real network data section: \"what entries of the adjacency matrix incorrectly classified as 0 are most likely to be edges\". What does this mean? Are you randomly setting some of the 1's in the adjacency matrix to 0 first and then trying to find these entries?\n2. The authors claim that the proposed inference procedure is computationally efficient. How does it compare to the CGGP? How large of networks can these models realistically scale up to? Is 10,000 nodes and 100,000 edges feasible?", "limitations": "Limitations are not really discussed, just possible extensions for further work. The authors should discuss the scalability by providing a rough scale of how large of networks they can fit in a reasonable amount of computation time (e.g. a few days).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Empirical results suggest that proposed TGGP provides a superior approach for modeling sparsity with mixed-membership block structure compared to the CGGP, which is the only other approach that can simultaneously model both properties.\n- The paper is mostly well written, and the explanations are quite clear. I enjoyed reading it! However, it seems to have been written in a rush, with lots of sloppy presentation issues (see weaknesses) that detract from overall presentation quality.\n- Proposed model and posterior inference algorithm appear to be technically sound and require some clever ways of sampling to avoid blowing up the computational complexity.\n\nWeaknesses:\n- Lots of presentation issues--this paper badly needs a copy edit and just a bit more time to correct the errors. I have provided a list below. These errors detract from what was a well written paper.\n- Experiments are on somewhat small data sets, with a maximum of about 2,000 nodes and about 33,000 edges. Also, no experiments were performed on real data with labeled communities, so estimated communities are only compared based on simulated data.\n- Novelty is only moderate, as the proposed model addresses the same setting as the CGGP from Todeschini et al. \\[17\\], and most of the results follow from the GPP-based construction of Caron and Fox \\[12\\].\n\nPresentation issues:\n- Unfinished last paragraph of intro beginning on line 39: \"In this paper, we propose a novel random graph model that\"\n- The variable $x$ is first used in equation (5) in Section 2.2 but not defined until its later usage in Section 3.\n- Lines 150-151: total number of proposed nodes $n_{ij}$ between any two edges $i$ and $j$ in the multigraph -> total number of proposed *edges* $n_{ij}$ between any two *nodes* $i$ and $j$ in the multigraph\n- Line 184: estiamte -> estimate\n- Figure 5 is too short--I cannot see how frequently the true simulated sociability values fall within the 95% credible intervals for most of the nodes, which have $w_i < 0.5$.\n- Figure 6 should have axis labels rather than needing to read the caption. Also, I find Figure 4 in the supplementary material, which shows the same results as Figure 6 in the main paper, but with all 5 models being compared, to be more convincing. I suggest for the authors to replace Figure 6 in the main paper with Figure 4 in the supplementary.\n- Checklist was not completed: entries 4 and 5 still listed as TODO.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GiFJFXAUTDs", "reviewer": "Reviewer_3Qbu", "summary": "The paper proposes TGGP, a new model for sparse random graphs with planted overlapping communities, based on the Generalized Gamma Process (GGP), and shows some experiments comparing the behaviour of TGGP compared to the previously proposed CGGP. Compared to CGGP, the proposed TGGP does not require to fix the number of communities a priori and has superior performance in terms of community detection and prediction of missing edges on synthetic and real-world graphs.", "questions": "There are several parts in the paper that require an improved presentation. Some specific examples include:     \n\nL1: What are \"exchangeable arrays\"? This concept is not used elsewhere in the paper\n\nL39: An entire paragraph is missing. \n\nL42: $Y. Y_{ij}$; $.$ should probably be a $:$\n\nThe probability distributions Cat, Beta, etc. should be introduced briefly\n\nL70-74: It is not clear how the $W_\\alpha$ are generated. How does $\\ell_i$ depend on $w_i$? Also, what exactly is $W_\\alpha$?\n\nFigure 1: Poisson rate should be $w_iw_j$ not $2w_iw_j$ according to Eq(4). Color bars are needed to understand the range of values of the colored cells\n\nFigure 2: Little to no explanation for this figure is provided in the text\n\nL112: $w_iw_j$ should not have bold font\n\nL114: what are $a_k,b_k$?\n\nL117: what is a non-matrix?\n\nFigure 4: If CGGP requires to specify the communities, why do we then get 9 communities instead of 15? Also, the qualitative comparison should be accompanied by some quantitative metric\n\nFigure 6: F-score, recall, ROC curve should be described better in the text: what exactly are you plotting here?\n\nL182: what exactly is \"your MCMC\"?\n\n\n\n", "limitations": "The paper does not discuss potential limitation ", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S.  \n* The idea of allowing for overlapping communities via thinning in the GGP model is interesting and new.   \n* TGGP performs better as compared to CGGP\n\nW.  \n*  The paper seems more like a draft, lots of work is needed to improve the presentation. For example, more explanation of backgrounds and related work, better structured contents, and more clear presentation of the generative algorithm based on MCMC\n* The performance in terms of community extraction / graph reconstruction is superior with respect to CGGP but it does not seem competitive with other available techniques for the specific tasks. So the authors should clarify what the main contribution exactly are, in particular to what extent they fit the machine learning community.\n* The work should come with an accompanying code that can be used to reproduce the experiments shown in the manuscript and to allow the use of the random graph generator by future researchers\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1y9Ja-7EyyN", "reviewer": "Reviewer_ju2a", "summary": "This paper proposed a new framework for analyzing the community structure in the network. They modeled the overlapping community structures in the network by extending the generalized gamma process(GGP) model. \nThe model first generated a latent multigraph where edges are assigned depending on the sociability of nodes and their community memberships. Then, the edges in the multigraph that connect two different communities are thinned (unobservable). The observed network is formulated as the projection of the latent multigraph excluding the thinned edges.\nThey also provided an efficient way to implement the posterior inference by utilizing the sparse property of the observed network. Specifically, they sampled the community concordant and community discordant edges separately based on the observed network. \nTheir experiments also showed that this new model recovered the community membership in the network better than previous model.  ", "questions": "1. I am a little confused about the conclusion that \"model formulation allows for learning the number of communities directly from the data, as it does not require fixing this number a priori. \" In the posterior inference, you still need the number of communities K in the computation. Do you mean that this number K can be chosen and changed, not fixed? \n\n2. In section 2.2, you mentioned that for fixed parameters, SBM and MMSB may only generate dense graphs. While many previous works on SBM and MMSB considered those parameters depending on the number of nodes like O(1/n) or O(log n/ n), which can also provide sparse networks. I am just curious about how this work compares to those works with non-constant parameters.  \n\n", "limitations": "Yes, they mentioned some potential generalizations of their model by including additional available information. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This new framework proposed in this paper is interesting. This new model can infer the overlapping community structures in the network, which has many applications and attracts a lot of attention in the research. This new model captures the sparsity and mixed community membership in real-world networks.  \nThis new model extended the generalized gamma process(GGP) model by introducing the mixed community membership for each node. The technique used in this extension is in some sense standard by utilizing the sparsity in the observed network.  ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept