Cubic spectral cancellation and random geometric graph detection: a quadratic-kernel counterexample

Source abstract

We study whether an observed graph can distinguish a random graph generated by latent geometry from one with independent edges. In the geometric model, vertex positions are independent and uniform on a high-dimensional sphere. Conditional on these positions, edges occur independently, with probabilities determined by a connection function $K$ of the inner products of their endpoints. The comparison model is an Erdős-Rényi graph with the same edge density. A general spectral conjecture asserts that if the cubic spectral trace, which corresponds to the signed triangle mean, is sufficiently small in the sense that $$n^3[\operatorname{tr}(κ^3)]^2\longrightarrow0,$$ where $n$ is the number of vertices and $κ$ is the centered and standardized spherical kernel operator, then the total variation distance between the two graph distributions tends to zero. Consequently, the lower limit of the sum of the two error probabilities of any sequence of tests is at least one. We give a counterexample to the formulation allowing dimension-dependent connection functions without monotonicity or a common-sign condition on the spectrum. Our quadratic connection functions are uniformly bounded away from zero and one. Their cubic trace vanishes identically through cancellation between positive and negative eigenvalues, whereas their quartic trace is strictly positive. When $d=\max\{3,\lfloor n^{1/20}\rfloor\}$, a signed four-cycle test has a sum of error probabilities tending to zero, and the total variation distance instead tends to one. A perturbation making the cubic trace strictly nonzero still satisfies the stated cubic-trace condition and yields strong detection. The construction and detection result follow, respectively, from a finite-rank spectral decomposition of the spherical kernel and estimates of the mean and variance of the four-cycle statistic.