ProtoGuide improves graph generation accuracy using prototype-driven guidance
ProtoGuide: Prototype-Driven Guidance for Class-Conditional Graph Generation
Machine LearningArtificial Intelligence
Summary
Generating graphs with specific characteristics is hard because the usual ways of guiding the process don’t work well with discrete graph data. The authors developed ProtoGuide, which gently adjusts graph creation step-by-step by comparing parts of the graph to example patterns. This method can be applied to different existing graph generation models without retraining them and significantly improves their ability to create graphs matching desired classes. It works best where current methods struggle and keeps the generated graphs diverse and accurate.
What this means in practice
- •For machine learning engineers: Enhance class-conditioned graph generation models by adding post-training guidance without retraining to improve accuracy on target graph types.
- •For network analysis teams: Generate realistic class-specific networks for testing and simulation by directing graph generators toward known prototype structures.
Authors
Salvatore Romano, Marco Grassia, Pietro Liò, Giuseppe Mangioni
Abstract
Discrete diffusion models are a prominent family for graph generation, but standard class-conditional mechanisms embed the class signal in the denoiser during training, tying the conditioning mechanism to the trained model. Classifier guidance avoids this coupling in continuous domains by steering a frozen model with a classifier's gradient, but discrete graph diffusion samples discrete edge states, so gradients cannot propagate through the sampled graph. We introduce ProtoGuide, a post-hoc, backbone-agnostic framework that recovers an analogous mechanism. At each reverse step the denoiser's per-edge output is relaxed into a differentiable soft adjacency, embedded by a frozen Siamese graph neural network, and scored against a target-class prototype and its nearest competitor; the resulting per-edge gradient, damped by a cosine schedule, is injected back into the denoiser output. All components stay frozen, so guidance is retargeted by supplying a different prototype. On five classes of real-world networks and two architecturally different backbones, EDGE and DiGress, ProtoGuide raises macro classification accuracy from 50.7% to 73.5% and from 73.6% to 83.8%, and outperforms DiGress's built-in conditional training under our configuration. Gains are largest where the unguided models are weakest, and are not uniform across classes. Per-graph coverage remains high in most settings, while distributional effects are class-dependent. A Best-of-N selection baseline matches this accuracy given enough oversampling, but at a substantial cost in graph diversity. An independently initialized classifier, a directionality test, and a few-shot analysis support target-directed steering and robustness to very small support sets.