Exact Topological Compliance: Generating Persistence-Equivalent Graphs

AI summary

Overview

Research area: Topological deep learning / graph generation, sitting at the intersection of persistent homology (topological data analysis) and generative modeling for graphs.

Technical level: Advanced. The paper is written for readers comfortable with persistent homology, filtrations, constraint programming, and the graph neural network literature. The core ideas are explained accessibly here, but the paper itself is dense with formal definitions and proofs.

Scope: The paper introduces a framework for generating graphs whose persistence diagrams match a target persistence diagram exactly, via two methods — a local iterative sampler and a global constraint-programming encoding — validated on four graph generation benchmarks (Comm-20, Planar, SBM, and ENZYMES).

What This Paper Is About

Persistent homology summarizes how the topology of a graph evolves under a filtration, producing a multiset of birth–death pairs called a persistence diagram (PD). Existing topology-aware generative models only use soft regularization — for example, a recent approach (Park et al., 2025) augments discrete diffusion with a 1-Wasserstein PD-matching loss — so individual generated graphs may only approximately match the target topology. This paper instead asks whether a generator can produce graphs that realize a target PD exactly, and answers yes with two complementary constructions.

Key Contributions

1. A local iterative sampler (Section 3). The authors give algorithms that build a graph filtration subgraph-by-subgraph, adding vertices, merging components, and adding cycles so that every truncation matches the target PD. They prove soundness and completeness on general, vertex-based, and degree-based filtrations (Theorems 3.1, 3.7, 3.9), and show the sampler always terminates on acyclic targets (Corollaries 3.4, 3.8).

2. An impossibility result for any local approach (Theorem 3.10). The authors prove that no local algorithm can simultaneously (a) generate all PD-equivalent filtrations and (b) make each incremental decision using only the locally available PD truncation. Any local method must trade off between sample diversity and reaching infeasible states.

3. A global constraint-programming formulation (Section 4). Generation is recast as a constraint satisfaction problem over Boolean and integer variables, applicable to any vertex-based, permutation-equivariant filtration scheme. Theorem 4.2 establishes soundness, completeness, and — for the degree filtration — degree minimality, meaning removing any one of the six constraint families admits assignments that are not PD-compliant.

4. Empirical validation (Section 5). On Comm-20, Planar, SBM, and ENZYMES, both the local and global methods realize the target degree-based PD exactly, while neural diffusion baselines with PD-conditioning regularizers retain a structural approximation gap that does not close with additional training.

Main Findings

• Soft conditioning has no guarantees: Existing topology-aware generators violate soundness by construction, since their regularizers only nudge the learned distribution toward topological plausibility rather than enforcing a target number of cycles or components.

• Persistent homology is not a complete descriptor: Figure 1 shows two non-isomorphic graphs with identical degree-based persistence, so a PD identifies a whole class of compatible graphs and conditioning on a PD amounts to sampling from that class.

• The local sampler is provably correct but can get stuck: Algorithm 1 (general filtrations) is sound and complete whenever it terminates, but it can run out of cycles to add during the cycle-addition stage. Example 3.2 demonstrates this failure directly on two graphs shown in Figure 2.

• A cycle-capacity criterion determines local feasibility: The authors define the cycle capacity of a graph as the sum, over its components, of |V(A)|(|V(A)|−1)/2 − |E(A)|. If the number of cycle births at a stage is bounded by this quantity, the cycle-addition step succeeds (Proposition 3.3).

• Acyclic targets are always achievable locally: Corollary 3.4 (general filtrations) and Corollary 3.8 (vertex-based filtrations) state the algorithms always terminate when the 1-dimensional persistence diagram is empty.

• Local approaches are fundamentally limited: Theorem 3.10 proves no algorithm can be both perfectly complete and purely local for general, vertex-based, or degree-based filtrations. The obstruction is that a PD-equivalent truncation need not extend to any full PD-equivalent filtration.

• The global encoding is exactly right in three senses: Theorem 4.2 proves soundness (every solver assignment yields a valid PD-compliant graph), completeness (every PD-compliant graph has at least one solver assignment, so every graph in the same isomorphism class is reachable), and minimality for the degree filtration.

• Six constraint families are necessary: The encoding uses vertex alignment (C₁), slot partitioning (C₂), edge-slot consistency (C₃), slot connectivity via spanning trees (C₄), Euler characteristic matching (C₅), and birth-time survival (C₆). Appendix G provides 6 counterexample assignments showing each family is needed.

• The framework extends beyond degree: The authors give concrete encodings for degree, triangle counts, k-clique counts, clustering coefficient, average neighbor degree, closeness centrality, Katz, and PageRank — only the alignment constraint C₁ changes between them.

• Spanning trees are an efficiency device: C₄ enforces connectivity via parent pointers and depth variables rooted at a canonical root, which the authors note is linear-time to check versus roughly quadratic for naive all-pairs connectivity.

Methodology in Plain English

The authors fix the standard degree-based filtration used throughout the GNN literature, where a vertex enters the filtration at a time equal to its degree. Given a target persistence diagram, they want to build a graph that reproduces it exactly.

Their first approach is local and incremental. Starting from the empty graph, they walk through filtration stages: at each stage they add the vertices prescribed by the 0-dimensional diagram, then connect components so that the prescribed merging time is realized, then add edges inside components to create independent cycles at the prescribed birth times. Component merging must be processed in random order, otherwise some valid targets become unreachable. They prove this sampler generates every valid answer whenever it finishes, and they characterize when it can get stuck (the cycle-addition stage running out of available non-edges).

Because local decisions can paint the method into a corner, the second approach is global. Instead of making choices one stage at a time, they write the entire graph down as a set of unknown 0/1 variables — an adjacency matrix, plus auxiliary slot variables tracking which vertices are connected to which at every stage, parent pointers encoding spanning trees, and per-vertex depth labels to rule out cycles. Then they write every property that a PD-compliant graph must satisfy as a logical or arithmetic constraint: prescribed degrees, one-slot-per-vertex partitioning, no cross-slot edges, connectedness of each slot, an Euler-characteristic identity relating edges, vertices, and components to cycle counts, and a survival count matching how many components born at each time remain alive. A modern constraint-programming solver then finds satisfying assignments, and each solution is a graph with exactly the target persistence. They prove this encoding captures exactly the right set of graphs, and that for degree filtrations you cannot drop any of the six constraint families. To show generality, they swap out only the alignment constraint to handle triangle counts, clustering coefficients, average neighbor degree, closeness, Katz, and PageRank.

Experiments compare both methods against PD-conditioned diffusion baselines on four benchmarks. Note that the provided content does not include the tables of numerical results (Table 2, Table 3) or dataset sizes, so specific figures beyond the qualitative outcome — exact realization of the target PD by both methods, persistent approximation gap for the baselines — are not reported here.

Why This Matters

The paper shifts topology-conditioned generation from a soft heuristic to a problem with provable guarantees, and it clarifies precisely what a persistence diagram does and does not pin down about a graph.

Impact on research:

• Provides controlled, label-noise-free datasets of graphs sharing identical persistence but differing combinatorially, useful for testing whether a model actually exploits prescribed topology or relies on unrelated statistics.
• Enables construction of counterexamples to conjectures about what properties persistence determines — something approximate generation cannot do at all.
• Establishes a formal soundness/completeness benchmark against which soft-conditioned models can be measured.

Real-world applications (as identified in the paper):

• Molecular generation, where ring counts must be exact (Ritchie and Macdonald, 2009).
• Sensor networks, where coverage holes are the topological features of interest (De Silva and Ghrist, 2007).
• Brain network analysis, where information flow depends on topological structure.
• Transportation, trade, and infrastructure networks, where structural risk is governed by components, cycles, and higher-order voids.

Industry relevance: Any pipeline that must hit an exact count of topological features — chemical design, network planning, medical imaging — benefits from hard guarantees rather than a regularizer that merely biases outputs in the right direction. The released code (at https://github.com/Aalto-QuML/ExactCompliance) makes both methods directly usable.

Future Directions

• Relaxing strictness in practice. The authors note that once strict compliance is established, it can be relaxed for applications, but the paper does not specify a principled relaxation scheme.
• Scaling the global solver. Appendix I provides a complexity and scaling analysis for the degree case only; how the encoding behaves for other filtration schemes, larger graphs, or different solver backends remains open.
• Balancing diversity against feasibility in the local method. Theorem 3.10 rules out a perfect local algorithm, but the paper does not characterize the optimal tradeoff frontier, nor how the local and global methods compare on sample diversity.
• Broadening to non-vertex-based filtrations. The global framework assumes vertex-based, permutation-equivariant, integer-valued filtrations; the introduction mentions extensions where they apply but the paper's primary treatment is degree-based, with edge-based filtrations addressed only as a remark.

Target Audience

Researchers and graduate students in topological data analysis, graph generative modeling, and geometric deep learning who work on topology-aware neural networks; practitioners who need generated graphs with exact topological properties; and theoretically inclined readers interested in constraint-programming formulations of combinatorial generation problems. Readers without background in persistent homology or constraint programming will need to consult the cited background references.

Authors’ abstract

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.