Sampling for Approximate Maximum Search in Factorized Tensor

Zhi Lu, Yang Hu, Bing ZengIJCAI 2017 · DOI

Introduction

In the era of big data, multi-dimensional relationships are frequently modeled using tensors. For instance, a recommendation system might use a user-item-tag cube to capture preferences. To handle the sparsity and scale of these structures, researchers often employ CP Decomposition (CANDECOMP/PARAFAC), which approximates the original tensor as a sum of rank-1 components derived from factor matrices.

A critical challenge in this domain is the "Maximum Search" problem: identifying the top-$t$ largest entries in the reconstructed tensor. For massive tensors (e.g., $10^6 \times 10^6 \times 10^2$), an exhaustive search is computationally prohibitive. This paper presents Core$^k$ Sampling, a randomized, graph-based algorithm designed to find these top entries orders of magnitude faster than traditional methods.

Methodology: From Graphs to Stars

The proposed solution reimagines the CP model as an $(N+1)$-partite graph. In this representation, "core nodes" correspond to latent factors, while "peripheral nodes" represent the indices of the tensor's dimensions.

Graph representation and sampling strategies: (a) factor matrices as a multipartite graph, (b) a single sampled star, and (c) two intersecting stars representing Core$^2$ sampling.

The algorithm utilizes two primary sampling techniques:

  1. Star Sampling: A "star" is a subgraph that connects one core node to exactly one node in each peripheral partition. By sampling these stars, the probability of selecting a specific index tuple is directly proportional to the value of that entry in the tensor.
  2. Core$^k$ Sampling: This is the central innovation. Instead of a single star, the algorithm samples "compound stars" involving $k$ core nodes simultaneously. This shift ensures that the probability of selecting an index is proportional to the $k$-th power of the entry's value ($x_i^k$).

By increasing $k$, the algorithm effectively "amplifies" the peaks of the tensor. This bias allows the search to focus on the largest values while ignoring the vast majority of smaller, less relevant entries.

Experimental Evaluation

The researchers tested Core$^k$ Sampling on five diverse real-world datasets, including Delicious Bookmarks, Last.FM, MovieLens (Small and Large), and DBLP. These datasets represent various scales and domains, from music recommendations to link prediction in citation networks.

Key Results

The experiments yielded several significant insights:

  • Efficiency and Speed: The sampling approach is significantly faster than exhaustive computation. On the Last.FM dataset, Core$^3$ sampling achieved high recall with only $10^6$ samples, despite the tensor containing billions of potential entries.
  • Recall Improvement: Increasing $k$ from 1 to 3 dramatically improved the recall—the percentage of actual top entries found—for a fixed number of samples.
  • Scalability: The algorithm scales well with tensor dimensions and order. Furthermore, it is particularly efficient for multi-user recommendation scenarios because samples can be shared and reused across different users.
Running time breakdown for each phase of the algorithm on the LastFM dataset across different core configurations.

As shown in the performance analysis, the computational overhead is distributed across different phases, with the sampling and pre-filtering strategies effectively pruning the search space before expensive exact calculations are required.

Conclusion and Future Work

Core$^k$ Sampling provides a robust, mathematically grounded framework for finding maximum entries in factorized tensors. By leveraging the "power of $k$," it transforms an impossible exhaustive search into a highly efficient randomized process. While the method currently assumes non-negative factor matrices for its tightest theoretical bounds and faces some initialization overhead at very high $k$, it represents a major step forward for real-time recommendation and link prediction. Future research may extend these sampling principles to other decomposition models like Tucker decomposition.

Summary updated

BibTeX
@inproceedings{lu2017sampling,
  author = {Zhi Lu and Yang Hu and Bing Zeng},
  title = {{Sampling for Approximate Maximum Search in Factorized Tensor}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/334},
}
Figure