Graph Kernels

polygraph.utils.kernels.RBFKernel

Bases: DescriptorKernel[GraphType], Generic[GraphType]

Radial Basis Function (RBF) kernel, also known as Gaussian kernel.

Computes similarity using the formula:

\[ k(x,y) = \exp\left(-\frac{\|x-y\|^2}{2\sigma^2}\right) \]

where \(\sigma\) is the bandwidth parameter.

Parameters:
  • descriptor_fn (GraphDescriptor[GraphType]) –

    Function that computes descriptors from graphs

  • bw (Union[float, ndarray]) –

    Bandwidth parameter(s). Can be a single float or 1-dimensional numpy array of floats for multiple kernels

polygraph.utils.kernels.LaplaceKernel

Bases: DescriptorKernel[GraphType], Generic[GraphType]

Laplace kernel using L1 (Manhattan) distance.

Computes similarity using the formula:

\[ k(x,y) = \exp\left(-\lambda\|x-y\|_1\right) \]

where \(\lambda\) is the scale parameter.

Parameters:
  • descriptor_fn (GraphDescriptor[GraphType]) –

    Function that computes descriptors from graphs

  • lbd (Union[float, ndarray]) –

    Scale parameter(s). Can be a single float or 1-dimensional numpy array of floats for multiple kernels

polygraph.utils.kernels.GaussianTV

Bases: DescriptorKernel[GraphType], Generic[GraphType]

Gaussian kernel using L1 distance.

Computes similarity using the formula:

\[ k(x,y) = \exp\left(-\frac{(\|x-y\|_1/2)^2}{2\sigma^2}\right) \]

where \(\sigma\) is the bandwidth parameter.

Warning

This kernel is not positive definite.

Parameters:
  • descriptor_fn (GraphDescriptor[GraphType]) –

    Function that computes descriptors from graphs

  • bw (Union[float, ndarray]) –

    Bandwidth parameter(s). Can be a single float or 1-dimensional numpy array of floats for multiple kernels

polygraph.utils.kernels.AdaptiveRBFKernel

Bases: DescriptorKernel[GraphType], Generic[GraphType]

Adaptive RBF kernel with data-dependent bandwidth.

Similar to the standard RBF kernel but adapts its bandwidth based on the data:

\[ k(x,y) = \exp\left(-\frac{\|x-y\|^2}{2(c\sigma)^2}\right) \]

where \(\sigma\) is the base bandwidth and \(c\) is a scaling factor computed from the typical distance between reference and generated graphs. Specifically, \(c\) is the square root of the mean or median of the squared \(\ell^2\) distance between reference and generated graphs.

Parameters:
  • descriptor_fn (GraphDescriptor[GraphType]) –

    Function that computes descriptors from graphs

  • bw (Union[float, ndarray]) –

    Base bandwidth parameter(s). Can be a single float or 1-dimensional numpy array of floats for multiple kernels

  • variant (Literal['mean', 'median'], default: 'mean' ) –

    Method for computing adaptive scaling. Either 'mean' or 'median' of the reference-generated distance.

polygraph.utils.kernels.LinearKernel

Bases: DescriptorKernel[GraphType], Generic[GraphType]

Simple linear kernel using dot product.

Computes similarity using the formula:

\[ k(x,y) = x^\top y \]
Parameters:
  • descriptor_fn (GraphDescriptor[GraphType]) –

    Function that computes descriptors from graphs