A Local Algorithm for Finding Well-Connected Clusters

Zeyuan Allen Zhu, Silvio Lattanzi, Vahab Mirrokni
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):396-404, 2013.

Abstract

Motivated by applications of large-scale graph clustering, we study random-walk-based LOCAL algorithms whose running times depend only on the size of the output cluster, rather than the entire graph. In particular, we develop a method with better theoretical guarantee compared to all previous work, both in terms of the clustering accuracy and the conductance of the output set. We also prove that our analysis is tight, and perform empirical evaluation to support our theory on both synthetic and real data. More specifically, our method outperforms prior work when the cluster is WELL-CONNECTED. In fact, the better it is well-connected inside, the more significant improvement we can obtain. Our results shed light on why in practice some random-walk-based algorithms perform better than its previous theory, and help guide future research about local clustering.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-allenzhu13, title = {A Local Algorithm for Finding Well-Connected Clusters}, author = {Allen Zhu, Zeyuan and Lattanzi, Silvio and Mirrokni, Vahab}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {396--404}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/allenzhu13.pdf}, url = {https://proceedings.mlr.press/v28/allenzhu13.html}, abstract = {Motivated by applications of large-scale graph clustering, we study random-walk-based LOCAL algorithms whose running times depend only on the size of the output cluster, rather than the entire graph. In particular, we develop a method with better theoretical guarantee compared to all previous work, both in terms of the clustering accuracy and the conductance of the output set. We also prove that our analysis is tight, and perform empirical evaluation to support our theory on both synthetic and real data. More specifically, our method outperforms prior work when the cluster is WELL-CONNECTED. In fact, the better it is well-connected inside, the more significant improvement we can obtain. Our results shed light on why in practice some random-walk-based algorithms perform better than its previous theory, and help guide future research about local clustering. } }
Endnote
%0 Conference Paper %T A Local Algorithm for Finding Well-Connected Clusters %A Zeyuan Allen Zhu %A Silvio Lattanzi %A Vahab Mirrokni %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-allenzhu13 %I PMLR %P 396--404 %U https://proceedings.mlr.press/v28/allenzhu13.html %V 28 %N 3 %X Motivated by applications of large-scale graph clustering, we study random-walk-based LOCAL algorithms whose running times depend only on the size of the output cluster, rather than the entire graph. In particular, we develop a method with better theoretical guarantee compared to all previous work, both in terms of the clustering accuracy and the conductance of the output set. We also prove that our analysis is tight, and perform empirical evaluation to support our theory on both synthetic and real data. More specifically, our method outperforms prior work when the cluster is WELL-CONNECTED. In fact, the better it is well-connected inside, the more significant improvement we can obtain. Our results shed light on why in practice some random-walk-based algorithms perform better than its previous theory, and help guide future research about local clustering.
RIS
TY - CPAPER TI - A Local Algorithm for Finding Well-Connected Clusters AU - Zeyuan Allen Zhu AU - Silvio Lattanzi AU - Vahab Mirrokni BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-allenzhu13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 396 EP - 404 L1 - http://proceedings.mlr.press/v28/allenzhu13.pdf UR - https://proceedings.mlr.press/v28/allenzhu13.html AB - Motivated by applications of large-scale graph clustering, we study random-walk-based LOCAL algorithms whose running times depend only on the size of the output cluster, rather than the entire graph. In particular, we develop a method with better theoretical guarantee compared to all previous work, both in terms of the clustering accuracy and the conductance of the output set. We also prove that our analysis is tight, and perform empirical evaluation to support our theory on both synthetic and real data. More specifically, our method outperforms prior work when the cluster is WELL-CONNECTED. In fact, the better it is well-connected inside, the more significant improvement we can obtain. Our results shed light on why in practice some random-walk-based algorithms perform better than its previous theory, and help guide future research about local clustering. ER -
APA
Allen Zhu, Z., Lattanzi, S. & Mirrokni, V.. (2013). A Local Algorithm for Finding Well-Connected Clusters. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):396-404 Available from https://proceedings.mlr.press/v28/allenzhu13.html.

Related Material