Kernel functions for vectors in discrete spaces There are lots of choices for kernel functions $k(\textbf{x}, \textbf{y})$ in continuous spaces (e.g., $\textbf{x}, \textbf{y}\in \mathbb{R}^d$), such as the RBF kernel, etc.
However, what are some common kernel functions for vectors on discrete spaces (e.g., $\textbf{x}, \textbf{y} \in\{0,1\}^d$, or even $\textbf{x}, \textbf{y} \in\{1,\dots,K\}^d$)?
 A: When $\mathcal{I}$ is a finite set with $m$ elements, a Gaussian
Process (GP) $Y_i$ with index $i \in \mathcal{I}$ is nothing but a
Gaussian random vector with length $m$, and a positive kernel defined
on $\mathcal{I}$ is nothing but a symmetric and positive semi-definite
$m \times m$ matrix. Special structures of matrices such as Compound
Symmetry or block matrices can be interesting: Many such structures
can be found in the literature on mixed effects e.g. in Pinheiro and
Bates.
Parameterised forms involving only a few parameters should be preferred
because the number of observations can easily be exceeded by the
number of parameters which can be as high as $m(m + 1)/2$ for the
so-called unconstrained structure. When $\mathcal{I}$ is the product
of $d$ finite sets, parameterised kernels on $\mathcal{I}$ can be
obtained as tensor products.
Some covariance structures correspond to a representation of the GP as
a sum of GP. As an example, a GP $Y_i$ with the Compound Symmetry
structure writes as $Y_i = \alpha + \beta_i$ where the effects
$\alpha$ and the $m$ r.vs $\beta_i$ are independent and $\sum_i
\beta_i = 0$. So by adding a white noise term $\varepsilon$ at right
hand side, the GP regression boils down to a classical random effect
model. More complex structures implying unobserved effects can be
obtained, and the estimated (or smoothed) values of the effects
can be interesting.  It should be kept in mind then that the kernel
acts as a Bayes informative prior. Consequently, the estimators of the
effects are shrinked.  Standard fixed-effects ANOVA models correspond
instead to diffuse priors which are limits of ''large'' covariance matrices
such as $\lambda \mathbf{I}$ for $\lambda \to \infty$.
A kernel $K$ on a continuous (infinite) set $\mathcal{X}$ relates to
interesting bases of functions in some infinite-dimensional space of
functions defined on $\mathcal{X}$. By contrast, the space of all
functions on a finite set $\mathcal{I}$ is finite-dimensional:
choosing a basis boils down to translating an ANOVA model formula.
A: One way to construct kernels over discrete spaces is by considering a graph representation of the data and defining a smooth function over nodes of graphs via graph fourier transform. This class of kernels (introduced by Kondor and Lafferty)  is called as diffusion kernels. Concretely, the kernel over the graph nodes $V$ is given by:
\begin{align}
K(V,V) = \exp(-\beta L) = U \exp(-\beta \Lambda) U^T
\end{align}
where $L$ is the graph laplacian, $U$, $\Lambda$ represent the eigenvector and eigenvalue matrices of L. Please note that each input is assumed to be one node of the constructed graph. This approach also has very nice connections to heat equation in continuous spaces. 
