Exact Topological Compliance: Generating Graphs with Persistence Diagrams Matching a Target Exactly

Forum topic · 小凯 · 2026-10-15

Summary

This paper (arXiv:2610.18856) by Mattie Ji, Indradyumun Roy, and Vikas Garg addresses exact topology-aware graph generation using persistent homology. Persistent homology summarizes a graph's topological evolution as a persistence diagram (PD), but existing topology-aware generative models use soft regularization and only approximately match a target PD. The authors initiate a principled study of generating graphs that realize a target PD exactly. They propose two approaches guided by the implicit local and global constraints a target PD imposes. A local method iteratively constructs degree-based PD-equivalent graphs with proofs that every output realizes the target PD and that every degree-based PD-equivalent graph is reachable—though local generation necessarily trades off sample diversity against reaching infeasible states. They then recast generation as a global constraint-satisfaction problem with a complete encoding solvable by modern constraint programming solvers, applicable to any vertex-based permutation-equivariant filtration and minimal under degree filtrations. Experiments on four standard graph generation benchmarks confirm both methods realize the target PD exactly.

Overview

Field: Machine Learning Authors: Mattie Ji, Indradyumun Roy, Vikas Garg arXiv: 2610.18856

Abstract (translated from Chinese summary)

Persistent homology summarizes the topological evolution of a graph as a persistence diagram (PD). Generating graphs whose topology matches a target descriptor is increasingly important, yet existing topology-aware generative models rely on soft regularization, so the produced graphs' PDs may only be approximately similar. This work initiates a principled investigation of the generation problem: exactly producing graphs that realize a target PD.

The authors propose two approaches, guided by the implicit local and global constraints that a target PD imposes:

Local approach: Iteratively builds degree-based PD-equivalent graphs. They prove that every output realizes the target PD, and that every degree-based PD-equivalent graph is reachable. However, local generation necessarily involves a trade-off between sample diversity and reaching infeasible states.
Global approach: Recasts generation as a global constraint-satisfaction problem with a complete encoding solvable by modern constraint programming solvers. This applies to any vertex-based permutation-equivariant filtration scheme, and is minimal under degree filtrations.

Experiments on four standard graph generation benchmarks confirm that both methods exactly realize the target PD.

Original Abstract (excerpt)

> 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 bet...

---

Paper link: https://arxiv.org/abs/2610.18856

*Auto-collected on 2026-10-15*