Do Graph Diffusion Models Accurately Capture and Generate Substructure Distributions?

• URL: http://arxiv.org/abs/2502.02488v1
• Date: Tue, 04 Feb 2025 17:04:16 GMT
• Title: Do Graph Diffusion Models Accurately Capture and Generate Substructure Distributions?
• Authors: Xiyuan Wang, Yewei Liu, Lexi Pang, Siwei Chen, Muhan Zhang,
• Abstract summary: Diffusion models do not possess universal expressivity to accurately model the distribution scores of complex graph data. Our work addresses this limitation by focusing on the frequency of specific substructures as a key characteristic of target graph distributions. We establish a theoretical connection between the expressivity of Graph Neural Networks (GNNs) and the overall performance of graph diffusion models.
• Score: 28.19526635775658
• License:
• Abstract: Diffusion models have gained popularity in graph generation tasks; however, the extent of their expressivity concerning the graph distributions they can learn is not fully understood. Unlike models in other domains, popular backbones for graph diffusion models, such as Graph Transformers, do not possess universal expressivity to accurately model the distribution scores of complex graph data. Our work addresses this limitation by focusing on the frequency of specific substructures as a key characteristic of target graph distributions. When evaluating existing models using this metric, we find that they fail to maintain the distribution of substructure counts observed in the training set when generating new graphs. To address this issue, we establish a theoretical connection between the expressivity of Graph Neural Networks (GNNs) and the overall performance of graph diffusion models, demonstrating that more expressive GNN backbones can better capture complex distribution patterns. By integrating advanced GNNs into the backbone architecture, we achieve significant improvements in substructure generation.

Related papers

• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs) This framework provides a standardized setting to evaluate GNNs across diverse datasets. We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• Advective Diffusion Transformers for Topological Generalization in Graph Learning [69.2894350228753]
  We show how graph diffusion equations extrapolate and generalize in the presence of varying graph topologies. We propose a novel graph encoder backbone, Advective Diffusion Transformer (ADiT), inspired by advective graph diffusion equations.
  arXiv  Detail & Related papers  (2023-10-10T08:40:47Z)
• Dynamic Causal Explanation Based Diffusion-Variational Graph Neural Network for Spatio-temporal Forecasting [60.03169701753824]
  We propose a novel Dynamic Diffusion-al Graph Neural Network (DVGNN) fortemporal forecasting. The proposed DVGNN model outperforms state-of-the-art approaches and achieves outstanding Root Mean Squared Error result.
  arXiv  Detail & Related papers  (2023-05-16T11:38:19Z)
• 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)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• OOD-GNN: Out-of-Distribution Generalized Graph Neural Network [73.67049248445277]
  Graph neural networks (GNNs) have achieved impressive performance when testing and training graph data come from identical distribution. Existing GNNs lack out-of-distribution generalization abilities so that their performance substantially degrades when there exist distribution shifts between testing and training graph data. We propose an out-of-distribution generalized graph neural network (OOD-GNN) for achieving satisfactory performance on unseen testing graphs that have different distributions with training graphs.
  arXiv  Detail & Related papers  (2021-12-07T16:29:10Z)
• Crime Prediction with Graph Neural Networks and Multivariate Normal Distributions [18.640610803366876]
  We tackle the sparsity problem in high resolution by leveraging the flexible structure of graph convolutional networks (GCNs) We build our model with Graph Convolutional Gated Recurrent Units (Graph-ConvGRU) to learn spatial, temporal, and categorical relations. We show that our model is not only generative but also precise.
  arXiv  Detail & Related papers  (2021-11-29T17:37:01Z)
• Generalization of graph network inferences in higher-order graphical models [5.33024001730262]
  Probabilistic graphical models provide a powerful tool to describe complex statistical structure. inferences such as marginalization are intractable for general graphs. We define the Recurrent Factor Graph Neural Network (RF-GNN) to achieve fast approximate inference on graphical models that involve many-variable interactions.
  arXiv  Detail & Related papers  (2021-07-12T20:51:27Z)
• Generating the Graph Gestalt: Kernel-Regularized Graph Representation Learning [47.506013386710954]
  A complete scientific understanding of graph data should address both global and local structure. We propose a joint model for both as complementary objectives in a graph VAE framework. Our experiments demonstrate a significant improvement in the realism of the generated graph structures, typically by 1-2 orders of magnitude of graph structure metrics.
  arXiv  Detail & Related papers  (2021-06-29T10:48:28Z)
• GRAND: Graph Neural Diffusion [15.00135729657076]
  We present Graph Neural Diffusion (GRAND) that approaches deep learning on graphs as a continuous diffusion process. In our model, the layer structure and topology correspond to the discretisation choices of temporal and spatial operators. Key to the success of our models are stability with respect to perturbations in the data and this is addressed for both implicit and explicit discretisation schemes.
  arXiv  Detail & Related papers  (2021-06-21T09:10:57Z)

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.