PaperlayerView exact revision on arXiv

Source-linked AI summary

DFacTo: Distributed Factorization of Tensors

Joon Hee Choi, S. V. N. Vishwanathan

arXiv:1406.4519v1stat.ML

TL;DR

Large-scale tensor factorization is hindered by an intermediate data explosion in ALS and GD. DFacTo exploits Khatri-Rao product properties to compute the difficult sub-step with two sparse matrix-vector products and distributed execution. It is reported as 4 to 10 times faster than competing algorithms across datasets, while using 3 times more memory than the Tensor Toolbox.

  • Problem

    ALS and GD require multiplying a matricized tensor by a Khatri-Rao product, creating an intermediate data explosion that challenges factorization of large sparse tensors.

  • Method

    DFacTo exploits Khatri-Rao product properties to address the difficult sub-step with two sparse matrix-vector products and a distributed implementation.

  • Results

    DFacTo is around 5 times faster than GigaTensor and 10 times faster than the Tensor Toolbox for ALS, and around 4 times faster than CP-OPT for GD.

  • Takeaways & Limitations

    DFacTo provides a scalable way to factorize massive sparse tensors that cannot be stored and manipulated on a single machine.

  • Takeaways & Limitations

    DFacTo uses 3 times more memory than the Tensor Toolbox, and reported performance differences are partly attributable to its C++ implementation versus competitors' MATLAB implementations.

Abstract

from arXiv · show

We present a technique for significantly speeding up Alternating Least Squares (ALS) and Gradient Descent (GD), two widely used algorithms for tensor factorization. By exploiting properties of the Khatri-Rao product, we show how to efficiently address a computationally challenging sub-step of both algorithms. Our algorithm, DFacTo, only requires two sparse matrix-vector products and is easy to parallelize. DFacTo is not only scalable but also on average 4 to 10 times faster than competing algorithms on a variety of datasets. For instance, DFacTo only takes 480 seconds on 4 machines to perform one iteration of the ALS algorithm and 1,143 seconds to perform one iteration of the GD algorithm on a 6.5 million x 2.5 million x 1.5 million dimensional tensor with 1.2 billion non-zero entries.

1 Introduction

Tensor factorization is difficult to scale because ALS and GD require multiplying a matricized tensor by a Khatri-Rao product, causing intermediate data explosion on large sparse tensors. DFacTo addresses this problem with a distributed algorithm that is substantially faster than existing approaches but uses more memory.

  • ALS and GD both require multiplying a matricized tensor by a Khatri-Rao product of two matrices.
  • Existing methods either lack clear distributed implementations or are relatively slow, limiting their scalability to large problems.
  • DFacTo is an efficient, scalable, distributed algorithm for sparse tensors that applies to both ALS and GD.
  • DFacTo is around 5 times faster than GigaTensor and 10 times faster than the Tensor Toolbox for ALS, and around 4 times faster than CP-OPT for GD.On the Amazon review dataset, one ALS iteration takes 480 seconds on 4 machines and one GD iteration takes 1,143 seconds.
  • DFacTo uses 3 times more memory than the Tensor Toolbox because it stores three flattened matrices instead of one tensor.In return, it requires only two sparse matrix-vector multiplications and supports natural distribution using standard sparse linear algebra operations.

2 Notation and Preliminaries

The paper establishes notation for scalars, vectors, matrices, tensors, observed entries, matrix operations, and tensor flattenings. It defines three mode-specific matrix representations of a third-order tensor and introduces relationships used to derive DFacTo.

  • Scalars, vectors, matrices, and three-dimensional tensors use distinct lowercase, bold lowercase, bold uppercase, and calligraphic notation.
  • Subscripts and index sets identify vector elements, matrix entries, tensor entries, rows, columns, slices, and observed or non-zero entries.
  • The notation includes transpose, Moore-Penrose pseudoinverse, Frobenius norm, vectorization, unvectorization, and standard matrix products.
  • 2.1 Flattening Tensors: A third-order tensor can be flattened in three ways by stacking horizontal, lateral, or frontal slices.
  • 2.1 Flattening Tensors: The resulting mode-n flattenings have sizes I × JK, J × KI, and K × IJ for n equal to 1, 2, and 3, respectively.
  • 2.1 Flattening Tensors: Slice relationships across tensor flattenings provide the basis for deriving the distributed tensor factorization algorithm.

3 DFacTo

DFacTo avoids explicitly forming the large Khatri-Rao product by exploiting sparse tensor structure and precomputed non-zero patterns. It computes the required product through sparse operations and CSR-based reshaping.

  • Explicitly forming C ⊙ B requires O(JKR) memory, creating the intermediate data explosion problem when J and K are large.
  • DFacTo derives the target product column-by-column using tensor flattening relationships and intermediate vectors and matrices.
  • The method computes only non-zero entries because the number of non-zeros in the intermediate vector is bounded by the non-zero row and column structure of the flattened tensor.
  • The non-zero pattern of each intermediate matrix depends on the flattened tensor and is independent of the factor vector, enabling memory preallocation.
  • CSR storage lets DFacTo precompute column and row arrays, write computed values directly into the value array, and reshape the sparse intermediate efficiently.
  • Algorithm 1 computes N by storing sparse products in preallocated matrices and multiplying each by the corresponding factor column.The procedure repeats these two sparse matrix-vector products across the R factor columns.

6 end

DFacTo avoids the intermediate data explosion with sparse computation and supports parallel execution across machines. Its extra memory is tied to tensor sparsity rather than the full Khatri-Rao product size.

  • DFacTo completely avoids the intermediate data explosion problem and uses the same subroutine for ALS and GD.
  • The master-slave implementation distributes rows of the flattened tensor to slaves, which compute corresponding rows of N and synchronize their results.
  • Naive computation requires forming the Khatri-Rao product and performing matrix operations involving JKR-scale intermediate work.
  • DFacTo's sparse computation uses nnzc(X2)R work for the intermediate matrix and exploits nnzc(X2) being typically much smaller than JK and the tensor's non-zero count.
  • The naive algorithm requires O(JKR) extra memory, whereas DFacTo requires only nnzc(X2) extra space for the intermediate matrix.

4 Related Work

Related work includes methods that efficiently compute the key matrix N in tensor factorization, including GigaTensor, the Sparse Tensor Toolbox, and CPALS/CPOPT.

  • Related algorithms: GigaTensor and the Sparse Tensor Toolbox both target efficient computation of N.GigaTensor uses intermediate matrices, while the Sparse Tensor Toolbox stores nonzero values and indices, forms intermediate vectors, computes Hadamard products, and sums selected entries.
  • GigaTensor: GigaTensor computes each column of N using 2 ΩX flops.Its procedure forms two intermediate matrices, multiplies them, and sums the result to obtain n_:,r.
  • Sparse Tensor Toolbox: The Sparse Tensor Toolbox also uses 2 ΩX flops to compute one column of N.Appendix D is cited for an illustrative comparison of intermediate calculations across the competing algorithms.
  • CPALS and CPOPT: CPALS denotes CP ALS using the Sparse Tensor Toolbox method, while CPOPT denotes gradient-based CP optimization using the same method.These names follow the terminology introduced by.

5 Experimental Evaluation

Experiments evaluate DFacTo on real-world and synthetic tensors, comparing its ALS and GD performance with established alternatives and testing distributed scaling. DFacTo is generally faster, scales across machines, and retains an advantage in most synthetic cases, though some comparisons are affected by implementation differences.

  • Scaling on Real-World Datasets: DFacTo (ALS) is around 5 times faster than GigaTensor and 10 times faster than CPALS on many real-world datasets.The differences are more pronounced on the larger datasets.
  • Scaling on Real-World Datasets: DFacTo (GD) is around 4 times faster than CPOPT on real-world datasets.
  • Experimental Setup: Performance differences versus CPALS and CPOPT can partially reflect C++ implementations for DFacTo versus MATLAB implementations for the competitors.Both MATLAB and the DFacTo implementation use an optimized BLAS library for computationally intensive numerical linear algebra.
  • Scaling on Real-World Datasets: 322 seconds per iteration is reported for DFacTo (ALS) on NELL-1, compared with 772 seconds for the C++ GigaTensor implementation on one machine.The comparison concerns one ALS iteration on NELL-1; the Java GigaTensor implementation previously took approximately 10,000 seconds per iteration with 35 machines for a tensor with around 10^9 non-zero entries.
  • Scaling across Machines: Iteration time decreases as the number of machines increases on both NELL-1 and Amazon, while computation time excluding synchronization and line search decreases linearly.The total iteration-time decrease is not completely linear.
  • Synthetic Data Experiments: DFacTo (ALS, GD) does not enjoy significant speedups over competing algorithms on the synthetic datasets, although DFacTo (ALS) is faster in all but one case and DFacTo (GD) is faster in all cases.The synthetic data use preferential attachment, producing power-law non-zero indices; the observed advantage is attributed to better memory locality from reusing N.

6 Discussion and Conclusion

DFacTo accelerates ALS and GD tensor factorization by exploiting the Khatri-Rao product and distributing computation across machines. The approach supports related joint matrix-completion and tensor-factorization models, while trading higher memory use for simple distributed computation.

  • DFacTo speeds up ALS and GD by exploiting properties of the Khatri-Rao product.
  • The method distributes tensor-factorization computations across multiple machines.
  • DFacTo extends to joint matrix completion and tensor factorization using user-item ratings and user-item-word side information.

A.2 Proof of Lemma 1

The CP model represents a tensor with factor matrices, and ALS solves for one factor at a time while holding the others fixed. GD instead updates the factors using gradients of the objective, with regularization available for overfitting.

  • CP decomposition represents tensor X with factor matrices A, B, and C and rank R.
  • ALS fixes all factor matrices except one and solves a least-squares problem for the remaining matrix.
  • The ALS procedure alternates updates of A, B, and C and normalizes their columns until a stopping criterion is met.
  • Regularization terms add λI to the factor-matrix Gram products to address overfitting.
  • GD computes gradients of the objective and updates A, B, and C using f̂ = f − α∇f.

D Illustrative Example

The illustrative example contrasts existing sparse tensor approaches with DFacTo for computing the matricized-tensor/Khatri-Rao product. DFacTo uses sparse operations and avoids the intermediate data-explosion bottleneck used by ALS and GD.

  • The example compares DFacTo with the Sparse Tensor Toolbox and GigaTensor for computing M := X₁(C ⊙ B).
  • The Sparse Tensor Toolbox stores nonzero values and indices, replicates factor entries, forms Hadamard products, and sums selected entries.
  • The example reports ΩX flops for computing one column of M in the compared approaches and ΩX flops for computing M with DFacTo.
  • DFacTo computes M using sparse matrix operations rather than explicitly forming the Khatri-Rao product.
  • The DFacTo subroutine avoids intermediate data explosion and is reused for both ALS and GD.

F.1 Experimental Evaluation

The evaluation compares a joint tensor factorization and matrix completion model with single matrix completion using GD and ALS, selecting models by validation MSE and reporting test MSE. Across the evaluated datasets and methods, the joint model achieves better MSE.

  • Experimental setup: 60% of review-rating pairs are used for training, with validation and test sets formed from the remaining pairs.Users or items absent from training are removed from validation and test data.
  • Experimental setup: Models are selected by validation mean square error, then evaluated on the test dataset using average mean square error.For GD, backtracking line search is used; the tables report results after 500 iterations for GD and ALS.
  • Results: The joint model produces better MSEs than matrix completion across all evaluated datasets and both optimization methods.This comparison covers the Gradient Descent and ALS results reported in Tables 6 and 7.
Loading 1406.4519v1…