Graphical model for tensor factorization by sparse sampling

Angelo Giorgio Cavaliere, Riki Nagasawa, Shuta Yokoi, Tomoyuki Obuchi, Hajime YoshinoarXiv 2025 · DOI · arXiv

Abstract

Tensor factorization and completion are essential for modern machine learning, particularly in large-scale recommendation systems. While much research focuses on low-rank or full-rank tensors, many real-world datasets exist in an intermediate regime where the rank is high but significantly smaller than the number of items. This paper presents a theoretical framework for reconstructing such tensors from extremely sparse measurements. By analyzing a "dense limit" ($N \gg M \gg 1$), the authors provide exact performance predictions and introduce a Generalized Approximate Message Passing (G-AMP) algorithm. Their findings reveal critical phase transitions and demonstrate that a sophisticated cumulant expansion is necessary to avoid the pitfalls of standard Gaussian approximations in high-rank settings.

Introduction

The challenge of filling in missing entries in multi-dimensional data arrays—tensor completion—is a cornerstone of modern data science. Most existing literature addresses two extremes: low-rank tensors, where the hidden dimension $M$ is a small constant, or extensive-rank tensors, where $M$ scales linearly with the number of data points $N$.

However, a significant "middle ground" remains under-explored: the regime where the rank is relatively high but still much smaller than the total number of items. This paper tackles this intermediate regime under conditions of sparse sampling, providing a rigorous statistical mechanical analysis of the conditions required for perfect reconstruction.

Methods and Graphical Representation

The authors employ a combination of statistical physics and algorithmic information theory to map the tensor factorization problem onto a graphical model.

The "Dense Limit" and Factor Graphs

The core of the analysis lies in the "dense limit," defined as the asymptotic regime where $N \gg M \gg 1$. This allows the use of the Replica Method to calculate the theoretical limits of inference, known as Bayes-optimal performance. The problem is represented as a factor graph where nodes represent variables and factors represent measurements.

Factor graph representations for different tensor orders $p$ and the overall network structure.

As shown in the figure above, the order of the tensor $p$ determines the connectivity of the factor nodes. For $p=2$, we have matrix factorization; for $p \ge 3$, we deal with higher-order tensors.

Algorithmic Innovations

A key technical innovation is the use of a cumulant expansion to handle interactions between variables. The authors demonstrate that the standard "Gaussian ansatz"—a common shortcut in physics-based inference—fails in certain fully connected systems. Their more sophisticated expansion provides a robust derivation of the "TAP equations" (mean-field equations) for these high-rank systems.

From these equations, they derive a "relaxed" version of Belief Propagation (r-BP), which is simplified into a Generalized Approximate Message Passing (G-AMP) algorithm. This algorithm is computationally efficient, with a scaling of $O(NM^2)$, making it practical for large-scale datasets. The average performance of G-AMP is tracked over time using State Evolution (SE) equations, which perfectly match theoretical predictions.

Key Insights: The "Hard" Region of Tensors

The study reveals fundamental differences between matrix and tensor factorization:

  • Phase Transitions: For tensors of order $p \ge 3$, the system undergoes a "first-order" phase transition. This creates a "hard" region where reconstruction is theoretically possible (the information is present in the data) but computationally impossible for standard algorithms, which become trapped in suboptimal local minima.
  • Matrix vs. Tensor: In contrast, matrix factorization ($p=2$) generally exhibits a continuous transition. This makes it significantly easier to initiate inference from a random guess compared to higher-order tensors.
  • Mixed Measurements: An intriguing finding is that "contaminating" a hard $p=3$ problem with a small number of $p=2$ measurements can destabilize "bad" local minima, potentially rendering previously unsolvable problems tractable.

Results and Validation

The paper focuses on a "Teacher-Student" setting using synthetic data to establish theoretical benchmarks. They evaluated performance across various priors (Ising and Gaussian) and noise models (Additive Gaussian and Sign Output).

Key results include:

  1. Exact Asymptotics: The first precise asymptotic results for tensor completion in the $N \gg M \gg 1$ regime with sparse measurements.
  2. Threshold Identification: The identification of the "Easy-to-Hard" threshold ($\alpha_P$). For instance, in the Ising case with $p=2$, the authors found that if the sampling rate $\alpha$ is below approximately 1.30, perfect reconstruction is impossible from a random start, even in the absence of noise.
  3. Algorithm Consistency: Numerical experiments on finite-size systems (e.g., $N=5000, M=400$) showed excellent agreement with State Evolution predictions, confirming the validity of the "dense limit" theory for practical applications.

Limitations and Future Directions

While the framework is robust, it currently assumes a uniform sampling pattern based on regular random graphs. Real-world data often features non-uniform or "clumpy" missingness, which may introduce loop effects not captured by the current model.

Future work aims to extend this theory to "multi-species" models to address problems like Dictionary Learning and to incorporate node-to-node fluctuations in connectivity, better reflecting the structure of real-world social networks and recommendation databases.

Summary updated

BibTeX
@misc{cavaliere2025graphical,
  author = {Angelo Giorgio Cavaliere and Riki Nagasawa and Shuta Yokoi and Tomoyuki Obuchi and Hajime Yoshino},
  title = {{Graphical model for tensor factorization by sparse sampling}},
  year = {2025},
  eprint = {2510.17886},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.17886},
}
Figure