Contact: Daichi Kuroda
Community detection, also known as graph clustering, involves partitioning the nodes of a network into distinct groups or communities. One of the most widely used approaches for this task is spectral clustering, which leverages spectral properties of matrices associated with graphs—such as the normalized Laplacian, unnormalized Laplacian, or the adjacency matrix.
Despite its popularity, the impact of different Laplacian choices on the resulting community structures—especially in terms of robustness—has not been thoroughly examined. For instance, while the normalized Laplacian is often considered more favorable than the unnormalized version [1], recent work [2] has shown that the unnormalized Laplacian can occasionally outperform its normalized counterpart, depending on the setting.
The goal of this project is to systematically evaluate various spectral clustering techniques through numerical experiments on both synthetic and real-world networks. We aim to identify conditions under which these methods exhibit significant differences and to explore metrics (e.g., Chernoff information [3,4]) that can help guide the selection of the most appropriate spectral method for a given network.
[1] Von Luxburg, Ulrike. "A tutorial on spectral clustering." Statistics and computing 17 (2007): 395-416.
[2] Bhaskara, Aditya, et al. "On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models." Advances in Neural Information Processing Systems 37 (2024): 112731-112776.
[3] Gallagher, Ian, et al. "Spectral embedding of weighted graphs." Journal of the American Statistical Association 119.547 (2024): 1923-1932.
[4] Tang, Minh, and Carey E. Priebe. "Limit theorems for eigenvectors of the normalized Laplacian for random graphs." (2018): 2360-2415.
Send your CV and transcript to Daichi at daichi.kuroda@epfl.ch.