🏢 University of Utah
On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
·1629 words·8 mins·
loading
·
loading
AI Theory
Robustness
🏢 University of Utah
Spectral algorithms for graph bisection show surprising robustness to helpful adversaries in semirandom models, with unnormalized Laplacian consistently outperforming the normalized one.