PaperlayerView exact revision on arXiv

Source-linked AI summary

Permutation Invariant Graph Generation via Score-Based Generative Modeling

Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, Stefano Ermon

arXiv:2003.00638v1cs.LGstat.ML

TL;DR

Graph generative models should respect node-order invariance, but enforcing this property is challenging in common likelihood-based architectures. The paper uses score-based modeling with a permutation-equivariant multi-channel GNN, achieving comparable generation quality to existing methods and stronger graph-algorithm learning than traditional GNNs.

  • Problem

    Graph generative models often fail to capture permutation invariance, although equivalent node orderings represent the same graph and should receive equal probability.

  • Method

    The paper models permutation-equivariant graph scores with score matching, EDP-GNN's trainable multi-channel adjacency matrices, and annealed Langevin dynamics followed by quantization.

  • Results

    EDP-GNN significantly outperforms traditional GNNs on graph-algorithm learning and achieves comparable graph-generation quality to existing state-of-the-art models.

  • Takeaways & Limitations

    Score-based modeling provides a permutation-invariant graph generator whose samples have quality comparable to existing state-of-the-art models.

  • Takeaways & Limitations

    The model assumes permutation invariance of graph adjacency-matrix distributions under node permutations.

Abstract

from arXiv · show

Learning generative models for graph-structured data is challenging because graphs are discrete, combinatorial, and the underlying data distribution is invariant to the ordering of nodes. However, most of the existing generative models for graphs are not invariant to the chosen ordering, which might lead to an undesirable bias in the learned distribution. To address this difficulty, 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 (a.k.a., the score function). This permutation equivariant model of gradients implicitly defines a permutation invariant distribution for graphs. We train this graph neural network with score matching and sample from it with annealed Langevin dynamics. In our experiments, we first demonstrate the capacity of this new architecture in learning discrete graph algorithms. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.

1 INTRODUCTION

Graph generation has broad applications, but existing learned graph generators struggle to respect permutation invariance. The paper proposes score-based modeling with a permutation-equivariant GNN and evaluates its architecture and generation quality.

  • Graph generation supports applications including drug design, architecture search, and network science.
  • Existing graph generative models use latent-variable or autoregressive approaches that do not fully capture graphs’ permutation invariance.Equivalent node orderings can correspond to the same graph, motivating equal probabilities for equivalent adjacency matrices.
  • GraphVAE approximates permutation invariance with graph matching requiring up to O(N 4) operations, while other methods augment data or select node orderings.
  • The proposed score-based model learns graph-density gradients with a permutation-equivariant GNN, implicitly defining a permutation-invariant adjacency-matrix distribution.Score-based modeling imposes fewer architectural constraints than likelihood-based models, enabling permutation-oriented inductive biases.
  • EDP-GNN uses learnable multi-channel adjacency matrices, significantly outperforms traditional GNNs on graph algorithms, and achieves comparable graph-generation performance to GraphRNN.

2 PRELIMINARIES

The preliminaries formalize permutation-invariant graph distributions and introduce score-based modeling. Training uses noisy score estimation, while annealed Langevin dynamics generates samples that are later quantized for discrete graphs.

  • 2.1 Notations: An undirected graph can be represented by symmetric adjacency matrices whose rows and columns follow a chosen node ordering.
  • 2.1 Notations: Different node orderings represent the same graph, so a permutation-invariant distribution assigns equal probability to their adjacency matrices.
  • 2.2 Graph Neural Networks: Message-passing GNNs map graphs to representations equivariantly, preserving the correspondence induced by node-order permutations.
  • 2.3 Score-Based Generative Modeling: For density p(x), the score function is ∇x log p(x); score-based models estimate the data score instead of directly modeling the density.
  • 2.3 Score-Based Generative Modeling: Training perturbs data with Gaussian noise at multiple intensities and jointly estimates scores using a noise-conditional model.
  • 2.3 Score-Based Generative Modeling: After training, annealed Langevin dynamics generates samples by iterating across noise levels and stochastic updates.

3 SCORE-BASED GENERATIVE MODELING FOR GRAPHS

The method adapts score-based generative modeling to discrete graphs while preserving permutation invariance through an equivariant score network. EDP-GNN uses multi-channel message passing and edgewise updates, then samples with annealed Langevin dynamics and quantizes continuous outputs.

  • Score-Based Modeling: Score-based modeling handles discrete graph generation by perturbing adjacency matrices with Gaussian noise and learning scores of the perturbed distributions.Noise is added only to the upper triangular matrix for undirected graphs, and the score-matching loss uses the perturbation score.
  • Sampling: Annealed Langevin dynamics samples a graph after first sampling its node count and iteratively applying score models across decreasing noise levels.The process uses a series of conditional score models, with symmetric noise to account for symmetric adjacency matrices.
  • Sampling: Continuous adjacency samples are converted to binary graphs by thresholding the generated matrix at the end of annealed Langevin dynamics.The indicator function returns one when the threshold condition holds and zero otherwise.
  • Permutation Equivariance and Invariance: A permutation equivariant score function induces a permutation invariant graph distribution, as formalized by a line-integral construction of the corresponding scalar function.The result follows because message passing and edgewise or nodewise transformations in EDP-GNN are permutation equivariant.
  • EDP-GNN Architecture: EDP-GNN transforms adjacency matrices into new ones using local connectivity information, combining node-feature inference with edge-feature inference.Its multi-channel GNN runs message passing on multiple graphs and concatenates channel features; edge updates use endpoint and current edge features.
  • Experiments: Experiments report that EDP-GNN significantly outperforms traditional GNNs on graph-algorithm learning, while score-based generation achieves comparable performance on several datasets.Noise-level conditioning shares MLP parameters across noise levels and empirically performs similarly to separately trained score networks.

4 RELATED WORK

Prior graph generative models include latent-variable and flow-based approaches, but permutation invariance remains difficult to enforce consistently. Earlier GNNs use edge features or multiple adjacency inputs, whereas EDP-GNN is designed for edgewise prediction with permutation-aware graph processing.

  • Flow-Based Graph Generative Models: Flow-based models such as GNF and GraphNVP use invertible mappings and coupling layers to enable maximum-likelihood learning.
  • Flow-Based Graph Generative Models: GraphNVP avoids full permutation invariance because it hurts empirical performance, whereas GNF achieves it using a permutation-equivariant auto-encoder.
  • GNNs that Learn Edge Features: Earlier GNNs compute intermediate edge features, including attention coefficients, but these features are not generally designed for direct edge prediction.
  • GNNs that Learn Edge Features: Gong and Cheng’s multi-input adjacency approach remains limited by normalized attention and restrictive attention forms for edgewise prediction.

5 EXPERIMENTS

The experiments evaluate EDP-GNN on edgewise graph algorithms and score-based graph generation. EDP-GNN improves weighted edgewise prediction, produces competitive samples, and uses interpretable, learnable multi-channel intermediate adjacency matrices for score modeling.

  • Learning Graph Algorithms: EDP-GNN and baselines are evaluated on shortest-path and maximum-spanning-tree edge-labeling tasks using dynamically generated training data and cross-entropy loss.
  • Learning Graph Algorithms: EDP-GNN performs similarly to GIN on unweighted graphs but achieves much better performance on weighted graphs.
  • Learning Graph Algorithms: Table 1 reports test-set accuracy for EDP-GNN and GIN on shortest-path and maximum-spanning-tree prediction, with separate unweighted and weighted settings.
  • Graph Generation Task: Graph generation is tested on Community-small and Ego-small against GraphRNN, GNF, GraphVAE, and DeepGMG.
  • Graph Generation Task: Generation quality is measured using MMD for degree, clustering-coefficient, and four-node-orbit distributions.
  • Graph Generation Task: EDP-GNN performs comparably to GraphRNN and GNF on most MMD metrics and has the best overall average MMD across the two datasets.
  • Understanding Intermediate Channels: Visualized intermediate channels transform a noise-perturbed Community-small graph with no visible structure into one showing two equal-sized communities.
  • Understanding Intermediate Channels: Ablations show that learnable and multi-channel intermediate adjacency matrices reduce training and test score-matching losses.

6 CONCLUSION

The paper proposes a permutation-invariant graph generative model based on score modeling and Langevin sampling, with EDP-GNN as its permutation-equivariant architecture. Experiments show stronger edgewise algorithm learning and graph-sample quality comparable to existing models.

  • Figure 3 compares training-data, EDP-GNN, and GraphRNN samples on Community-small and Ego-small.
  • The model implicitly defines a permutation-invariant distribution by modeling a permutation-equivariant score function and sampling with Langevin dynamics.
  • EDP-GNN uses learnable multi-channel adjacency matrices as intermediate layers to model graph distributions effectively.
  • EDP-GNNs outperform vanilla GNNs on edgewise prediction tasks for classic graph algorithms, including shortest paths.
  • The score-based model produces graph samples with quality comparable to existing state-of-the-art models.

A EXPERIMENTAL DETAILS

The implementation uses PyTorch with Adam optimization, and the authors make the code publicly available.

  • The model is implemented using PyTorch and optimized with Adam.
  • The authors provide code at https://github.com/ermongroup/GraphScoreMatching.

A.1 Hyperparameters

The experiments use fixed noise and sampling schedules, with hyperparameters selected using validation-set MMD metrics. The architecture stacks EDP-GNN layers with bounded channels and node-feature size.

  • The noise-level settings are σ_i = [1.6, 0.8, 0.6, 0.4, 0.2, 0.1], and σ_L = 0.1 supports accurate recovery of perturbed binary graphs.
  • Sampling uses T = 1000 steps at each noise level, with step size α_i = ϵ · σ_L^2 and an additional scaling coefficient ϵ_s.
  • Hyperparameters are chosen using MMD metrics on a validation set containing 32 training samples.
  • The architecture uses 4 message-passing steps per GIN, 5 EDP-GNN layers, at most 4 channels, and node features of maximum size 16.

A.2 Dataset

The experiments use Community-small and Ego-small graph datasets, while the appendix defines permutation operations and invariant or equivariant functions for adjacency-matrix representations. It also introduces an implicitly defined scalar function from a vector field.

  • Community-small contains two equal-sized Erdős–Rényi communities with p = 0.7 and randomly added inter-community edges, using 12 ≤ N ≤ 20 nodes.
  • Ego-small consists of one-hop ego graphs extracted from Citeseer, with 4 ≤ N ≤ 18 nodes.
  • A permutation-invariant function returns the same value after permuting an adjacency matrix.
  • A permutation-equivariant function transforms its output under node permutations in the same way as its input.
  • A vector field s implicitly defines a scalar function through a line integral from the zero matrix to A using the Frobenius inner product.

C EXTRA SAMPLES

This section presents extra graph samples from the training data and EDP-GNN across Ego-small, Community-small, Protein, and Lobster datasets, with GraphRNN included for the Ego-small and Community-small comparisons.

  • Ego-small: Ego-small samples compare the training data, EDP-GNN, and GraphRNN.The figure presents these three sample sources side by side.
  • Community-small: Community-small samples compare the training data, EDP-GNN, and GraphRNN.The figure presents these three sample sources side by side.
  • Protein: Protein samples compare the training data and EDP-GNN for graphs with 20 ≤N ≤30 nodes.The Protein dataset is attributed to Dobson and Doig (2003).
  • Lobster: Lobster samples compare the training data and EDP-GNN for graphs with N = 10 nodes.The Lobster graph dataset is attributed to Golomb (1996).
Loading 2003.00638v1…