PaperlayerView exact revision on arXiv

Source-linked AI summary

On Sampling Strategies for Neural Network-based Collaborative Filtering

Ting Chen, Yizhou Sun, Yue Shi, Liangjie Hong

arXiv:1706.07881v1cs.LGcs.IRcs.SIstat.ML

TL;DR

Neural network-based recommendation combines interaction data with content features but incurs substantial computational cost. The paper introduces a general collaborative-filtering framework and three graph-aware sampling strategies, reporting improved training efficiency and recommendation performance. It also analyzes computational cost and convergence theoretically.

  • Problem

    Neural network-based recommendation can combine interaction and content information but is computationally expensive, making efficient training important.

  • Method

    The paper generalizes neural network-based collaborative filtering through functional embeddings and designs three sampling strategies based on the mismatch between link-defined losses and node-based computation.

  • Results

    The proposed sampling strategies significantly improve training efficiency and recommendation performance, with experiments reporting up to ×30 faster training.

  • Takeaways & Limitations

    Sampling strategies that account for shared node computation provide a way to improve efficiency and recommendation performance in the proposed framework.

  • Takeaways & Limitations

    Under explicit feedback, Negative Sharing can be less effective, and neural-network interaction functions make negative-sample construction noticeably costly.

Abstract

from arXiv · show

Recent advances in neural networks have inspired people to design hybrid recommendation algorithms that can incorporate both (1) user-item interaction information and (2) content information including image, audio, and text. Despite their promising results, neural network-based recommendation algorithms pose extensive computational costs, making it challenging to scale and improve upon. In this paper, we propose a general neural network-based recommendation framework, which subsumes several existing state-of-the-art recommendation algorithms, and address the efficiency issue by investigating sampling strategies in the stochastic gradient descent training for the framework. We tackle this issue by first establishing a connection between the loss functions and the user-item interaction bipartite graph, where the loss function terms are defined on links while major computation burdens are located at nodes. We call this type of loss functions "graph-based" loss functions, for which varied mini-batch sampling strategies can have different computational costs. Based on the insight, three novel sampling strategies are proposed, which can significantly improve the training efficiency of the proposed framework (up to $\times 30$ times speedup in our experiments), as well as improving the recommendation performance. Theoretical analysis is also provided for both the computational cost and the convergence. We believe the study of sampling strategies have further implications on general graph-based loss functions, and would also enable more research under the neural network-based recommendation framework.

1 INTRODUCTION

The paper develops a general hybrid recommendation framework combining collaborative filtering with deep neural networks, then addresses its computational cost through graph-aware sampling strategies.

  • Motivation: Hybrid recommendation combines collaborative filtering for user preferences with deep neural networks for extracting high-level features from complex content.The framework is motivated by the complementary strengths of interaction data and content such as image, audio, and text.
  • Framework: The framework generalizes several state-of-the-art neural network-based recommendation algorithms while unifying collaborative filtering and deep neural networks.It is designed to incorporate both user-item interactions and content information.
  • Computational challenge: Loss terms are defined on user-item interaction links, whereas the main computational burdens occur at nodes such as users and items.This mismatch makes sampling choices important for stochastic-gradient training cost.
  • Proposed strategies: Three sampling strategies account for coupled computation across interactions by grouping links, sharing negatives, or combining both approaches.The paper names these strategies Stratified Sampling, Negative Sharing, and their combination, and provides theoretical analysis of cost and convergence.
  • Reported outcomes: The proposed strategies improve training efficiency by up to ×30 in experiments while also improving recommendation performance.The paper reports both empirical experiments and theoretical analysis supporting the proposed methods.

2 A GENERAL FRAMEWORK FOR NEURAL NETWORK-BASED COLLABORATIVE FILTERING

The framework combines collaborative filtering with differentiable user and item functions that process interaction and content information. It supports implicit-feedback losses and SGD training, but neural content functions substantially increase computational cost.

  • 2.1 Text Recommendation Problem: In text recommendation, user features are one-hot user IDs, item features are text sequences, and non-interactions are treated as implicit negative feedback.The model learns to rank new articles for existing users using user interests and article text content.
  • 2.2 Functional Embedding: Functional Embedding replaces user and item latent vectors with differentiable functions of their features, producing embeddings for scoring user-item pairs.The score can use a vector dot product or a general neural network; CNNs and RNNs can extract content features.
  • 2.3 Loss Functions for Implicit Feedback: The framework supports pointwise losses over user-item pairs and pairwise losses over user, positive-item, and negative-item triplets.Pointwise losses encourage positive scores and discourage negative scores, while pairwise losses encourage positive items to rank above negatives.
  • 2.4 Stochastic Gradient Descent Training and Computational Challenges: SGD training samples user-item tuples, computes user and item functions plus their interaction, then applies gradients from the loss.Pairwise losses instead use user-item triplets during mini-batch sampling.
  • 2.4 Stochastic Gradient Descent Training and Computational Challenges: Orders-of-magnitude longer training times arise when linear item embeddings are replaced by CNN- or RNN/LSTM-based content embeddings.The mini-batch cost is tf × # of users + tд × # of items + ti × # of interactions, with tд assumed much larger than tf and ti.

3 MINI-BATCH SAMPLING STRATEGIES FOR EFFICIENT MODEL TRAINING

The paper views mini-batch losses as graph-based: loss terms lie on user-item links, while costly neural computations occur at shared nodes. It therefore proposes sampling strategies that exploit node sharing to reduce training cost and improve recommendation performance.

  • Motivation: Graph-based loss functions place loss terms on user-item links, but their main computational burden lies at nodes shared across multiple links.This coupling makes sampling strategy determine whether node computations can be amortized within a mini-batch.
  • Existing strategies: IID Sampling independently draws positive and negative links, while Negative Sampling replaces each positive item with k sampled negative items.Neither strategy effectively shares costly item computations across sampled links.
  • Stratified Sampling: Stratified Sampling groups links sharing a node, samples a stratum first, and can reduce item-function computations from b(1+k) to b/s per mini-batch.For s = 4 and k = 10, the item-based variant yields an optimal ×40 speedup under item-dominated computation.
  • Negative Sharing: Negative Sharing reuses the sampled node set to create additional negative links, providing (1+k) times speedup over Negative Sampling when item computation dominates.With b = 512 and k = 20, it considers many additional non-interactions, which the paper reports as helpful for faster convergence and better performance.
  • Combined strategy: The combined strategy applies stratified positive-link sampling and constructs negatives from non-interactions, supporting pointwise and pairwise losses with a flexible positive-negative ratio.In the reported b = 512, s = 4 setting, it uses 127 negative links per positive and requires one-quarter as many item-function computations as Negative Sharing.

3.4 Computational Cost and Convergence Analysis

The analysis compares sampling strategies through per-iteration computation and iteration counts, then establishes unbiased gradients and local convergence behavior. It also links additional negative links to lower stochastic-gradient variance and potentially faster convergence.

  • Computational cost: The computational analysis separates speedup into mini-batch cost per iteration and iterations required to reach a reference loss.The comparison fixes the number of positive links per mini-batch and approximates speedup using costly item-function computations because t_g dominates in practice.
  • Unbiased gradients: Under the proposed Algorithms 2–5, the stochastic mini-batch gradient equals the true gradient in expectation for both pointwise and pairwise losses.The paper attributes this guarantee to stochastic sampling with appropriate reweighting.
  • Convergence: The proposed sampling strategies follow a local convergence bound despite the highly nonlinear and non-convex neural-network functions.The bound is presented as a local result rather than a global convergence characterization.
  • Convergence: Using more negative links can lower expected stochastic-gradient variance, suggesting better convergence for Negative Sharing with or without Stratified Sampling than for item-based Stratified Sampling.The paper connects variance reduction to faster convergence through prior results.

4 EXPERIMENTS

The experiments compare sampling strategies for efficiency and recommendation quality across neural collaborative-filtering models, using fixed positive-link batch sizes and recall@M evaluation. The proposed strategies reduce computation, accelerate convergence, and can improve recommendation performance.

  • Data Sets: The experiments use CiteULike and Yahoo! News implicit-feedback datasets, with held-out test items simulating recommendations for newly emerged articles.CiteULike contains 5,551 users, 16,980 items, and 204,986 positive interactions; Yahoo! News contains 10,000 users, 58,579 items, and 515,503 interactions.
  • Evaluation Metrics: Recommendation performance is measured with recall@M, while efficiency is measured by per-iteration time, iterations to a reference loss, and total wall time.The reference loss is the smallest loss obtained by IID sampling within 30 epochs.
  • Speedup Under Different Sampling Strategies: All proposed sampling strategies significantly reduce computation within a mini-batch, while Negative Sharing variants can also improve convergence across iterations.The compared strategies include Stratified Sampling, Negative Sharing, and their combination, evaluated against IID and Negative Sampling.
  • Speedup Under Different Sampling Strategies: Negative Sharing variants converge fastest by iteration, and wall-time comparisons also favor these strategies in the reported convergence curves.The faster convergence is attributed to using more negative samples; earlier overfitting can be handled with early stopping.
  • Recommendation Performance Under Different Sampling Strategies: Recommendation performance improves with reasonable stratification size and with Negative Sharing, whose gains show diminishing returns as the number of negatives increases.For Stratified Sampling, s = 4 or 8 improves convergence time and recommendation performance; performance continues increasing even at 20 negative examples.

5 RELATED WORK

Related work combines collaborative filtering with neural networks to address cold-start limitations and extract features from content. Prior approaches use autoencoders, recurrent networks, CNNs, pairwise losses, and unsupervised text embeddings.

  • Collaborative Filtering: Collaborative filtering is effective but suffers from cold-start settings where new users or items have few or no observed interactions.Side information and item content have been incorporated to address this limitation.
  • Deep Neural Networks: Deep neural networks are used in recommendation systems because they can automatically extract high-level features from raw video, audio, and text.This contrasts with traditional feature detectors such as SIFT and n-grams.
  • Neural Collaborative Filtering: Existing neural recommendation models apply autoencoders, RNNs or GRUs, CNNs, pairwise losses, and unsupervised text embeddings to combine content with collaborative filtering.The paper’s functional embedding framework subsumes the cited existing models.
  • Sampling Strategies: IID sampling is standard in stochastic-gradient training, while negative sampling is used when negative examples are overwhelming.The related-work discussion motivates more efficient sampling when loss terms share computation under graph structure.

6 DISCUSSIONS

The paper frames its sampling methods as relevant beyond content-based collaborative filtering to graph-based loss functions more generally. Its main limitation is that Negative Sharing depends on implicit feedback and cheap interaction computation.

  • Implications: For ordinary loss functions, IID mini-batch sampling has nearly uniform computation because loss terms usually do not share common computations.Graph-structured models violate this assumption when computation is coupled across nodes.
  • Implications: The sampling strategies may therefore have implications for graph-based losses in social graphs, knowledge graphs, image-caption ranking, and related applications.The discussion specifically suggests that better sampling can train such models faster than IID sampling.
  • Limitations: Negative Sharing is less effective for explicit feedback because constructed negative samples may not overlap with explicit negative examples.The paper also assumes efficient interaction functions; neural-network interaction functions can make negative construction noticeably costly.

7 CONCLUSIONS AND FUTURE WORK

The paper presents a hybrid collaborative-filtering and neural-network framework with sampling strategies designed to reduce the computational cost of combining cheap collaborative filtering with expensive neural computation. It identifies future work in model exploration, negative-sampling distributions, and distributed training.

  • Conclusions: The framework combines conventional collaborative filtering with deep neural networks and generalizes several existing state-of-the-art recommendation models.It is intended to support hybrid models that incorporate interaction and content information.
  • Conclusions: The paper connects loss functions to the user-item interaction graph and uses that connection to design three sampling strategies that improve training efficiency and recommendation performance.The reported experiments achieve up to ×30 faster training, alongside recommendation improvements.
  • Future Work: Future work includes more efficient study of neural networks and auxiliary information, investigation of negative-sampling distributions, and application of the strategies to distributed training.These directions extend the sampling framework to broader model and training settings.

A PROOFS

The proofs formalize the sampling procedures, establish unbiased stochastic gradients, and derive convergence results under smoothness and bounded-gradient assumptions.

  • Convergence analysis: The convergence analysis assumes an L-smooth loss and a σ-bounded gradient, with θ* denoting a minimizer of L.The proposition applies a constant step size ηt = η under these assumptions.
  • Sampling and gradient estimation: The framework samples positive and negative links into a mini-batch before computing and applying a stochastic gradient.The batch contains B+ and B−, with m and n denoting their respective sizes.
  • Sampling and gradient estimation: Under Algorithms 2–5, the stochastic mini-batch gradient equals the true gradient in expectation.This unbiasedness lemma is the basis for analyzing the proposed sampling strategies.
  • Sampling strategies: Negative Sampling draws m positive links and k negative links conditioned on each positive link by replacing items independently.Positive links come from Pd(u,v), while negative items come from Pn(v′).
  • Sampling strategies: Stratified Sampling by Items first draws an item, then samples positive and negative users, with negative terms re-weighted.This groups links by items while preserving the required sampling distribution.
  • Sampling strategies: Negative Sharing samples positive links and constructs negative links by sharing batch items, producing m positive and m(m −1) negative links.The constructed negative links are probability-corrected through re-weighting.
  • Sampling strategies: Stratified Sampling with Negative Sharing draws items and positive users in two steps, then constructs negative links from independently drawn batch items.Its batch contains m positive links and n negative links, with negative terms re-weighted.

B VECTOR DOT PRODUCT VERSUS MATRIX MULTIPLICATION

The paper contrasts element-wise matrix multiplication with ordinary matrix multiplication, whose asymptotic cost is higher for square matrices.

  • Computational comparison: Element-wise matrix multiplication has complexity O(n2), whereas matrix multiplication has complexity O(n3) for square matrices of size n.The comparison motivates measuring their computation-time ratio empirically.
  • Computational comparison: Figure 9 reports the computation-time ratio between matrix multiplication and element-wise matrix multiplication across different square matrix sizes.The figure varies the matrix size n and compares the two operations directly.

C FUNCTIONAL EMBEDDING VERSUS FUNCTIONAL REGULARIZATION

Functional Embedding produces user and item embeddings directly from feature-processing functions, whereas functional regularization penalizes deviations from those function outputs.

  • Functional Embedding: Functional Embedding obtains user and item embeddings from differentiable functions applied to their features.The functions f and g replace the original embedding vectors and output vectors in R^d.
  • Functional Regularization: Functional regularization adds a penalty encouraging an embedding to match the corresponding function output.The paper contrasts this indirect constraint with Functional Embedding’s direct replacement of embedding vectors.
  • Functional Regularization: Large regularization weight λ slows coordinate-descent training and prevents interaction information from effectively updating the embedding.As λ increases, the embedding update approaches the function output.
Loading 1706.07881v1…