In machine learning, unsupervised discovery of latent structure has historically been approached from two distinct philosophical paradigms: linear algebra and Bayesian statistics.
The algebraic approach favors matrix factorization. Given a nonnegative data matrix $V$ (such as a document-term matrix or a graph adjacency matrix), it decomposes it into the product of two lower-rank nonnegative matrices, $W$ and $H$, by minimizing a reconstruction error. The statistical approach favors generative latent variable models. It assumes data is generated by sampling from hidden probability distributions, and uncovers these distributions by maximizing the log-likelihood of the observed data.
While these two worlds look entirely different on the surface—one manipulating geometric spaces and the other calculating probability densities—they are often mathematically identical. A rich body of research has revealed that under specific normalization constraints and error metrics, optimizing a matrix factorization objective is exactly equivalent to maximizing the likelihood of a probabilistic latent variable model.
The Core Bridge: KL Divergence and Normalization
To understand why this equivalence holds, we must look at how we measure the distance between a data matrix $V$ and its factorization $WH$. If we use the standard Euclidean distance, the connection to statistics is weak. However, if we use the generalized Kullback-Leibler (KL) divergence as our loss function, a direct bridge appears.
The generalized KL divergence between the observed matrix $V$ and its approximation $\hat{V} = WH$ is defined as:
$$D_{KL}(V \parallel WH) = \sum_{i,j} \left( V_{ij} \log \frac{V_{ij}}{(WH)_{ij}} - V_{ij} + (WH)_{ij} \right)$$
Now, consider a probabilistic model like Probabilistic Latent Semantic Indexing (PLSI), which models the joint probability of documents and words via a latent topic variable $z$:
$$P(d, w) = \sum_{z} P(z) P(d|z) P(w|z)$$
As demonstrated by Tao Li et al., when the factorization matrices $W$ and $H$ are subject to $L_1$ normalization (meaning their columns or rows sum to 1), they behave exactly like conditional probability distributions. Under this constraint, minimizing the KL divergence of the matrix factorization yields the exact same objective function as maximizing the log-likelihood of the PLSI model.
This is not a mere coincidence of optimal points; the entire optimization landscape is identical. Bhiksha Raj et al. extended this insight by showing a strict numerical equivalence between the iterative parameter updates. The multiplicative update rules widely used to solve Nonnegative Matrix Factorization (NMF) are mathematically identical to the Expectation-Maximization (EM) updates used to solve latent class models.
Extending the Equivalence to Networks
This algebraic-probabilistic duality is not limited to text or general tabular data; it extends deeply into network analysis and community detection.
In graph analysis, the Stochastic Block Model (SBM) is a popular generative model where nodes belong to latent communities, and the probability of an edge forming between two nodes depends entirely on their community memberships. When nodes can belong to multiple communities simultaneously, this is known as a Mixed-Membership Stochastic Block Model (MMSBM).
On the algebraic side, graphs are represented by symmetric adjacency matrices, which can be factored using Symmetric NMF ($V \approx W W^T$). Xueyu Mao et al. proved that under conditions where communities primarily interact internally, symmetric NMF is mathematically equivalent to the MMSBM.
Expanding on this connection, Zhongyuan Zhang et al. systematically derived the algebraic equivalents for a wide array of SBM variants. They demonstrated that maximizing the log-likelihood of standard, degree-corrected, bipartite, directed, and even signed SBMs maps directly to minimizing specific constrained NMF objectives. The statistical assumptions of the network model (such as assuming edge weights follow a Poisson or Normal distribution) dictate the specific constraints and distance metrics required in the corresponding matrix factorization.
| Probabilistic Model | Matrix Factorization Equivalent |
|---|---|
| Probabilistic Latent Semantic Indexing (PLSI) | Standard NMF (with KL Divergence & $L_1$ Normalization) |
| Mixed-Membership Stochastic Block Model | Symmetric NMF ($V \approx W W^T$) |
| Variational Stochastic Block Models (SBMs) | Constrained NMF (with specific structural constraints) |
| Bi-mixture PLSA (Co-clustering) | Tri-Factorization NMF ($V \approx F S G^T$) |
Co-Clustering and Tri-Factorization
The equivalence also scales to more complex, multi-modal data structures. For instance, in tasks like multi-document summarization, one might want to simultaneously cluster documents and sentences. This requires a co-clustering framework.
In the probabilistic domain, this is achieved via bi-mixture latent variable models, which decouple the cluster assignments of different data types. Chao Shen et al. established that this bi-mixture probabilistic framework is mathematically equivalent to NMF Tri-Factorization. Instead of splitting a matrix into two pieces ($WH$), tri-factorization introduces a core matrix $S$ bounded by two factor matrices ($FSG^T$). The probabilistic mixtures map perfectly onto the algebraic interactions of these three matrices, providing a rigid linear-algebraic foundation for what otherwise appears to be a highly complex statistical simulation.
Why This Equivalence Matters
Understanding that matrix factorizations and probabilistic latent variable models are two sides of the same coin is not just theoretically satisfying—it unlocks significant practical advantages for algorithm design and analysis.
1. Escaping Local Minima
Even though the objective functions of NMF and PLSI can be identical, the algorithms used to solve them (Multiplicative Updates vs. EM) navigate the optimization landscape differently. Because they take different paths, they tend to get trapped in different local minima. As exploited by Tao Li et al., researchers can design hybrid algorithms that alternate between algebraic updates and statistical updates, effectively "jumping" out of sub-optimal local choices to find superior global solutions.
2. Importing Theoretical Guarantees
Statistical models can be notoriously difficult to analyze for convergence and uniqueness. By mapping a probabilistic model to a matrix factorization, researchers can leverage geometric and spectral insights from linear algebra. For example, Xueyu Mao et al. utilized this duality to create GeoNMF, a fast, spectral algorithm that provides provable theoretical guarantees for community recovery while running up to 100x faster than traditional variational statistical methods.
3. Seamless Model Extensions
When NMF is reinterpreted as a probabilistic model, it inherits the entire toolkit of Bayesian statistics. As noted by Bhiksha Raj et al., this makes it straightforward to incorporate prior knowledge via Dirichlet or Gamma priors, handle complex tensorial data structures, and model shift invariances—extensions that would be highly unintuitive to design purely within a rigid linear algebra framework.
Key Foundational Work
Probabilistic Latent Variable Models as Nonnegative Factorizations (2008) — contributed 2 concept elements to this direction.
Nonnegative Matrix Factorization and Probabilistic Latent Semantic Indexing: Equivalence Chi-Square Statistic, and a Hybrid Method (2006) — contributed 2 concept elements to this direction.