Research map / Graph learning / GNN architectures
On the Power of Edge Independent Graph Models
Sudhanshu Chanpuriya, Cameron N Musco, Konstantinos Sotiropoulos, Charalampos Tsourakakis
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Constrain an edge-independent model to bounded overlap | Edge-independent graph models · Graphs generated by the model | expected triangles: ≤ \frac{\sqrt{2}}{3} \cdot Ov(P)^{3/2} \cdot V(P)^{3/2} | Hurt |
| Constrain an edge-independent model to bounded overlap | Edge-independent graph models · Graphs generated by the model | expected k-cycles: ≤ \frac{2^{k/2}}{2k} \cdot Ov(P)^{k/2} \cdot V(P)^{k/2} | Hurt |
| Constrain an edge-independent model to bounded overlap | Edge-independent graph models · Graphs generated by the model with V(P) \ge 2 n | expected global clustering coefficient: O \left (\frac{Ov(P)^{3/2} \cdot n}{V(P)^{1/2}} \right ) | Hurt |
| Use low overlap | Edge-independent graph generative models · Cora-ML | average triangles: 2,802 -> 1,461 | Hurt |
| Use low overlap | Edge-independent graph generative models · Cora-ML | average squares: 14,268 -> 6,880 | Hurt |
| Increase overlap | Edge-independent graph generative models · Tested graph datasets | triangle count | Improved |
| Use CCOP or HDOP, which match the input degree sequence | CCOP and HDOP · Tested graph datasets at overlap less than 0.2 | degree sequence match | Improved |
| Fix edges from high-degree nodes | HDOP · Tested graph datasets | triangle density | Improved |
| Use TSVD instead of CELL | TSVD · Tested graph datasets | degree sequence match | Improved |
| Use TSVD instead of CELL | TSVD · Tested graph datasets | characteristic path length | Hurt |
| Use edge-independent random connections | Tested edge-independent graph models · Tested graph datasets except Web-Edu | characteristic path length | Hurt |
Closest papers by meaning
- On the Role of Edge Dependency in Graph Generative Models (ICML 2024 · similarity 0.92)
- When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors (NeurIPS 2026 · similarity 0.88)
- Efficient and Scalable Graph Generation through Iterative Local Expansion (ICLR 2024 · similarity 0.87)
- Geometric Generative Modeling with Noise-Conditioned Graph Networks (ICML 2025 · similarity 0.87)
- HiGen: Hierarchical Graph Generative Networks (ICLR 2024 · similarity 0.86)
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.86)
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.
