Research map / Graph learning / Graph self-supervised learning
On the Role of Edge Dependency in Graph Generative Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves triangle-count upper bounds for edge independent, node independent, and fully dependent graph generative models as a function of overlap, and proposes simple max-clique-based models (MCEI, MCNI, MCFD) that are competitive with deep baselines.
Problem
Deep graph generative models are hard to evaluate for both output quality and output diversity; it is unclear how much triangle density a model can produce at a given level of overlap (memorization), and how edge dependency affects this trade-off.
Approach
Defines a nested hierarchy (edge independent, node independent, fully dependent) and proves overlap-dependent triangle bounds (overlap^3, overlap^1.5, overlap times n^3) with matching tight examples; uses maximal-clique planting with an odds-product residual model to build simple baselines whose overlap is tunable via a single probability p.
Key results
- Theory: expected triangles bounded by (n^3/6)·overlap^3 for edge independent, (n^3/6)·overlap^1.5 for node independent, and (n^3/2)·overlap for fully dependent models, with matching tight constructions up to constant factors.
- Proposed MCEI/MCNI/MCFD models produce higher triangle counts at low overlap than CELL and GraphVAE on the reported datasets, and higher edge dependency gives more triangles at fixed overlap.
- Overlap of the proposed models is tunable via a single planting probability p, whereas CELL and GraphVAE require early stopping to control overlap.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase edge dependency from edge independent to node independent to fully dependent | Graph generative models · Graph generative models at fixed overlap | triangle count | Helped |
| Use maximal-clique-based MCEI, MCNI, or MCFD instead of CELL | Graph generative models · Les Miserables and other evaluated datasets at low overlap | triangle count | Helped |
| Use maximal-clique-based MCEI, MCNI, or MCFD instead of CELL or GraphVAE | Graph generative models · Les Miserables at low overlap | 4-clique count | Helped |
| Use maximal-clique-based MCEI, MCNI, or MCFD instead of CELL or GraphVAE | Graph generative models · Les Miserables at low overlap | 4-cycle count | Helped |
| Train CELL at low overlap | CELL · Les Miserables | triangle count | Hurt |
| Train GraphVAE at low overlap rather than in a high-overlap regime | GraphVAE · Les Miserables | graph-statistic match | Hurt |
| Use VGAE with its dot-product kernel | VGAE · Evaluated real-world graph datasets | graph-statistic match | Hurt |
| Use the two-stage maximal-clique plus residual-edge method | MCEI, MCNI, and MCFD · Evaluated real-world graph datasets | connectivity-pattern match | Hurt |
| Increase planting probability p | MCEI, MCNI, and MCFD · PolBlogs | overlap | Helped |
Surprising findings
- Deep models such as GraphVAE and CELL can nearly memorize the input graph at high overlap but fail to match triangle and clique statistics at low overlap.
- The simple proposed two-stage models fail to capture connectivity statistics such as fraction of connected pairs and characteristic path length.
Limitations
- Models fail to capture connectivity patterns (fraction of connected pairs, path length) in the two-stage clique-based approach.
- All models generally struggle to match graph statistics at low overlap, per the paper's own findings.
- Theoretical bounds are for triangles and short cycles; hierarchy is coarse (three levels) and the authors note refinement as future work.
Experimental setup
Datasets: Citeseer Cora PPI PolBlogs Web-Edu Les Miserables Wiki-Elect Facebook-Ego Ring of Cliques
Benchmarks: Citeseer Cora PPI PolBlogs Web-Edu Les Miserables Wiki-Elect Facebook-Ego Ring of Cliques
Metrics: max degree degree and triangle sequence Pearson correlation normalized triangle, 4-clique, and 4-cycle counts fraction of connected pairs characteristic path length overlap
Baselines: CELL VGAE GraphVAE Erdős–Rényi Chung-Lu
Builds on: overlap (Seshadhri et al. triangle-overlap trade-off) Chung-Lu model odds product model Shearer's entropy lemma
Closest papers by meaning
- HiGen: Hierarchical Graph Generative Networks (ICLR 2024 · similarity 0.90)
- A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equations (ICML 2025 · similarity 0.89)
- Quality Measures for Dynamic Graph Generative Models (ICLR 2025 · similarity 0.88)
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.88)
- Efficient and Scalable Graph Generation through Iterative Local Expansion (ICLR 2024 · similarity 0.88)
- Towards Addressing Frontiers in Graph Generation (AAAI 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.