gOCCF: Graph-Theoretic One-Class Collaborative Filtering Based on Uninteresting Items

Yeon-Chang Lee, Sang-Wook Kim, Dongwon LeeAAAI 2018 · DOI

Abstract

One-Class Collaborative Filtering (OCCF) is the standard for recommendation systems using implicit feedback, yet it suffers from extreme data sparsity and a lack of negative signals. This paper introduces gOCCF, a graph-theoretic framework that identifies "uninteresting items" (U-items) to serve as negative preferences. By applying graph shattering theory to determine the optimal density of these negative signals, gOCCF creates a robust bipartite graph for recommendation. Experimental results demonstrate that gOCCF significantly outperforms state-of-the-art methods, achieving up to a 48% improvement in nDCG@10 on highly sparse datasets.

Introduction

Most modern recommendation engines operate in a "one-class" environment, tracking positive interactions like clicks or purchases while lacking explicit negative feedback. This leads to two primary challenges: the ambiguity of unobserved interactions and extreme data sparsity, where user-item matrices are often over 99% empty. Traditional models like Matrix Factorization (WRMF) or Bayesian Personalized Ranking (BPR) frequently struggle as sparsity increases. The gOCCF framework addresses these issues by systematically identifying items a user is likely to find uninteresting and modeling them as negative edges in a graph.

Methodology

The gOCCF framework follows a five-step pipeline to transform sparse implicit data into a rich, signed graph structure for inference:

  1. Infer Interestingness: An initial model (e.g., WRMF) generates preliminary scores for all unrated items.
  2. Identify U-items: Items with the lowest scores are designated as "Uninteresting Items" (U-items).
  3. Graph Shattering Theory: To avoid manual tuning of negative signal density, the authors utilize graph shattering theory. By analyzing topological properties such as effective diameter and connectivity, they identify the "shattering point" where the negative graph's structure most effectively mirrors a real interaction network (the R-region).
  4. Graph Modeling: Users and items are represented as nodes in a bipartite graph, configured either as separate positive/negative graphs or a single signed graph.
  5. Graph-Based Inference: Classic algorithms like Random Walk with Restart (RWR) and Belief Propagation (BP) are adapted to propagate information across these dual-natured links.
The five-step gOCCF pipeline, illustrating the transition from a sparse preference matrix to graph-based inference via graph shattering analysis.

Experimental Evaluation

The researchers evaluated gOCCF against eight competing methods across three real-world datasets: MovieLens 100K (93.69% sparse), Watcha (96.98% sparse), and CiteULike (99.82% sparse).

A key finding was the sensitivity of traditional models to the injection of negative signals (zeros). As shown in the performance metrics, models like SVD and PMF exhibit volatile performance depending on the percentage of zero injection, often peaking early before declining. gOCCF overcomes this by using graph shattering to automatically identify the optimal injection level.

Impact of zero injection on nDCG@10 and MRR, demonstrating the performance sensitivity of baseline models compared to the stable baseline of WRMF.

On the extremely sparse CiteULike dataset, gOCCF variants (separateRWR and separateBP) achieved significant gains over the best-performing baselines, including a 48% improvement in nDCG@10, a 36% increase in MRR, and a 67% boost in Half-Life Utility (HLU).

Conclusion

gOCCF represents a significant advancement in OCCF by turning the "mystery" of unrated items into a structured roadmap of negative preferences. By leveraging the topological properties of graphs through shattering theory, the framework provides a parameter-free method to densify sparse data. This approach not only improves recommendation accuracy but also demonstrates remarkable robustness in the most data-poor scenarios common in real-world applications.

Summary updated

BibTeX
@inproceedings{lee2018goccf,
  author = {Yeon-Chang Lee and Sang-Wook Kim and Dongwon Lee},
  title = {{gOCCF: Graph-Theoretic One-Class Collaborative Filtering Based on Uninteresting Items}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11707},
}
Figure