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.
Figures & tables
Table 1: Overview of the core contributions in our paper.
Figure 1: Two non-isomorphic graphs with identical degree-based persistence. Vertex color encodes degree; edges inherit the color of their max-degree endpoint.
Figure 2: An example of how Algorithm 1 can run out of cycles in the cycle adding stage.
Comm-20
Planar
SBM
ENZYMES
Local (Alg. 3 )
Success rate (%) ↑
100.0
100.0
15.0
99.1
Wall-clock per target (s) ↓
0.17
5.88
1465.0
6.94
Attempts to first success ↓
49.6
137.5
4583.5
431.5
Global (CP, Sec. 4 )
Success rate (%) ↑
100.0
100.0
82.5
100.0
Wall-clock per target (s) ↓
0.30
16.35
654.8
6.85
Table 2: Local degree-filtration sampler vs. the global CP solver. Wall-clock means charge the full attempt or time budget on failed runs.
Figure 3: Qualitative example on an ENZYMES test graph. Node colour encodes degree. CP matches (n,∣E∣,β0,β1) exactly, while neural variants add excess cycles. More in Appendix H.6 .
Comm-20
Planar
SBM
ENZ.
CP
Wˉ1↓
0.00
0.00
0.00
0.00
Time (s) ↓
0.30
16.35
654.8
6.85
Train (h) ↓
0
0
0
0
ConStr. +TAGG
Wˉ1↓
9.35
43.23
434.48
17.35
Time (s) ↓
0.88
4.73
17.11
4.92
Train (h) ↓
9.4
24.3
59.8
61.6
Table 3: Global (CP) vs. TAGG-augmented neural baselines on degree-PD Wˉ1 ( 0 = exact match).
Table 5: Full local/global comparison across the three filtration regimes. Random and Vertex target their respective filtrations; Degree (Alg. 3 ) and CP both target the canonical degree filtration. Wall-clock means include the full 20,000 -attempt or 1,800 s budget on failed runs; attempt statistics are over successful runs only. CP performs a single solver call per target.
Comm-20
Planar
SBM
ENZYMES
Global (CP)
Wˉ1↓
0.000
0.000
0.000
0.000
Time/graph (s) ↓
0.30
16.35
654.8
6.85
Train (h) ↓
0
0
0
0
ConStruct+TAGG
Wˉ1↓
9.35 ± 0.97
43.23 ± 0.56
434.48 ± 17.54
17.35 ± 0.24
Time/graph (s) ↓
0.88 ± 0.01
4.73 ± 0.09
17.11 ± 0.09
4.92 ± 0.46
Train (h) ↓
9.4
24.3
59.8
61.6
Appendix
Table 6: Full version of Table 3 : Global (CP) vs. TAGG-augmented neural baselines, with standard deviations over 5 random seeds. CP is deterministic.
SBM , Wˉ1↓
All 40 targets
Same 33 targets (CP-solved)
ConStruct+TAGG
434.48
408.95
DiGress+TAGG
464.99
454.49
CP (ours)
0.00 ( 33/40 solved)
0.00
Appendix
Table 7: Handling of failed CP runs on SBM . CP solves 33/40 targets within the 1,800 s budget (the coverage reported in Table 2 ); its Wˉ1 in Table 3 is over these solved targets. Restricting the neural baselines to the same 33 targets gives an equal comparison.
Figure 4: Two qualitative examples on ENZYMES test graphs ( enzymes_87 , top; enzymes_93 , bottom). Left to right: reference, Global (CP), ConStruct+TAGG , DiGress+TAGG . Node colour encodes degree. CP matches (n,∣E∣,β0,β1) exactly on both graphs; neural variants drift in edge count and cycle count.
Generating signals on graphs requires permutation-equivariant models that exhibit stability with respect to relative structural perturbations. While recent graph-aware Schrödinger bridge models incorporate topology information directly into their reference dynamics, it is unclear how perturbations of the graph propagate through these dynamics and affect the resulting generated distributions. In this paper, we analyze the structural stability of graph-aware continuous-time generative models whose drift combines a graph filter with a learned graph neural network. We derive explicit Wasserstein stability bounds that quantify the effect of relative graph perturbations on the generated distributions. Motivated by these bounds, we introduce a principled framework for designing stable graph filters that preserve the smoothing behavior of graph heat diffusion, while boosting structural stability. Experiments on synthetic and fMRI signals show our stable filters enhance structural robustness while matching or exceeding the generative quality of the heat equation baseline.
Current topology aware diffusion models face an architectural mismatch by using Gaussian noise for corruption while recovering structural features through conditional side channels To fix this we introduce PFlow T a generative model that bases its forward process entirely on persistent homology In PFlow T time measures the destruction of H1 topological features like holes rather than Gaussian noise injection This forward process eliminates features based on their persistence The reverse network then directly inverts this structured corruption to predict the clean state in one step Tests on MNIST digits zero one and eight show PFlow T significantly outperforms a baseline model in generating requested Betti numbers and handling out of distribution tasks PFlow T is the first generative architecture using persistent homology for the forward process although we note it is currently limited to low resolution pixel space proxies
Generation of graphs constrained by a specified graph edit distance from a source graph is important in applications such as cheminformatics, network anomaly synthesis, and structured data augmentation. Despite the growing demand for such constrained generative models in areas including molecule design and network perturbation analysis, the neural architectures required to provably generate graphs within a bounded graph edit distance remain largely unexplored. In addition, existing graph generative models are predominantly data-driven and depend heavily on the availability and quality of training data, which may result in generated graphs that do not satisfy the desired edit distance constraints. In this paper, we address these challenges by theoretically characterizing ReLU neural networks capable of generating graphs within a prescribed graph edit distance from a given graph. In particular, we show the existence of constant depth and O(n^2 d) size ReLU networks that deterministically generate graphs within edit distance d from a given input graph with n vertices, eliminating reliance on training data while guaranteeing validity of the generated graphs. Experimental evaluations demonstrate that the proposed network successfully generates valid graphs for instances with up to 1400 vertices and edit distance bounds up to 140, whereas baseline generative models fail to generate graphs with the desired edit distance. These results provide a theoretical foundation for constructing compact generative models with guaranteed validity.
Mamoona Ghafoor, Tatsuya Akutsu
Bioinformatics Center, Institute for Chemical Research, Department of Intelligence Sciences and Technology, Kyoto University, Uji 611-0011, Japan