# On the Role of Edge Dependency in Graph Generative Models

arXiv: https://arxiv.org/abs/2312.03691 · HTML: https://mlsanity.com/paper/2312.03691/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 61 references that are in the map.
- First posted on arXiv 6 Dec 2023.

## Builds on (most cited first, 20 of 20)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [GraphGAN: Graph Representation Learning with Generative Adversarial Nets](https://mlsanity.com/paper/1711.08267/) (2017)
- [Graphite: Iterative Generative Modeling of Graphs](https://mlsanity.com/paper/1803.10459/) (2018)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [A Survey on Deep Graph Generation: Methods and Applications](https://mlsanity.com/paper/2203.06714/) (2022)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [Node Embeddings and Exact Low-Rank Representations of Complex Networks](https://mlsanity.com/paper/2006.05592/) (2020)
- [On the Power of Edge Independent Graph Models](https://mlsanity.com/paper/2111.00048/) (2021)
- [Deep learning for drug repurposing: methods, databases, and applications](https://mlsanity.com/paper/2202.05145/) (2022)
- [Scalable motif-aware graph clustering](https://mlsanity.com/paper/1606.06235/) (2016)
- [The Power of Pivoting for Exact Clique Counting](https://mlsanity.com/paper/2001.06784/) (2020)

## Built on by (most cited first, 3 of 3)

- [Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms](https://mlsanity.com/paper/2405.16726/) (2024)
- [When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors](https://mlsanity.com/paper/2610.13765/) (2026)
- [Your Discrete Graph Diffusion Model is Secretly Memorizing](https://mlsanity.com/paper/2610.13786/) (2026)

## Abstract (arXiv)

In this work, we introduce a novel evaluation framework for generative models of graphs, emphasizing the importance of model-generated graph overlap (Chanpuriya et al., 2021) to ensure both accuracy and edge-diversity. We delineate a hierarchy of graph generative models categorized into three levels of complexity: edge independent, node independent, and fully dependent models. This hierarchy encapsulates a wide range of prevalent methods. We derive theoretical bounds on the number of triangles and other short-length cycles producible by each level of the hierarchy, contingent on the model overlap. We provide instances demonstrating the asymptotic optimality of our bounds. Furthermore, we introduce new generative models for each of the three hierarchical levels, leveraging dense subgraph discovery (Gionis & Tsourakakis, 2015). Our evaluation, conducted on real-world datasets, focuses on assessing the output quality and overlap of our proposed models in comparison to other popular models. Our results indicate that our simple, interpretable models provide competitive baselines to popular generative models. Through this investigation, we aim to propel the advancement of graph generative models by offering a structured framework and robust evaluation metrics, thereby facilitating the development of models capable of generating accurate and edge-diverse graphs.