CCSMR: A Combinatorial Category Space-Based Model for Recommendation

Chunjing Xiao, Kewen Xia, Leilei Sun, Cong Xie, Yuxiang Zhang

Introduction

Modern recommender systems frequently encounter the challenge of "data sparsity," where the vast majority of users interact with only a tiny sliver of the available item catalog. To mitigate this, researchers often leverage "side information," such as item categories. However, traditional models struggle with items that belong to multiple categories (e.g., a film categorized as both "Action" and "Sci-Fi"). These models typically treat categories as independent tags, failing to capture the nuanced semantic information inherent in their combinations.

The CCSMR (Combinatorial Category Space-Based Model for Recommendation) addresses this by transforming the complex one-to-many relationship between items and categories into a precise one-to-one mapping within a structured lattice.

The Combinatorial Category Space (CCS)

The core innovation of CCSMR is the Combinatorial Category Space (CCS). Rather than viewing categories as a flat list, they are organized into a subset-superset lattice, often visualized as a Hasse diagram. Each node in this lattice represents a unique combination of categories.

Mapping items and categories into the Combinatorial Category Space (CCS) lattice.

As shown in the figure above, items in the item space are mapped to specific nodes in the CCS. This structure allows the model to track user behavior as a trajectory through the lattice, providing a mathematical framework to determine whether a user is broadening their horizons or refining a specific niche interest.

Modeling Semantic Transitions

By mapping interactions to the CCS, the researchers identified five distinct ways a user moves through the interest space:

  • Preference Expanding ($R_e$): Moving from a specific category set to a broader one (e.g., "Medical Drama" to "Drama").
  • Preference Narrowing ($R_n$): Moving toward a more specific subset (e.g., "Action" to "Action/Sci-Fi").
  • Preference Stabilizing ($R_s$): Remaining within the same category combination.
  • Preference Jumping ($R_j$): Moving to an unrelated category set, categorized as either "near" or "far" jumps.

This directional approach is a significant advancement over standard models, which often treat the sequence of interactions as unordered, missing the critical context of "interest drift."

Implementation: CCSRank and CCSMF

The CCSMR framework is implemented through two primary models:

  1. CCSRank: A personalized PageRank algorithm operating on a "CoGraph" (a compound graph of user interactions and category relations). It learns optimal weights for different semantic transitions.
  2. CCSMF: A modified Matrix Factorization model that incorporates CCS ranking values as latent factors to improve the accuracy of rating predictions.

Empirical Evaluation

The model was tested on two real-world datasets: MovieLens 1M (3,952 movies, 18 genres) and Yelp (29k food items, 19 categories). In the MovieLens dataset, the authors identified 301 unique combinatorial categories.

Distribution of movies and watch patterns across combinatorial categories in the MovieLens dataset.

Analysis of the datasets (as seen in the figure above) reveals that while many movies cluster in a few common category combinations, there is a long tail of distinct combinations. The CCSMR model's ability to navigate this space allows it to remain robust even when direct user-item interaction data is sparse.

Key Results and Insights

CCSMR consistently outperformed state-of-the-art baselines like CHMF (Hierarchical MF) and GUCF (Temporal Collaborative Filtering). On the MovieLens dataset, CCSMF improved Recall by 17.6% and AUC by 2.3% over the best-performing baseline.

Key takeaways include:

  • Order Matters: Capturing the direction of interest (narrowing vs. expanding) provides a more descriptive profile of user intent.
  • Complexity Reduction: Mapping items to unique nodes in a lattice reduces the computational difficulty of handling multi-label categories while increasing the model's descriptive power.
  • Sparsity Resilience: By inferring preferences based on semantic distances in the CCS, the model provides high-quality recommendations even for items with few ratings.

Future Directions

While highly effective, the model currently relies on expert-assigned categories. Future iterations may integrate advanced word embeddings (such as BERT) to define semantic relationships between categories automatically. Additionally, the researchers plan to explore user-user commonalities within the CCS to further refine social-based recommendation strategies.

Summary updated

Abstract

Various side information has been exploited in recommender systems to help users finding items they prefer to alleviate data sparsity. Because item category can be used to view the user’s preference in a high-level scope and an item can have more than one associated category, the existing works leverage this characteristic, that enriches the information density of item, to further improve the recommendation performance. However, the existing works either treat item categories or their correlations as additional information to compute the similarity between users and items, or introduce <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">category hierarchy</i> as a latent factor into matrix factorization (MF) models. In these works, each item corresponds to a category set, that makes it too difficult to utilize item category’s potential and valuable information. In this paper, we propose a novel combinatorial category space based recommendation model, which can fully exploit item category information and reduce the difficulty by converting the relationship between item and its categories from one-to-many to one-to-one. It considers a combinatorial category associated with an item, not each of them individually. Specifically, we first define a combinatorial category space (CCS), which is viewed as a subset-superset lattice of item categories. Then semantic relations and semantic distances are defined to model a user preference, and a compound graph (CoGraph) is constructed to model users’ interactive behaviors in CCS, respectively. Finally, two recommendation models, CCSRank and CCSMF, are exploited on user interactive graph. We carry out extensive experimental evaluations on two real datasets to show the effectiveness of our model.
BibTeX
@article{xiao2019ccsmr,
  author = {Chunjing Xiao and Kewen Xia and Leilei Sun and Cong Xie and Yuxiang Zhang},
  title = {{CCSMR: A Combinatorial Category Space-Based Model for Recommendation}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2933028},
}
Figure