Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies edge independent graph models that covers a large family of graph models. The main result is that it shows under certain conditions, the edge independent models are limited to generate graphs with high triangle and other subgraph densities, which are commonly observed in real world networks. Based on this finding, this paper propose a way to generate graph which balances matching the original graph and memorizing the graph statistics. 
main_review: This paper studies the limitation of edge independence graph models that it could not generate graphs with many triangles and other subgraph densities, which are common subgraphs in real networks. Motivated by this finding, they propose a method of generating graphs with matching graph statistics. Section 2 investigates the upper bound on subgraphs generated by the edge independent models, which is novel and valid. Meanwhile, I have several concerns about the proposed baseline edge independence models. I summarized the questions that need authors' address below. 

1. This paper mentioned some examples of edge independent models such as ER and SBM. I wonder how your results would look like for another family, latent space models (Hoff 2002), where $P_{i,j} = similarity(Z_i, Z_j)$ and $Z_i$, $Z_j$ are node embeddings of node $i$ and $j$. I believe this family of models would be more flexible than ER or SBM here as node individual embeddings provide more flexibility. Also this model is known to show transitivity. I understand the upper bound in Theorem 1-7 would stay the same format for all edge independent models, but I wonder would this setting would make the larger bound number larger and therefore increase the power of edge independent model? 

2. If certain edge independent models could not match the graph statistics, it is a signal that this model is not a good fit for the graph. Under this case, why we choose stay with the edge independent graph models, and try to modify the graph generating mechanism that matches graph statistics, rather than using the models that can handle triangles or subgraphs or more flexible edge independent models (as mentioned in question 1).

3. Related to question 2, I am wondering matching summary statistics would be a necessary or sufficient criterion when evaluating graph generation. It is possible that two graph have similar # of triangles, degrees, etc but show very different structure. 


limitations_and_societal_impact: The main limitation is about the proposed baseline edge independent models. This paper proposes a method that could match graph statistics well in the meantime not memorizing the original graph. The authors need to provide justifications on why graph statistics are enough for evaluating the generated graph, or could think of other ways of evaluating the goodness of the generated graph.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors in this work study the limitations of edge independent models which are an important class of graph generative models. Specifically the authors demonstrate that such models are inherently limited in their ability to generate graphs with high triangle and other subgraph properties which are typical in real-world graphs. The authors demonstrate the main results of their work via empirical experiments.
main_review: The authors do thorough theoretical analysis regarding the main points of the paper. The empirical results are also exhaustive given the number of datasets the authors decided to use. My major concern with this paper is its applicability and potential impact. Specifically the authors themselves claim that maybe non-independent models should be preferable to edge-independent models, which reduces the significance of this current work.

The work would be significantly strengthened if the authors could extend their analysis to non-independent models, a limitation of the work the authors themselves acknowledge. 

The paper would be strengthened in case the authors can prove that Algorithm 1 always converges so that it can be more practically applicable. In this work, the authors claim that the above algorithm converges for different test cases which is not a guarantee in general.

==== After reading authors' response and reviews by other reviewers ==== 

I would like to thank the authors for their response to all reviewers and would like to keep my score as it is. The authors are in agreement with the limitations of the paper I pointed out earlier. I wanted to wish the authors all the very best. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors analyze some properties of edge-independent generative graph models: given a fixed matrix of connection probabilities in [0,1], the edges are drawn independently. This is the basis for several methods to generate graphs that match certain statistics of a given input graph (*over the same set of nodes*). It has been observed that such models tend to produce less triangles (or generally k-cycles) than real graphs. In light of this, the authors show that the expected density of k-cycles can be bounded by the model *overlap*, which measures how much the model tends to memorize only one graph, as opposed to generating a large variety of graphs. The proofs are simple and are mostly given in the main paper. They also show that their bounds are tight, up to multiplicative constants, for Erdös-Rényi graphs, which are models with minimal overlap. Numerical experiments are performed to compare several edge-independent models, including a novel one introduced in the paper, and illustrate the (negative) theoretical findings.
main_review: I liked this paper. It is generally clearly written, pedagogical, and quite complete. To my knowledge, the theoretical contributions are novel (at least under this form), and, if quite simple, relatively well-put into context.

My main comment would be about a quite significant blind spot concerning edge-independent models as presented here, which may be usual in this (particular corner of the) literature, but I feel that it deserved to be clearly mentioned as limitations. Indeed, in many generative models, *the matrix P itself is random*, and edges are drawn independently conditionally on P. Think for instance of any latent-position models with random latent variables such as those studied in the graphon literature (in which motifs density is a key quantity, by the way), but also any GAN/VAE model with random input in the generator such as Variational Graph Encoder for instance, unlike what is claimed by the authors. Depending on the distribution of P, allowing random P may significantly decrease the overlap. In return, an additional difficulty is that graphs may then need to be considered up to isomorphism.
Nevertheless, I feel that, with minimal modifications (mostly taking double expectation everywhere, first on P then conditionally on P, and defining a notion of overlap that takes into account the variance of the distribution of Ps), all the theory presented could be adapted to random P, which would include many more models and significantly increase its impact. On the other hand, the resulting bounds might already exist in the graphon literature, which studied extensively motifs density.

In conclusion, I would have no real problem accepting the paper as is, but I feel that the theory could be significantly extended to include most "real" edge-independent models with latent variables. At minima, these limitations must be mentioned, including the fact that most GAN models have other sources of randomness that are not taken into account here.


Typo: the expectation is missing in the equation at the bottom of page 3 (middle)

**==== Edit after rebuttal ====**

I thank the authors for their response. It seems we agree on the current limitations of this work, and I am confident that they will describe them and future directions in the final version of the paper. I keep my score as is.
limitations_and_societal_impact: See above
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The main result is that certain structural properties of an edge-independent graph model, e.g. the expected number of triangles, are upper bounded by how strongly the graphs sampled from the model are expected to be overlapping. 

Experiments on two datasets empirically confirm that several edge-independent baseline models require a high amount of overlap in their sampled graphs in order to match the number of triangles in the original graph dataset.
main_review: **Originality**

The work provides a valuable insight to the field and addresses open questions on how well graph models can model certain structural properties. The theoretical results use the notion of overlap, which is intuitively defined and appears to be tied to the analysis of structural properties in an original manner, allowing for theoretical proofs that are easy to understand. 


**Quality**

All theorems appear correct (though I did not check Theorem 6 in detail) and are potentially useful starting points for later work.

My main concern with the paper is that the theoretical results are not explicitly validated in the experiments:
1) It would be nice to see the theoretical bounds on the number of triangles reflected in Figures 1 and 2. Considering that the algorithms have a controllable overlap, a fixed volume and that the bound on the number of triangles is independent of the model, including the bound would only result in one additional curve per subplot. It would provide more information on how important the bound actually is in practice.

2) All algorithms are edge-independent models. It would be interesting to at least run one baseline that is not edge-independent.

I further have a minor remark:

3) The quality could be improved in Section 3 by building further upon prior work on models where $P_{ij} = \sigma(l_i + l_j)$. Such parameters should arguably be better defined in graph learning literature, but they have been referred to as 'popularity' [1] or 'parameters modeling degree heterogeneity' [2] in the context of latent space models. The authors may be interested in the Maximum Entropy distribution subject to the constraint that the expected degree sequence (or row/column sums in the adjacency matrix) should equal the empirical degree sequence [3]. Finding this distribution is a convex optimization problem, and the solution is a model of the form $P_{ij} = \sigma(l_i + l_j)$ if its parameters were optimized with Maximum Likelihood Estimation.


**Clarity**

The paper is a joy to read and communicates the result in a surprisingly clear manner.

I do question if it is useful to divide by $V(P)$ in the definition of the overlap. If this division were not present, then the overlap definition would be simpler, and the bound in Theorem 1 would no longer contain the $V(P)$ factor.

**Significance**

The technical contributions appear highly valuable to the literature on graph generative models, where matching structural properties is key. The results may further have a positive impact on other graph-related topics such as link prediction or community detection. Very similar graph models are used there to make predictions, and this paper suggests that those models may also fail to make predictions that correspond with the actual structure of the graph. 


[1] Goldenberg, A., Zheng, A. X., Fienberg, S. E., & Airoldi, E. M. (2010). A survey of statistical network models.

[2] Ma, Z., Ma, Z., & Yuan, H. (2020). Universal Latent Space Model Fitting for Large Networks with Edge Covariates. J. Mach. Learn. Res., 21, 4-1.

[3] De Bie, T. (2011). Maximum entropy models and subjective interestingness: an application to tiles in binary databases. Data Mining and Knowledge Discovery, 23(3), 407-446.

**UPDATE**

I thank the authors for their responses. My score remains unchanged and I hope to see the paper accepted and inspire future work.
limitations_and_societal_impact: It is unclear how useful the theoretical bounds are in practice. An empirical study of the bound would have made it significantly easier to study this usefulness.
review_title: null

Meta-review: The reviewers are generally leaning to accept the paper. They unanimously appreciate the theoretical contribution of the paper regarding edge-indendent graph models and consider the paper well written. Most concerns have been very well addressed by the authors. Possible extensions of the paper to edge-dependent models are interesting but beyond the scope of the paper at hand. Reviewers disagree on the potential impact of the paper and on the relevance of the theoretical results in practical applications. It was mentioned that the paper is highly valuable for research on graph generative models and may have further impact on other research regarding learning on graphs.
Decision: Accept (Poster)