PSD-Safe Bernstein Distance Kernel

1. Integration point: use this scalar distance kernel inside a graph message-passing layer or as a relative-distance bias in attention. For a controlled implementation, embed each node on the unit circle with angle phi_i, compute x_ij=min(|phi_i-phi_j|,2*pi-|phi_i-phi_j|), and multiply messages by g_theta(x_ij). In attention, use g_theta(x_ij) as a multiplicative gate; only add log(epsilon+g_theta(x_ij)) to logits if a strictly positive gate is required. 2. Pseudocode: initialize theta[0:M]. Compute a_m=softplus(theta[m])+epsilon. Precompute T[k,m]=cos(m*pi*k/n) for k=0,...,n and m=0,...,M. For every distance x, compute u=x/pi, Bernstein weights w_k=binom(n,k)*u^k*(1-u)^(n-k), evaluate f_k=a_0+sum_{m=1}^M a_m*T[k,m], and return g_theta(x)=sum_{k=0}^n w_k*f_k. Backpropagate through theta; cache T and, for fixed angular coordinates, cache pairwise x and w. 3. The paper supplies the exact cone-preservation result on S^1 and the nonnegative spectral-coefficient mechanism for Q_{n,m}; no theorem constants need to be estimated. Empirically form K for random angle batches and check its smallest eigenvalue, allowing a tolerance such as -1e-6 for floating-point error. For non-circular graph distances, report PSD violations as an empirical diagnostic and do not claim the circle theorem applies. 4. Cheap experiment: train a 3-layer GCN or small graph transformer on synthetic circle-coordinate node classification and a two-moons graph dataset. Compare an unconstrained two-layer MLP distance kernel, a direct nonnegative cosine-spectrum kernel f_theta, and the Bernstein kernel for n in {8,16,32}. Measure validation accuracy, training-loss variance, gradient-norm spikes, smallest Gram eigenvalue, and the fraction of batches with negative eigenvalues. Success means zero or near-machine-precision PSD violations on circle data, fewer optimization instabilities, and equal-or-better accuracy at comparable parameter count and FLOPs.