Fourier Ratios of Graph Kernels: Energy Bounds, Optimal Labelings, and Recovery

Abstract

We study labeling-sensitive Fourier complexity for finite graph kernels. After identifying the vertices of a graph with the cyclic group ${\mathbb{Z}}_N$, its adjacency matrix becomes a function on ${\mathbb{Z}}_N^2$. Minimizing the quotient of the ${\ell }^1$ and ${\ell }^2$ norms of its two-dimensional Fourier transform over all vertex labelings gives an isomorphism invariant ${\mathrm{FR}}_{\min }(G)$. A nuclear-norm argument gives \[\operatorname{FR}_{\min}(G) \geq \frac{\mathcal E(G)}{\sqrt{2s}},\] where $s$ is the number of edges and $\mathcal{E}(G)$ is the graph energy. The natural cyclic labeling attains equality for every circulant graph. We obtain exact formulas for several graph families and a labeling-sensitive complete bipartite example. We also connect the invariant with the Fourier algebra of ${\mathbb{Z}}_N^2$. The quantitative Cohen idempotent theorem implies that every Boolean kernel of bounded Fourier ratio has an exact signed coset decomposition whose length is independent of $N$. A previously established Fourier-ratio recovery theorem gives stable Frobenius approximation of a fixed labeled adjacency matrix from Bernoulli samples. We distinguish this conclusion from exact edge recovery and from the problem of finding a good labeling. For a Laplacian eigenvalue of multiplicity $m(\lambda )$, we prove \[ \operatorname{FR}_{\min}(Π_λ) \geq \sqrt{m(λ)}, \] with equality for circulant graphs. Strongly regular graphs and the Petersen graph show how adjacency and projector complexity can agree or differ. Direct projector sampling yields heat-kernel approximation. We conclude with a graph-signal spectral synthesis principle and asymptotic uniqueness from incomplete vertex data.

Title changed, theoretical bounds expanded, and proofs revised