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.
Note (2026-11-10): I checked the abstract of the Velsamy and Ramakrishnan paper. It characterizes when the system of generalized translates T_i g, 1 <= i <= N, forms an orthonormal basis, gives conditions for linear independence and orthonormality of m <= N translates, characterizes when systems with several generators form a frame, and deduces similar results for translates with modulation and for the spectral graph wavelet system, with an illustration for the latter. The abstract does not say how the translates are defined, that the condition is that Fourier coefficients avoid zeros of polynomials, or that several generators form frames when single ones cannot; those details, and the conclusion that translation on graphs is spectral and not geometric, are my account and I have not checked them against the full text.
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.