SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generation

• URL: http://arxiv.org/abs/2307.01646v4
• Date: Wed, 19 Jun 2024 04:48:13 GMT
• Title: SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generation
• Authors: Qi Yan, Zhengyang Liang, Yang Song, Renjie Liao, Lele Wang,
• Abstract summary: Diffusion models based on permutation-equivariant networks can learn permutation-invariant distributions for graph data. We propose a non-invariant diffusion model, called $textitSwinGNN$, which employs an efficient edge-to-edge 2-WL message passing network.
• Score: 15.977241867213516
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Diffusion models based on permutation-equivariant networks can learn permutation-invariant distributions for graph data. However, in comparison to their non-invariant counterparts, we have found that these invariant models encounter greater learning challenges since 1) their effective target distributions exhibit more modes; 2) their optimal one-step denoising scores are the score functions of Gaussian mixtures with more components. Motivated by this analysis, we propose a non-invariant diffusion model, called $\textit{SwinGNN}$, which employs an efficient edge-to-edge 2-WL message passing network and utilizes shifted window based self-attention inspired by SwinTransformers. Further, through systematic ablations, we identify several critical training and sampling techniques that significantly improve the sample quality of graph generation. At last, we introduce a simple post-processing trick, $\textit{i.e.}$, randomly permuting the generated graphs, which provably converts any graph generative model to a permutation-invariant one. Extensive experiments on synthetic and real-world protein and molecule datasets show that our SwinGNN achieves state-of-the-art performances. Our code is released at https://github.com/qiyan98/SwinGNN.

Related papers

• Graph Sampling for Scalable and Expressive Graph Neural Networks on Homophilic Graphs [7.658211994479856]
  Graph Neural Networks (GNNs) excel in many graph machine learning tasks but face challenges when scaling to large networks. We propose a novel graph sampling algorithm that leverages feature homophily to preserve graph structure.
  arXiv  Detail & Related papers  (2024-10-22T00:30:31Z)
• Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation [36.896680500652536]
  We introduce a Permutation-invariant Auto Regressive Diffusion model that integrates diffusion models with autoregressive methods. Pard achieves state-of-the-art performance on molecular and non-molecular datasets, and scales to large datasets like MOSES containing 1.9M molecules.
  arXiv  Detail & Related papers  (2024-02-06T04:17:44Z)
• Graph Invariant Learning with Subgraph Co-mixup for Out-Of-Distribution Generalization [51.913685334368104]
  We propose a novel graph invariant learning method based on invariant and variant patterns co-mixup strategy. Our method significantly outperforms state-of-the-art under various distribution shifts.
  arXiv  Detail & Related papers  (2023-12-18T07:26:56Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Pure Transformers are Powerful Graph Learners [51.36884247453605]
  We show that standard Transformers without graph-specific modifications can lead to promising results in graph learning both in theory and practice. We prove that this approach is theoretically at least as expressive as an invariant graph network (2-IGN) composed of equivariant linear layers. Our method coined Tokenized Graph Transformer (TokenGT) achieves significantly better results compared to GNN baselines and competitive results.
  arXiv  Detail & Related papers  (2022-07-06T08:13:06Z)
• Going Deeper into Permutation-Sensitive Graph Neural Networks [6.685139672294716]
  We devise an efficient permutation-sensitive aggregation mechanism via permutation groups. We prove that our approach is strictly more powerful than the 2-dimensional Weisfeiler-Lehman (2-WL) graph isomorphism test.
  arXiv  Detail & Related papers  (2022-05-28T08:22:10Z)
• Top-N: Equivariant set and graph generation without exchangeability [61.24699600833916]
  We consider one-shot probabilistic decoders that map a vector-shaped prior to a distribution over sets or graphs. These functions can be integrated into variational autoencoders (VAE), generative adversarial networks (GAN) or normalizing flows. Top-n is a deterministic, non-exchangeable set creation mechanism which learns to select the most relevant points from a trainable reference set.
  arXiv  Detail & Related papers  (2021-10-05T14:51:19Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  Graph neural networks (GNNs) are emerging machine learning models on graphs. Permutation-equivariance and proximity-awareness are two important properties highly desirable for GNNs. We show that existing GNNs, mostly based on the message-passing mechanism, cannot simultaneously preserve the two properties. In order to preserve node proximities, we augment the existing GNNs with node representations.
  arXiv  Detail & Related papers  (2020-09-05T16:46:56Z)
• Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
  We propose a permutation invariant approach to modeling graphs, using the recent framework of score-based generative modeling. In particular, we design a permutation equivariant, multi-channel graph neural network to model the gradient of the data distribution at the input graph. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.
  arXiv  Detail & Related papers  (2020-03-02T03:06:14Z)

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.