Measuring Generated Graphs: Validity, Uniqueness, Novelty, Diversity, and MMD
Supervised learning has accuracy; graph generation has no such single number. A generator can produce graphs that are individually plausible but all identical, or wildly diverse but structurally wrong, or perfect copies of the training set. Each of those is a distinct failure, so evaluation needs a panel of metrics rather than one score. TGraphX ships exactly such a panel in tgraphx/generation/metrics.py. This note explains what each metric measures and which failure it is designed to catch — useful whether or not you use TGraphX's generators.
A caveat up front about maturity: classical graph generation and these metrics are Beta, while the neural generators (VGAE, autoregressive, transformer) are Experimental — correct foundations, but an API that may evolve. The capability-map article (here) explains those labels.
The four set-level scores
tgraphx/generation/metrics.py defines four scores over a set of generated graphs:
| Metric | Question it answers | Failure it catches |
|---|---|---|
validity_score |
what fraction satisfy the required constraints? | producing malformed graphs |
uniqueness_score |
what fraction are distinct (non-duplicate)? | mode collapse to a few graphs |
novelty_score |
what fraction are not in the training set? | memorising and replaying training data |
diversity_score |
how spread out is the generated set? | low variety even among "unique" graphs |
These are deliberately complementary. A degenerate generator that emits one valid graph repeatedly scores high on validity but near-zero on uniqueness. One that memorises the training set scores high on uniqueness but zero on novelty. Only a generator that is valid, unique, novel, and diverse passes all four — which is why you report them together, not individually. This is the standard evaluation philosophy from the molecular-generation literature (GraphRNN and successors), implemented here for general graphs.
Distributional distance: MMD
The four scores above are about the set; MMD is about the distribution. Maximum Mean Discrepancy compares a structural statistic (degree distribution, clustering coefficients) of generated graphs against a reference set. The source documents the estimator directly:
MMD² = E_{x,x'~p}[ k(x,x') ] − 2·E_{x~p, y~q}[ k(x,y) ] + E_{y,y'~q}[ k(y,y') ]
where p is the generated distribution, q the reference, and k a kernel. The value is a non-negative MMD²: zero means the two distributions are indistinguishable under the kernel, larger means more different. TGraphX provides mmd_degree and mmd_clustering, applying this to degree and clustering-coefficient statistics respectively. The intuition: a good generator should reproduce the statistics of real graphs even when no individual generated graph is a copy — MMD measures that distributional match in a way the four set-scores cannot.
Reading the panel together
A practical reading guide:
- High validity, low uniqueness → mode collapse; the generator found one safe graph.
- High uniqueness, low novelty → memorisation; it is replaying training graphs with cosmetic changes.
- High novelty, high MMD → it invents graphs, but they do not match the target structure.
- Balanced scores, low MMD → the healthy regime worth aiming for.
No single number summarises this, and trying to collapse it into one would hide exactly the trade-offs you need to see.
Honest framing
Three honest points. First, the neural generators these metrics evaluate are Experimental in TGraphX — treat generated-model APIs as subject to change and pin your version. Second, MMD depends on the chosen kernel and statistic; a low mmd_degree does not guarantee a low MMD on some other property, so report which statistics you used. Third, "validity" is defined by your constraints — the metric is only as meaningful as the validity check you supply. None of these metrics is a quality claim about TGraphX's generators; they are measurement tools that are equally honest about a good or a bad model.
A reporting template
Because no single number captures generation quality, report the panel as a small table and state the choices that affect it. A minimal, honest report includes the four set-level scores (validity, uniqueness, novelty, diversity), at least one MMD statistic (degree and/or clustering) with the kernel you used, the size of the generated set, and the reference set the metrics were computed against. State your validity definition explicitly, since validity_score is only as meaningful as the constraint you supply.
Two further disclosures keep the report defensible: the seed (generation is stochastic, so a single set is a sample, not a verdict) and the package version (the neural generators are Experimental and may change between releases). With those in place, a reader can see not just that a generator scored well but under what definition — the difference between a reproducible claim and an unfalsifiable one. Reporting MMD without naming the statistic and kernel, or validity without the constraint, hides exactly the assumptions a reviewer needs to interpret the result.
One last caution: every metric here evaluates a set of graphs, so a small sample gives noisy estimates of every score. Generate enough graphs that the numbers stabilise before reporting them, and state the sample size alongside the scores so a reader can judge their reliability.
Related guides
- Graph Generation with Tensor-Valued Node Features
- TGraphX Capability Map
- Graph Mining and Motif Discovery
Conclusion
Generation quality is multi-dimensional, so TGraphX measures it with a panel: validity, uniqueness, novelty, and diversity over the set, plus MMD on degree and clustering distributions. Each catches a different way a generator can disappoint, and reading them together — rather than chasing one number — is how you tell a genuinely good generator from one that has merely gamed a single metric.