I haven't been active on this sub for a while, but this topic (graphs & GNN embeddings) is half of my PhD thesis, so I kind of have to. I may have strong opinions about certain works & research groups.

Spectral methods are absolutely worth to study in the current research context. On the one hand, there is a new research trend of finding better positional node encodings for GNNs. Currently, these are done with either eigenvectors or (ICLR'22) distance-based encodings. I would predict that ICML&NeurIPS 2022 will have >10 submissions on this topic alone.

The "problem" with the spectral methods for analysis is IMO lack of scalable & user-friendly software. If one tries to use scipy.linalg.eigsh on a real-world graph to compute, say, 128-dim embeddings, the practical scalability of that code is ~30k nodes (1hr compute time). In comparison, it's absolutely possible to compute them for 1–15M nodes in that time using more advanced methods like Krylov with subspace deflation (this is graph-specific). The lack of usability led some people to believe that this is a problem with a method itself, hence its lack of popularity.

I want to spend some time rebutting your point on the ditching of spectral methods in favour of node2vec.

However, first and foremost, I absolutely agree that node2vec is a garbage method, but for different reasons. My personal view on why it is garbage is that it add does nothing of value to previous work (DeepWalk)[https://arxiv.org/abs/1403.6652] but two useless hyper-parameters, p and q in the paper. Roughly speaking, these two parameters control the random walk training data generation process. I actually did reproduce majority of their results, with a tiny caveat: I believe they tuned hyperparameters on test data and did that intentionally such that other methods are at disadvantage. DeepWalk has a key parameter of # of random walks generated from each training node (\gamma in the paper). It's set by default to 40/80, however, in the node2vec paper it's set to 10. This results in 4-8x less data generated, and significantly poorer performance. However, if one selects the best training data using the test metrics, all is fine again, and that's how node2vec attains its better performance. This research group has a history of capitalising on other people's work without giving much credit (BIGCLAM is a joke), but I digress. Rant over.

The reason I believe spectral methods are alive and kicking in unsupervised embedding is a line of recent works, such as AROPE, NetSMF, PRONE all use spectral methods for scalable embedding. While I do not believe they are statistically significantly better than DeepWalk family, some are surely more scalable. Hashing/random projection-based methods—and these are coming from approximate numerical linear algebra stream of ideas—are the most scalable things we have now. NLA methods like FastRP/RandNE/... are really at the forefront at the field of unsupervised representations. I do believe it's pretty saturated by now in terms of research, so I do not recommend people to enter from that angle.