Top-N: Equivariant Set and Graph Generation without Exchangeability

Clement Vignac, Pascal Frossard

TL;DR

This paper challenges the long-held belief that generative models for sets and graphs must be "exchangeable" (producing all permutations with equal probability) to be permutation equivariant. The authors introduce Top-n creation, a differentiable mechanism that selects the most relevant points from a learned reference set, leading to significantly better training stability and performance across tasks like molecule generation and object detection.

What Problem Does This Paper Address?

Generating sets (like point clouds) or graphs (like molecules) from a single latent vector is a "one-shot" generation problem. The hardest part is the creation step: how do you turn one vector into $n$ distinct points?

Comparison of set creation methods: MLP, Independent sampling (i.i.d.), and First-n (a reference-based approach).

The standard approach is to sample $n$ points randomly (i.i.d.) from a normal distribution and concatenate the latent vector to each. This makes the model "exchangeable," meaning the order of the generated points is random. While this feels "fair" to the unordered nature of sets, the authors point out two major flaws:

  1. Optimization Issues: Stochastic decoders (like those using random sampling) actually optimize a lower bound of the Evidence Lower Bound (ELBO), making them notoriously difficult and slow to train.
  2. The Equivariance Myth: Researchers previously thought exchangeability was the only way to achieve permutation equivariance in generative models. This paper proves that is not the case.

Methods

The authors propose a two-fold solution involving a new theoretical framework and a practical architectural module.

1. $(F, l)$-equivariance

They introduce a relaxed definition of equivariance. They prove that as long as your loss function is permutation invariant (like the Chamfer loss or Wasserstein distance) and your encoder is equivariant, the overall training dynamics remain independent of the data's representation. Crucially, this means the generator does not need to be exchangeable to be part of an equivariant system.

2. Top-n Creation

Instead of sampling random noise, the model learns a Reference Set of points. Each point in this dictionary has a learned "representation" and an "angle."

The Top-n creation mechanism: A latent vector predicts a target angle, which is compared against a trainable reference set via cosine similarity to select and modulate the top n points.
  • Selection: Given a latent vector, the model calculates a target "angle." It then selects the $n$ points from the reference set whose angles are most similar (highest cosine similarity) to the target.
  • Differentiability: Since picking the "top $n$" (an argsort operation) isn't differentiable, they use a FiLM (Feature-wise Linear Modulation) layer. They multiply the selected points' representations by their cosine similarity scores. This creates a path for gradients to flow back to the selection mechanism, allowing the model to learn which points in the dictionary are most useful for specific latent vectors.

Datasets

The model was evaluated on four distinct benchmarks:

  • SetMNIST: A point-cloud version of the classic digit dataset.
  • CLEVR: A complex scene dataset used here for object detection (predicting a set of bounding boxes and attributes from an image).
  • Synthetic 3D Molecules: A new dataset introduced by the authors to test a model's ability to respect physical constraints like valency (how many bonds an atom can have) and diversity.
  • QM9: A standard chemical dataset containing ~134k small organic molecules.

Key Insights and Ideas

  • Breaking the Exchangeability Requirement: The most significant "aha moment" is the proof that non-exchangeable generators can still result in equivariant models. This frees researchers from relying on noisy, hard-to-train random sampling.
  • The "Dictionary" Approach: By using a trainable reference set, the model acts more like an artist choosing specific "brushes" or components from a kit rather than trying to mold white noise into a structured object.
  • FiLM for Gradients: Using modulation (multiplication/addition) to bypass the non-differentiable nature of sorting is a clever trick that makes the "Top-n" selection end-to-end trainable.

Key Results

Top-n creation consistently outperformed i.i.d. sampling and standard MLP-based generators:

  • SetMNIST: Improved reconstruction accuracy by 15%.
  • CLEVR Object Detection: Outperformed i.i.d. generation by 33% in Average Precision.
  • Synthetic Molecules: Generated sets that were 74% closer to the true distribution than previous methods.
  • QM9: Produced a higher percentage of valid and unique molecules compared to other one-shot generators.
  • Training Speed: Top-n converges much faster and with less variance than random sampling methods.

Limitations and Future Work

  • Normalizing Flows: The authors acknowledge that Top-n is not suited for Normalizing Flows because the "hard selection" of points is not an invertible operation.
  • Reference Set Size: While the reference set size is a hyperparameter, there is a trade-off: larger sets allow for more diversity but can slow down training as each point is updated less frequently.
  • Scaling to Large Sets: Most experiments focused on relatively small sets (up to ~35 points). The authors note that the "curse of dimensionality" might still pose challenges for generating very large, complex graphs (like proteins), which remains an open area for future research.

Summary updated

Abstract

This work addresses one-shot set and graph generation, and, more specifically, the parametrization of probabilistic decoders that map a vector-shaped prior to a distribution over sets or graphs. Sets and graphs are most commonly generated by first sampling points i.i.d. from a normal distribution, and then processing these points along with the prior vector using Transformer layers or Graph Neural Networks. This architecture is designed to generate exchangeable distributions, i.e., all permutations of the generated outputs are equally likely. We however show that it only optimizes a proxy to the evidence lower bound, which makes it hard to train. We then study equivariance in generative settings and show that non-exchangeable methods can still achieve permutation equivariance. Using this result, we introduce Top-n creation, a differentiable generation mechanism that uses the latent vector to select the most relevant points from a trainable reference set. Top-n can replace i.i.d. generation in any Variational Autoencoder or Generative Adversarial Network. Experimentally, our method outperforms i.i.d. generation by 15% at SetMNIST reconstruction, by 33% at object detection on CLEVR, generates sets that are 74% closer to the true distribution on a synthetic molecule-like dataset, and generates more valid molecules on QM9.
BibTeX
@inproceedings{vignac2022top,
  author = {Clement Vignac and Pascal Frossard},
  title = {{Top-N: Equivariant Set and Graph Generation without Exchangeability}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=-Gk_IPJWvk},
}

Loading related content...

Figure