Diversified Coverage based Tag Recommendation

Ying Yin, Yuhai Zhao, Qingze Wang, Gang ShengThe Open Automation and Control Systems Journal 2014 · DOI

Abstract

Tag recommendation systems are pivotal in e-commerce and social networking services, yet they frequently suffer from semantic redundancy. Current algorithms prioritize relevance, often resulting in clusters of synonymous tags (e.g., "movie," "film," "cinema") that offer little additional value to the user. This paper introduces a novel framework that balances relevance with semantic diversity. By defining a tag correlation metric based on local and global co-occurrence and mapping the recommendation task to a Minimum Independent Dominating Set (MIDS) problem, we propose the EDC (Exact Diversified Coverage) and GDC (Greedy Diversified Coverage) algorithms. Experimental results on MovieLens and Last.fm datasets demonstrate that our approach significantly enhances recommendation diversity without compromising accuracy.

Introduction

In the Web 2.0 era, user-generated tags (folksonomies) have become a primary source of metadata. However, the "Top-K" tags recommended by traditional systems often lack novelty. If a user tags an item as "action," a redundant system might suggest "adventure" and "thriller" alongside "action-packed," failing to cover other dimensions like "1980s" or "Arnold Schwarzenegger." We address this by introducing "semantic coverage," ensuring that the recommended set represents a broad spectrum of concepts.

Methodology

Our approach involves three key components:

1. Correlation and Relevance

We calculate tag relevance using a hybrid metric that combines local co-occurrence (user-specific patterns), global co-occurrence (system-wide relationships), and TF-ITF (Term Frequency-Inverse Tag Frequency). TF-ITF identifies tags that are descriptive but not overly generic, similar to the TF-IDF weighting used in text mining.

2. Semantic Similarity Graph

Using WordNet and Information Content (IC) metrics, we construct a graph where nodes are candidate tags. An edge exists between two nodes if their semantic similarity exceeds a predefined threshold. This graph identifies clusters of redundant tags that should not appear together in the final recommendation set.

3. Diversified Coverage via MIDS

The core innovation is treating diversified recommendation as a Minimum Independent Dominating Set (MIDS) problem. The goal is to find the smallest set of tags such that every tag in the candidate set is either in the chosen set or connected to one (coverage), while ensuring no two chosen tags are connected to each other (diversity).

Graph reduction techniques for handling cliques and bipartite structures in the EDC algorithm.

To solve the MIDS problem efficiently, we developed two algorithms:

  • EDC (Exact Diversified Coverage): This algorithm recursively simplifies the graph by identifying and collapsing specific structures like cliques and bipartite components, as illustrated in the figure above.
  • GDC (Greedy Diversified Coverage): A heuristic approach that iteratively selects the tag with the highest "coverage power" relative to its correlation score, ensuring scalability for real-time applications.

Experimental Evaluation

We tested EDC and GDC against standard baselines (PageRank, FolkRank, and Tucker) using MovieLens and Last.fm datasets.

  • Diversity: Both EDC and GDC showed a marked improvement in Average Intra-List Distance (AILD), effectively breaking up semantic clusters.
  • Relevance: The Normalized Discounted Cumulative Gain (nDCG) remained competitive, indicating that the gain in diversity did not come at the cost of user interest.
  • Efficiency: While EDC provides exact solutions, GDC's performance was nearly constant as the number of requested tags ($K$) increased, making it highly suitable for large-scale production environments.

Conclusion

By integrating semantic coverage into the recommendation pipeline, we move beyond simple relevance to provide a more holistic view of content. Mapping the problem to MIDS allows for a mathematically rigorous way to ensure both diversity and representativeness. Future work will focus on handling "out-of-vocabulary" tags and slang that are not currently captured by formal semantic dictionaries like WordNet.

Summary updated

Abstract

Tag recommendation, as a branch of recommendation engine, has drawn more and more attention, which is also extensively exploited in e-commerce and SNS (Social Networking Services). The results generated by the current algorithms could describe the items with a high relevance. However, they are often of poor diversity in the recommended results. That indicates there is a redundancy in the results in term of semantics. Such a case reduces the novelty and diversity of the recommended results, seriously affecting the user's experience. In this paper, we define the tag correlation metric based on the local and global tag co-occurrence matrices, which improves the recommendation accuracy by incorporating both the user's interests and the popularity of tags. Moreover, we propose the concept of semantic coverage, by which the redundancy of semantics can be removed efficiently. To our best knowledge, it is first proposed in the context of tag recommendation. Finally, a diversified coverage based tag recommendation algorithm, namely EDC, is developed. By converting the problem of diversified coverage tag recommendation to the MIDS (Minimum Independent Dominating Set) problem, EDC first handles the cliques and the bipartites in the graph. Then, it recursively searches the MIDSs in the remaining graph. Further, a greedy algorithm GDC is proposed. The experiments conducted on the real datasets of Mov-ieLens and Last.fm show that the proposed EDC and GDC improve the diversity significantly.
BibTeX
@article{yin2014diversified,
  author = {Ying Yin and Yuhai Zhao and Qingze Wang and Gang Sheng},
  title = {{Diversified Coverage based Tag Recommendation}},
  journal = {The Open Automation and Control Systems Journal},
  year = {2014},
  doi = {10.2174/1874444301406010872},
}
Figure