Gaussian kernels for arbitrary metric spaces

Question

Let $(I,d)$ be an arbitrary (pseudo-)metric space. Define the function $$c(i,i') := \exp\big( - d(i,i')^2 / 2 \big)$$

Is $c$ necessarily nonnegative-definite, hence a kernel function?

Answer 1

No. A counterexample is given by the $4$-cycle graph with path distance. That is, the space consists of $4$ points $v_1,\dots,v_4$ such that $d(v_1,v_3)=d(v_2,v_4)=2$, and other nonzero distances are $1$. Let $a = e^{-1/2}$. The matrix $\exp(-d^2/2)$ is $$\begin{pmatrix} 1 & a & a^{4} & a \\ a & 1 & a & a^{4} \\ a^{4} & a & 1 & a \\ a & a^{4} & a & 1 \end{pmatrix}$$ The determinant, according to Sage, is $${\left(a^{3} + a^{2} + a - 1\right)} {\left(a^{3} - a^{2} + a + 1\right)} {\left(a^{2} + 1\right)}^{2} {\left(a + 1\right)}^{3} {\left(a - 1\right)}^{3}$$ This is negative; the only factor that needs checking is $a^{3} + a^{2} + a - 1>0$.