Why is Dirac kernel positive semi-definite? I read a paper Weisfeiler-Lehman Graph Kernel. In this paper, it says:

Let the base kernel $k$ be a function counting pairs of matching node labels in two graphs: $k\left(G, G^{\prime}\right)=\sum_{v \in V} \sum_{\nu^{\prime} \in V^{\prime}} \delta\left(\ell(v), \ell\left(v^{\prime}\right)\right)$, where $\delta$ is the Dirac kernel, that is, it is 1 when its arguments are equal and 0 otherwise. Then $k_{W L}^{(h)}\left(G, G^{\prime}\right)=k_{W L s u b t r e e}^{(h)}\left(G, G^{\prime}\right)$ for all $G$, $G'$.

I think the Gram Matrix of Dirac kernel is a matrix with all 1's on the diagonal, and the other positions in the Gram Matrix could be 0 or 1. Why is the Dirac kernel a valid kernel? Or why is the gram matrix of the Dirac kernel PSD?
 A: I tried to do some proof of the question by myself, but I am not very sure.
I want to prove $\delta$ kernel is a valid kernel. $\delta$ kernel is represented as follows:
\begin{equation}
k\left(v_{1}, v_{2}\right)=\left\{\begin{array}{lr}
1 & \text { if } \ell\left(v_{1}\right)=\ell\left(v_{2}\right) \\
0 & \text { otherwise }
\end{array}\right.
\end{equation}
where $\ell\left(v_{1}\right)$ is the label of node $v_1$. We consider $\ell\left(\cdot\right)$ is a one-hot mapping, and then the kernel function $k\left(v_{1}, v_{2}\right)$ be equivalent to $k\left(v_{1}, v_{2}\right) = <onehot(\ell\left(v_{1}\right)), onehot(\ell\left(v_{2}\right))> = <\phi(v_1),\phi(v_2)>$, where $\phi: V \to \mathcal{H}$ and $\mathcal{H} = \mathbb{R}^{num\_labels}$. Therefore, for a nonempty set $V$, $k$ is a valid kernel and it is psd.
A: The kernel matrix for the Dirac kernel is "diagonally dominant" (the magnitude of the diagonal element is larger than the sum of the magnitudes of the off-diagonal elements of that row/column).  A symmetric diagonally dominant real matrix with nonnegative diagonal entries is positive semidefinite.   Diagonal dominance can be problematic for kernel methods.
As for why it is a valid kernel.  Consider a feature space in which there was a feature corresponding to every possible input vector.  So if your input space was the space of all strings of length, 3 composed from the alphabet 'a', 'b' and 'c', then the feature space would have a feature that was one if the input string was 'aaa', and zero otherwise, and one for 'aab', and another for 'aba', ... and so on.  The inner product in that feature space would be the Dirac kernel.  Similar reasoning might apply to continuous input spaces, but would require an infinite-dimensional feature space.
Note that when we regularised a kernel method, we are typically adding a multiple of the Dirac kernel onto the original kernel matrix, so if it wasn't a valid kernel, then that regularisation would immediately destroy the interpretation of the kernel model as being a simple (linear?) model constructed in a fixed kernel-induced feature space.
A: The Dirac kernel is a valid kernel since it is positive semidefinite.
In other words, because its matrix is positive definite, it follows that the Dirac Kernel is a valid kernel. See Mercer's Theorem for further reference.
To see that it is positive semidefinite, it only suffices to note that all the entries of the gram matrix are non-negative, i.e., those elements on the diagonal, since they will be squared: $\forall v.\ell(v)^2 \geq 0$
