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.

通过引入一种新的评估框架，本文提出了一种新颖的图生成模型，并强调了模型生成的图重叠对于确保准确性和边缘多样性的重要性。该文对图生成模型进行了分层，并根据模型重叠推导出了三个级别的理论界限。作者还引入了新的生成模型，并通过在真实数据集上的评估比较，证明了这些模型的竞争性基准。通过这项调查，作者旨在通过提供结构化框架和强大的评估度量，推动图生成模型的发展，从而实现生成准确和边缘丰富的图。

关于边依赖在图生成模型中的作用