sometimes spectral algorithms fail

[[concept]]
Takeaway

Even by doing spectral embedding or feature-aware spectral embeddings, since we have to fix c and κ (the number of eigenvectors we use) our spectral algorithms might fail. In practice, spectral algorithms fail above the information theoretic threshold (sometimes, significantly above that threshold!)

Mentions

File
2025-02-12 graphs lecture 7