Standard PolyGraphDiscrepancy

StandardPGD is a PolyGraphDiscrepancy metric based on six different graph descriptors.

• OrbitCounts: Counts of different graphlet orbits
• ClusteringHistogram: Distribution of clustering coefficients
• SparseDegreeHistogram: Distribution of node degrees
• EigenvalueHistogram: Distribution of graph Laplacian eigenvalues
• RandomGIN: Graph Neural Network embedding of the graph, combined with a normalization layer (NormalizedDescriptor). Proposed by Thompson et al. [1].

By default, we use TabPFN for binary classification and evaluate it by data log-likelihood, obtaining a PolyGraphDiscrepancy that provides an estimated lower bound on the Jensen-Shannon distance between the generated and true graph distribution.

This metric is implemented in the StandardPGD class and can be used as follows:

from polygraph.datasets import PlanarGraphDataset, SBMGraphDataset
from polygraph.metrics import StandardPGD

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

benchmark = StandardPGD(reference)
print(benchmark.compute(generated))     # {'pgd': 0.9902651620251016, 'pgd_descriptor': 'clustering', 'subscores': {'orbit': 0.9962500491652303, 'clustering': 0.9902651620251016, 'degree': 0.9975117559449073, 'spectral': 0.9634302070519823, 'gin': 0.994213920319544}}

We also provide classes that implement individual ClassifierMetrics:

• ClassifierOrbit4Metric: Classifier metric based on OrbitCounts
• ClassifierOrbit5Metric: Classifier metric based on OrbitCounts
• ClassifierClusteringMetric: Classifier metric based on ClusteringHistogram
• ClassifierDegreeMetric: Classifier metric based on SparseDegreeHistogram
• ClassifierSpectralMetric: Classifier metric based on EigenvalueHistogram
• GraphNeuralNetworkClassifierMetric: Classifier metric based on RandomGIN