Graph Generation: Classical, Neural, and Metrics in TGraphX
Graph generation is the task of producing new graphs that share statistical properties with a target distribution. It sits at the intersection of graph theory and deep generative modeling, and it spans a wide range of applications: generating novel drug-like molecules, simulating realistic social networks for epidemiological modeling, augmenting graph datasets for training GNNs, and constructing controlled synthetic benchmarks with known topological properties.
TGraphX provides both classical and neural graph generation approaches, along with a set of evaluation metrics — validity, uniqueness, novelty, and maximum mean discrepancy — that characterize the quality of generated graphs. Classical generation is labeled Beta; neural generation is Experimental. This article explains both families, their metrics, and how to use them practically.
The Two Families of Graph Generation
Graph generation methods divide into two broad families based on whether they require training data:
Classical generators use parametric statistical models grounded in random graph theory. Erdős-Rényi (ER), Barabási-Albert (BA), Watts-Strogatz (WS), and Stochastic Block Model (SBM) are the most widely used. They are deterministic given a random seed, require no training, and generate graphs with known mathematical properties. They are the right tool for constructing controlled benchmarks, stress-testing GNN implementations, and generating synthetic data when real-world graphs are unavailable.
Neural generators learn a distribution over graphs from a training set and generate new samples from that distribution. Variational Graph Autoencoders (VGAE) represent the most established neural approach for small-to-medium graphs. These models require training data and training time, but they can in principle generate graphs that match the statistical properties of complex real-world distributions — something classical generators cannot do when the target distribution is multimodal or has complex higher-order structure.
TGraphX marks classical generation as Beta and neural generation as Experimental. Neither should be used for safety-critical applications (e.g., drug discovery) without additional domain-specific validation.
Prerequisites
This article assumes familiarity with:
- Basic graph concepts (nodes, edges, adjacency)
- PyTorch tensors and basic Python
- The concept of generative models at a high level
For TGraphX background and tensor-valued graph creation, see the graph generation with tensor-valued node features tutorial. For graph mining operations that work downstream of generation, see the graph mining guide.
Install TGraphX:
pip install tgraphx
Classical Graph Generation
Erdős-Rényi Graphs
ER graphs place an edge between each pair of nodes independently with probability p. They are the simplest random graph model. For a connected graph, p must exceed approximately ln(N) / N.
import torch
from tgraphx.generation import FeatureAwareERGraph
# Single ER graph with vector node features
g = FeatureAwareERGraph(
n=50, # number of nodes
p=0.12, # edge probability
node_feature_dim=16, # feature dimensionality
node_feature_shape=(16,), # shape for vector features
seed=42,
)
print(g.num_nodes) # 50
print(g.node_features.shape) # [50, 16]
print(g.edge_index.shape) # [2, ~50*49*0.12 ≈ 294 edges]
ER graphs are useful for stress-testing GNNs with known properties: average degree (N-1)*p, no community structure, Poisson degree distribution.
Barabási-Albert Preferential Attachment
BA graphs model scale-free networks where new nodes preferentially attach to existing high-degree nodes. The parameter m controls how many edges each new node creates, producing a power-law degree distribution:
from tgraphx.generation import run_graph_generation
result = run_graph_generation(
method="barabasi_albert",
num_graphs=30,
num_nodes=60,
m=3, # edges added per new node
node_feature_dim=16,
seed=42,
)
print(f"Generated {len(result.graphs)} graphs")
print(f"Mean edges per graph: {sum(g.edge_index.shape[1] for g in result.graphs) / len(result.graphs):.0f}")
BA graphs are appropriate when simulating scale-free network properties (e.g., internet topology, citation networks, protein interaction networks). The largest hub nodes have degree proportional to N.
Watts-Strogatz Small-World Graphs
WS graphs start from a ring lattice and rewire edges with probability p, producing graphs with high clustering and short path lengths — the "small-world" property:
result_ws = run_graph_generation(
method="watts_strogatz",
num_graphs=20,
num_nodes=60,
k=6, # each node connected to k nearest in ring
p=0.1, # rewiring probability
node_feature_dim=8,
seed=42,
)
WS graphs are useful when you need synthetic graphs with realistic clustering coefficients, as seen in social and biological networks.
Stochastic Block Model
SBM generates graphs with planted community structure. Nodes within the same block connect with probability p_in, and nodes in different blocks connect with probability p_out. The signal-to-noise ratio p_in / p_out controls how easy it is to detect the community structure:
result_sbm = run_graph_generation(
method="stochastic_block_model",
num_graphs=15,
num_nodes=90,
num_blocks=3, # number of communities
p_in=0.35, # within-block edge probability
p_out=0.04, # between-block edge probability
node_feature_dim=8,
seed=42,
)
SBM is the standard tool for generating benchmark graphs for community detection and clustering algorithms. At p_in = p_out, the model degenerates to an ER graph with no community structure.
Generating Graphs with Tensor Node Features
TGraphX's generation utilities support image-like [C, H, W] or volumetric [C, D, H, W] node features, enabling generation of synthetic datasets for testing tensor-aware GNN layers:
from tgraphx.generation import FeatureAwareBAGraph
# BA graph with image-like [C, H, W] node features
g_spatial = FeatureAwareBAGraph(
n=40,
m=2,
node_feature_shape=(3, 8, 8), # [C, H, W] per node
seed=42,
)
print(g_spatial.node_features.shape) # [40, 3, 8, 8]
# Use directly with spatial GNN layers
from tgraphx.layers.sage import TensorGraphSAGELayer
layer = TensorGraphSAGELayer(in_channels=3, out_channels=8, spatial_rank=2)
out = layer(g_spatial.node_features, g_spatial.edge_index)
print(out.shape) # [40, 8, 8, 8]
Neural Graph Generation with VGAE
The VGAE generator trains a variational autoencoder on a collection of training graphs and samples new graphs from the learned latent distribution. It operates on the adjacency matrix, modeling edge existence as a Bernoulli random variable conditioned on a latent node embedding:
from tgraphx.generation.neural import VGAEGenerator, VGAEConfig
config = VGAEConfig(
in_dim=16,
hidden_dim=64,
latent_dim=32,
num_epochs=80,
lr=1e-3,
seed=42,
)
# Generate training graphs using classical methods
training_result = run_graph_generation(
method="barabasi_albert",
num_graphs=200,
num_nodes=25,
m=2,
node_feature_dim=16,
seed=0,
)
vgae = VGAEGenerator(config)
vgae.fit(training_result.graphs)
# Sample new graphs
new_graphs = vgae.generate(num_graphs=20)
print(f"Generated {len(new_graphs)} new graphs")
for g in new_graphs[:3]:
print(f" nodes={g.num_nodes}, edges={g.edge_index.shape[1]}")
The VGAE generator is Experimental. It does not guarantee any structural validity constraints. For molecular generation where chemical validity (valence rules, connectivity) is required, specialized molecular generation frameworks are more appropriate.
Generation Metrics
TGraphX provides four standard metrics for evaluating generation quality. Each captures a different aspect of whether the generated graphs are good:
from tgraphx.generation import (
validity_score,
uniqueness_score,
novelty_score,
graph_mmd,
)
# Validity: fraction of generated graphs satisfying structural constraints
val = validity_score(new_graphs, require_connected=True)
# Uniqueness: fraction of generated graphs that are distinct from each other
uniq = uniqueness_score(new_graphs)
# Novelty: fraction of generated graphs not seen in the training set
nov = novelty_score(new_graphs, training_result.graphs)
# Graph MMD: distribution-level similarity (lower = closer to training distribution)
mmd = graph_mmd(training_result.graphs, new_graphs, kernel="degree")
print(f"Validity: {val:.3f}")
print(f"Uniqueness: {uniq:.3f}")
print(f"Novelty: {nov:.3f}")
print(f"Graph MMD: {mmd:.4f}")
Understanding what each metric tells you and what it cannot:
| Metric | What it measures | Higher is better? | Can be gamed by |
|---|---|---|---|
| Validity | Structural constraint satisfaction | Yes | Generating only trivially simple graphs |
| Uniqueness | Diversity among generated graphs | Yes | Noisy random generation |
| Novelty | Non-memorization of training data | Yes | Generating completely random graphs |
| Graph MMD | Statistical closeness to training distribution | No (lower = better) | Copying training data exactly |
A good generator balances all four. High uniqueness with low novelty means the model is generating diverse graphs but memorizing training data. High novelty with high MMD means the model is generating novel graphs, but they don't match the training distribution. The ideal is high validity, uniqueness, and novelty, with low MMD.
Data Augmentation with Generated Graphs
A practical use case: your training set has too few graphs for a graph classification task. Generated graphs with similar topological properties can augment the dataset:
import torch
# Suppose your training set has 50 BA graphs
original_result = run_graph_generation(
method="barabasi_albert",
num_graphs=50,
num_nodes=30,
m=2,
node_feature_dim=16,
seed=1,
)
# Generate 150 additional graphs with same parameters
augmented_result = run_graph_generation(
method="barabasi_albert",
num_graphs=150,
num_nodes=30,
m=2,
node_feature_dim=16,
seed=2, # different seed for different graphs
)
augmented_dataset = original_result.graphs + augmented_result.graphs
print(f"Augmented dataset size: {len(augmented_dataset)}") # 200
# Assign synthetic labels based on graph properties
labels = [0] * 50 + [1] * 150 # placeholder — use domain knowledge for real labels
For augmentation to improve GNN performance, the generated graphs must preserve the statistical properties relevant to the classification task (degree distribution, clustering, etc.). Verify this using graph MMD between the original and generated sets.
Limitations and Honest Notes
Classical generators produce simplified topologies. ER, BA, WS, and SBM graphs capture specific known properties but do not replicate the rich multi-scale structure of real-world graphs (hierarchical communities, temporal evolution, typed edges). They are useful benchmarks but should not be mistaken for realistic simulations.
Neural generation (VGAE) is Experimental. The VGAE generator is implemented but not thoroughly benchmarked in TGraphX. For serious molecular generation, drug-likeness requires chemistry-specific validity constraints (valence, aromaticity, stereochemistry) that TGraphX does not implement. Use RDKit-integrated frameworks for those applications.
Generation metrics are approximate. Uniqueness and novelty use Weisfeiler-Lehman graph hashing for isomorphism testing. WL hashing at finite depth can fail to distinguish non-isomorphic graphs that are WL-equivalent — they will be counted as duplicates. For large graphs, this approximation error increases.
Graph MMD is slow for large sets. The current implementation computes pairwise kernel evaluations, which scales as O(N²) in the number of graphs. For hundreds of graphs, this is fast; for thousands, consider subsampling.
No node-type conditioning. Classical generators produce homogeneous graphs (one node type, no edge types). For heterogeneous graphs with multiple node and edge types, custom generators are necessary.
Frequently Asked Questions
Can I generate graphs with specific degree sequences?
Not directly via the built-in generators. Erdős-Rényi generates an expected degree sequence; BA produces a power-law sequence. For exact degree sequence matching, use the configuration model (not currently in TGraphX).
How do I evaluate whether generated graphs are suitable for augmentation?
Compute graph MMD between the original training set and the generated set using the degree kernel. A low MMD indicates similar degree distributions. Also verify that downstream task metrics (e.g., GNN classification accuracy) improve with augmentation on a validation set.
Can I condition the VGAE generator on graph properties?
Conditional generation is not supported in the current TGraphX VGAE generator. Conditioning on properties like graph size or density requires custom encoder/decoder modifications.
What is the difference between this and the graph-generation article with tensor features?
The tensor-valued node features generation tutorial focuses on constructing graphs with specific tensor feature shapes. This article focuses on generation methods and evaluation metrics. The two are complementary.
Where is the source code?
GitHub, package: PyPI, preprint: arXiv:2504.03953.