Orthogonal Symmetric Nonnegative Matrix Tri-Factorization

Symmetric nonnegative matrix tri-factorization (trisymNMF) factorizes a symmetric input n-by-n matrix, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex>, using two matrices, a nonnegative <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex>-by-<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$r$</tex> matrix <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$W$</tex> and a nonnegative symmetric <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$r$</tex>-by-<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$r$</tex> matrix <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S$</tex>, such that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X\approx WSW^{\mathrm{T}}$</tex>. trisym-NMF has been used in many applications, including topic modeling and community detection. In the latter application, each column of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$W$</tex> corresponds to a community, and the entries of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S$</tex> indicate the interactions between the communities. In this paper, we focus on the particular case of an orthogonal matrix <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$W$</tex>, corresponding to the case of disjoint communities. We first analyse this problem, and in particular provide an identifiability result. Then we propose an efficient coordinate descent method that exploits the properties of the problem to solve it efficiently. We also propose a new initialization strategy, provably correct in the noiseless case and robust to noise, relying on smooth separable NMF. Empirically, we show that our method outperforms the state of the art on synthetic and real data.