geometric_kernels.spaces.hamming_graph

This module provides the HammingGraph space and the respective Eigenfunctions subclass VilenkinFunctions.

Module Contents

class geometric_kernels.spaces.hamming_graph.HammingGraph(dim, n_cat)[source]

Bases: geometric_kernels.spaces.base.DiscreteSpectrumSpace

The GeometricKernels space representing the q-ary Hamming graph \(H(d,q) = \{0, 1, ..., q-1\}^d\), the combinatorial space of categorical vectors (with \(q\) categories) of length \(d\).

The elements of this space are represented by d-dimensional categorical vectors (with \(q\) categories) taking integer values in \(\{0, 1, ..., q-1\}\).

Levels are the whole eigenspaces.

Note

If you need a kernel operating on categorical vectors where \(q\) varies between dimensions, you can use HammingGraph in conjunction with ProductGeometricKernel or ProductDiscreteSpectrumSpace.

Note

For the special case \(q = 2\), this reduces to the binary hypercube graph, also available as HypercubeGraph.

Note

A tutorial on how to use this space is available in the HammingGraph.ipynb notebook.

Note

Since the degree matrix is a constant multiple of the identity, all types of the graph Laplacian coincide on the Hamming graph up to a constant, we choose the normalized Laplacian for numerical stability.

Parameters:

  • dim (int) – Dimension \(d\) of the Hamming graph \(H(d,q)\), a positive integer.

  • n_cat (int) – Number of categories \(q\) of the Hamming graph \(H(d,q)\), a positive integer \(q \geq 2\).

Citation

If you use this GeometricKernels space in your research, please consider citing Borovitskiy et al. [2023] and Doumont et al. [2025].

get_eigenfunctions(num)[source]

Returns the VilenkinFunctions object with num levels.

Parameters:

num (int) – Number of levels.

Return type:

geometric_kernels.spaces.eigenfunctions.Eigenfunctions

get_eigenvalues(num)[source]

Eigenvalues of the Laplacian corresponding to the first num levels.

Parameters:

num (int) – Number of levels.

Returns:

(num, 1)-shaped array containing the eigenvalues.

Return type:

lab.Numeric

Note

The notion of levels is discussed in the documentation of the MaternKarhunenLoeveKernel.

get_repeated_eigenvalues(num)[source]

Eigenvalues of the Laplacian corresponding to the first num levels, repeated according to their multiplicity within levels.

Parameters:

num (int) – Number of levels.

Returns:

(J, 1)-shaped array containing the repeated eigenvalues, J is the resulting number of the repeated eigenvalues.

Return type:

lab.Numeric

Note

The notion of levels is discussed in the documentation of the MaternKarhunenLoeveKernel.

random(key, number)[source]

Sample uniformly random points on the Hamming graph \(H(d,q)\).

Always returns [N, D] integer array of the key’s backend with values in \(\{0, 1, ..., q-1\}\).

Parameters:

  • key (lab.RandomState) – Either np.random.RandomState, tf.random.Generator, torch.Generator or jax.tensor (representing random state).

  • number (int) – Number N of samples to draw.

Returns:

An array of number uniformly random samples on the space.

Return type:

lab.Numeric

property dimension: int

Returns d, the dim parameter that was passed down to __init__.

Return type:

int

property element_dtype
Returns:

B.Int.

property element_shape
Returns:

[d].

class geometric_kernels.spaces.hamming_graph.VilenkinFunctions(dim, n_cat, num_levels)[source]

Bases: geometric_kernels.spaces.eigenfunctions.EigenfunctionsWithAdditionTheorem

Eigenfunctions of the graph Laplacian on the q-ary Hamming graph \(H(d,q)\), whose nodes are indexed by categorical vectors in \(\{0, 1, ..., q-1\}^d\).

These eigenfunctions are the Vilenkin functions (also called Vilenkin-Chrestenson functions), which generalize the binary Walsh functions to q-ary alphabets. They map vertices to complex values via products of characters on cyclic groups.

For the special case \(q = 2\), the Vilenkin functions reduce to the Walsh functions on the binary hypercube \(\{0, 1\}^d\).

Note

The Vilenkin functions can be indexed by “character patterns” - choices of coordinates and non-identity characters at those coordinates. Each eigenspace (level) \(j\) has dimension \(\binom{d}{j}(q-1)^j\), corresponding to choosing \(j\) coordinates and assigning \((q-1)\) possible non-identity characters to each.

Levels are the whole eigenspaces, comprising all Vilenkin functions with the same number of coordinates having non-identity characters. The addition theorem for these is based on generalized Kravchuk polynomials, i.e. discrete orthogonal polynomials on the q-ary Hamming scheme.

Parameters:

  • dim (int) – Dimension \(d\) of the q-ary Hamming graph \(H(d,q)\).

  • n_cat (int) – Number of categories \(q \geq 2\) in the q-ary alphabet \(\{0, 1, ..., q-1\}\).

  • num_levels (int) – Specifies the number of levels (eigenspaces) of the Vilenkin functions to use.

abstractmethod __call__(X, **kwargs)[source]

Evaluate the individual eigenfunctions at a batch of input locations.

Parameters:

  • X (lab.Int) – Points to evaluate the eigenfunctions at, an array of shape [N, <axis>], where N is the number of points and <axis> is the shape of the arrays that represent the points in a given space.

  • **kwargs – Any additional parameters.

Returns:

An [N, J]-shaped array, where J is the number of eigenfunctions.

Return type:

lab.Float

weighted_outerproduct(weights, X, X2=None, **kwargs)[source]

Computes

\[\sum_{l=0}^{L-1} w_l \sum_{s=1}^{d_l} f_{l s}(x_1) f_{l s}(x_2).\]

for all \(x_1\) in X and all \(x_2\) in X2, where \(w_l\) are weights.

Parameters:

  • weights (lab.Numeric) – An array of shape [L, 1] where L is the number of levels.

  • X (lab.Numeric) – The first of the two batches of points to evaluate the weighted outer product at. An array of shape [N, <axis>], where N is the number of points and <axis> is the shape of the arrays that represent the points in a given space.

  • X2 (beartype.typing.Optional[lab.Numeric]) –

    The second of the two batches of points to evaluate the weighted outer product at. An array of shape [N2, <axis>], where N2 is the number of points and <axis> is the shape of the arrays that represent the points in a given space.

    Defaults to None, in which case X is used for X2.

  • **kwargs – Any additional parameters.

Returns:

An array of shape [N, N2].

Return type:

lab.Numeric

weighted_outerproduct_diag(weights, X, **kwargs)[source]

Computes the diagonal of the matrix weighted_outerproduct(weights, X, X, **kwargs).

Parameters:
Returns:

An array of shape [N,].

Return type:

lab.Numeric

property num_eigenfunctions: int

The number J of eigenfunctions.

Return type:

int

property num_eigenfunctions_per_level: beartype.typing.List[int]

The number of eigenfunctions per level: list of \(d_l\), \(0 \leq l < L\).

Return type:

beartype.typing.List[int]

property num_levels: int

The number L of levels.

Return type:

int