On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations

Xueyu Mao, Purnamrita Sarkar, Deepayan Chakrabarti
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2324-2333, 2017.

Abstract

The problem of finding overlapping communities in networks has gained much attention recently. Optimization-based approaches use non-negative matrix factorization (NMF) or variants, but the global optimum cannot be provably attained in general. Model-based approaches, such as the popular mixed-membership stochastic blockmodel or MMSB (Airoldi et al., 2008), use parameters for each node to specify the overlapping communities, but standard inference techniques cannot guarantee consistency. We link the two approaches, by (a) establishing sufficient conditions for the symmetric NMF optimization to have a unique solution under MMSB, and (b) proposing a computationally efficient algorithm called GeoNMF that is provably optimal and hence consistent for a broad parameter regime. We demonstrate its accuracy on both simulated and real-world datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-mao17a, title = {On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations}, author = {Xueyu Mao and Purnamrita Sarkar and Deepayan Chakrabarti}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {2324--2333}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/mao17a/mao17a.pdf}, url = {https://proceedings.mlr.press/v70/mao17a.html}, abstract = {The problem of finding overlapping communities in networks has gained much attention recently. Optimization-based approaches use non-negative matrix factorization (NMF) or variants, but the global optimum cannot be provably attained in general. Model-based approaches, such as the popular mixed-membership stochastic blockmodel or MMSB (Airoldi et al., 2008), use parameters for each node to specify the overlapping communities, but standard inference techniques cannot guarantee consistency. We link the two approaches, by (a) establishing sufficient conditions for the symmetric NMF optimization to have a unique solution under MMSB, and (b) proposing a computationally efficient algorithm called GeoNMF that is provably optimal and hence consistent for a broad parameter regime. We demonstrate its accuracy on both simulated and real-world datasets.} }
Endnote
%0 Conference Paper %T On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations %A Xueyu Mao %A Purnamrita Sarkar %A Deepayan Chakrabarti %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-mao17a %I PMLR %P 2324--2333 %U https://proceedings.mlr.press/v70/mao17a.html %V 70 %X The problem of finding overlapping communities in networks has gained much attention recently. Optimization-based approaches use non-negative matrix factorization (NMF) or variants, but the global optimum cannot be provably attained in general. Model-based approaches, such as the popular mixed-membership stochastic blockmodel or MMSB (Airoldi et al., 2008), use parameters for each node to specify the overlapping communities, but standard inference techniques cannot guarantee consistency. We link the two approaches, by (a) establishing sufficient conditions for the symmetric NMF optimization to have a unique solution under MMSB, and (b) proposing a computationally efficient algorithm called GeoNMF that is provably optimal and hence consistent for a broad parameter regime. We demonstrate its accuracy on both simulated and real-world datasets.
APA
Mao, X., Sarkar, P. & Chakrabarti, D.. (2017). On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:2324-2333 Available from https://proceedings.mlr.press/v70/mao17a.html.

Related Material