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.