Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes an edge-independent graph generative model. Besides the model, the paper also proposes the training process of the model and some theoretical contributions. Unfortunately, the evaluation of the model is based on another problem, clustering. This makes the paper complicate to evaluate. While the main contributions could be important, its evaluation does not guarantee that is able to replicate real networks. Most importantly, given its current results, it must suffer from the degeneracy problem.
main_review: The paper has a strong motivation over the generative graph model problem (GGM). It covers its use, and it explains some of the problems, especially the difficulty to capture heterophily. The paper also explains a type of GGMs and most importantly, it develops the training algorithm and some interesting theoretical results, which seems correct. So far, the paper is making an important contribution. 

Unfortunately, there are some problems that must be addressed before publication.

First, the related work does not cover generative graph models (GGM). Instead, it focuses on node clustering, modeling heterophily, overlapping clustering. There are several works about GGMs that must be included in this paper. Especially, GGMs that are able to replicate the network structure and other characteristics, such as: Chung-lu, mKPGM, Bter, and others.

Second, it is difficult to figure out the main contribution inside the proposed generative graph model. Equation 1 is just one of the many ways to define the generative graph model. Then, the main contribution seems to be the training algorithm. However, this is based on a previous theory (Chanpuriya et al. (2020) and others). So it seems that the main contribution is the second stage, but it is not clear. 

Third, the paper should explain why this model is able to model heterophily. The training process minimizes the sum of binary cross-entropies of the link predictions over all pairs of nodes. So, why does this minimization can model heterophily? How are they linked?

Forth, the implementation of this model is quite complicated and details are avoided. In line 6 from algorithm 1, where it is just mentioned "Calculate ∂X,Y R via differentiation through Steps 3 to 5". Please give more details about this step.

Fifth, add a time complexity analysis of the model, including the training and sampling process. While most generative graph models are able to reduce the time of the sampling process, as it is, the time complexity of the proposition is O(N^2), which is prohibitive for medium-size networks. 

Sixth, given the low Frobenius error, it seems that the model suffers from the degenerative problem. This means that the model will generate almost the same network every time that is used to generate a network. 

However, the main problem is the evaluation of the model. The paper proposes a generative graph model (GGM) and the evaluation is based on node clustering. The main purpose of GGMs is to replicate the characteristics and structure of the network. This is not evaluated in this paper. To do this, you have to sample multiple networks from your model and figure out if they can actually replicate some global and local network characteristics from the original network, such as clustering coefficient, geodesic distance, and others. Most importantly, the paper does not evaluate if the model is able to replicate heterophily, one of their main contribution. 
summary_of_the_review: While all contributions are very interesting, the evaluation of the paper is focused on another completely different problem. So, it is impossible to evaluate if the graph generative model is able to replicate the global and local characteristics of real networks.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this work, the authors claim to propose the first edge-independent graph based generative model that can capture heterophily and via producing non-negative embeddings, it allows link predictions to be interpreted in terms of communities. The authors demonstrate the efficacy of their approach via empirical results in multi-label clustering and link prediction based tasks.
main_review: Strengths :-
1) The paper discusses an important problem of modeling heterophily and overlapping communities in graph based generative models. Subsequently proposes an interesting approach to solving the same. 
2) Via usage of non-negative matrix factorization (NMF), the approach in the paper can supposedly output link probabilities which are interpretable in terms of the detected communities.

Weaknesses :-
1) The approach proposed in the paper lacks motivation. Specifically, i) why did the authors choose to solve the problem using the three stage process, ii) what does each stage achieve, iii) can the approach be simplified from its complicated current form ? 
2) I found the notation and descriptions in the paper to be confusing and wrong in several cases. Specifically I found the example demonstrated in Figures 1 and 2 to be confusing and not clear at all. In addition to this, it has typos - In figure 2, (right) and (left) in the captions are interchanged. Furthermore equation 1) is incorrect, i.e., how did the authors evaluate V.T * W * V when W is a k-by-k matrix and V is a n-by-k matrix is beyond me. I found parts of Section 4 to be unclear and confusing. To be more clear, the authors should have added more details about their training procedure and how they exactly achieve the different steps. I did not quite understand which part of their framework/approach or training procedure helps them capture/model the heterophily. 
3) Building on weakness 1), I did not like the authors complicated three stage approximation procedure. Using NMF on top of that, builds in more error in the expressions. I am curious as to how much approximation error they incorporate during the entire process. Additionally I am not sure if one requires non-negativity of embeddings for interpretability.
4) There is no discussion of time/space complexity of their approach. I would like to see this detail in the paper.
5) The experiments are limited and use small datasets. I would have liked to see more analysis and discussion of the results. Also the authors should have compared their results against other more recent methodologies to demonstrate the clear superiority of their approach which is lacking in the paper. Via using small datasets, it adds more doubts to 4) above. Will their approach work on larger datasets ?

summary_of_the_review: The current version of the draft needs some work. The paper lacks motivation and novelty in terms of its approach. The paper also needs i) more empirical results both with larger datasets, ii)comparison with more recent state-of-the-art approaches and iii) some discussion/analysis. Many parts of the paper are unclear and missing important details.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This article deals with the task of community detection in the case of mixed membership networks, where a node can have multiple comunity assignments at once. It has been notice that in real-world networks, community overlaps tend to be much denser than the rest of the graph, which is a challenge to usual models (such as the stochastic block model).

The authors introduce a new mixed-membership graph model, where the expected adjacency matrix has the form

$$ \bar A = \sigma( V W V^\top), $$

with $\sigma$ the logistic function. In this model, the matrix $V$ represents the soft community assignments, and $W$ the inter-community similarities. The negative entries of $W$ allow this model to represent the heterophily of the network, wherein vertices are less likely to be connected when they belong to the same community.

They provide a learning algorithm to approximate $V$ and $W$ given the adjacency matrix $A$ of a graph, and show some existence results about such approximations.

In a second part, the authors provide several numerical experiments on real-world datasets, studying both the reconstruction of the matrix $\bar A$ and of the community membership matrix $V$.  They show that, in the chosen datasets, their algorithm outperforms or equals several others in the litterature.


main_review: The model is a combination of three distinct features: a soft assignment matrix $V$, the use of a non-linearity $\sigma$, and finally a link matrix $W$ with arbitrary weights allowing for the modelling of heterophily. Many combinations of those three features are present in the literature (with Millet et al. being the closest one), but to the best of my knowledge this is the first general model that includes all three.

The algorithm proposed is technically sound, although the justification for steps 1 and 2 is tenuous: is it useful apart from selecting the right values for $k_B$ and $k_C$ ? This is an especially interesting question since step 2 involves the eigendecomposition of an $n \times n$ matrix, which implies an important computational cost. It is also further exacerbated by the fact that the supplementary material only implements step 3 of the algorithm, with $k_B$ and $k_C$ set to appropriate "magic" values and $B, C$ randomly initialized.

I find the section on theoretical results to be kind of a mixed bag. On the one hand, Theorem 5.3 is an interesting result, as it shows that the proposed algorithm covers a larger selection of mixed-membership models, including thresholding the matrix $\bar A$ instead of drawing Bernoulli variables. On the other hand, Theorem 5.2 seems to me more of a negative result: if any adjacency matrix can be simulated in the form of equation (1), even if there is no community structure, this casts a doubt on the interpretability of the algorithm output.

Finally, the experimental results are quite convincing, although they lack computation time analysis to really allow comparing algorithms together. It should maybe be noted that the results of Figure 1 are simply a consequence of Theorem 5.2, and the real interest of those experiments is to show that this approximation still captures the group assignments.

Overall, this article glossed quite quickly on a major interpretability problem: the model in equation (1) is invariant with respect to a lot of transformations (rotations, scalings...) the the matrices $V$ and $W$; this is used in the proof of Claim 4.3 and Theorems 5.2 and 5.3. I am unsure how all those transformations affect the community memberships, and whether the simpler model with $W$ diagonal has the same clustering effectiveness than the full model. Of course, this does not affect link prediction, but the main selling point of this article is its connection to clustering (else is it similar to e.g. Peysakhovich & Bottou) and it falls short on this part.

I am of course willing to revise my judgement if there is a simple resolution to this problem that I've missed and that can be added easily to the paper.

summary_of_the_review: This paper introduces a general model for mixed-membership community detection, along with an approximation algorithm to recover its parameters. This algorithms shows promising results on real-world datasets; however, the model has some interpretability issues that undermine its main selling point, and reduce its novelty compraed to the existing literature.
review_title: null

Meta-review: The paper proposes an edge-independent graph generative model that can capture heterophily. The authors propose a 3-stage process to obtain the node representations. The idea of factorization in the form of BB^T-CC^T is an interesting approach to model heterophily.

The paper can be improved in terms of writing to better motivate the need for a 3-stage algorithm and how these individual steps are related to the existing techniques in the literature. The authors should elaborate on the implications of the theorems and the concerns raised by the reviewers in the body of the paper.

The algorithm faces scalability challenges, which are not studied well in the experiments. The reviewers also have raised concerns about degeneracy in network reconstruction experiments. Overall, the paper needs further improvements for publication.
Decision: Reject