  Symmetric Nonnegative Matrix Factorization (SNMF) models arise naturally as
simple reformulations of many standard clustering algorithms including the
popular spectral clustering method. Recent work has demonstrated that an
elementary instance of SNMF provides superior clustering quality compared to
many classic clustering algorithms on a variety of synthetic and real world
data sets. In this work, we present novel reformulations of this instance of
SNMF based on the notion of variable splitting and produce two fast and
effective algorithms for its optimization using i) the provably convergent
Accelerated Proximal Gradient (APG) procedure and ii) a heuristic version of
the Alternating Direction Method of Multipliers (ADMM) framework. Our two
algorithms present an interesting tradeoff between computational speed and
mathematical convergence guarantee: while the former method is provably
convergent it is considerably slower than the latter approach, for which we
also provide significant but less stringent mathematical proof regarding its
convergence. Through extensive experiments we show not only that the efficacy
of these approaches is equal to that of the state of the art SNMF algorithm,
but also that the latter of our algorithms is extremely fast being one to two
orders of magnitude faster in terms of total computation time than the state of
the art approach, outperforming even spectral clustering in terms of
computation time on large data sets.
