summaries: 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. 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. 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. 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. 
abstractText: 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 Erdös-Rényi 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.
authors.name: Sudhanshu Chanpuriya
authors.name: Cameron Musco
authors.name: Konstantinos Sotiropoulos
authors.name: Charalampos E. Tsourakakis
references.authors: Lada A Adamic Natalie Glance
references.title: The political blogosphere and the 2004 us election: divided they blog
references.venue: In Proceedings of the 3rd International Workshop on Link Discovery,
references.authors: Albert-László Barabási Réka Albert
references.title: Emergence of scaling in random networks
references.venue: Science, 286(5439):509–512,
references.authors: Aleksandar Bojchevski Oleksandr Shchur Daniel Zügner Stephan Günnemann
references.title: NetGAN: Generating graphs via random walks
references.venue: Proceedings of the 35th International Conference on Machine Learning (ICML),
references.authors: Sudhanshu Chanpuriya Cameron Musco Konstantinos Sotiropoulos Charalampos E Tsourakakis
references.title: Node embeddings and exact low-rank representations of complex networks
references.venue: Advances in Neural Information Processing Systems
references.authors: Fan Chung Linyuan Lu
references.title: The average distances in random graphs with given expected degrees
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Jesper Dall Michael Christensen
references.title: Random geometric graphs
references.venue: Physical Review E,
references.authors: Tijl De Bie
references.title: Maximum entropy models and subjective interestingness: an application to tiles in binary databases
references.venue: Data Mining and Knowledge Discovery,
references.authors: Nicola De Cao Thomas Kipf
references.title: MolGAN: An implicit generative model for small molecular graphs
references.venue: ICML Deep Generative Models Workshop,
references.authors: Nurcan Durak Ali Pinar Tamara G Kolda C Seshadhri
references.title: Degree relations of triangles in real-world networks and graph models
references.venue: In Proceedings of the 21st ACM International Conference on Information and Knowledge Management,
references.authors: Paul Erdös Alfréd Rényi
references.title: On the evolution of random graphs
references.venue: Publications of the Mathematical Institute of the Hungarian Academy of Sciences,
references.authors: David Gleich Leonid Zhukov Pavel Berkhin
references.title: Fast parallel pagerank: A linear system approach
references.venue: Yahoo! Research Technical Report,
references.authors: Anna Goldenberg Alice X Zheng Stephen E Fienberg Edoardo M Airoldi
references.title: A survey of statistical network models
references.authors: Aditya Grover Aaron Zweig Stefano Ermon
references.title: Graphite: Iterative generative modeling of graphs
references.venue: In Proceedings of the 36th International Conference on Machine Learning (ICML),
references.authors: Peter D Hoff
references.title: Random effects models for network data
references.venue: In Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers. Citeseer,
references.authors: Peter D Hoff
references.title: Bilinear mixed-effects models for dyadic data
references.venue: Journal of the American Statistical Association,
references.authors: Thomas N Kipf Max Welling
references.title: Variational graph auto-encoders
references.venue: NeurIPS Bayesian Deep Learning Workshop,
references.authors: Jure Leskovec Deepayan Chakrabarti Jon Kleinberg Christos Faloutsos Zoubin Ghahramani
references.title: Kronecker graphs: an approach to modeling networks
references.venue: Journal of Machine Learning Research,
references.authors: Yujia Li Oriol Vinyals Chris Dyer Razvan Pascanu Peter Battaglia
references.title: Learning deep generative models of graphs
references.authors: Renjie Liao Yujia Li Yang Song Shenlong Wang Charlie Nash William L Hamilton David Duvenaud Raquel Urtasun Richard S Zemel
references.title: Efficient graph generation with graph recurrent attention
references.authors: Zhuang Ma Zongming Ma Hongsong Yuan
references.title: Universal latent space model fitting for large networks with edge covariates
references.venue: J. Mach. Learn. Res.,
references.authors: Ali Pinar Comandur Seshadhri Tamara G Kolda
references.title: The similarity between stochastic Kronecker and Chung-Lu graph models
references.venue: In Proceedings of the 2012 SIAM International Conference on Data Mining,
references.authors: Luca Rendsburg Holger Heidrich Ulrike von Luxburg
references.title: NetGAN without GAN: From random walks to low-rank approximations
references.venue: In Proceedings of the 37th International Conference on Machine Learning (ICML),
references.authors: Ryan A. Rossi Nesreen K. Ahmed
references.title: The network data repository with interactive graph analytics and visualization
references.venue: In AAAI,
references.authors: Alessandra Sala Lili Cao Christo Wilson Robert Zablit Haitao Zheng Ben Y Zhao
references.title: Measurement-calibrated graph models for social network experiments
references.venue: In Proceedings of the 19th International World Wide Web Conference (WWW),
references.authors: Prithviraj Sen Galileo Namata Mustafa Bilgic Lise Getoor Brian Galligher Tina Eliassi- Rad
references.title: Collective classification in network data
references.venue: AI Magazine,
references.authors: C Seshadhri Aneesh Sharma Andrew Stolman Ashish Goel
references.title: The impossibility of low-rank representations for triangle-rich complex networks
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Martin Simonovsky Nikos Komodakis
references.title: GraphVAE: Towards generation of small graphs using variational autoencoders
references.venue: In International Conference on Artificial Neural Networks,
references.authors: Tom AB Snijders Krzysztof Nowicki
references.title: Estimation and prediction for stochastic blockmodels for graphs with latent block structure
references.venue: Journal of Classification,
references.authors: Chris Stark Bobby-Joe Breitkreutz Andrew Chatr-Aryamontri Lorrie Boucher Rose Oughtred Michael S Livstone Julie Nixon Kimberly Van Auken Xiaodong Wang Xiaoqi Shi
references.title: The BioGRID interaction database: 2011 update
references.venue: Nucleic Acids Research,
references.authors: Duncan J Watts Steven H Strogatz
references.title: Collective dynamics of ‘small-world’networks
references.venue: Nature, 393(6684):440–442,
references.authors: Jiaxuan You Rex Ying Xiang Ren William Hamilton Jure Leskovec
references.title: GraphRNN: Generating realistic graphs with deep auto-regressive models
references.venue: In Proceedings of the 35th International Conference on Machine Learning (ICML),
sections.heading: 1 Introduction
sections.text: Our work centers on edge independent graph models, in which each edge (i, j) is added to the graph independently with some probability Pij ∈ [0, 1]. Formally, Definition 1 (Edge Independent Graph Model). For any symmetric matrix P ∈ [0, 1]n×n let G(P ) be the distribution over undirected unweighted graphs where G ∼ G(P ) contains edge (i, j) independently, with probability Pij . I.e., p(G) = ∏ (i,j)∈E(G) Pij · ∏ (i,j)/∈E(G)(1− Pij).
  Edge independent models encompass many classic random graph models. This includes the ErdösRényi model, where for all i ̸= j, Pij = p for some fixed p ∈ [0, 1] [10]. It also includes the stochastic block model where Pij = p if two nodes are in the same community and Pij = q if two nodes are in different communities for some fixed p, q ∈ [0, 1] with q < p [29]. 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 to learn a distribution over graphs that share similar properties to a given training graph, or set of graphs. Many 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 ∈ [0, 1]n×n and then sample edges independently without replacement with probabilities proportional to its entries, ensuring that at least one edge is sampled adjacent to each node [3, 23]. Variational Graph Autoencoders (VGAE), GraphVAE, Graphite, and MolGAN are also all based on edge independent models [16, 28, 8, 13].
  Given their popularity in both classical and modern graph generative models, it is natural to ask:
  35th Conference on Neural Information Processing Systems (NeurIPS 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 properties, and high clustering coefficients (triangle densities)?
sections.heading: 1.1 Impossibility Results for Edge Independent Models
sections.text: 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) is a well-known hallmark of real-work networks [31, 25, 9] and has been the focus of recent work exploring the power and limitations of edge-independent graph models [27, 4].
  It is clear that edge independent models can generate triangle dense graphs. In particular, P ∈ [0, 1]n×n in Def. 1 can be set to the binary adjacency matrix of any undirected graph, and G(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 G(P ) should generate a wide range of graphs. To capture this intuitive notion, we define the overlap of an edge-independent model, which is closely related to the overlap stopping criterion for training used in training graph generative models [3, 23].
  Definition 2 (Expected Overlap). For symmetric P ∈ [0, 1]n×n let V (P ) def= EG∼G(P )|E(G)| and
  Ov(P ) def = EG1,G2∼G(P )|E(G1) ∩ E(G2)| V (P ) .
  That is, for any P ∈ [0, 1]n×n, Ov(P ) ∈ [0, 1] is the ratio of the expected number of edges shared by two graphs drawn independently from G(P ) to the expected number of edges in a graph drawn from G(P ). In one extreme, when P is a binary adjacency matrix, Ov(P ) = 1, and our generative model has simply memorized a single graph. In the other, if Pij = p for all i ̸= j (i.e., G(P ) is Erdös-Rényi), Ov(P ) = p. This is the minimum possible overlap when V (P ) = p · ( n 2 ) .
  Our main result is that for any edge independent model with bounded overlap, G ∼ G(P ) cannot have too many triangles in expectation. In particular: Theorem 1 (Main Result – Expected Triangles). For a graph G, let ∆(G) denote the number of triangles in G. Consider symmetric P ∈ [0, 1]n×n.
  EG∼G(P ) [∆(G)] ≤ √ 2
  3 ·Ov(P )3/2 · V (P )3/2.
  As an example, consider the setting where the distribution generates sparse graphs, with V (P ) = Θ(n). Theorem 1 shows that whenever Ov(P ) = o(1/n1/3), EG∼G(P )∆(G) = o(n) – i.e. the graph is very triangle sparse with the number of triangles sublinear in the number of nodes. This verifies that an Erdös-Rényi graph cannot achieve simultaneously linear number of edges (i.e., Ov(P ) = O(1/n) ) and super-linear number of triangles (i.e., Ov(P ) = Ω(1/n1/3)) under our proposed lens of viewing generative models.
  We extend Theorem 1 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 are tight – e.g., in the triangle case, there is indeed an edge independent model with EG∼G(P ) [∆(G)] = Θ ( Ov(P )3/2 · V (P )3/2 ) , matching the lower bound in Theorem 1.
sections.heading: 1.2 Empirical Findings
sections.text: 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. [23] test a suite of these models, including their own CELL model and the related NetGAN model [3]. Of all these models, when trained on the CORA-ML 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 1 demonstrates that this underestimation of triangle count, and its connection to overlap is inherent to all edge independent models, no matter how refined a method used to learn the underlying probability matrix P .
  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 an Erdös-Rényi 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.
sections.heading: 1.3 Related Work
sections.text: 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 ∈ Rn×k for k ≪ n and the max and min are applied entrywise, then G ∼ G(P ) cannot have many triangles adjacent to low-degree nodes in expectation. This setting arises commonly when P is generated using low-dimensional node embeddings – represented by the rows of X . Chanpuriya et al. [4], show that in a slightly more general model, where P = max(0,min(1, XY T )), this lower bound no longer holds – X,Y ∈ Rn×k can be chosen so that P is the binary adjacency matrix of any graph with maximum degree upper bounded by O(k) – 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 to 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.
  It is well understood that specific edge independent models, e.g., Erdös-Rényi graphs, the Chung-Lu model, and stochastic Kronecker graphs, do not capture many properties of real-world networks, including high triangle density [31, 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 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–Albert and other preferential attachment models [2], Watts–Strogatz small-world graphs [31], 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. A 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 is needed to generate graphs with both low overlap 1and hallmark features of real-world networks.
sections.heading: 2 Impossibility Results for Edge Independent Models
sections.text: 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 ∈ [0, 1]n×n, ∥P∥ 2 F
  2 ≤ Ov(P ) · V (P ) ≤ ∥P∥ 2 F .
  1We 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.
  Proof. Let I[(i, j) ∈ G] be the 0, 1 indicator random variable that an edge (i, j) appears in the graph G. Ov(P ) · V (P ) = EG1,G2∼G(P )|E(G1) ∩ E(G2)|. By linearity of expectation and the independence of G1 and G2 we have,
  Ov(P ) · V (P ) = EG1,G2∼G(P ) ∑ i≤j I[(i, j) ∈ G1] · I[(i, j) ∈ G2] = ∑ i≤j P 2ij .
  The bound follows since P is symmetric. Note that the lower bound ∥P∥ 2 F
  2 ≤ Ov(P ) · V (P ) is an equality if P is 0 on the diagonal – i.e., there is no probability of self loops.
sections.heading: 2.1 Triangles
sections.text: Lemma 2 connects Ov(P ) · V (P ) to ∥P∥2F and in turn the eigenvalue spectrum of P since ∥P∥2F =∑n i=1 λi(P )
  2, where λ1(P ), . . . , λn(P ) ∈ R are the eigenvalues of P . The expected number of triangles in G ∼ G(P ) can be written in terms of this spectrum as well, allowing us to relate overlap to this expected triangle count, and prove our main theorem (Theorem 1), restated below.
  Theorem 1. For a graph G, let ∆(G) denote the number of triangles in G. Consider symmetric P ∈ [0, 1]n×n.
  EG∼G(P ) [∆(G)] ≤ √ 2
  3 ·Ov(P )3/2 · V (P )3/2.
  Proof. By linearity of expectation,
  EG∼G(P ) [∆(G)] = 1
  6 n∑ i=1 n∑ j=1 n∑ k=1 Pr [(i, j) ∈ E(G) ∩ (j, k) ∈ E(G) ∩ (k, i) ∈ E(G)]
  = 1
  6 n∑ i=1 n∑ j=1 n∑ k=1 PijPjkPki = 1 6 tr(P 3) = 1 6 n∑ i=1 λi(P ) 3. (1)
  Letting λ1(P ) denote the largest magnitude eigenvalue of P , we can in turn bound
  tr(P 3) ≤ |λ1(P )| · n∑
  i=1
  λi(P ) 2 = |λ1(P )| · ∥P∥2F .
  Since |λ1(P )| ≤ ∥P∥F , this gives via Lemma 2
  tr(P 3) ≤ ∥P∥3F ≤ 2 √ 2 ·Ov(P )3/2 · V (P )3/2.
  Combining this bound with (1) completes the theorem.
  The bound of Theorem 1 is tight up to constants, for any possible value of Ov(P ). The tight example is when P is simply an Erdös-Rényi graph.
  Theorem 3 (Tightness of Expected Triangle Bound). For any γ ∈ (0, 1], there exists a symmetric P ∈ [0, 1]n×n with Ov(P ) = γ and EG∼G(P )[∆(G)] = Θ(γ3/2 · V (P )3/2). Proof. Let Pij = γ for all i ̸= j. We have V (P ) = γ · ( n 2 ) and Ov(P ) · V (P ) = γ2 · ( n 2 ) Thus, Ov(P ) = γ. Further, by linearity of expectation,
  EG∼G(P )[∆(G)] = γ3 · ( n
  3
  ) = Θ(γ3 · n3) = Θ(γ3/2 · V (P )3/2).
  We note that another example when Theorem 1 is tight is when P is a union of a fixed clique on Θ(γ · n) nodes and an Erdös-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. 1 to bound the expected number of k-cycles in G ∼ G(P ) in terms of Ov(P ). Theorem 4 (Bound on Expected k-cycles). For a graph G, let Ck(G) denote the number of k-cycles in G. Consider symmetric P ∈ [0, 1]n×n.
  EG∼G(P ) [Ck(G)] ≤ 2k/2
  2k ·Ov(P )k/2 · V (P )k/2.
  Proof. For notational simplicity, we focus on k = 4. The proof directly extends to general k. C4(G) is the number of non-backtracking 4-cycles in G (i.e. squares), which can be written as
  EG∼G(P ) [C4(G)] = 1
  8 · n∑ i=1 ∑ j∈[n]\i ∑ k∈[n]\{i,j} ∑ ℓ∈[n]\{i,j,k} PijPjkPkℓPℓi.
  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 12k . We then can bound
  EG∼G(P ) [C4(G)] ≤ 1 8 · ∑ i∈[n] ∑ j∈[n] ∑ k∈[n] ∑ ℓ∈[n] PijPjkPkℓPℓi = 1 8 · tr(P 4).
  For general k-cycles this bound would be EG∼G(P ) [Ck(G)] ≤ 12k tr(P k). This in turn gives
  EG∼G(P ) [Ck(G)] ≤ 1
  2k · |λ1(P )|k−2 · ∥P∥2F ≤
  1
  2k ∥P∥kF ≤
  2k/2
  2k Ov(P )k/2 · V (P )k/2,
  where the last bound follows from Lemma 2. This completes the theorem..
  It is not hard to see that Theorem 4 is also tight up to a constant depending on k for any overlap γ ∈ (0, 1], also for an Erdös-Rényi graph with connection probability γ. Theorem 5 (Tightness of Expected k-cycle Bound). For any γ ∈ (0, 1], there exists P ∈ [0, 1]n×n
  with Ov(P ) = γ and EG∼G(P )[Ck(G)] = Θ ( γk/2·V (P )k/2 k! ) .
sections.heading: 2.3 Clustering Coefficient
sections.text: Theorem 1 shows that the expected number of triangles generated by an edge independent model is bounded in terms of the model’s overlap. Intuitively, we 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 are closed into triangles [31]. Definition 3 (Global Clustering Coefficient). For a graph G with ∆(G) triangles, no self-loops, and node degrees d1, d2, . . . , dn, the global clustering coefficient is given by
  C(G) = 3∆(G)∑n
  i=1 di(di − 1) .
  We extend Theorem 1 to give a bound on EG∼G(P ) [C(G)] in terms of Ov(P ). The proof, given in Appendix A, is related, but more complex due to the ∑n i=1 di(di − 1) in the denominator of C(G). Theorem 6 (Bound on Expected Clustering Coefficient). Consider symmetric P ∈ [0, 1]n×n with zeros on the diagonal and with V (P ) ≥ 2n.
  EG∼G(P ) [C(G)] = O ( Ov(P )3/2 · n V (P )1/2 ) .
  Thus, to have a constant clustering coefficient for a graph with O(n) edges in expectation, we need Ov(P ) = Ω(1/n1/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 our triangle bound, Theorem 6 is tight when G(P ) is just an Erdös-Rényi distribution.
  Theorem 7 (Tightness of Expected Clustering Coefficient Bound). For any γ ∈ (0, 1], there exists P ∈ [0, 1]n×n with zeros on the diagonal, Ov(P ) ≤ γ and EG∼G(P )[C(G)] = Θ ( γ3/2·n V (P )1/2 ) . Proof. Let Pij = γ for all i ̸= j. We have V (P ) = γ · ( n 2 ) = Θ(γn2) and Ov(P ) = γ. Additionally,
  E[∆(G)] = Θ(γ3 · n3), and, if n is large enough with respect to γ, with very high probability,∑n i=1 di(di − 1) ≤ ∑n i=1 d 2 i = O(γ 2n3). This gives:
  EG∼G(P )[C(G)] = Θ(γ) = Θ ( γ3/2 · n γ1/2 · n ) = Θ ( γ3/2 · n V (P )1/2 ) .
sections.heading: 3 Baseline Edge Independent Models
sections.text: We now shift from proving theoretical limitations of edge independent models to empirically evaluating the tradeoff between overlap and performance for a number of particular models. Given an input adjacency matrix A ∈ {0, 1}n×n, these generative models produce a P ∈ [0, 1]n×n, 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 is 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 P as a linear function of A, just matching its volume.
  Odds product model. In this model, each node is assigned a logit ℓ ∈ R, and the probability of adding an edge between nodes i and j is Pij = σ(ℓi + ℓj), where σ is the logistic function. We fit the model by finding a vector ℓ ∈ Rn of logits, with one logit for each node, such that the reconstructed network has the same expected degrees (i.e. row and column sums) as the original graph. We note that this model can be seen as a special case of the MaxEnt [7] and random-effects [21, 14, 15] models. In the context of directed graphs, ℓi has been called the expansiveness or popularity of node i [12].
  For adjacency matrix A ∈ {0, 1}n×n, we denote its degree sequence by d = A1 ∈ Rn, 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 a root-finding problem: we seek ℓ ∈ Rn such that the degree errors are zero, that is, d̂− d = 0. We use the multivariate Newton-Raphson method to solve this root-finding problem. To apply Newton-Raphson, we need the Jacobian matrix J of derivatives of the degree errors with respect to the entries of ℓ. Since d does not vary with ℓ, these derivatives are exactly ∂d̂i∂ℓj . Letting δij be 1 if i = j and 0 otherwise (i.e. the Kronecker delta), we compute in Appendix A,
  ∂d̂i ∂ℓj
  = Pij (1− Pij) + δij ∑
  k∈[n] Pik (1− Pik) .
  In Algorithm 1, we provide pseudocode for the fully Jacobian matrix J and for implementing NewtonRaphson method to compute P . We do not have a proof that Algorithm 1 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 a 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, di ≤ √ V (A) for all nodes i. Given this
  restriction, each node is assigned a weight wi = di/ √ V (A), and the probability of adding edge (i, j) is Pij = wiwj . Since the weights are all in [0, 1], they can be interpreted as probabilities, and the probability of adding an edge between two nodes is the product of the two nodes’ probabilities.
  Our odds product model works similarly, but instead of a probability, for each node, there is an associated odds, that is, a value in (0,∞), and the odds of adding an edge between two nodes is the product of the two nodes’ odds. There is a one-to-one-to-one relationship between probability p ∈ [0, 1], odds o = p1−p ∈ [0,∞), and logit ℓ = ln(o) ∈ (−∞,+∞). We outlined above how our
  Algorithm 1 Fitting the odds product model input graphical degree sequence d ∈ Rn, error threshold ϵ output symmetric matrix P ∈ (0, 1)n×n with row/column sums approximately d
  1: ℓ← 0 ▷ ℓ ∈ Rn is the vector of logits, initialized to all zeros 2: P ← σ ( ℓ1⊤ + 1ℓ⊤ ) ▷ σ is the logistic function applied entrywise, and 1 is the all-ones column vector of length n 3: d̃← P1 ▷ degree sequence of P 4: while ∥d̃− d∥2 > ϵ do 5: B ← P ◦ ( 11⊤ − P ) ▷ ◦ is an entrywise product 6: J ← B + diag (B1) ▷ diag is the diagonal matrix with the input vector along its diagonal 7: ℓ← ℓ− J−1 ( d̃− d ) ▷ rather than inverting J , we solve this linear system
  8: P ← σ ( ℓ1⊤ + 1ℓ⊤ ) 9: d̃← P1
  10: end while 11: 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 in 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 P generated by the odds product model to match the degree sequence of A, we use a convex combination of P and A. That is, we use P̃ = (1 − ω)P + ωA, where 0 ≤ ω ≤ 1. As ω increases to 1, P̃ approaches a model which returns the original graph with high certainty; hence high ω produce P̃ with high overlap which closely match graph statistics, while low ω produce P̃ with lower overlap which may diverge from A in some statistics. Note that since P̃ is 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 as the original graph A, then return a convex combination P̃ of P and A. In particular, each entry of P is V (A)/n2, and, as with the odds product model, P̃ = (1− ω)P + ωA, where 0 ≤ ω ≤ 1. This model can alternatively be seen as producing a P̃ by lowering each entry of A which is 1 to some probability α, and raising each entry of A which is 0 to a probability β, with α ≥ β, such that the volume is conserved.
sections.heading: 4 Experimental Results
sections.text: We now present our evaluations of different edge independent graph generative models in terms of the tradeoff 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, as established by our theoretical bounds.
sections.heading: 4.1 Methods
sections.text: We compare our proposed models from Section 3 with a number of existing models described below
  1. CELL [23] (Cross-Entropy Low-rank Logits) An alternative to the popular NetGAN method [3] which strips the proposed architecture of deep leaning components and achieves comparable 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 a value that allows us to get up to 75% overlap (typical values are 16 and 32).
  2. TSVD (Truncated Singular Value Decomposition) A classic spectral method which computes a rank-k approximation of the adjacency matrix using truncated SVD. As in [27], the resulting matrix is clipped to [0,1] to yield P . Overlap is controlled by varying k.
  CCOP, HDOP, and Linear all produce edge probability matrices P with the same volume, V (G), in expectation as the original adjacency matrix. For TSVD, letting L be the low-rank approximation of the adjacency matrix, we learn a scalar shift parameter σ using Newton’s method such that P = max(0,min(1, L + σ)) has volume V (G). We then generate new networks from the edge independent distribution G(P ) (Def. 1). For CELL, we follow the authors’ approach of generating V (G) edges without replacement - an edge (i, j) is added with probability proportional to Pij).
  We sample 5 networks from each distribution and report the average for every statistic. For implementation details and code, see the supplemental material.
sections.heading: 4.2 Datasets and network statistics
sections.text: For evaluation we use seven popular datasets with varied structure, from triangle-rich social networks to planar road networks – see Table 1. We treat each network as 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 a collection of political blogs and the links between them. CITESEER is a graph of papers from six scientific categories and the citations among them. Finally, WEB-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 all nodes.
  3. Exponent of a 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 1).
  5. Pearson correlation of the triangle sequence (number of triangles a node participates in).
  6. Total triangle count (analyzed theoretically in Thm. 1).
  7. Global clustering coefficient (defined in Def. 3 and analyzed theoretically in Thm. 6).
  8. Characteristic path length (average path length between any two nodes).
sections.heading: 4.3 Results
sections.text: The theoretical results from Section 2 highlight a key weakness of edge independent generative models: they cannot generate many triangles (or other higher-order locally dense areas), without
  having high overlap and thus not generating a diversity of graphs. We observe that these theoretical findings hold in practice – generally speaking, all models tested tend to significantly underestimate triangle count and global clustering coefficient, as well as inaccurately match the triangle degree sequence, when overlap is low. See Figures 1, 2, and 3 for results on the POLBLOGS, CITESEER, and WEB-EDU networks. As overlap increases, performance in reconstructing these metrics does as well, as expected.
  All methods are able to capture certain network characteristics accurately, even at low overlap. Even for a 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 do 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 in terms of characteristic path length. In general, it is the method that gives the best results when the overlap is extremely small, appearing to be less sensitive to 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 in the supplemental). This is perhaps not surprising due to the independent random edge connections, however it would be interesting to understand more theoretically.
sections.heading: 5 Conclusion
sections.text: 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 a diverse set 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 nonindependent models, such as graph RNNs [32] have been proposed. An interesting future direction would be to study the representative power and limitations of such models, giving general theoretical results that provide a foundation for the study of graph generative models.
  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 no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
title: On the Power of Edge Independent Graph Models