Gaussian TV MMD Metrics

MMD metrics based on graph descriptors introduced by You et al. [1] and Liao et al. [2], using a Gaussian TV kernel.

We provide both point estimates of MMD and uncertainty quantifications. The following graph descriptors are available:

Graph Descriptors

OrbitCounts: Counts of different graphlet orbits
ClusteringHistogram: Distribution of clustering coefficients
SparseDegreeHistogram: Distribution of node degrees
EigenvalueHistogram: Distribution of graph Laplacian eigenvalues

The GaussianTV kernel is used with descriptor-specific bandwidths.

Warning

The Gaussian TV kernel is not positive definite, as shown by O'Bray et al. [3]. While it is most widely used in the literature, consider also evaluating the linear and RBF kernels.

Below, we demonstrate how to evaluate all metrics in the benchmark with point estimates and with uncertainty quantification. Note that the parameter subsample_size in GaussianTVMMD2BenchmarkInterval should match the number of generated and reference graphs in GaussianTVMMD2Benchmark to obtain comparable results:

from polygraph.datasets import PlanarGraphDataset, SBMGraphDataset
from polygraph.metrics import GaussianTVMMD2Benchmark, GaussianTVMMD2BenchmarkInterval

reference = list(PlanarGraphDataset("val").to_nx())
generated = list(SBMGraphDataset("val").to_nx())

# Evaluate the benchmark with point estimates
benchmark = GaussianTVMMD2Benchmark(reference[:20])
print(benchmark.compute(generated[:20]))

# Evaluate the benchmark with uncertainty quantification
benchmark_with_uncertainty = GaussianTVMMD2BenchmarkInterval(
    reference,
    subsample_size=20,
    num_samples=100,
    coverage=0.95,
)
print(benchmark_with_uncertainty.compute(generated))

The individual metrics are also provided in seperate classes, e.g. GaussianTVOrbitMMD2 and GaussianTVOrbitMMD2Interval.

References

[1] You, J., Ying, R., Ren, X., Hamilton, W., & Leskovec, J. (2018). GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models. In International Conference on Machine Learning (ICML).

[2] Liao, R., Li, Y., Song, Y., Wang, S., Hamilton, W., Duvenaud, D., Urtasun, R., & Zemel, R. (2019). Efficient Graph Generation with Graph Recurrent Attention Networks. In Advances in Neural Information Processing Systems (NeurIPS).

[3] O'Bray, L., Horn, M., Rieck, B., & Borgwardt, K. (2022). Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions. In International Conference on Learning Representations (ICLR).

Summary Benchmark

`polygraph.metrics.GaussianTVMMD2Benchmark`

Bases: MetricCollection[Graph]

Collection of MMD2 metrics using the Gaussian TV kernel.

This graphs combines the following graph descriptors into one benchmark:

Parameters:	`reference_graphs` (`Collection[Graph]`) – Collection of reference graphs to fit the metric to.

`polygraph.metrics.GaussianTVMMD2BenchmarkInterval`

Bases: MetricCollection[Graph]

Collection of MMD2 metrics using the Gaussian TV kernel with uncertainty quantification.

This class provides the same metrics as GaussianTVMMD2Benchmark but with uncertainty quantification.

Parameters:

reference_graphs (Collection[Graph]) –

Collection of reference graphs to fit the metric to.
subsample_size (int) –

Size of the subsample used to compute the uncertainty interval.
num_samples (int, default: 500 ) –

Number of samples used to compute the uncertainty interval.
coverage (Optional[float], default: 0.95 ) –

Coverage of the uncertainty interval.