Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
- 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.
- 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.
- 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.

Weaknesses:
- 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.
- 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.
- 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\].

Presentation issues:
- Unfinished last paragraph of intro beginning on line 39: "In this paper, we propose a novel random graph model that"
- The variable $x$ is first used in equation (5) in Section 2.2 but not defined until its later usage in Section 3.
- 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
- Line 184: estiamte -> estimate
- 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$.
- 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.
- Checklist was not completed: entries 4 and 5 still listed as TODO.
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?
2. 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).
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: S.  
* The idea of allowing for overlapping communities via thinning in the GGP model is interesting and new.   
* TGGP performs better as compared to CGGP

W.  
*  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
* 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.
* 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


questions: There are several parts in the paper that require an improved presentation. Some specific examples include:     

L1: What are "exchangeable arrays"? This concept is not used elsewhere in the paper

L39: An entire paragraph is missing. 

L42: $Y. Y_{ij}$; $.$ should probably be a $:$

The probability distributions Cat, Beta, etc. should be introduced briefly

L70-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$?

Figure 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

Figure 2: Little to no explanation for this figure is provided in the text

L112: $w_iw_j$ should not have bold font

L114: what are $a_k,b_k$?

L117: what is a non-matrix?

Figure 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

Figure 6: F-score, recall, ROC curve should be described better in the text: what exactly are you plotting here?

L182: what exactly is "your MCMC"?




limitations: The paper does not discuss potential limitation
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
The 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.
They 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. 
Their experiments also showed that this new model recovered the community membership in the network better than previous model.  
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.  
This 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.  
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? 

2. 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.  


limitations: Yes, they mentioned some potential generalizations of their model by including additional available information.
review_title: null

Meta-review: metareview: The authors present a framework for thinning edges from from random graph realizations from the generalized gamma process (GGP) to generate sparse graphs with mixed community memberships. The authors provide an efficient Monte Carlo methods that scale sub-quadratically with the number of nodes. There are concerns about scalability of the proposed method and its novelty over the GGP based construction of Caron and Fox. The reviewers also note that the paper needs proof reading and a clearer exposition. 
confidence: Less certain
Decision: Accept