Efficient and Scalable Graph Generation through Iterative Local Expansion

• URL: http://arxiv.org/abs/2312.11529v4
• Date: Tue, 14 May 2024 10:59:05 GMT
• Title: Efficient and Scalable Graph Generation through Iterative Local Expansion
• Abstract summary: We introduce a method that generates a graph by progressively expanding a single node to a target graph. In each step, nodes and edges are added in a localized manner through denoising diffusion, building first the global structure, and then refining the local details. Our model achieves state-of-the-art performance on well-established benchmark datasets while successfully scaling to graphs with at least 5000 nodes.
• Score: 26.843529744867222
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the realm of generative models for graphs, extensive research has been conducted. However, most existing methods struggle with large graphs due to the complexity of representing the entire joint distribution across all node pairs and capturing both global and local graph structures simultaneously. To overcome these issues, we introduce a method that generates a graph by progressively expanding a single node to a target graph. In each step, nodes and edges are added in a localized manner through denoising diffusion, building first the global structure, and then refining the local details. The local generation avoids modeling the entire joint distribution over all node pairs, achieving substantial computational savings with subquadratic runtime relative to node count while maintaining high expressivity through multiscale generation. Our experiments show that our model achieves state-of-the-art performance on well-established benchmark datasets while successfully scaling to graphs with at least 5000 nodes. Our method is also the first to successfully extrapolate to graphs outside of the training distribution, showcasing a much better generalization capability over existing methods.

Related papers

• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  We introduce SparseDiff, a novel diffusion model based on the observation that almost all large graphs are sparse. By selecting a subset of edges, SparseDiff effectively leverages sparse graph representations both during the noising process and within the denoising network. Our model demonstrates state-of-the-art performance across multiple metrics on both small and large datasets.
  arXiv  Detail & Related papers  (2023-11-03T16:50:26Z)
• 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)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Node-wise Localization of Graph Neural Networks [52.04194209002702]
  Graph neural networks (GNNs) emerge as a powerful family of representation learning models on graphs. We propose a node-wise localization of GNNs by accounting for both global and local aspects of the graph. We conduct extensive experiments on four benchmark graphs, and consistently obtain promising performance surpassing the state-of-the-art GNNs.
  arXiv  Detail & Related papers  (2021-10-27T10:02:03Z)
• Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
  This paper presents a cross-view graph pooling (Co-Pooling) method to better exploit crucial graph structure information. Through cross-view interaction, edge-view pooling and node-view pooling seamlessly reinforce each other to learn more informative graph-level representations.
  arXiv  Detail & Related papers  (2021-09-24T08:01:23Z)
• 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)
• Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
  We propose a Graph Multiset Transformer (GMT) that captures the interaction between nodes according to their structural dependencies. Our experimental results show that GMT significantly outperforms state-of-the-art graph pooling methods on graph classification benchmarks.
  arXiv  Detail & Related papers  (2021-02-23T07:45:58Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.