This project for Georgia Tech’s Computational Data Analysis course explored scalable approximations for spectral clustering on large networks. Standard spectral clustering relies on the eigendecomposition of the graph Laplacian, which introduces an O(n^3) computational bottleneck that becomes prohibitive for graphs with millions of nodes.
To overcome this computational barrier, I implemented and evaluated two approximate eigendecomposition techniques across synthetic LFR benchmark graphs and real-world network datasets from Stanford SNAP (including DBLP, YouTube, and collaboration networks):
- Moment-Based Approximation: Uses simulated random walks to estimate the spectral density and eigenvalue distribution in sub-linear time, providing rapid analytical utility for network spectra.
- Nyström Method Approximation: Extrapolates eigenvectors from a small, random subsample of nodes to generate full spectral embeddings for K-Means clustering. This approach achieved up to a 29x runtime speedup over exact decomposition while maintaining high clustering fidelity and community detection accuracy (measured via Adjusted Rand Index and Normalized Mutual Information).