PaperlayerView exact revision on arXiv

Source-linked AI summary

Challenging the Long Tail Recommendation

Hongzhi Yin, Bin Cui, Jing Li, Junjie Yao, Chen Chen

arXiv:1205.6700v1cs.DB

TL;DR

The paper addresses long tail recommendation, aiming to suggest niche items rather than merely popular ones. It proposes graph-based Hitting Time, Absorbing Time, and Absorbing Cost algorithms, whose experiments on two real datasets show improved accuracy, quality, and diversity over state-of-the-art methods.

  • Problem

    The paper addresses the novel problem of recommending niche long tail items to users rather than merely popular items.

  • Method

    The paper represents user-item information as an undirected edge-weighted graph and develops Hitting Time, Absorbing Time, and entropy-cost-based Absorbing Cost algorithms.

  • Results

    The proposed algorithms outperform state-of-the-art recommendation algorithms on two real datasets for long tail item recommendation in accuracy, quality, and diversity.

  • Takeaways & Limitations

    The approaches can exploit less popular inventory items while emphasizing user interests and recommendation diversity.

  • Takeaways & Limitations

    Computing absorbing times by solving the linear system can become extremely inefficient for millions of variables, with a stated complexity of O(n3).

Abstract

from arXiv · show

The success of "infinite-inventory" retailers such as Amazon.com and Netflix has been largely attributed to a "long tail" phenomenon. Although the majority of their inventory is not in high demand, these niche products, unavailable at limited-inventory competitors, generate a significant fraction of total revenue in aggregate. In addition, tail product availability can boost head sales by offering consumers the convenience of "one-stop shopping" for both their mainstream and niche tastes. However, most of existing recommender systems, especially collaborative filter based methods, can not recommend tail products due to the data sparsity issue. It has been widely acknowledged that to recommend popular products is easier yet more trivial while to recommend long tail products adds more novelty yet it is also a more challenging task. In this paper, we propose a novel suite of graph-based algorithms for the long tail recommendation. We first represent user-item information with undirected edge-weighted graph and investigate the theoretical foundation of applying Hitting Time algorithm for long tail item recommendation. To improve recommendation diversity and accuracy, we extend Hitting Time and propose efficient Absorbing Time algorithm to help users find their favorite long tail items. Finally, we refine the Absorbing Time algorithm and propose two entropy-biased Absorbing Cost algorithms to distinguish the variation on different user-item rating pairs, which further enhances the effectiveness of long tail recommendation. Empirical experiments on two real life datasets show that our proposed algorithms are effective to recommend long tail items and outperform state-of-the-art recommendation techniques.

1. INTRODUCTION

Internet retailers make niche products broadly available, but recommendation systems often fail to help users discover them because of data sparsity. The paper addresses this gap with graph-based algorithms designed to improve long-tail recommendation accuracy, diversity, and quality.

  • Motivation: Long-tail products can generate substantial aggregate sales and may also boost mainstream sales through one-stop shopping convenience.Their relatively large marginal profits provide an additional incentive to expand the niche market.
  • Problem: Most existing recommendation algorithms favor popular items and cannot reliably recommend long-tail products when historical data are sparse.Association rules and collaborative filtering typically require strong support and therefore produce generic, locally popular recommendations.
  • Problem: Popular recommenders can reduce sales diversity by directing different users toward the same products, creating a rich-get-richer effect.The paper therefore targets both niche-item discovery and more diverse aggregate recommendations.
  • Approach: The paper proposes Hitting Time and extends it with Absorbing Time to improve long-tail recommendation diversity and accuracy.These methods are based on a user-item graph.
  • Approach: Entropy-cost modeling distinguishes variation across user-item rating pairs and supports Absorbing Cost algorithms intended to improve recommendation accuracy and quality.A separate LDA-based method mines latent user interests from rating information to compute user entropy.
  • Evaluation: Experiments on two real datasets compare the proposed algorithms with state-of-the-art techniques across recall, diversity, and quality.The reported results demonstrate superiority for long-tail item recommendation.

2. RELATED WORK

Existing recommendation research includes content-based, collaborative-filtering, topic-model, and graph-based approaches. The paper identifies limited long-tail coverage and poor recommendation diversity as unresolved problems motivating its graph-based methods.

  • Existing approaches: Content-based filtering uses item descriptions and users’ preferences for liked or disliked items, but limited product descriptions restrict its effectiveness in e-commerce.The cited descriptions include metadata, words, prices, tags, and reviews.
  • Existing approaches: Collaborative filtering uses behavioral histories from like-minded users to recommend items to a target user.Its core assumption is that users with similar tastes on some items may share preferences on others.
  • Existing approaches: LDA-based topic models have been applied to community recommendation and tag recommendation.
  • Existing approaches: Graph-based methods include node similarity, hitting time, commute time, random walk with restart, Katz, and random-forest approaches.Prior hitting-time and commute-time methods often recommend items similarly to stationary-distribution popularity rankings.
  • Research gap: Most existing methods struggle with long-tail recommendation under sparse historical data and provide poor recommendation diversity.The paper proposes graph-based algorithms to address both limitations.

3. OVERVIEW OF THE LONG TAIL RECOMMENDATION

The paper formulates long-tail recommendation on an undirected, edge-weighted user-item graph and uses random-walk proximity to rank niche items. Hitting time discounts item popularity while retaining graph-based relevance to the query user.

  • Graph model: User-item information is represented as an undirected, edge-weighted graph whose nodes are users or items and whose edge weights encode relation strength.In movie data, user-movie edges represent watched links and their weights represent ratings.
  • Problem formulation: The long-tail task seeks top-k item nodes that are sufficiently close to a query user and lie in the long tail.
  • Random-walk basis: Random walks provide graph-based proximity statistics by modeling transitions between adjacent nodes.The stationary probability of a node is proportional to its degree, linking popularity to graph connectivity.
  • Motivation for hitting time: Several prior random-walk methods provide proximity scores but do not adequately challenge long-tail recommendation.Some ignore item popularity, while others tend toward popular recommendations.
  • Hitting-time rationale: Using the reverse transition probability from item j to user q discounts item popularity because it divides relevance by the item’s stationary probability.The stationary probability is proportional to item degree.
  • Hitting Time: Hitting time is the expected number of steps for a random walker starting at item j to reach query user q.The algorithm ranks unrated items by hitting time and recommends the k items with the smallest values.

4. ENHANCEMENTS OF RECOMMENDATION

The paper frames long-tail recommendation as finding items relevant to a user while remaining hard to discover, then develops graph-based enhancements from Hitting Time to Absorbing Time and Absorbing Cost. These methods address scalability and rating-pair variation through truncated local computation and entropy-based transition costs.

  • Problem: Long-tail recommendation seeks top-k items close to a query user’s preferred set while lying in the long-tail distribution.The formulation requires recommendations to be both relevant and hard to find.
  • Absorbing Time: Absorbing Time ranks candidate items by the expected steps for a random walker to reach the user’s rated-item set.Absorbing nodes stop the walker upon first arrival, and smaller absorbing times determine recommendations.
  • Absorbing Time: The straightforward Absorbing Time computation is constrained by graph scale and exact linear-system solving, whose worst-case cost is O(n^3).The paper notes that millions of variables make exact solutions inefficient.
  • Absorbing Time: A truncated Absorbing Time algorithm iterates τ times on a breadth-first-search local subgraph capped at μ item nodes, reducing global per-user complexity to O(τ · m).The approach targets stable top-k rankings rather than exact absorbing-time values.
  • Absorbing Cost: Absorbing Cost distinguishes user-item rating pairs by assigning transition costs, with Absorbing Time recovered when every transition cost equals 1.This extension addresses information lost when equal ratings from users with different interest breadths are treated identically.
  • Entropy-based weighting: User entropy captures interest breadth and is used to compute transition costs so ratings from taste-specific and broad-interest users can be treated differently.The paper introduces entropy as a feature for weighting jumps from item nodes to connected users.

5. EXPERIMENTS

The experiments evaluate the proposed approaches for long tail recommendation and compare them with other competitive techniques to demonstrate their performance.

  • The study conducts extensive experiments to evaluate the proposed approaches for long tail recommendation.
  • The evaluation compares the proposed methods with other competitive recommendation techniques.

5.1 Experimental Setup

The experimental setup uses real-world MovieLens and Douban data, defines long tail recommendation through popularity and user-interest criteria, and evaluates accuracy, novelty, quality, diversity, and efficiency.

  • Experimental comparison: The study compares HT, AT, AC1, and AC2 with existing recommendation techniques on MovieLens and Douban datasets.HT denotes Hitting Time, AT Absorbing Time, AC1 item-based Absorbing Cost, and AC2 topic-based Absorbing Cost.
  • Data description: Long tail items are the least-popular products that collectively generate 20% of total ratings, sales, or downloads.The datasets contain approximately 66% hard-to-find MovieLens movies and 73% least-rated Douban books in this long tail.
  • Data description: MovieLens contains 1M ratings for 3,883 movies from 6,040 users, with a 4.26% rating-matrix density.
  • Data description: Douban contains 13,506,215 book ratings from 383,033 users for 89,908 books, with 0.039% matrix density.
  • Evaluation metrics and methodologies: The evaluation measures recommendation accuracy with Recall@N and long-tail positioning using recommended-item rating frequency.
  • Evaluation metrics and methodologies: Recommendation quality is assessed by similarity to user interests, diversity by normalized item variety, and efficiency by computational time cost.Efficiency reflects the need for scalable online operation on large-scale datasets.

5.2 Performance on Recommendation

The proposed algorithms are evaluated against state-of-the-art methods on recall, long-tail popularity, diversity, similarity, scalability, and user satisfaction using MovieLens and Douban data. Across these measures, the methods generally favor niche-item discovery while maintaining recommendation relevance and efficiency.

  • 5.2.1 Accuracy Measurement: Accuracy is higher on Douban than MovieLens, while the comparison trend remains similar across datasets.The reported rating-matrix densities are 4.26% for MovieLens and 0.039% for Douban.
  • 5.2.1 Accuracy Measurement: AC2 achieves the highest long-tail recall, followed by AC1, AT, and HT, outperforming the other competitors.On MovieLens, AC2 recall is about 0.12 at N = 10 and 0.48 at N = 50.
  • 5.2.2 Long Tail Measurement: The proposed algorithms consistently recommend more niche items than existing methods across recommendation-list sizes.DPPR shows comparable long-tail popularity but performs worse on Recall@N, whereas LDA and PureSVD prioritize popular items.
  • 5.2.3 Diversity Measurement: AC1 achieves the best Douban diversity with 12,500 unique recommended items among 2,000 users, while AT and AC2 each reach 11,600.HT recommends 11,000 unique items, and LDA recommends about 700; diversity is generally lower on MovieLens.
  • 5.2.4 Similarity Measurement: AC2 performs best on similarity, while AT, AC1, and AC2 recommend more relevant items than user-based HT.The topic-based AC2 entropy is reported as more proximate to exact user entropy than the item-based AC1 entropy.
  • 5.2.5 Impact of Parameter μ: The methods remain scalable by using smaller user-centered subgraphs, with similarity increasing up to μ = 6k and changing little thereafter.Increasing μ slightly decreases popularity and diversity, while subgraph processing avoids time-consuming global graph scans.
  • 5.2.7 User Study: User-study participants found the proposed recommendations more satisfactory, combining taste matching with greater novelty and serendipity.LDA and PureSVD concentrated on familiar hit movies, while DPPR provided novelty but matched users’ interests less well.

6. CONCLUSIONS

The paper addresses long-tail recommendation by using graph-based algorithms to recommend niche items while emphasizing user interests and recommendation diversity. Experiments on two real datasets report improvements over state-of-the-art methods in accuracy, quality, and diversity.

  • 6. CONCLUSIONS: The paper represents user-item information as an undirected edge-weighted graph and proposes four variants based on hitting time, absorbing time, and absorbing cost.The methods are designed to exploit less popular inventory items while emphasizing user interests and recommendation diversity.
  • 6. CONCLUSIONS: Experiments on two real datasets show that the proposed algorithms outperform state-of-the-art methods for long-tail recommendation in accuracy, quality, and diversity.The paper presents the approach as an alternative recommender-system design and a potential feature for online sales services.
Loading 1205.6700v1…