# Exact Topological Compliance: Generating Persistence-Equivalent Graphs

arXiv: https://arxiv.org/abs/2610.18856 · HTML: https://mlsanity.com/paper/2610.18856/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 67 references that are in the map.
- First posted on arXiv 13 Oct 2026.

## Builds on (most cited first, 30 of 33)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Hierarchical Generation of Molecular Graphs using Structural Motifs](https://mlsanity.com/paper/2002.03230/) (2020)
- [A roadmap for the computation of persistent homology](https://mlsanity.com/paper/1506.08903/) (2015)
- [PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures](https://mlsanity.com/paper/1904.09378/) (2019)
- [Deep Learning with Topological Signatures](https://mlsanity.com/paper/1707.04041/) (2017)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [Topological Graph Neural Networks](https://mlsanity.com/paper/2102.07835/) (2021)
- [Graph Filtration Learning](https://mlsanity.com/paper/1905.10996/) (2019)
- [Position: Topological Deep Learning is the New Frontier for Relational Learning](https://mlsanity.com/paper/2402.08871/) (2024)
- [Constructions in combinatorics via neural networks](https://mlsanity.com/paper/2104.14516/) (2021)
- [Going beyond persistent homology using persistent homology](https://mlsanity.com/paper/2311.06152/) (2023)
- [Curvature Filtrations for Graph Generative Model Evaluation](https://mlsanity.com/paper/2301.12906/) (2023)
- [On the Expressivity of Persistent Homology in Graph Learning](https://mlsanity.com/paper/2302.09826/) (2023)
- [Generative Modelling of Structurally Constrained Graphs](https://mlsanity.com/paper/2406.17341/) (2024)
- [Neural Approximation of Graph Topological Features](https://mlsanity.com/paper/2201.12032/) (2022)
- [Topological Neural Networks go Persistent, Equivariant, and Continuous](https://mlsanity.com/paper/2406.03164/) (2024)
- [Cliques and Cavities in the Human Connectome](https://mlsanity.com/paper/1608.03520/) (2016)
- [Graphcode: Learning from multiparameter persistent homology using graph neural networks](https://mlsanity.com/paper/2405.14302/) (2024)
- [A Riemannian Framework for Statistical Analysis of Topological Persistence Diagrams](https://mlsanity.com/paper/1605.08912/) (2016)
- [Reconstructing Embedded Graphs from Persistence Diagrams](https://mlsanity.com/paper/1912.08913/) (2019)
- [TopoCL: Topological Contrastive Learning for Medical Imaging](https://mlsanity.com/paper/2603.14647/) (2026)
- [Statistical learning on measures: an application to persistence diagrams](https://mlsanity.com/paper/2303.08456/) (2023)
- [On topological descriptors for graph products](https://mlsanity.com/paper/2511.08846/) (2025)

## Abstract (arXiv)

Persistent homology summarizes the topological evolution of a graph as persistence diagrams (PDs). Generating graphs whose topology matches a target descriptor is increasingly important, yet existing topology-aware generative models rely on soft regularization, producing graphs whose PDs may only be approximately similar. We initiate a principled investigation of the generation problem: produce graphs that realize a target PD exactly. We propose two approaches guided by the implicit local and global constraints a target PD imposes. The local approach builds degree-based PD-equivalent graphs iteratively, and we prove that every output realizes the target PD and that every degree-based PD-equivalent graph is reachable. However, as shown thereafter, local generation necessarily trades off between sample diversity and reaching infeasible states. We therefore recast generation as a global constraint satisfaction problem with a complete encoding solvable by modern constraint programming solvers. This is applicable to any vertex-based permutation equivariant filtration scheme and is minimal under the degree filtration. Experiments on four standard graph generation benchmarks confirm that both methods realize the target PD exactly. Together, our methods provide a principled treatment of strict topology-compliant graph generation. Code is available at https://github.com/Aalto-QuML/ExactCompliance.