Graph Generation with $K^2$-trees

• URL: http://arxiv.org/abs/2305.19125v4
• Date: Tue, 26 Mar 2024 05:18:13 GMT
• Title: Graph Generation with $K^2$-trees
• Authors: Yunhui Jang, Dongwoo Kim, Sungsoo Ahn,
• Abstract summary: We introduce a novel graph generation method leveraging $K2$-tree representation. We also present a sequential $K2$-treerepresentation that incorporates pruning, flattening, and tokenization processes. We extensively evaluate our algorithm on four general and two molecular graph datasets to confirm its superiority for graph generation.
• Score: 13.281380233427287
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Generating graphs from a target distribution is a significant challenge across many domains, including drug discovery and social network analysis. In this work, we introduce a novel graph generation method leveraging $K^2$-tree representation, originally designed for lossless graph compression. The $K^2$-tree representation {encompasses inherent hierarchy while enabling compact graph generation}. In addition, we make contributions by (1) presenting a sequential $K^2$-treerepresentation that incorporates pruning, flattening, and tokenization processes and (2) introducing a Transformer-based architecture designed to generate the sequence by incorporating a specialized tree positional encoding scheme. Finally, we extensively evaluate our algorithm on four general and two molecular graph datasets to confirm its superiority for graph generation.

Related papers

• SeqGrowGraph: Learning Lane Topology as a Chain of Graph Expansions [17.302926840794193]
  We present SeqGrowGraph, a novel framework that learns lane topology as a chain of graph expansions.<n>We evaluate it on nuScenes and Argoverse 2 datasets.
  arXiv  Detail & Related papers  (2025-07-07T09:42:37Z)
• InstructG2I: Synthesizing Images from Multimodal Attributed Graphs [50.852150521561676]
  We propose a graph context-conditioned diffusion model called InstructG2I. InstructG2I first exploits the graph structure and multimodal information to conduct informative neighbor sampling. A Graph-QFormer encoder adaptively encodes the graph nodes into an auxiliary set of graph prompts to guide the denoising process.
  arXiv  Detail & Related papers  (2024-10-09T17:56:15Z)
• Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data [91.27527985415007]
  Existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph. We advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set.
  arXiv  Detail & Related papers  (2023-06-05T07:53:52Z)
• 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)
• Let There Be Order: Rethinking Ordering in Autoregressive Graph Generation [6.422073551199993]
  Conditional graph generation tasks involve training a model to generate a graph given a set of input conditions. Many previous studies employ autoregressive models to incrementally generate graph components such as nodes and edges. As graphs typically lack a natural ordering among their components, converting a graph into a sequence of tokens is not straightforward.
  arXiv  Detail & Related papers  (2023-05-24T20:52:34Z)
• 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)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• GraphGen-Redux: a Fast and Lightweight Recurrent Model for labeled Graph Generation [13.956691231452336]
  We present a novel graph preprocessing approach for labeled graph generation. By introducing a novel graph preprocessing approach, we are able to process the labeling information of both nodes and edges jointly. The corresponding model, which we term GraphGen-Redux, improves upon the generative performances of GraphGen in a wide range of datasets.
  arXiv  Detail & Related papers  (2021-07-18T09:26:10Z)
• Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation [18.03898476141173]
  A graph generative model defines a distribution over graphs. We derive the exact joint probability over the graph and the node ordering of the sequential process. We train graph generative models by maximizing this bound, without using the ad-hoc node orderings of previous methods.
  arXiv  Detail & Related papers  (2021-06-11T06:37:52Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Adaptive Graph Auto-Encoder for General Data Clustering [90.8576971748142]
  Graph-based clustering plays an important role in the clustering area. Recent studies about graph convolution neural networks have achieved impressive success on graph type data. We propose a graph auto-encoder for general data clustering, which constructs the graph adaptively according to the generative perspective of graphs.
  arXiv  Detail & Related papers  (2020-02-20T10:11:28Z)

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.