linear algebra - Fast Fourier Transform for Graph Laplacian?

In the case of a regularly-sampled scalar-valued signal $f$ on the real line, we can construct a discrete linear operator $A$ such that $A(f)$ approximates $partial^2 f / partial x^2$. One way to interpret this operator is via spectral decomposition of the corresponding matrix:

$$A = UVU^T.$$

If our operator $A$ has spectral accuracy, then $U^T$ is precisely the discrete Fourier transform matrix. Hence, we could compute the Fourier transform of $x$ by computing all the eigenvectors of $A$ and sticking them in the columns of $U$. Of course, we all know there's a quicker way to do it: use the fast Fourier transform (FFT).

What about in a more general setting? In particular, consider the graph Laplacian $L=UVU^T$ which for a weighted, undirected graph on $n$ vertices is an $n times n$ matrix with the weights of incident vertices on the off-diagonal and (the additive inverse of) total incident weight on the diagonal.

Question:

Can we transform a signal on vertices into frequency space without computing the entire spectrum of $L$ (using something like the FFT)?

In particular I'm interested in the case where $L$ approximates the Laplace-Beltrami operator on some manifold $M$ -- here eigenvectors of $L$ approximate an orthogonal eigenbasis for square-integrable functions on $M$. However, pointers to nearby results (e.g., FFT for the combinatorial graph Laplacian) are appreciated.