Equivariant Normalizing Flows for Point Processes and Sets

Marin Bilos, Stephan Günnemann

Abstract

Modeling sets is an important problem in machine learning since this type of data can be found in many domains. A promising approach defines a family of permutation invariant densities with continuous normalizing flows. This allows us to maximize the likelihood directly and sample new realizations with ease. In this work, we demonstrate how calculating the trace, a crucial step in this method, raises issues that occur both during training and inference, limiting its practicality. We propose an alternative way of defining permutation equivariant transformations that give closed form trace. This leads not only to improvements while training, but also to better final performance. We demonstrate the benefits of our approach on point processes and general set modeling.

Introduction

Many real-world datasets are "exchangeable," meaning the order of the elements doesn't matter—think of a collection of stars in a galaxy, items in a shopping cart, or GPS check-ins in a city. Modeling the probability density of these sets is challenging because traditional machine learning models often assume a specific order or treat points as independent.

Normalizing Flows are a powerful tool for density estimation, but applying them to sets requires the model to be permutation invariant. While Continuous Normalizing Flows (CNFs) can handle this using equivariant layers, they hit a major bottleneck: they require calculating the trace of the Jacobian. Usually, researchers use "stochastic estimators" to guess this trace, which introduces noise that makes training unstable and inference slow. The alternative—calculating the exact trace—is computationally ruinous for large sets ($O(n^2)$ complexity).

Methodology: The Decoupling Strategy

The authors propose a method to get the best of both worlds: the expressiveness of CNFs and the efficiency of an exact trace. Their core contribution is a decoupling strategy for permutation equivariant transformations that achieves an exact trace calculation in $O(nd)$ time (linear with respect to the number of points $n$ and dimensions $d$), whereas standard exact methods are $O(n^2d^2)$.

The proposed decoupling strategy separates transformations into per-dimension, within-point, and between-points interactions to ensure a structured Jacobian with a tractable trace.

This is achieved through three specific interaction types:

  1. Interactions Between Points: Aggregation functions (like sums or means) allow points to communicate. By subtracting the current point's contribution from the global sum, they create a "between-points" transformation with a zero-trace Jacobian (volume-preserving).
  2. Interactions Within Points: To model dependencies between dimensions of a single point, masked neural networks (like MADE) ensure that one dimension only depends on previous ones, keeping the diagonal of the Jacobian zero.
  3. Per-Dimension Transformation: A simple element-wise transformation is added. Because the previous two steps have zero diagonals in their Jacobians, the trace of the entire system becomes a simple sum of these per-dimension derivatives.

Key Results and Insights

By providing an exact trace, the ODE solver used in the CNF requires significantly fewer steps to converge, making the model much more efficient. The results show that this decoupled structure is still "universal" enough to match or beat unrestricted models.

Comparison of relative log-likelihood across various datasets. The exact trace methods (attention and deep set) consistently outperform the approximate stochastic estimators.
  • Stability and Speed: The proposed CNF required fewer ODE solver evaluations (NFE) than models using stochastic trace estimation. In some cases, inference was an order of magnitude faster.
  • Superior Density Estimation: On point process datasets (like Matérn and Thomas), the model consistently achieved higher log-likelihoods than baselines like Inhomogeneous Poisson Processes (IHP) and Autoregressive models.
  • Qualitative Success: The model successfully generated realistic-looking point clouds and MNIST-style digits, proving it captured the underlying spatial distributions and interactions between points.

Conclusion

This paper introduces a scalable way to model sets using CNFs by cleverly decoupling how points interact. By achieving a closed-form trace calculation in linear time, the authors enable faster, more stable training and superior performance on complex point processes. While the method still relies on ODE solvers, it represents a significant step forward in making permutation-equivariant generative models practical for large-scale data.

Summary updated

Abstract

Modeling sets is an important problem in machine learning since this type of data can be found in many domains. A promising approach defines a family of permutation invariant densities with continuous normalizing flows. This allows us to maximize the likelihood directly and sample new realizations with ease. In this work, we demonstrate how calculating the trace, a crucial step in this method, raises issues that occur both during training and inference, limiting its practicality. We propose an alternative way of defining permutation equivariant transformations that give closed form trace. This leads not only to improvements while training, but also to better final performance. We demonstrate the benefits of our approach on point processes and general set modeling.
BibTeX
@inproceedings{bilos2021equivariant,
  author = {Marin Bilos and Stephan Günnemann},
  title = {{Equivariant Normalizing Flows for Point Processes and Sets}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=_vR9tq485H},
}
Figure