On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Multiplicative updates for symmetric-cone factorizations
Given a matrix $X\in \mathbb{R}^{m\times n}_+$ with non-negative entries, the cone factorization problem over a cone $\mathcal{K}\subseteq \mathbb{R}^k$ concerns computing $\{ a_1,\ldots, a_{m} \} \subseteq \mathcal{K}$ …
Asymmetric Semi-Nonnegative Matrix Factorization for Directed Graph Clustering
Graph clustering is a fundamental task in the network analysis, which is essential for many modern applications. In recent years, Nonnegative Matrix Factorization (NMF) has been effectively used to discover cluster struc…
ClusteringGraph ClusteringAsymmetric Semi-Nonnegative Matrix Factorization for Directed Graph Clustering
Graph clustering is a fundamental task in the network analysis, which is essential for many modern applications. In recent years, Nonnegative Matrix Factorization (NMF) has been effectively used to discover cluster struc…
ClusteringGraph ClusteringEstimating Mixed-Memberships Using the Symmetric Laplacian Inverse Matrix
Mixed membership community detection is a challenging problem. In this paper, to detect mixed memberships, we propose a new method Mixed-SLIM which is a spectral clustering method on the symmetrized Laplacian inverse mat…
ClusteringCommunity DetectionAlgorithms for Approximate Subtropical Matrix Factorization
Matrix factorization methods are important tools in data mining and analysis. They can be used for many tasks, ranging from dimensionality reduction to visualization. In this paper we concentrate on the use of matrix fac…
Dimensionality Reduction