Introduction
Tensors are essential multi-way arrays for representing complex relationships, such as (Author × Word × Venue) interactions. While tensor factorization is a powerful tool for pattern discovery and missing entry prediction, traditional methods often assume real-valued data. However, real-world datasets are frequently discrete—social networks are binary, and purchase histories consist of counts. Applying standard Gaussian tools to such data typically yields suboptimal results. Furthermore, as datasets scale to millions of observations, traditional Bayesian methods like Gibbs sampling become computationally prohibitive.
Researchers at Duke University have addressed these challenges by developing PGCP (Polya-Gamma Canonical PARAFAC), a scalable probabilistic framework designed specifically for binary and count-valued tensor data.
Methodology
The PGCP framework is built upon three primary technical pillars:
- Polya-Gamma (PG) Augmentation: This core innovation utilizes a data augmentation strategy to "Gaussian-ify" non-conjugate likelihoods. By transforming logistic (binary) and negative binomial (count) distributions into a Gaussian-like form, the researchers enable simpler, closed-form parameter updates.
- Multiplicative Gamma Process (MGP) Prior: To avoid the manual selection of tensor rank, the MGP prior automatically shrinks redundant latent factors toward zero, allowing the model to learn the optimal rank directly from the data.
- Online Expectation-Maximization (EM): To achieve massive scalability, the authors implemented an online EM algorithm. By processing data in mini-batches and recursively updating sufficient statistics, the model eliminates the need to store the entire tensor in memory, facilitating the analysis of datasets with millions of entries.
Experimental Evaluation
The framework was evaluated across several diverse real-world datasets:
- Binary Tensors: Kinship (social relationships), Digg (user-story-tag interactions), and DBLP (author-conference-keyword relationships).
- Count Tensors: GDELT (geopolitical interactions), Scholars (author word usage), and Transactions (a massive dataset of 117,054 households and 67,095 items).
Results and Discussion
The proposed PGCP model demonstrated significant improvements in both accuracy and computational efficiency.
Convergence and Accuracy
In tensor completion tasks, PGCP consistently outperformed baselines such as Inf-Tucker and Poisson Tensor Factorization (PTF). A key finding is that the Online EM algorithm is not merely a faster alternative to Batch EM; it often discovers superior solutions by navigating the parameter space more dynamically.
Scalability to Massive Data
The framework's scalability was most evident on the Transactions dataset. While traditional Bayesian methods often fail on data of this magnitude, the online EM approach handled it efficiently.
Interpretability
By incorporating non-negativity constraints enabled by the PG augmentation, the model successfully extracted interpretable research topics from the Scholars dataset, such as "Machine Learning" and "Immunology."
Conclusion
PGCP provides a robust, generative framework for scalable tensor factorization of discrete data. By leveraging Polya-Gamma augmentation and online EM, it bridges the gap between probabilistic rigor and large-scale computational demands. Future work may extend this framework to categorical data and incorporate auxiliary side information to further enhance decomposition quality.
Summary updated