CoPHo: Classifier-guided Conditional Topology Generation with Persistent Homology

AI summary

Overview

Research area: Machine learning for graph generation — specifically conditional graph diffusion models, discrete diffusion, classifier-guided sampling, and topological data analysis (persistent homology), applied to synthetic network topology generation.

Technical level: Advanced. The paper combines discrete denoising diffusion, importance sampling, message-passing GNN gradient analysis, and persistent homology filtrations. Readers need working familiarity with graph neural networks and diffusion models.

Scope: CoPHo is a post-training, classifier-guided conditional graph generator that injects persistent-homology-guided discrete node/edge edits into the reverse diffusion process, evaluated on four generic/network benchmarks (Community-small, Enzymes, Planar, Topology-Zoo) plus the QM9 molecular dataset.

What This Paper Is About

Real network topologies are hard to obtain — carrier and enterprise graphs are proprietary, and even research testbeds release only limited or anonymized structure — so researchers need synthetic graphs that match user-specified structural properties. Existing conditional diffusion approaches either bake the condition into the model (requiring a separate conditional score network retrained for every new attribute) or apply classifier gradients at every denoising step, which the authors argue ignores the discrete, edge-sparse nature of real topologies and can cause the generated graph to collapse. CoPHo's goal is to steer an already-trained unconditional graph diffusion model toward specified global and fine-grained properties without retraining the backbone.

Key Contributions

1. Conceptual and methodological (discrete view). The authors model each reverse-time diffusion update as a two-stage Markov chain and show that gradients from a pretrained graph-level property classifier can directly drive discrete node and edge edits, so desired properties can be enforced at every denoising step without retraining the base diffusion model.
2. Technical (persistent homology in the loop). CoPHo builds a decreasing persistent homology filtration over each denoised graph, extracts persistence scores from classifier gradients, and uses them to guide node/edge removals in stages. This structured schedule is designed to counteract the sparse-gradient under-connectivity that arises from message-passing GNNs whose cost scales as O(E).
3. Empirical (benchmarks). Evaluation on Planar, Enzymes, Community-small, and Topology Zoo, plus molecular graphs, is reported as showing better fidelity to target properties while preserving local connectivity and validating cross-domain transferability. (The paper's contribution statement cites degree distributions, clustering coefficients, and diameter specifications; the reported result tables cover density, clustering, assortativity, transitivity, and shortest paths.)

Main Findings

• Single-property conditioning beats baselines. On Community-small and Enzymes (Table 2), CoPHo attains the lowest mean absolute error on clustering, assortativity, and transitivity. On Community-small it also has the lowest density error (1.89, versus 2.07 for Twigs and 2.32 for DiGress). On Enzymes, CoPHo's density error (7.78) is not the lowest — Twigs reports 7.35.
• Multi-property conditioning improves across all tested combinations. Table 3 (Community-Small) reports CoPHo with the lowest MAE for every pairing and the triplet: assortativity 12.4 ± 0.3, transitivity 7.61 ± 0.6, clustering 9.28 ± 0.6 (Pair 1); assortativity 13.8 ± 0.5, clustering 9.65 ± 0.6 (Pair 2); assortativity 11.7 ± 0.5, transitivity 7.30 ± 0.6 (Triplet), versus best baseline Twigs at 16.9 ± 0.4, 8.94 ± 0.5, 10.5 ± 0.3, 17.1 ± 0.3, 10.7 ± 0.6, 15.8 ± 0.6, and 8.77 ± 0.4.
• Fine-grained shortest-path conditioning. Averaged over Topology-Zoo and Planar (Table 4), CoPHo reports MAE 0.43 ± 0.01 with KL 0.02 ± 0.00 for one conditioned path, versus DiGress at 1.45 ± 0.13 and 0.12 ± 0.01. With 5 paths, MAE is 1.33 ± 0.01 (DiGress 1.51 ± 0.03); with 50 paths, 1.37 ± 0.01 (DiGress 1.48 ± 0.01). Overlapping rates are close between the two methods (e.g., 2.11 ± 0.01 versus 2.13 ± 0.01 at 50 paths), and the NSP control reports 100% overlap with zero MAE and zero KL because it overlaps the original graph.
• Case study on shortest-path steering. Guiding the shortest path between nodes #16 and #8 from an original distance of 3 to a target of 5, CoPHo introduced the path #8 → #58 → #56 → #6 → #60 → #16 and removed shorter alternatives.
• Hyperparameters matter. Ablations (Table 5) show T_homo = 5 gives transitivity 7.2, assortativity 10.9, orbit 0.092, while T_homo = 20 degrades assortativity to 14.2 and orbit to 0.112. Timing ablations (Table 6) show ph_timing = 0.6 gives the best transitivity (7.2), with 0.8 worst (8.9 transitivity, 14.5 assortativity). The authors adopt T_homo = 5 and ph_timing = 0.6 to balance compute and accuracy.
• Cross-domain transfer. CoPHo is reported to generalize to QM9 using a fully-connected Graph Transformer backbone with multi-class atom and bond features (Table 8 in the paper).
• Proposal distribution ablation (partial). Table 7 on Enzymes compares a random proposal (density 7.81 ± 0.53, clustering 2.35 ± 0.06, assortativity 1.68 ± 0.04, transitivity 2.04 ± 0.12) against an "EBC" proposal (density 7.59 ± 0.15); the remaining EBC entries are cut off in the provided text.

Methodology in Plain English

Start with an unconditional discrete graph diffusion model (DiGress is used as the backbone) that denoises a graph step by step. At each denoising step, instead of sampling the conditional distribution directly — which is intractable for discrete graph properties — CoPHo uses an importance-sampling scheme:

1. Score the graph. A lightweight pretrained graph-level classifier/regressor predicts the target property (for example the length of the shortest path between two nodes, or the clustering coefficient). Its gradient with respect to nodes and edges gives a per-node and per-edge score indicating which elements push the graph toward or away from the target.
2. Order and prune like a filtration. Nodes and edges are sorted by these gradient scores, and a decreasing filtration removes exactly one edge or node at each homology step, for T_homo steps. This mirrors the way message-passing GNNs only propagate gradients along existing edges, and avoids the collapse that the authors show occurs when continuous perturbations are applied directly to sparse graphs.
3. Weight the candidates. Each intermediate subgraph is evaluated against the target property, and weighted by a term that combines a transition ratio (penalizing large edits away from the unconditional sample, roughly exp(−‖Ĝ − G‖)), a condition-likelihood term, and an indicator function that rejects samples whose properties fall outside an error tolerance ε.
4. Select. The weighted candidates steer the diffusion update, biasing the sample toward the target property while minimally disturbing the original reverse kernel.

Notably, no retraining of the diffusion model is required for a new property — only the classifier/regressor and the guidance schedule change.

Why This Matters

Impact on research. The paper offers a discrete, topology-aware alternative to both condition-embedding diffusion and generic continuous classifier guidance. It is presented as the first work to integrate persistent homology into the denoising and conditioning loop with theoretical justification and a scalable implementation, and it argues why gradient sparsity on sparse graphs causes structural collapse in prior methods.

Real-world applications.

• Generating realistic synthetic topologies for network planning, simulation, and benchmarking when real carrier or enterprise graphs cannot be shared.
• Privacy-preserving release of plausible network graphs that preserve key structural patterns (the paper notes that naive subgraph extraction plus noise, labeled NSP, can still risk privacy breaches).
• "What-if" analysis and protocol/algorithm evaluation — for instance assessing routing resilience under varied connectivity patterns, and reproducing shortest paths among critical node pairs so routing remains accurate.
• Cross-domain molecular graph generation, demonstrated via QM9 transfer.

Industry relevance. Telecom and carrier network operators, network equipment vendors, protocol designers, simulation tooling vendors, and research testbeds stand to benefit from controllable synthetic topology generation. The privacy angle also matters for organizations that want to publish network data without disclosing the real infrastructure. The molecular transfer suggests relevance to cheminformatics and materials discovery, though that is demonstrated only as a validation of transferability.

Future Directions

• Scaling and architecture generalization. The paper states the framework extends to fully-connected GNNs (e.g., graph transformers) and multi-class node/edge-type GNNs, and demonstrates this only via QM9. How well this holds for larger topologies — Topology Zoo spans 9 to 754 nodes — is not resolved.
• Compute–accuracy trade-offs in the homology schedule. The ablations indicate that more homology steps (T_homo = 20) and later PH introduction (ph_timing = 0.8) can degrade certain metrics, so a principled way to choose the schedule per property would be a natural next step.
• Completing and broadening the proposal-distribution ablation. The reported Table 7 comparison is incomplete in the available text, and it currently covers only Enzymes; a fuller study across datasets would clarify when classifier-gradient proposals help most.
• Privacy guarantees. The paper frames shortest-path conditioning partly as a privacy-preserving release mechanism and points out that NSP-style perturbation still risks disclosure, but does not evaluate formal privacy metrics — an open question for practical data sharing.

Target Audience

This paper is most useful for machine learning researchers working on graph generative models, discrete diffusion, or conditional generation; network researchers and engineers who need controllable synthetic topologies; and practitioners in privacy-preserving data release or molecular design who want property-conditioned graph generation without retraining a diffusion model per property. Readers with only introductory ML background will find the persistent homology and importance-sampling sections demanding, while those already familiar with diffusion and GNNs will find the discrete-guidance argument the most valuable part.

Authors’ abstract

The structure of topology underpins much of the research on performance and robustness, yet available topology data are typically scarce, necessitating the generation of synthetic graphs with desired properties for testing or release. Prior diffusion-based approaches either embed conditions into the diffusion model, requiring retraining for each attribute and hindering real-time applicability, or use classifier-based guidance post-training, which does not account for topology scale and practical constraints. In this paper, we show from a discrete perspective that gradients from a pre-trained graph-level classifier can be incorporated into the discrete reverse diffusion posterior to steer generation toward specified structural properties. Based on this insight, we propose Classifier-guided Conditional Topology Generation with Persistent Homology (CoPHo), which builds a persistent homology filtration over intermediate graphs and interprets features as guidance signals that steer generation toward the desired properties at each denoising step. Experiments on four generic/network datasets demonstrate that CoPHo outperforms existing methods at matching target metrics, and we further validate its transferability on the QM9 molecular dataset.