On the Role of Edge Dependency in Graph Generative Models
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Switchover phenomenon for general graphsJournal of Graph Theory, 2024
- Deep learning for drug repurposing: Methods, databases, and applicationsWIREs Computational Molecular Science, 2022
- Array programming with NumPyNature, 2020
- SciPy 1.0: fundamental algorithms for scientific computing in PythonNature Methods, 2020
- Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time2010
- The average distances in random graphs with given expected degreesProceedings of the National Academy of Sciences, 2002
- Connected Components in Random Graphs with Given Expected Degree SequencesAnnals of Combinatorics, 2002
- The degree sequence of a scale‐free random graph processRandom Structures & Algorithms, 2001
- A Random Graph Model for Power Law GraphsExperimental Mathematics, 2001
- Some intersection theorems for ordered sets and graphsJournal of Combinatorial Theory, Series A, 1986