Top-N: Equivariant set and graph generation without exchangeability

Clément Vignac, Pascal Frossard

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.

Introduction

Generating sets and graphs, such as molecules or point clouds, presents a unique challenge in machine learning due to their unordered nature. Traditional "one-shot" generators typically rely on sampling random noise and transforming it into an "exchangeable" distribution, where the likelihood of any permutation of the output elements is identical. While this approach respects the inherent symmetries of the data, this paper demonstrates that forcing exchangeability through stochastic i.i.d. sampling makes models significantly harder to train. Specifically, in Variational Autoencoders (VAEs), this method optimizes only a proxy to the Evidence Lower Bound (ELBO), leading to suboptimal data fitting and training instability.

Methods

The authors propose a shift from stochastic exchangeability to deterministic equivariance. They decompose the set generation process into two primary stages: Creation and Update.

Architectural overview of set generation comparing different input dependencies.

As shown in the architectural overview (Figure 2), the process begins with a latent vector $z$ and a set size $n$, which are used to create an initial set of points $X^0$. These points are then refined through an equivariant update function $h$ (e.g., a Transformer or GNN) to produce the final set $X$, which is eventually treated as a multi-set $\mathcal{X}$.

The core innovation lies in the Top-n creation mechanism (referred to as "First-n" in Figure 3). Unlike standard methods that reshape an MLP output or sample rows independently from a normal distribution, Top-n creation utilizes a trainable reference set of "anchor" points.

Comparison of set creation mechanisms: MLP, Independent sampling, and the proposed First-n (Top-n) approach.

The selection process works as follows:

  1. Selection: Given a latent vector $z$, the model calculates the cosine similarity between $z$ and learned "angles" associated with each point in the reference set.
  2. Top-n Selection: It selects the $n$ points with the highest similarity scores.
  3. Modulation: To ensure the process is differentiable, a "FiLM" layer modulates the selected points based on their similarity scores, allowing gradients to flow back and inform which reference points are most relevant for specific outputs.

This deterministic selection ensures that the generator remains permutation equivariant without the training overhead of random sampling.

Experimental Evaluation

The Top-n method was benchmarked against standard i.i.d. sampling and MLP baselines across four diverse tasks:

  • SetMNIST: In reconstructing 2D point clouds of digits, Top-n improved accuracy by 15% over i.i.d. sampling.
  • CLEVR Object Detection: For predicting object properties in complex scenes, Top-n achieved an Average Precision (AP) of 86.4, a 33% improvement over the 60.5 AP of the i.i.d. baseline.
  • Synthetic 3D Molecules: Top-n generated sets 74% closer to the ground truth distribution, demonstrating superior handling of physical constraints.
  • QM9 Chemical Database: The method produced 56.2% unique and valid molecules, nearly doubling the 29.9% achieved by i.i.d. sampling.

Beyond performance metrics, Top-n demonstrated faster convergence and reached lower loss values, confirming the theoretical advantage of avoiding the "proxy" ELBO problem.

Conclusion

The findings suggest that exchangeability is a self-imposed constraint that often hinders the training of set generators. By replacing random sampling with a deterministic, learned selection mechanism like Top-n, models can achieve better performance and stability.

However, some limitations remain. The size of the reference set is a hyperparameter that requires tuning, and the method's "hard selection" logic is currently incompatible with Normalizing Flows. Future research may explore dynamic scaling of the reference set to handle even larger and more complex data structures.

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 = {Clément 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},
}
Figure