On the Role of Edge Dependency in Graph Generative Models
- URL: http://arxiv.org/abs/2312.03691v1
- Date: Wed, 6 Dec 2023 18:54:27 GMT
- Title: On the Role of Edge Dependency in Graph Generative Models
- Authors: Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos,
Charalampos Tsourakakis
- Abstract summary: We introduce a novel evaluation framework for generative models of graphs.
We focus on the importance of model-generated graph overlap to ensure both accuracy and edge-diversity.
Our results indicate that our simple, interpretable models provide competitive baselines to popular generative models.
- Score: 28.203109773986167
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
Related papers
- Hierarchical Blockmodelling for Knowledge Graphs [0.5530212768657544]
We use blockmodels for the purpose of hierarchical entity clustering on knowledge graphs.
The integration of the Nested Chinese Restaurant Process and the Stick Breaking Process into the generative model allows for the induction of hierarchical clusterings.
We evaluate our model on synthetic and real-world datasets and quantitatively compare against benchmark models.
arXiv Detail & Related papers (2024-08-28T09:04:15Z) - (Deep) Generative Geodesics [57.635187092922976]
We introduce a newian metric to assess the similarity between any two data points.
Our metric leads to the conceptual definition of generative distances and generative geodesics.
Their approximations are proven to converge to their true values under mild conditions.
arXiv Detail & Related papers (2024-07-15T21:14:02Z) - Grounding and Enhancing Grid-based Models for Neural Fields [52.608051828300106]
This paper introduces a theoretical framework for grid-based models.
The framework points out that these models' approximation and generalization behaviors are determined by grid tangent kernels (GTK)
The introduced framework motivates the development of a novel grid-based model named the Multiplicative Fourier Adaptive Grid (MulFAGrid)
arXiv Detail & Related papers (2024-03-29T06:33:13Z) - Unifying Generation and Prediction on Graphs with Latent Graph Diffusion [24.505897569096476]
We propose the first framework that enables solving graph learning tasks of all levels.
We first formulate prediction tasks including regression and classification into a generic (conditional) generation framework.
We then propose Latent Graph Diffusion (LGD), a generative model that can generate node, edge, and graph-level features of all categories simultaneously.
arXiv Detail & Related papers (2024-02-04T15:03:47Z) - HiGen: Hierarchical Graph Generative Networks [2.3931689873603603]
Most real-world graphs exhibit a hierarchical structure, which is often overlooked by existing graph generation methods.
We propose a novel graph generative network that captures the hierarchical nature of graphs and successively generates the graph sub-structures in a coarse-to-fine fashion.
This modular approach enables scalable graph generation for large and complex graphs.
arXiv Detail & Related papers (2023-05-30T18:04:12Z) - GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton.
The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases.
In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
arXiv Detail & Related papers (2022-12-01T11:49:07Z) - On the Power of Edge Independent Graph Models [22.085932117823738]
We study the limitations of edge independent random graph models, in which each edge is added to the graph independently with some probability.
We prove that subject to a bounded overlap condition, edge independent models are inherently limited in their ability to generate graphs with high triangle and other subgraph densities.
arXiv Detail & Related papers (2021-10-29T19:12:14Z) - Improving Label Quality by Jointly Modeling Items and Annotators [68.8204255655161]
We propose a fully Bayesian framework for learning ground truth labels from noisy annotators.
Our framework ensures scalability by factoring a generative, Bayesian soft clustering model over label distributions into the classic David and Skene joint annotator-data model.
arXiv Detail & Related papers (2021-06-20T02:15:20Z) - A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
We propose a robust framework for adversarial graph embedding, named AGE.
AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution.
Based on this framework, we propose three models to handle three types of graph data.
arXiv Detail & Related papers (2021-05-22T07:05:48Z) - Interpretable Deep Graph Generation with Node-Edge Co-Disentanglement [55.2456981313287]
We propose a new disentanglement enhancement framework for deep generative models for attributed graphs.
A novel variational objective is proposed to disentangle the above three types of latent factors, with novel architecture for node and edge deconvolutions.
Within each type, individual-factor-wise disentanglement is further enhanced, which is shown to be a generalization of the existing framework for images.
arXiv Detail & Related papers (2020-06-09T16:33:49Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.