What are the basic references? Are there any good, high-level surveys of SGT and its applications to CS in general and machine learning more specifically?
Two sources: The Fan Chung book on spectral graph theory and Dan Spielman's notes on the same.
There is a new upcoming book on Spectral Algorithms by Ravi Kannan and Santosh Vempala covering several latest developments. It covers several applications of spectral methods, algorithms for estimating spectral parameters and low rank approximation of matrices.
I really like L. Lovász: Random walks on graphs: a survey
Beside Fan Chung's book, I also like Biggs'; it's short and sweet. I heard that Cvetković-Doob-Sachs is supposed to be encyclopedic but I haven't had a chance to check it out yet. Yes, I agree with Ryan than Lovasz' survey is a pleasure to read (so do most of his surveys).
2$\begingroup$ I have seen Cvetković-Doob-Sachs and agree that it is encyclopedic. Lots of examples worked out. Expensive though... $\endgroup$ Sep 10, 2010 at 21:13
Godsil and Royle's Algebraic Graph Theory is a good book too, though it has more than just spectral graph theory.
I found this lecture note to be of great help Michael W. Mahoney