Tensor Factorization Using Auxiliary Information

Atsuhiro Narita, Kohei Hayashi, Ryota Tomioka, Hisashi Kashima

TL;DR

Tensor completion usually relies on the assumption that the underlying data has a low rank, but this approach falls apart when observations are extremely sparse. This paper introduces a method to incorporate auxiliary information—like similarities between users or items—as graph Laplacian regularization terms in CP and Tucker decompositions. This dramatically improves missing value imputation accuracy in highly sparse and "cold-start" scenarios without increasing overall computation time.

What Problem Does This Paper Address?

Tensors (multi-way arrays) are incredibly useful for modeling complex, multi-object relationships, such as (user, item, time) interactions in recommendation systems. A common task in this domain is tensor completion: guessing missing entries based on the observed ones.

Standard tensor completion methods assume the data is "low-rank" (i.e., the complex interactions can be explained by a small number of latent factors). However, if the tensor is highly sparse—say, 95% to 99% of the data is missing—the low-rank assumption alone isn't enough, and prediction accuracy plummets. In the real world, we rarely only have the interaction data; we usually have side information, like user demographics or item categories. The authors tackle the problem of how to mathematically inject this auxiliary similarity data into tensor factorization to rescue predictive performance in extremely sparse regimes.

Methods

The authors modify the standard objective functions for two popular tensor factorizations—CP (CANDECOMP/PARAFAC) and Tucker decompositions—by adding regularization terms derived from auxiliary similarity matrices. They propose two variants:

  1. Within-mode regularization: Regularizes each mode (dimension) independently using graph Laplacians. If two objects are highly similar in the auxiliary data, the model forces their learned latent factor vectors to be similar.
  2. Cross-mode regularization: Uses the Kronecker product of the similarity matrices to co-regularize combinations of elements across different modes simultaneously. This is a more aggressive approach tailored for "bursty" missing data.

To solve these new objective functions, they provide two algorithmic frameworks:

  • An EM-like approach: Iteratively imputes missing values with current estimates and decomposes the resulting dense tensor. It is highly stable but computationally heavy.
  • Gradient-based optimization (L-BFGS): Optimizes the factors by looking only at the observed entries. This scales linearly with the number of observed elements, making it viable for massive datasets.

Datasets

The authors evaluated their methods on one synthetic and three real-world datasets:

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

Key Insights and Ideas

  • Context is King in Sparse Data: When data is missing at extreme rates (99%), or missing entirely for specific objects (a "slice-wise" missing or cold-start problem), the low-rank assumption fails because there are too many ways to fit the sparse points. Auxiliary data acts as an anchor, guiding the factorization toward a logical structure.
  • Cross-Mode Shines in Cold Starts: Within-mode regularization is sometimes too conservative for slice-wise missing data (e.g., a brand new user with zero interactions). Cross-mode regularization bridges this gap by inducing dense similarities across the entire tensor structure, allowing the model to infer behavior based on similar triplets of objects.
  • Regularization Speeds Up Convergence: Counterintuitively, adding complex regularization math didn't increase total computation time. By smoothing the objective function's landscape, the algorithms required fewer iterations to converge, effectively canceling out the extra per-iteration computational cost.

Key Results

  • Element-wise sparsity: In extreme sparsity (99% missing data), ordinary CP/Tucker decompositions saw their Mean Squared Error (MSE) spike massively (e.g., >0.8 on the synthetic dataset). The proposed regularized methods kept the MSE stable and low (near 0.1-0.2).
  • Slice-wise sparsity (Cold-start): For slice-wise missing data (up to 95% missing), the cross-mode regularization consistently outperformed both ordinary and within-mode methods across all datasets.
  • Scalability: The gradient-based approach successfully scaled to the massive Delicious dataset (which has over 437,000 observed elements in a space of trillions), where the EM-like approach was entirely unfeasible.

Limitations and Future Work

  • Limitations: The EM-like approach, while highly stable for small/sparse datasets, scales poorly to real-world big data. Conversely, the scalable gradient-based approach can be slightly less stable in extreme sparsity due to the high degrees of freedom relative to the observed data. Additionally, the paper relies strictly on the squared loss function, which assumes Gaussian noise.
  • Future Work: The authors suggest extending this framework to non-Gaussian probabilistic models (e.g., using exponential family loss functions for binary or count data). They also propose combining auxiliary information with modern convex formulations of tensor factorization (e.g., using trace norm constraints instead of strict low-rank constraints) to further improve stability and performance.

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},
}

Loading related content...

Figure