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).
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