On the Power of Edge Independent Graph Models
Authors: Sudhanshu Chanpuriya
Cameron N Musco
Konstantinos Sotiropoulos
Charalampos Tsourakakis
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph generative models
random graphs
edge independent models
node embeddings
triangle density

Abstract: Why do many modern neural-network-based graph generative models fail to reproduce typical real-world network characteristics, such as high triangle density?  In this work we study the limitations  of $edge\ independent\ random\ graph\ models$, in which  each edge is added to the graph independently with some probability. Such models include both the classic Erdos-Renyi and stochastic block models, as well as  modern generative models such as NetGAN, variational graph autoencoders, and CELL. 
 We prove that subject to a $bounded\  overlap$ condition, which ensures that the model does not simply memorize a single graph, edge independent models are inherently limited in their ability to generate graphs with high triangle and other subgraph densities. Notably, such high densities are known to appear in real-world social networks and other graphs. We complement our negative results with a simple generative model that balances overlap and accuracy, performing comparably to more complex models in reconstructing many graph statistics. 

On the Power of Edge Independent Graph Models
Sudhanshu Chanpuriya University of Massachusetts Amherst schanpur i waaaumms.sse... edu
Cameron Musco
University of Massachusetts Amherst cmuscoêcs. umass.
Konstantinos Sotiropoulos
Charalampos E. Tsourakakis Boston University & ISI Foundation Esourolampis@gnet com
Boston University ksotiropebu. edu edu
Abstract
Why many modern neural-network- based graph generative models fail repro- duce typical real-world network characteristics, such as high triangle density? In this work we study the limitations of edge independent random graph models, which each edge is added to the graph independently with some probability. Such models include both the classic Erdös-Rényí and stochastic block models, as well modern generative models such as NetGAN, variational graph autoencoders, and CELL. We prove that subject to a bounded overlap condition, which ensures that the model does not simply memorize single graph, edge independent models are inherently limited in their ability to generate graphs with high triangle and other subgraph densities. Notably, such high densities known to appear in real-world social networks and other graphs. We complement our negative results with simple generative model that balances overlap and accuracy, performing comparably to more complex models in reconstructing many graph statistics.
1 Introduction
Our work centers edge independent graph models, in which each edge (i.j) is added to the graph independently with some probability P.j E [0, 1). Formally,
Definition 1 (Edge Independent Graph Model). For any symmetric matrix P E [0, 1|axn let G(P) be the distribution over undirected unweighted graphs where G G(P) contains edge (i.j) inde- pendently, with probability Pij. l.e., p(G) II(a))eeR()) Psj Il (1 -1- P.)).
Edge independent models encompass many classic random graph models. This includes the Erdös- Rényi model, where for all * j. Psj = p for some fixed E [0, 1] [10]. It also includes the stochastic block model where P.j if two nodes are in the same community and P. g if two nodes are in different communitics for some fixed p, E [0, 1] with q < p [2]]. Other examples include e.g., the Chung-Lu configuration model 5 stochastic Kronecker graphs (17).
Recently, significant attention has focused on graph generative models, which seek learn distribution over graphs that share similar properties algorithms parameterize this distribution as an edge independent model or closely related distribution. E.g., NetGAN and the closely related CELL model both produce P E [0, 1 and then sample edges independently without replacement with probabilities proportional to its entries, ensuring that least one edge is sampled adjacent to each node
given training graph, or set of graphs. Many
[ 23). Variational Graph Autoencoders (VGAE), EraphVAE, Graphite, and MolGAN are also all based on edge independent models [16] 28 8 [3]
Given their popularity in both classical and modern graph generative models, it is natural to ask:
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

How suited are edge independent models to modeling real-world networks. Are they able to capture features such as power-law degree distributions, small-world properlies, and high clustering coefficients (Iriangle densities)?
1.1 Impossibility Results for Edge Independent Models
In this work we focus on the ability of edge independent models to generate graphs with high triangle, or other small subgraph densities. High triangle density (equivalently, a high clustering coefficient) well-known hallmark of real-work networks 31
and has been the focus of recent work exploring the power and limitations of edge-independent graph models [27
25 9
It is clear that edge independent models can generate triangle dense graphs. In particular, P [0, 1]nXa in Def. [ can be set to the binary adjacency matrix of any undirected graph, and ((P) will generate that graph with probability 1, no matter how triangle dense it is. However, this would not be a particularly interesting generative model - ideally ((P) should generate a wide range of graphs. To capture this intuitive notion, define the overlap of edge-independens model, which is closely related to the overlap stopping criterion for training used in training graph generative models B 23
Definition (Expected Overlap). For symmetric E [0, 1]=xx let ((P) def
EG-g(m) and
Ov(P) def G2 |(GG) n F(G2)
V(P)
That is, for any P E [0, 1|nxn, Ov(P)= [0, 1. is the ratio of the expected number of edges shared by two graphs drawn independently from (PP) to the expected number of edges in graph drawn from ((P). In one extreme, when is binary adjacency matrix, Ov(P) 1, and our generative model has simply memorized a single graph. In the other, if P.j for all + (i.c., G(P) is Erdös-Rényjn Oo(P) P) = p. This is the minimum possible overlap when V(P) = p (2)
Our main result is that for any edge independent model with bounded overlap, G ((P) cannot have too many triangles in expectation. In particular:
Theorem (Main Result- - Expected Triangles). For a graph G, let A(G) denote the number of triangles in G. Consider symmetric P [0, mmx.
V2 3
EG~ [AG <
As an example, consider the setting where the distribution generates sparse graphs, with V(P) = (n). Theorem I shows that whenever Ov(P)= = o(1/n1/3) Ba-g()) A(G) (n) i.e. the graph very triangle sparse with the number of triangles sublinear in the number of nodes. This verifies that an Medös-Rényí graph cannot achieve simultaneously linear number of edges (i.e., Ov(P) 0(1/n)
) and super-linear number of triangles (i.e., Ov( P) = 22 (/n1///3)) under our proposed lens of viewing generative models.
We extend Theorem T to give similar bounds for the density of squares and other k-cycles (Thm. 4. as well as for the global clustering coefficient (Thm. (6). In all cases we show that our bounds tight- - e.g., in the triangle case, there is indeed an edge independent model with EGNO(P) (A(G))
@ (Oo(P)3/2 V(P)3/2), matching the lower bound in Theorem
1.2 Empirical Findings
Our theoretical results help explain why, despite performing well in a variety of other metrics, edge independent graph generative models have been reported to generate graphs with many fewer triangles and squares on average than the real-world graphs that they are trained on. Rendsburg et al. (3] test suite of these models, including their own CELL model and the related NetGAN model 3 Of all
these models, when trained on the CORA-MP MML graph with 2,802 triangles and 14,268 squares, none is able to generate graphs with more than 1,461 triangles and 6,880 squares on average. Similar gaps are observed for a number of other graphs. Rendsburg et al. also report that the triangle count increases as their notion of overlap (closely related to Def. 2 increases. Theorem T demonstrates that this underestimation of triangle count, and its connection to overlap inherent to all edge independent models, matter how refined a method used to learn the underlying probability matrix P.
2

---

While our theoretical results bound the performance of any edge independent model, there may still be variation in how specific models trade-off overlap and realistic graph generation. To better understand this trade-off, we introduce two simple models with easily tunable overlap as baselines. One is based on reproducing the degree sequence of the original graph; the other, which is even simpler, is based on reproducing the volume. In both models, P is a weighted average of the input graph adjacency matrix and a probability matrix of minimal complexity which matches either the input degrees or the volume. In the latter case, to match just the volume, we simply use Erdös-Rény: graph. In the former case, to match the degree sequence, we introduce our own model, the odds product model; this model is similar to the Chung Lu configuration model [5], but, unlike Chung-Lu. is able to match degree sequences of real-world graphs with high maximum degree. We find that these simple baselines are often competitive with more complex models like CELL in terms of matching key graph statistics, like triangle count and clustering coefficient, at similar levels of overlap.
1.3 Related Work
Existing impossibility results. Our work is inspired by that of Seshadhri et al. [27], which also proves limitations on the ability of edge independent models to represent triangle dense graphs They show that if P = max(0, min(1, XXT)) where X E R for k < n and the max and min are applied entrywise, then G (PP) cannot have many triangles adjacent to low-degree nodes in expectation. This setting arises commonly when P is generated using oww-dimensional node embeddings -aainng---ppreeee represented by the rows of X. Chanpuriya et al. [4] show that in slightly more general model, where P = m0 min(1, ))")), this lower bound no longer holds - Y E I can be chosen so that P is the binary adjacency matrix of any graph with maximum degree upper bounded by (kk) no matter how triangle dense that graph is. Thus, even such low-rank edge independent models can represent triangle dense graphs - by memorizing a single one. In the appendix, we prove a similar result when P is generated from the CELL model of (23). which simplifies NetGAN [3.
Our results show that this trade-off between the ability capture triangle density and memorization is inherent - even without any low-rank constraint, edge independent models with low overlap simply cannot represent graphs with high triangle or other small subgraph density.
is well understood that specific edge independent models, e.g., Erdös-Rény Rényi graphs, the Chung-Lu model, and stochastic Kronecker graphs, do not capture many properties of real-world networks, including high triangle density [3]] [22]. Our results can be viewed as a generalization of these observations. to all edge independent models with low overlap. Despite the limitations of classic models, edge independent models are still very prevalent in today's 's literature on graph generative models. Our more general results make clear the limitations of this approach.
Non-independent models. While edge independent models are very prevalent in the literature, many important models do not fit into this framework. Classic models include the Barabási-Alber and other preferential attachment models (2), Watts StttogSStoggtz small-world graphs [MI), and random geometric graphs [6] Many of these models were introduced directly in response to shortcomings of classic edge independent models, including their inability to produce high triangle densities
More recent graph generative models include GraphRNN (32) and a number of other works 19 20
Our impossibility results do not apply to such models, and in fact suggest that perhaps they may be preferable to edge independent models, if a distribution over graphs with high triangle density is desired. very interesting direction for future work would be to prove limitations on broad classes of non-independent models, and perhaps to understand exactly what type of correlation amongst edges needed to generate graphs with both low overlap and hallmark features of real-world networks.
2 Impossibility Results for Edge Independent Models
We now prove our main results on the limitations of edge independent models with bounded overlap. We start with a simple lemma that will be central in all our proofs.
Lemma 2. For any symmetric P E [0, 1x
|| 2 < Ov(P) ((P) < ||P|2
We note that for non-edge independent models, the measure of overlap as defined earlier should be adapted to take into account the order (permutation) of the vertices in the final graph. In particular, the overlap in this case should be the maximum value of it over any permutation of the vertex set.
3

---

Proof. Let [[( E G be the 0, indicator random variable that an edge (i.j) appears in the E(G2)]. By linearity of expectation and the
graph G. Ov(P)- (P) Gc
independence of G1 and G2 we have,
Ou(P) V(P) = BGG GP)(()
Σ ((1,)) E Gi) -.(.) E G2)
Σ p?
The bound follows since P is symmetric. Note that the lower bound |
I Ov((P V(P) is an
equality if P is on the diagonal i.e., there is no probability of self loops.
2.1 Triangles
Lemma 2 connects Ov(P). (PP to P| and in turn the eigenvalue spectrum P since ||] = E== (P) where (P),, An (P) E are the cigenvalues of Р. The expected number of triangles in G ~ ((P) can be written in terms of this spectrum as well, allowing us to relate overlap to this expected triangle count, and prove main theorem (Theorem [ restated below.
Theorem 1 For graph G, let (G) denote the number of triangles in G. Consider symmetric
PE [0,1] Rxn
v2 3
BaNg(P) [AGG]] S (u(P))/2.V(P)))
Proof. By linearity of expectation,
EG-S(P) [AG)]
Pr (i. E ())) E(G))
n
PuPPpPa - = Σ (P)
(I)
Letting (P) denote the largest magnitude eigenvalue P, we can in turn bound
tr(pa) < (P))
Σ - |P|
Since [Ar( < ||l|e this gives via Lemma
tr(P²) < PI| < 2 Ou(P)8/2 (PP)8/2.
Combining this bound with completes the theorem.
The bound of Theorem is tight up to constants, for any possible value Ov(P). The tight example is when P is simply an Erdös-Rént Rényi graph.
Theorem 3 (Tightness of Expected Triangle Bound). For any (0, 1}, there exists symmetric P [0, 1|axn with Ov (P) 7 and (Ccg(P)/A((T))) ( 3P))3/2).
Proof. Let Psg = y for all + j. We have V(P) = y (r) and Ou(P) V(P) = 72 (g) Thus,
Ou(P) = y. Further, by linearity of expectation,
Eo-g())(A(G) = = (m)
O(7² nz) = 0(23/2 (P)33/2).
We note that another example when Theorem | is tight when P is union of a fixed clique on
((y nt) nodes and Erdös-Rén Rényi graph with connection probability 1/n on the rest of the nodes.

---

2.2 Squares and Other k-cycles
We can extend Thm. to bound the expected number of k-cycles in G ~ G(P) in terms of Ov(P).
Theorem 4 (Bound Expected k-cycles), For graph G, let (R(G) denote the number of k-cycles G. Consider symmetric P E [0, 1|mxx.
2k/2
EG-s(P) [Cx(G)] & 2k
Proof. For notational simplicity, we focus k 4. The proof directly extends to general Ca(G) is the number of non-backtracking 4-cycles in G (i.e. squares), which can be written as
BG- (Ca-)) 1
Σ E
E PapPyePPePa.
i=1 jEjn) (E.A))
The 1/8 factor accounts for the fact that in the sum, each square is counted 8 times once for each potential starting vector i and once of each direction it may be traversed. For general k-cycles this factor would be 2h
We then can bound
Bc- (C]()
ΣΣΣ LEim] kE[n] 6E(m)
E
PoPPsPPePP
tr(P").
For general k-cycles this bound would be Ea-a(P) [C+(G)]
1 &
tr(Pk). This in turn gives
26
2
EG-s(P) [Cx(G)) 2
(A)
PP|
PI
2k
2k
where the last bound follows from Lemma
This completes the theorem..
It is not hard to see that Theorem also tight up constant depending on k for any overlap E (0, 1]. also for an Erdös-Rényí graph with connection probability ?
Theorem (Tightness of Expected k-cycle Bound), For any y (0, 1], there exists Pe [0, 1]mx
with Ou P) 7 and (Cx θ ( ((P))/
2.3 Clustering Coefficient
Theorem shows that the expected number of triangles generated by an edge independent model is bounded in terms of the model's overlap. Intuitively, thus expect that graphs generated by the edge independent model will have low global clustering coefficient, which is the fraction of wedges in the graph that closed into triangles [II]
Definition (Global Clustering Coefficient), For a graph G with AGG) triangles, no self-loops, and node degrees d1, d2, ..., dny the global clustering coefficient given by
32(G)
C(G)
d,(d, 1))
We extend Theorem 1 to give a bound on EG- [C(G)) in terms of Ov(P). The proof, given in Appendix A is related, but more complex due to the Σ d,(d, (dd the denominator of C(G). Theorem (Bound on Expected Clustering Coefficient). Consider symmetric P e [0, 1|axn with zeros on the diagonal and with V(P) 2 2n.
EG-O(P) [C(G)] - (0 V(P)1/2
(
Thus, to have constant clustering coefficient for graph with O(n) edges in expectation, need Ou(P) ((1/nt/3). Note that the requirement of V(P) 2n is very mild it means that the expected average degree is at least 1.
As with triangle bound, Theorem 6 is tight when G(P) is just an Erdös-Rénn Rényi distribution.
5

---

Theorem 7 (Tightness of Expected Clustering Coefficient Bound). For any 7 E (0, 1]. there exists P E [0, 1|aXn with zeros on the diagonal, Ov(P) S and [G-g(P)(C(G)] = = 93/2mm
((P)-7
Proof. Let P.j =7 for all i + j. We have (PP) 7 = ( and Ov(P) y, Additionally, [[A(G)) = O(7² =n),, and, if n is large enough with respect to y, with very high probability, Em=1 di - 1) s Ei= df = (77"n²) This gives:
(c-(() = O(7) = - ( (2./..
= (28/22.
-
(1/2.
3 Baseline Edge Independent Models
We now shift from proving theoretical limitations of edge independent models empirically evaluat- ing the tradeoff between overlap and performance for a number of particular models. Given an input adjacency matrix A E {0, 1JmXn, these generative models produce a P E [0, 1| samples from which should match various graph statistics of A, such as the triangle count, clustering coefficient, and assortativity. At the same time, P should ideally have lower overlap so that the model does not just memorize the original graph. We propose two simple generative models as baselines to more complicated existing models- in both the level of overlap easily tuned. Our first baseline, the odds product model, is based on just matching the degree sequence of A; more simple still, the second baseline computes
linear function of A, just matching its volume.
Odds product model. In this model, each node is assigned a logit & E R. and the probability of adding an edge between nodes and j is P.j ale + f,): where is the logistic function. We fit the model by finding a vector & E IR" of logits, with one logit for each node, such that the reconstructed network has the same expected degrees (i.e. row and column sums) the original graph. We note that this model can be seen as special case of the MaxEnt 7 and random-effect, 22 14] [5] models. In the context of directed graphs, L; has been called the expansiveness or popularity of node i [12].
For adjacency matrix A E 1)mx, we denote its degree sequence by d A1 E RR, where 1 is the all-ones vector of length n. Similarly, the degree sequence of the model is d = P1. We pose fitting the model as root-finding problem: we seek & E IR" such that the degree errors are zero, that method to solve this root- moot-finding problem.
is, d - d= = 0. We use the multivariate To apply Newton-Raphson we need the Jacobian matrix J of derivatives of the degree errors with respect to the entries of f. Since d does not vary with l, these derivatives are exactly dd, Letting d:g be 1 if i = j and otherwise (i.e. the Kronecker delta), we compute in Appendix
ad. 0e, = P.j (1 (1)) + 5:z ERE(H)
kE]N] Pue (1-P)))
In Algorithm I we provide pseudocode for the fully Jacobian matrix J and for implementing Newton- Raphson method to compute P. We do not have a proof that Algorithm always converges and produces which exactly reproduces in the inut degree sequence. However, the algorithm converged on all test cases, and proving that it always converges would be an interesting future direction.
Our odds product model can be viewed as a variant of the Chung-Lu configuration model [5) which is also based on degree sequence matching. However, but our model comes without certain restriction on the maximum degree: in Chung-Lu, it is assumed that the degrees of all nodes are bounded above by the square root of the volume of the graph, that is, d, S VV(A) for all nodes i. Given this restriction, each node is assigned weight w; di/ VVA), and the probability of adding edge (i,5) is P.j = w; Wy Since the weights are all in [0, 1). they can be interpreted as probabilities, and the probability of adding edge between two nodes is the product of the two nodes' probabilities.
Our odds product model works similarly, but instead of probability, for each node, there is an associated odds, that is, value in (0, oo), and the odds of adding an edge between two nodes is the product of the two nodes" odds. There a one-to-one-to-one relationship between probability p E [0, 1]. odds I [0, co), and logit & = In(o) E (-o0, +oo). We outlined above how our

---

Algorithm Fitting the odds product model
input graphical degree sequence d E R", error threshold output symmetric matrix E (0, 1) with row/column sums approximately
1: l t
b L E R' is the vector of logits, initialized to all zeros > is the logistic function applied entrywise,
2: P (E1 + +
and 1 is the all-ones column vector of length n D degree sequence of P
3: d P1
4: while || d|l do
5:
B - Po (11 P)
D o is an entrywise product b diag is the diagonal matrix with the input vector along its diagonal rather than inverting we solve this linear system
6:
+ + diag (B1)
7:
l - d
8:
P (aI + 1
9: d-
10: end while
return P
model is based on adding logits associated with each node; since the odds is the exponentiation of the logit, the model can equally be viewed as multiplying odds associated with nodes.
Varying overlap the odds product model. We propose a simple method to control the trade-off between overlap and accuracy in matching the input graph statistics in the odds product model. Given the original adjacency matrix A and the generated by the odds product model to match the degree sequence of A, we use a convex combination P and A. That is, we use P = w) + wA, where 0 < w S 1. As w increases to 1, P approaches model which returns the original graph with high certainty; hence high w produce P with high overlap which closely match graph statistics, while low w produce P with lower overlap which may diverge from in some statistics. Note that since P a convex combination of adjacency matrices with the expected degree sequence of A, P also has the same expected degree sequence regardless of the value of
Linear model. As an even simpler baseline, we also propose and evaluate the following model: we produce an Erdös Rényi model P with the same expected volume the original graph A, then return convex combination P of P and A. In particular, each entry of P is V (A)/n?, and, with the < 1. This model can alternatively be producing a P by lowering each entry of A which is 1 to probability a, and raising each entry of which is 0 to probability 3, with a 2 8, such that the volume is conserved.
odds product model, P (1 P + WA, where
Experimental Results
We now present our evaluations of different edge independent graph generative models terms the tradcoff achieved between overlap and performance in generating graphs with similar key statistics to an input network. These experiments highlight the strengths and limitations of each model, as well as the overall limitations of this class, established by our theoretical bounds.
4.1 Methods
We compare our proposed models from Section with number of existing models described below
1. CELL 23
(Cross- (Cross-Entropy Low-rank Logits) An alternative to the popular NetGAN method which strips the proposed architecture of deep leaning components and achieves com- parable performance in significantly less time, via a low-rank approximation approach. To control overlap, we follow the approach of the original paper, halting training once the generated graph exceeds a specified overlap threshold with the input graph. We set the rank parameter to value that allows us get up 75% overlap (typical values 16 and 32).
2. TSVD (Truncated Singular Value Decomposition) A classic spectral method which computes rank-k approximation of the adjacency matrix using truncated SVD. As (77, the resulting matrix is clipped to [0.1] to yield P. Overlap is controlled by varying k.
7

---

Table 1: Dataset summaries
Dataset
Nodes
Edges
Triangles
POLBLOGS
1,222
33,428
101,043
CITESEER 26
2,110
7,336
1,083
WEB-EDU
3,031
12,948
10,058
CORA 26
2,485
10,138
1,558
MOAD-MINNESOTA
24
2,640
6,604
53
PPI 30
3,852
75,682
91,461
FACEBOOK 1
4,039
176,468
1,612,010
3. CCOP (Convex Combination Odds Product) The odds product model of Sec. 3 with overlap controlled by taking a convex combination of P and the input adjacency matrix A.
4. HDOP (Highest Degree Odds Product) The odds product model, but with overlap controlled by fixing the edges adjacency to certain number of the highest degree nodes. See Appendix for results on other variants, e.g., where some number of dense subgraphs are fixed.
5. Linear The convex combination between the input adjacency matrix and Erdös-Rénn -énni graph, as described in Sec. 3 with overlap controlled by varying the parameter.
CCOP, HDOP, and Linear all produce edge probability matrices P with the same volume, V(G), in expectation the original adjacency matrix. For TSVD, letting L be the low-rank approximation of the adjacency matrix, we learn a scalar shift parameter a using Newton's 's method such that P max(0, min( 1, L + o)) has volume V(G). We then generate new networks from the edge independent distribution G(P) (Def. T.. For CELL, we follow the authors' approach generating edge (i. is added with probability proportional to P.j).
V(G) edges without replacement
sample networks from each distribution and report the average for every statistic. For imple- mentation details and code, see the supplemental material.
4.2 Datasets and network statistics
For evaluation we use seven popular datasets with varied structure, from triangle-rich social networks to planar road networks see Table I We treat each network undirected and keep its largest connected component. In the main text we present results on three of the networks. POLBLOGS, CITESEER, and WEB-EDU. POLBLOGS is collection of political blogs and the links between them. CITESEER is graph of papers from six scientific categories and the citations among them. Finally, WER-EDU is a web-graph from educational institutions. Descriptions of other networks and results on them are deferred to the appendix.
We evaluate performance in matching the following key network statistics:
1. Pearson correlation of the degree sequences of the input and the generated network.
2. Maximum degree over nodes.
3. Exponent power-law distribution fit to the degree sequence.
4. Assortativity, a measure that captures the preference of nodes to attach to others with similar degree (ranging from -1 to l).
5. Pearson correlation of the triangle sequence (number of triangles a node participates in).
6. Total triangle count (analyzed theoretically in Thm. D
7. Global clustering coefficient (defined in Def. and analyzed theoretically in Thm.
8. Characteristic path length (average path length between any two nodes).
4.3 Results
The theoretical results from Section 2
highlight key weakness of edge independent generative models: they cannot generate many tranggees (or other higher-order locally dense areas), without

---

having high overlap and thus not generating diversity of graphs. We observe that these theoretical findings hold practice generally speaking. all models tested tend significantly underestimate triangle count and global clustering coefficient, as well inaccurately match the triangle degree sequence, when overlap low. See Figures | [ 3nd for results on the POIBBLOGS, CITESEER, and WEB-EDU networks. As overlap increases, performance in reconstructing these metrics does well, as expected.
All methods are able to capture certain network characteristics accurately, even at low overlap. Even for relatively small overlap (less than 0.2), the CCOP and HDOP methods accurately capture the degree sequences of the true networks (as they are designed to do). These methods, especially HDOP which fixes edges from high degree nodes, often outperform more sophisticated methods like CELL in terms of triangle density and triangle degree sequence correlation. On the other hand, CELL seems to a somewhat better job capturing global features, like the characteristic path length. TSVD provides a fair compromise it performs better than CELL in terms of degree sequence and triangle counts, but worse terms of characteristic path length. general, is the method that gives the best results when the overlap is extremely small, appearing to be less sensitive the variation in overlap.
Broadly speaking, all methods do reasonably well in matching the power-law degree distribution of the networks, even when they do not match the actual degree sequence closely. With the exception of WEB-EDU they tend to underestimate the characteristic path length (see additional plots the supplemental). This is perhaps not surprising due to the independent random edge connections, however it would be interesting to understand more theoretically.
Degree Correlation
Max Degree
Power Law Exp.
Assortativity
2.2
1.0
350
0.05
0.9
2.0
0.00
0.8
-0.05
-0.1
1.6
0.15
0020
1.4
-0.25
0.0
Triangle Correlation
Norm. Triangle Count
Clustering Coeff.
Charac. Path Length
1.00
1.50
0.95
1.25
0.30
2.8
0.90
1.00
2.7
0.85
0.15
0.50
0.10
0.75
0.25
0.05
0.70
2.5
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
True
CELL
CCOP
Linear
Figure 1: Metrics for POLBLOGS.
Conclusion
Our theoretical results prove limitations on the ability of any edge independent graph generative model to produce networks that match the high triangle densities of real-world graphs, while still generating diverse of networks, with low model overlap. These results match empirical findings that popular edge independent models indeed systematically underestimate triangle density, clustering coefficient, and related measures. Despite the popularity of edge independent models, many non- independent models, such as graph RNNs 32 have been proposed. An interesting future direction would to study the representative power and limitations of such models, giving general theoretical results that provide foundation for the study of graph generative models.

---

Degree Correlation
Max Degree
Power Law Exp.
Assortativity
2.05
80
2.00
0:10
0.6
1.95
0.05
0.4
40
1.90
1.85
-0.05
0.2
1.80
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Triangle Correlation
Norm. Triangle Count
Clustering Coeff.
Charac. Path Length
1.0
0.8
0.8
0.6
0.08
0.06
7
0.4
0.04
0.2
0.2
0.02
0.0
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
True
HDOP
CELL
TSVD
CCOP
Linear
Figure 2: Metrics for CITESEER.
Degree Correlation
Max Degree
Power Law Exp.
Assortativity
1.0
100
2.00
0.8
1.95
1.90
0.1
60
1.85
0.0
0.4
40
1.80
0..
20
1.75
-0.2
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
Triangle Correlation
Norm. Triangle Count
Clustering Coeff.
Charac, Path Length
0.3
0.2
0.1
0.2
0.2
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
True
HDOP
CELL
TSVD
CCOP
Linear
Figure 3: Metrics for WEB-EDU.
Acknowledgments and Disclosure of Funding
CT acknowledges support from Intesa Sanpaolo Innovation Center. CM was partially supported by NSF grants no. 1763618 and 2046235 and an Adobe Research Grant. The funders had role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
10

---

References
[1] Lada Adamic and Natalie Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd International Workshop on Link Discovery, pages 36-43, 2005.
[2] Álsert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512 1999.
[3] Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. NetGAN: Generating graphs via random walks. Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
[4] Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. Node embeddings and exact low-rank representations of complex networks. Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[5] Fan Chung and Linyuan Lu. The average distances random graphs with given expected degrees. Proceedings of the National Academy of Sciences, (1125):15879-18888 2002.
[6] Jesper Dall and Michael Christensen. Random geometrie graphs. Physical Review E, 66(1):01112, 2002.
[7] Tijl Bie. Maximum entropy models and subjective interestingness: an application to tiles in binary databases. Data Mining and Knowledge Discovery, 23(3):407-446, 2011.
[8] Nicola De Cao and Thomas Kipf. MolGAN: An implicit generative model for small molecular
graphs. ICML Deep Generative Models Workshop, 2018.
[9] Nurcan Durak, Ali Pinar, Tamara G Kolda, and C Seshadhri. Degree relations of triangles in real-world networks and graph models. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2012.
[10] Paul Erdös and Alfréd Rényi. On the evolution of random graphs. Publications of the Mathe- matical Institute of the Hungarian Academy of Sciences, 5(1):17-60, 1960.
[11] David Gleich, Leonid Zhukov, and Pavel Berkhin. Fast parallel pagerank: A linear system approach. Yahoo! Research Technical Report, 13:22, 2004.
[12] Anna Goldenberg, Alice X Zheng, Stephen E Fienberg, and Edoardo M Airoldi. A survey of statistical network models. 2010.
[13] Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
[14] Peter D Hoff. Random effects models for network data. In Dynamic Social Network Modeling and Analysis: Workshop Summary and Pupers. Citeseer, 2003.
[15] Peter D Hoff. Bilinear mixed-effects models for dyadic data. Journal of the American Statistical Association, 100(469):286-2955 2005.
[16] Thomas N Kipf and Max Welling. Variational graph auto-encoders. NeurIPS Bayesian Deep
Learning Workshop, 2016.
[17] Jure Leskovee, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahra- mani. Kronecker graphs: an approach to modeling networks. Journal of Machine Learning Research, 11()), 2010.
[18] Jure Leskovec and Julian J Mcauley. Learning discover social circles in ego networks. In Advances in Neural Information Processing Systems 25 (NeurIPS), pages 539-547, 2012.
[19] Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. a0331:1803.033324 2018
[20] Renjie Liao, Yujia Li, Yang Song. Shenlong Wang, Charlie Nash, William L Hamilton, David Duvenaud, Raquel Urtasun, and Richard S Zemel. Efficient graph generation with graph recurrent attention networks. 1rXiv:1910.00710 2019.
[21] Zhuang Ma, Zongming Ma, and Hongsong Yuan. Universal latent space model fitting for large networks with edge covariates. J. Mach. Learn. Res., 21:4-1, 2020.
11

---

[22] Ali Pinar, Comandur Seshadhri, and Tamara G Kolda. The similarity between stochastic Kronecker and Chung-Lu graph models. In Proceedings of the 2012 SIAM International Conference Data Mining, 2012.
[23] Luca Rendsburg, Holger Heidrich, and Ulrike von Luxburg. NetGAN without GAN: From random walks to low-rank approximations. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
[24] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015.
[25] Alessandra Sala, Lili Cao, Christo Wilson, Robert Zablit, Haitao Zheng, and Ben Y Zhao. Measurement--cllivaaeed graph models for social network experiments. In Proceedings of the 19th International World Wide Web Conference (WWW), 2010.
[26] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Magazine, 29(3):93-93, 2008.
[27] C Seshadhri, Aneesh Sharma, Andrew Stolman, and Ashish Goel. The impossibility of low-rank representations for triangle-rich complex networks. Proceedings of the National Academy of Sciences, 117(11):5611-6637 2020.
(28) Martin Simonovsky and Nikos Komodakis. Graph VAE: Towards generation of small graphs using variational autoencoders. In International Conference on Artificial Neural Networks, pages 412-422. Springer, 2018.
[29] Tom AB Smijders and Krzysztof Nowicki. Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of Classification, 14(1):75-100, 1997.
[30] Chris Stark, Bobby-Joe Breitkreutz, Andrew Shatr-Aryamontri Lorrie Boucher, Rose Oughtred, Michael Livstone, Julie Nixon, Kimberly Van Auken, Xiaodong Wang, Xiaoqi Shi, et al. The BioGRID interaction database: 201 I update. Nucleic Acids Research, 39:D698-D704, 2010.
[31] Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world" 'small-wworddneewwoss... Nature, 393(6684):444-442, 1998.
networks.
[32] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 3708-5717 2018.
12


Reviews:
[{"review_id": "qITLoRMBmw-", "reviewer": "Reviewer_XR1M", "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. \n\nExperiments 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Originality**\n\nThe 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. \n\n\n**Quality**\n\nAll theorems appear correct (though I did not check Theorem 6 in detail) and are potentially useful starting points for later work.\n\nMy main concern with the paper is that the theoretical results are not explicitly validated in the experiments:\n1) 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.\n\n2) All algorithms are edge-independent models. It would be interesting to at least run one baseline that is not edge-independent.\n\nI further have a minor remark:\n\n3) 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.\n\n\n**Clarity**\n\nThe paper is a joy to read and communicates the result in a surprisingly clear manner.\n\nI 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.\n\n**Significance**\n\nThe 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. \n\n\n[1] Goldenberg, A., Zheng, A. X., Fienberg, S. E., & Airoldi, E. M. (2010). A survey of statistical network models.\n\n[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.\n\n[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.\n\n**UPDATE**\n\nI thank the authors for their responses. My score remains unchanged and I hope to see the paper accepted and inspire future work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "YEuVW0fRD-", "reviewer": "Reviewer_nDnc", "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. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n\n1. 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? \n\n2. 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).\n\n3. 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. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "UnF_pL4sv6Z", "reviewer": "Reviewer_NNzz", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nMy 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.\nNevertheless, 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.\n\nIn 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.\n\n\nTypo: the expectation is missing in the equation at the bottom of page 3 (middle)\n\n**==== Edit after rebuttal ====**\n\nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6iAQEU3BRR0", "reviewer": "Reviewer_iT9Y", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nThe 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. \n\nThe 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.\n\n==== After reading authors' response and reviews by other reviewers ==== \n\nI 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~ 6-7 hours"}, "extra_text": {}}]

Author rebuttal:

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)