Labeled Graph Clustering via Projected Gradient Descent

Shiau Hong Lim, Gregory Calvez
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1988-1997, 2018.

Abstract

Advances in recovering low-rank matrices from noisy observations have led to tractable algorithms for clustering from general pairwise labels with provable performance guarantees. Based on convex relaxation, it has been shown that the ground truth clusters can be recovered with high probability under a generalized stochastic block model by solving a semidefinite program. Although tractable, the algorithm is typically too slow for sufficiently large problems in practice. Inspired by recent advances in non-convex approaches to low-rank recovery problems, we propose an algorithm based on projected gradient descent that enjoys similar provable guarantees as the convex counterpart, but can be orders of magnitude faster. Our theoretical results are further supported by encouraging empirical results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-lim18b, title = {Labeled Graph Clustering via Projected Gradient Descent}, author = {Lim, Shiau Hong and Calvez, Gregory}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1988--1997}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/lim18b/lim18b.pdf}, url = {https://proceedings.mlr.press/v84/lim18b.html}, abstract = {Advances in recovering low-rank matrices from noisy observations have led to tractable algorithms for clustering from general pairwise labels with provable performance guarantees. Based on convex relaxation, it has been shown that the ground truth clusters can be recovered with high probability under a generalized stochastic block model by solving a semidefinite program. Although tractable, the algorithm is typically too slow for sufficiently large problems in practice. Inspired by recent advances in non-convex approaches to low-rank recovery problems, we propose an algorithm based on projected gradient descent that enjoys similar provable guarantees as the convex counterpart, but can be orders of magnitude faster. Our theoretical results are further supported by encouraging empirical results. } }
Endnote
%0 Conference Paper %T Labeled Graph Clustering via Projected Gradient Descent %A Shiau Hong Lim %A Gregory Calvez %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-lim18b %I PMLR %P 1988--1997 %U https://proceedings.mlr.press/v84/lim18b.html %V 84 %X Advances in recovering low-rank matrices from noisy observations have led to tractable algorithms for clustering from general pairwise labels with provable performance guarantees. Based on convex relaxation, it has been shown that the ground truth clusters can be recovered with high probability under a generalized stochastic block model by solving a semidefinite program. Although tractable, the algorithm is typically too slow for sufficiently large problems in practice. Inspired by recent advances in non-convex approaches to low-rank recovery problems, we propose an algorithm based on projected gradient descent that enjoys similar provable guarantees as the convex counterpart, but can be orders of magnitude faster. Our theoretical results are further supported by encouraging empirical results.
APA
Lim, S.H. & Calvez, G.. (2018). Labeled Graph Clustering via Projected Gradient Descent. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1988-1997 Available from https://proceedings.mlr.press/v84/lim18b.html.

Related Material