The AL$\ell_0$CORE Tensor Decomposition for Sparse Count Data

AISTATS 2024

TL;DR

This paper introduces AlloCORE, a novel probabilistic tensor decomposition method that efficiently represents sparse, high-dimensional count data. By introducing a sparsity constraint on the core tensor, AlloCORE achieves the representational richness of Tucker decomposition at a fraction of the computational cost, making complex tensor analysis more accessible.

What Problem Does This Paper Address?

Tensor decomposition methods are powerful tools for uncovering latent structure in multi-way data. However, two dominant methods, Canonical Polyadic (CP) and Tucker decomposition, have limitations. CP is computationally efficient but can be less expressive. Tucker decomposition offers richer representations but suffers from an "exponential blowup" in computational cost as the number of latent factors increases, making it infeasible for large, complex datasets. This is particularly problematic for sparse count tensors, common in domains like network analysis, where the desire for detailed representations clashes with computational constraints. AlloCORE aims to bridge this gap by providing a method that combines the expressiveness of Tucker with the computational tractability needed for large, sparse data.

Methods

AlloCORE is a probabilistic Tucker decomposition with a key innovation: a constraint on the lo-norm of the core tensor, meaning it can have at most $Q$ non-zero elements. The locations and values of these non-zero elements are treated as latent variables and inferred using a sampling-based approach. This approach, specifically a Gibbs sampler, iteratively re-samples the coordinates of the non-zero locations from their complete conditionals. This allows the model to explore the latent space efficiently without the exponential cost associated with full Tucker decomposition. The paper also proposes a Bayesian Poisson AlloCORE model, tailored for count data, which leverages Poisson additivity for efficient inference.

Datasets

The paper evaluates AlloCORE on two real-world datasets:

  • TERRIER dataset: This dataset codes for international relations events and is used to construct a 4-mode count tensor.
  • ICEWS dataset: Similar to TERRIER, this dataset also codes for international relations events and is used to create a 4-mode count tensor.

The authors do not introduce new benchmarks but rather use these existing datasets to demonstrate the effectiveness of their proposed method.

Key Insights and Ideas

  • Sparsity as a Computational Enabler: The core insight is that by enforcing sparsity on the core tensor (not just the observed data), AlloCORE can achieve Tucker-like expressiveness without the computational burden. This is a crucial departure from methods that only consider data sparsity.
  • Sampling-Based Inference is Key: The paper highlights that the computational advantage of AlloCORE is unlocked by its sampling-based inference strategy, which efficiently explores the latent space of non-zero core locations. This contrasts with optimization-based approaches that might still suffer from the exponential blowup.
  • Bridging CP and Tucker: AlloCORE offers a compelling middle ground, inheriting the computational benefits of CP (due to sparsity) while retaining the richer representational capacity of Tucker.

Key Results

  • Computational Efficiency: AlloCORE typically requires only a tiny fraction (e.g., 1%) of the core tensor's elements to achieve performance comparable to full Tucker decomposition, leading to significant speedups. For instance, AlloCORE can match full Tucker performance in approximately 1 hour for 5,000 MCMC iterations, while a state-of-the-art EM implementation for full Tucker (NNTuck) takes around 125 seconds per iteration.
  • Predictive Performance: AlloCORE consistently outperforms CP and full Tucker decomposition in predictive performance across experiments, especially as the number of latent classes ($Q$) increases.
  • Interpretable Latent Structure: The method successfully uncovers interpretable latent structures in international relations data, identifying community-community interactions, action topics, and temporal regimes. The qualitative analysis reveals patterns related to major wars, demonstrating the model's ability to capture complex relational dynamics.

Limitations and Future Work

  • Hyperparameter Tuning: While AlloCORE is less sensitive to the number of latent factors than full Tucker, the choice of $Q$ still influences performance and requires tuning.
  • Inference for Other Parameters: The paper focuses on the sampling-based approach for core locations ($k_q$) and suggests that interleaving this with point estimation or variational inference for other parameters could be explored.
  • Theoretical Guarantees: While empirical results are strong, further theoretical investigation into the properties of AlloCORE, particularly regarding the recovery of ground-truth parameters in synthetic settings, is suggested for future work.
  • Broader Applicability: The authors note that the motif of "allocated sparsity" could be extended to other tensor decomposition models and methods, opening avenues for future research.

Summary updated

BibTeX
@inproceedings{2024al,
  title = {{The AL$\textbackslash\{\}ell\_0$CORE Tensor Decomposition for Sparse Count Data}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
}
Figure