# Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 94 references that are in the map.
- First posted on arXiv 26 May 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [Reparameterizable Subset Sampling via Continuous Relaxations](https://mlsanity.com/paper/1901.10517/) (2019)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [How Do Hyperedges Overlap in Real-World Hypergraphs? -- Patterns, Measures, and Generators](https://mlsanity.com/paper/2101.07480/) (2021)
- [On the Power of Edge Independent Graph Models](https://mlsanity.com/paper/2111.00048/) (2021)
- [A Scalable Generative Graph Model with Community Structure](https://mlsanity.com/paper/1302.6636/) (2013)
- [Two-Sample Tests for Large Random Graphs Using Network Statistics](https://mlsanity.com/paper/1705.06168/) (2017)
- [Group interactions modulate critical mass dynamics in social convention](https://mlsanity.com/paper/2103.10411/) (2021)
- [Encapsulation Structure and Dynamics in Hypergraphs](https://mlsanity.com/paper/2307.04613/) (2023)
- [Neighborhood Structure Configuration Models](https://mlsanity.com/paper/2210.06843/) (2022)
- [Differentiable Random Partition Models](https://mlsanity.com/paper/2305.16841/) (2023)
- [On the Role of Edge Dependency in Graph Generative Models](https://mlsanity.com/paper/2312.03691/) (2023)
- [Atomic subgraphs and the statistical mechanics of networks](https://mlsanity.com/paper/2008.10346/) (2020)
- [Interplay between Topology and Edge Weights in Real-World Graphs: Concepts, Patterns, and an Algorithm](https://mlsanity.com/paper/2305.09083/) (2023)
- [Random Graph Modeling: A survey of the concepts](https://mlsanity.com/paper/2403.14415/) (2024)
- [Counting Triangles in Massive Graphs with MapReduce](https://mlsanity.com/paper/1301.5887/) (2013)
- [Tractably Modelling Dependence in Networks Beyond Exchangeability](https://mlsanity.com/paper/2007.14365/) (2020)

## Abstract (arXiv)

Desirable random graph models (RGMs) should (i) reproduce common patterns in real-world graphs (e.g., power-law degrees, small diameters, and high clustering), (ii) generate variable (i.e., not overly similar) graphs, and (iii) remain tractable to compute and control graph statistics. A common class of RGMs (e.g., Erdos-Renyi and stochastic Kronecker) outputs edge probabilities, so we need to realize (i.e., sample from) the output edge probabilities to generate graphs. Typically, the existence of each edge is assumed to be determined independently, for simplicity and tractability. However, with edge independency, RGMs provably cannot produce high subgraph densities and high output variability simultaneously. In this work, we explore RGMs beyond edge independence that can better reproduce common patterns while maintaining high tractability and variability. Theoretically, we propose an edge-dependent realization (i.e., sampling) framework called binding that provably preserves output variability, and derive closed-form tractability results on subgraph (e.g., triangle) densities. Practically, we propose algorithms for graph generation with binding and parameter fitting of binding. Our empirical results demonstrate that RGMs with binding exhibit high tractability and well reproduce common patterns, significantly improving upon edge-independent RGMs.