Community detection, or graph clustering, is a task to group network nodes into distinct communities. For weighted networks, the transformation of edge weights—using methods like logarithmic scaling or thresholding—can significantly influence clustering performance. Different transformations often yield distinct and sometimes notably improved community separations.

This project seeks to identify optimal edge weight transformations for a range of spectral clustering algorithms, with a focus on maximizing community separation in the embedded space.

Building on [1], which demonstrated that spectral embedding can be modeled with a Gaussian mixture model, we leverage recent advances in clustering mixture models (such as [2], [3]) to examine the effect of edge weight transformations on clustering error rates. Ultimately, we aim to determine whether optimal edge weight transformations can be identified in a data-driven manner.

Related paper:
[1] Gallagher, Ian, et al. "Spectral embedding of weighted graphs." Journal of the American Statistical Association 119.547 (2024): 1923-1932. [2] Dreveton, Gözeten, Grossglauser, Thiran (2024). Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models. Proceedings of Thirty Seventh Conference on Learning Theory  247:1451-1485
[3] Xin Chen and Anderson Y. Zhang. "Optimal clustering in anisotropic Gaussian mixture models." arXiv preprint arXiv:2101.05402 (2021).