Tensor factorization using auxiliary information

Atsuhiro Narita, Kohei Hayashi, Ryota Tomioka, Hisashi Kashima

Abstract

Most of the existing analysis methods for tensors (or multi-way arrays) only assume that tensors to be completed are of low rank. However, for example, when they are applied to tensor completion problems, their prediction accuracy tends to be significantly worse when only a limited number of entries are observed. In this paper, we propose to use relationships among data as auxiliary information in addition to the low-rank assumption to improve the quality of tensor decomposition. We introduce two regularization approaches using graph Laplacians induced from the relationships, one for moderately sparse cases and the other for extremely sparse cases. We also give present two kinds of iterative algorithms for approximate solutions: one based on an EM-like algorithms which is stable but not so scalable, and the other based on gradient-based optimization which is applicable to large scale datasets. Numerical experiments on tensor completion using synthetic and benchmark datasets show that the use of auxiliary information improves completion accuracy over the existing methods based only on the low-rank assumption, especially when observations are sparse.

Introduction

Tensors, or multi-way arrays, are essential for modeling complex, multi-dimensional relationships, such as (user, item, time) interactions in recommendation systems. A critical task in this domain is tensor completion: estimating missing entries based on a subset of observed data.

Standard tensor completion methods typically rely on a "low-rank" assumption, positing that complex interactions can be explained by a small number of latent factors. However, this assumption often fails in highly sparse regimes—where 95% to 99% of the data is missing—leading to a significant drop in prediction accuracy. In practical scenarios, we often possess side information, such as user demographics or item categories, which can be represented as similarity relationships. This paper explores how to mathematically integrate this auxiliary similarity data into tensor factorization to maintain predictive performance even in extremely sparse or "cold-start" conditions.

Methodology

The authors propose enhancing the objective functions of two foundational tensor factorization models—CP (CANDECOMP/PARAFAC) and Tucker decompositions—by incorporating regularization terms derived from auxiliary similarity matrices.

CP and Tucker Decompositions

CP decomposition approximates a tensor as a sum of rank-one tensors, while Tucker decomposition decomposes a tensor into a core tensor multiplied by a matrix along each mode.

CP decomposition approximates a tensor as a sum of rank-one tensors.
Tucker decomposition decomposes a tensor into a core tensor and factor matrices.

Regularization Approaches

Two specific regularization strategies are introduced:

  1. Within-mode regularization: This approach regularizes each mode independently using graph Laplacians. By penalizing differences between latent factors of similar objects, the model is forced to learn representations that respect the auxiliary similarity data.
  2. Cross-mode regularization: This more aggressive technique uses the Kronecker product of similarity matrices to co-regularize combinations of elements across different modes. This is particularly effective for "bursty" missing data or cold-start scenarios.

Optimization Algorithms

To solve these regularized objective functions, the authors provide two algorithmic frameworks:

  • EM-like approach: This method iteratively imputes missing values with current estimates and then decomposes the resulting dense tensor. While stable for small datasets, it is computationally intensive.
  • Gradient-based optimization (L-BFGS): This approach optimizes factors by considering only observed entries. Its complexity scales linearly with the number of observations, making it suitable for large-scale applications.

Experimental Evaluation

The proposed methods were evaluated using one synthetic dataset and three real-world datasets:

  • Synthetic dataset: A 30x30x30 tensor with correlated objects to establish baseline performance.
  • Flow injection: A 12x100x89 tensor representing chemical substances, wavelengths, and reaction times.
  • Licorice: An 18x241x12 tensor from an odor sensing system.
  • Delicious (hetrec2011-delicious-2k): A massive, highly sparse 1,867 x 69,223 x 40,897 binary tensor of (user, URL, tag) relationships.

Key Insights and Results

Performance in Sparse Regimes

In scenarios with extreme element-wise sparsity (99% missing data), standard CP and Tucker decompositions exhibit high Mean Squared Error (MSE). The proposed regularized methods significantly stabilize performance, maintaining low MSE. For slice-wise sparsity (cold-start problems), cross-mode regularization consistently outperformed both standard and within-mode methods.

The Role of Context

When data is extremely sparse, the low-rank assumption alone is insufficient because the solution space is too large. Auxiliary data acts as an anchor, guiding the factorization toward a structurally logical solution. Interestingly, the added complexity of regularization does not necessarily increase total computation time; the smoother objective landscape often leads to faster convergence, requiring fewer iterations.

Scalability

The gradient-based optimization successfully handled the massive Delicious dataset, which contains over 437,000 observed elements within a space of trillions of possible entries— a task that was unfeasible for the EM-like approach.

Conclusion and Future Work

While the EM-like approach is stable for small datasets, gradient-based methods are necessary for scalability, though they may require careful tuning in extreme sparsity. Current limitations include the reliance on squared loss functions, which assume Gaussian noise.

Future research directions include extending this framework to non-Gaussian probabilistic models (e.g., exponential family loss functions for binary data) and integrating auxiliary information with modern convex formulations, such as trace norm constraints, to further enhance stability and predictive power.

Summary updated

Abstract

Most of the existing analysis methods for tensors (or multi-way arrays) only assume that tensors to be completed are of low rank. However, for example, when they are applied to tensor completion problems, their prediction accuracy tends to be significantly worse when only a limited number of entries are observed. In this paper, we propose to use relationships among data as auxiliary information in addition to the low-rank assumption to improve the quality of tensor decomposition. We introduce two regularization approaches using graph Laplacians induced from the relationships, one for moderately sparse cases and the other for extremely sparse cases. We also give present two kinds of iterative algorithms for approximate solutions: one based on an EM-like algorithms which is stable but not so scalable, and the other based on gradient-based optimization which is applicable to large scale datasets. Numerical experiments on tensor completion using synthetic and benchmark datasets show that the use of auxiliary information improves completion accuracy over the existing methods based only on the low-rank assumption, especially when observations are sparse.
BibTeX
@inproceedings{narita2011tensor,
  author = {Atsuhiro Narita and Kohei Hayashi and Ryota Tomioka and Hisashi Kashima},
  title = {{Tensor factorization using auxiliary information}},
  booktitle = {ECML/PKDD},
  year = {2011},
  doi = {10.1007/978-3-642-23783-6\_32},
}
Figure