On the real line, a shift-invariant space is generated by translating a single function: every element is a linear combination of shifts of a generator. Signal processing lives in these spaces. On a graph with N vertices, there is no natural “shift” — the graph has topology but no translation symmetry.
The paper on frames and bases of translates on undirected graphs (arXiv: 2603.21026) defines generalized translates using the graph's spectral structure (eigenvalues and eigenvectors of the graph Laplacian or adjacency matrix) and characterizes when these translates form orthonormal bases or frames for ℂ^N.
The conditions are algebraic: whether the translates of a signal span all of ℂ^N depends on whether the signal's graph Fourier coefficients avoid the zeros of certain polynomials determined by the graph spectrum. Multiple generators can combine to form frames even when individual generators cannot.
Applications include modulated systems (graph analogues of Gabor frames) and spectral graph wavelets, where the generalized translates provide localized building blocks for analyzing signals on graphs.
The through-claim: translation symmetry on graphs is spectral, not geometric. The real line has a group of translations; graphs don't. But the spectral decomposition (graph Fourier transform) provides a substitute: “translating” a signal on a graph means modulating its spectral coefficients. The resulting bases and frames inherit the graph's topology through the spectrum.
2603.21026. Signal processing / graph signal processing / frames / graph Fourier transform / spectral graph theory.