PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Normalizing Flows

Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, Kevin Swersky

arXiv:1905.13177v1cs.LGstat.ML

TL;DR

Graph learning needs models that handle relational structure while scaling beyond the memory demands of ordinary message passing and the sequential structure of autoregressive generation. The paper introduces reversible graph normalizing flows, using them directly for supervised learning and with a permutation-invariant graph auto-encoder for generation. GNFs match conventional GNN performance, outperform Neumann RBP, and remain competitive with GraphRNN, though graph-generation evaluation can show considerable variance.

  • Problem

    Graph models must support prediction and generation on relational data while addressing message-passing memory costs and permutation-invariant graph generation.

  • Method

    The paper extends normalizing flows to reversible graph neural networks and combines GNFs with a permutation-invariant graph auto-encoder for graph generation.

  • Results

    GNFs match conventional GNN performance, outperform Neumann RBP on benchmark tasks, and achieve competitive results with GraphRNN.

  • Takeaways & Limitations

    Reversibility reduces supervised-model memory requirements, while the permutation-invariant generative model produces whole graphs in a feed-forward architecture suited to parallel computing.

  • Takeaways & Limitations

    Graph-generation MMD results can exhibit considerable variance because the graph test sets are quite small.

Abstract

from arXiv · show

We introduce graph normalizing flows: a new, reversible graph neural network model for prediction and generation. On supervised tasks, graph normalizing flows perform similarly to message passing neural networks, but at a significantly reduced memory footprint, allowing them to scale to larger graphs. In the unsupervised case, we combine graph normalizing flows with a novel graph auto-encoder to create a generative model of graph structures. Our model is permutation-invariant, generating entire graphs with a single feed-forward pass, and achieves competitive results with the state-of-the art auto-regressive models, while being better suited to parallel computing architectures.

1 Introduction

The paper extends normalizing flows to graph neural networks, yielding reversible models for supervised prediction and permutation-invariant graph generation. These models reduce memory requirements for message passing and achieve competitive results against established supervised and autoregressive graph-generation approaches.

  • Graph normalizing flows extend normalizing flows to graph-structured data with exactly reversible message passing.The input node features can be exactly reconstructed from the GNN representation.
  • GRevNets reconstruct lower-layer hidden states during backpropagation, reducing stored states from O(#nodes × #message passing steps) to O(#nodes).This addresses the memory cost of storing hidden states after every message passing step in ordinary GNNs.
  • GRevNets are competitive with conventional memory-inefficient GNNs and outperform RBP on standard benchmarks.
  • Graph generation is challenging because permuting nodes leaves the underlying graph unchanged, requiring permutation-invariant modeling.Autoregressive methods generate nodes and edges sequentially and may face likelihood-marginalization and long-range-dependency challenges.
  • A permutation-invariant graph auto-encoder combined with GNFs generates entire graphs in a feed-forward model competitive with GraphRNN and suited to parallel architectures.

2 Background

The background defines message-passing graph neural networks and normalizing flows as the foundations for the paper’s reversible graph models. GNNs aggregate neighbor messages over iterative updates, while flows use invertible transformations with tractable density calculations.

  • A graph is represented by node features H and edge features Ω, whose first channel records adjacency.H contains features for N nodes, while Ω also stores edge features for possible node pairs.
  • Message-passing neural networks alternate message generation, neighbor aggregation, and vertex updates over T steps before task-specific readout.The readout can convert final node embeddings into task-specific features through operations such as max-pooling.
  • Graph attention weights messages from adjacent nodes, and multi-headed attention applies multiple learned weights before concatenating the results.
  • Normalizing flows transform an observed vector x into a latent vector z through an invertible mapping and relate their densities using the change-of-variables formula.The inverse mapping reconstructs x from z, while the density relation depends on the mapping’s derivative determinant.
  • RealNVP affine coupling partitions x into two variable sets and uses nonlinear scaling and translation functions to produce an efficiently computable triangular Jacobian determinant.The transformation applies elementwise multiplication by exp(s(x^(0))) and adds t(x^(0)) to x^(1).

3 Methods

GRevNets make graph message passing reversible by partitioning node features and applying coupled half-steps, enabling hidden-state reconstruction and lower-memory training. GNFs extend this framework to permutation-invariant graph generation by modeling continuous node embeddings and decoding them into adjacency matrices.

  • 3.1 Reversible Graph Neural Networks (GRevNets): GRevNets split node features into two partitions and update them through reversible message-passing half-steps.F1, F2, G1, and G2 apply message generation and vertex updates to alternating feature partitions using the graph adjacency matrix.
  • 3.1 Reversible Graph Neural Networks (GRevNets): GNFs compute exact density transformations because their message-passing Jacobians are lower triangular and therefore tractable.The change-of-variables formulation maps distributions across reversible graph transformations.
  • 3.2 GNFs for Structured Density Estimation: Generation samples Gaussian latent vectors, inverts the GNF to obtain embeddings, and decodes them into binary edges by thresholding predicted adjacency values.The prior is a product of independent standard Gaussian distributions, and the generated graph structure is recovered from the decoded adjacency matrix.
  • 3.2 GNFs for Structured Density Estimation: Fully connected message passing costs O(N^2), but matrix-operation implementations make GNF computation more amenable to parallel architectures.Graph attention is used so nodes can select the messages they consider most informative.
  • 3.2 GNFs for Structured Density Estimation: For graph generation, GNFs use a permutation-invariant graph auto-encoder to embed graphs into continuous node vectors before decoding embeddings into adjacency matrices.The encoder outputs node embeddings, while the decoder predicts edge probabilities; the two stages are trained separately.

4 Supervised Experiments

The supervised evaluation tests GRevNets on transductive classification and inductive prediction tasks against matched GNNs and memory-efficient Neumann-RBP. Across these benchmarks, GRevNets are reported as competitive with standard GNNs and superior to NRBP.

  • 4.1 Performance on benchmark tasks: Experiments cover citation-network classification on Cora and Pubmed, PPI interaction prediction, and QM9 molecule-property regression.The reported metrics are classification accuracy, Micro F1, and Mean Absolute Error, respectively.
  • 4.1 Performance on benchmark tasks: GRevNets are compared with vanilla GNNs using identical architectures and message-passing steps, plus Neumann-RBP as a memory-efficient baseline.Neumann-RBP is described as a state-of-the-art memory-efficient GNN baseline.
  • 4.1 Performance on benchmark tasks: GRevNet performance is competitive with standard GNNs and outperforms Neumann RBP on the reported benchmark comparisons.Table 1 includes accuracy, Micro F1, and Mean Absolute Error evaluations under the stated training settings.

5 Unsupervised Experiments

The unsupervised experiments evaluate GNFs for structured density estimation and permutation-invariant graph generation. GNFs outperform RealNVP on structured datasets, reconstruct graphs well, and achieve competitive graph-generation performance under multiple evaluation settings.

  • Structured Density Estimation: GNFs outperform RealNVP on all three structured density-estimation datasets.The comparison covers MOG, MOG RING, and 6-HALF MOONS.
  • Graph Auto-Encoder: The graph auto-encoder generalizes to unseen test graphs, with a small train–test cross-entropy gap and strong edge reconstruction.Test reconstruction is good on EGO-SMALL and near-perfect on COMMUNITY-SMALL.
  • Graph Generation: GNF models graph-embedding distributions with a Gaussian prior and decodes sampled embeddings into graph adjacency structures.The auto-encoder and GNF are trained separately.
  • Evaluation: Graph generation is evaluated using MMD between generated graphs and unseen test graphs across degree, clustering-coefficient, and orbit-count statistics.The evaluation includes both node-distribution matching and all-1024-sample settings.
  • Results: GNF outperforms GRAPHVAE and DEEPGMG and is competitive with GraphRNN on graph-generation results.The reported comparisons include results from the GraphRNN evaluation scheme and generated graph visualizations.

6 Conclusion

The paper presents GNFs as reversible graph neural networks for supervised prediction and generative modeling. They reduce memory requirements in supervised learning and provide permutation-invariant graph generation competitive with GraphRNN.

  • Contribution: GNFs make graph message passing reversible, enabling reconstruction of input node features from the GNN representation.The supervised formulation avoids storing hidden node states during backpropagation.
  • Supervised Learning: In supervised tasks, GNFs match GNN performance while outperforming Neumann RBP and reducing memory requirements.Reversibility permits backpropagation without storing hidden node states.
  • Unsupervised Learning: In unsupervised learning, GNFs model distributions over graph auto-encoder embeddings and use the decoder to generate graphs.The resulting model is permutation invariant.
  • Conclusion: The graph-generation model is competitive with the state-of-the-art auto-regressive GraphRNN model.The paper identifies larger-graph applications and end-to-end training as future work.

7.1 Supervised Experiments Details

The supervised experiments cover molecular property prediction, citation-network classification, and inductive protein–protein interaction learning. They document datasets, training splits, regularization, optimization, model selection, and architecture settings.

  • Datasets and Tasks: The experiments use QM9 for molecule property prediction, Cora and Pubmed for citation-network classification, and PPI for inductive learning.PPI contains separate training, validation, and testing graphs, with testing graphs unobserved during training.
  • Datasets and Tasks: Citation-network classification is evaluated with both author-provided splits and a 1%/49%/50% train/test/validation split.The latter setting supports comparison with prior work.
  • Optimization and Regularization: All models use L2 weight regularization with coefficient 0.001.This is listed among the shared hyperparameter settings.
  • Architecture and Optimization: Message-passing depth was selected by search, yielding 4 steps for GNN and GRevNet and 100 for Neumann RBP.The search considered [2] [4] [5] [10] for GNN and GRevNet, and 100 or 200 for Neumann RBP.
  • Model Selection: Models were selected using held-out validation performance measured by accuracy, Micro F1 score, or mean squared error for QM9.The selected model was the one with the best corresponding validation metric.
  • Optimization: Batch normalization was applied during message passing because deeper models became harder to optimize and performed worse beyond 20 steps.The reported issue was observed for both GNN and GRevNet.

7.2 Unsupervised Experiment Details

The additional unsupervised results report graph-generation comparisons with error bars and expanded samples. They use MMD-based results for GNF and GraphRNN alongside reproduced GraphVAE and DeepGMG results.

  • Quantitative Results: GraphRNN and GNF results include error bars from repeated training and evaluation runs.The table caption describes averages over repeated runs for the compared settings.
  • Graph Samples: Figures 4 and 5 provide the full sets of generated samples for EGO-SMALL and COMMUNITY-SMALL.Figure 4 specifically contrasts training graphs with randomly sampled GNF and GraphRNN outputs for EGO-SMALL.
  • Quantitative Results: Table 5 reports graph-generation MMD results for GraphVAE, DeepGMG, GraphRNN, and GNF.GraphVAE and DeepGMG are reproduced from GraphRNN, while GraphRNN and GNF are evaluated using the authors’ scripts.

7.3 Computing Infrastructure

Experiments used single-GPU training with specified message-passing or coupling-layer architectures, optimization settings, and graph-generation samples from COMMUNITY-SMALL.

  • All experiments were trained on a single Tesla P100 or Titan Xp GPU.
  • GNF used 12 message-passing steps with shared self-attention–MLP modules, 8 attention heads, and latent dimension 256.Each module used batch normalization, a 5-layer MLP, and ReLU nonlinearities.
  • RealNVP used an analogous 12-layer coupling architecture with batch normalization and a 5-layer, 256-dimensional ReLU MLP.
  • Both models were trained for 15k steps with Adam at a learning rate of 1e-04.
  • The graph auto-encoder and flow models used dataset-specific node-embedding sizes and multi-step attention-based message-passing architectures.EGO-SMALL used embedding size 14, while COMMUNITY-SMALL used 30; the supplied configurations used 10 or 12 message-passing steps and 8 attention heads.
Loading 1905.13177v1…