PolyGraphDiscrepancy

PolyGraph discrepancy metrics compare generated graphs to reference graphs by fitting a binary classifier to discriminate between the two. Performance metrics of this classifier lower-bound intrinsic probability metrics. Multiple graph descriptors may be combined within the metric to yield a theoretically grounded summary metric.

Any binary classifier implementing the standard scikit-learn interface (as defined in ClassifierProtocol) may be used for classification. By default, we use TabPFN. The classifiers may be then be evaluated by either:

  • Data log-likelihood (default) - Provides a lower bound on the Jensen-Shannon distance, or
  • Informedness - Provides a lower bound on the total variation distance.

The PolyGraphDiscrepancy class combines metrics across multiple graph descriptors, providing the tightest lower-bound on the probability metrics. The ClassifierMetric class, on the other hand, computes a lower bound for a single graph descriptor.

The PolyGraphDiscrepancyInterval class implements a variant of the PolyGraphDiscrepancy with uncertainty quantification.

Example 
from polygraph.datasets import PlanarGraphDataset, SBMGraphDataset
from polygraph.metrics.base import PolyGraphDiscrepancy
from polygraph.utils.descriptors import OrbitCounts, SparseDegreeHistogram

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

benchmark = PolyGraphDiscrepancy(
    reference,
    descriptors={
        "orbit": OrbitCounts(),
        "degree": SparseDegreeHistogram(),
    },
)
print(benchmark.compute(generated))         # {'pgd': 0.9975117559449073, 'pgd_descriptor': 'degree', 'subscores': {'orbit': 0.9962500491652303, 'degree': 0.9975117559449073}}

PolyGraphDiscrepancy

polygraph.metrics.base.PolyGraphDiscrepancy

Bases: GenerationMetric[GraphType], Generic[GraphType]

PolyGraphDiscrepancy to compare graph distributions, combining multiple graph descriptors.

Parameters:
  • reference_graphs (Collection[GraphType]) –

    Reference graphs

  • descriptors (Dict[str, GraphDescriptor[GraphType]]) –

    Dictionary of descriptor names and descriptor functions

  • variant (Literal['informedness', 'jsd'], default: 'jsd' ) –

    Classifier metric to compute. To estimate the Jensen-Shannon distance, use "jsd". To estimate total variation distance, use "informedness".

  • classifier (Optional[ClassifierProtocol], default: None ) –

    Binary classifier to fit

compute(generated_graphs)

Compute the PolyGraphDiscrepancy.

Parameters:
  • generated_graphs (Collection[GraphType]) –

    Generated graphs
Returns:
  • PolyGraphDiscrepancyResult –

    Typed dictionary of scores. The key "polygraphscore" specifies the PolyGraphDiscrepancy, giving the estimated tightest lower-bound on the probability metric. The key "polygraphscore_descriptor" specifies the descriptor that achieves this bound. All descritor-wise scores are returned in the key "subscores".

polygraph.metrics.base.PolyGraphDiscrepancyInterval

Bases: GenerationMetric[GraphType], Generic[GraphType]

Uncertainty quantification for PolyGraphDiscrepancy.

Parameters:
  • reference_graphs (Collection[GraphType]) –

    Reference graphs. Must provide at least 2 * subsample_size graphs.

  • descriptors (Dict[str, GraphDescriptor[GraphType]]) –

    Dictionary of descriptor names and descriptor functions

  • subsample_size (int) –

    Size of each subsample, should be consistent with the number of reference and generated graphs passed to PolyGraphDiscrepancy for point estimates.

  • num_samples (int, default: 10 ) –

    Number of samples to draw for uncertainty quantification.

compute(generated_graphs)

Compute the PolyGraphDiscrepancyInterval.

Parameters:
  • generated_graphs (Collection[GraphType]) –

    Generated graphs. Must provide at least 2 * subsample_size graphs.
Returns:
  • PolyGraphDiscrepancyIntervalResult –

    Typed dictionary of scores. The key "pgd" specifies the PolyGraphDiscrepancy, giving mean and standard deviation as MetricInterval objects. The key "pgd_descriptor" describes which descriptors achieve this score. This is a dictionary mapping descriptor names to the ratio of samples in which the descriptor was chosen. All descritor-wise scores are returned in the key "subscores". These are MetricInterval objects.

Estimating Distances with a Single Descriptor

polygraph.metrics.base.ClassifierMetric

Bases: GenerationMetric[GraphType], Generic[GraphType]

Classifier-based metric using a single graph descriptor.

Parameters:
  • reference_graphs (Collection[GraphType]) –

    Reference graphs

  • descriptor (GraphDescriptor[GraphType]) –

    Descriptor function

  • variant (Literal['informedness', 'jsd'], default: 'jsd' ) –

    Classifier metric to compute. To estimate the Jensen-Shannon distance, use "jsd". To estimate total variation distance, use "informedness".

  • classifier (Optional[ClassifierProtocol], default: None ) –

    Binary classifier to fit

compute(generated_graphs)

Compute the classifier metric.

Parameters:
  • generated_graphs (Collection[GraphType]) –

    Generated graphs
Returns:
  • Tuple[float, float] –

    Tuple of train and test metric

Classifier Interface

polygraph.metrics.base.polygraphdiscrepancy.ClassifierProtocol

Bases: Protocol

Protocol for binary classifiers used in the PolyGraph discrepancy metric.

fit(X, y)

Fit the classifier to the data.

Parameters:
  • X (ndarray) –

    Feature matrix of shape (n_samples, n_features)

  • y (ndarray) –

    Labels of shape (n_samples,)
Returns:

predict_proba(X)

Predict the probability of the positive class.

Parameters:
  • X (ndarray) –

    Feature matrix of shape (n_samples, n_features)
Returns:
  • ndarray –

    Probabilities of shape (n_samples, 2)