Uncertain Graphs meet Collaborative Filtering

Claudio Taranto, Nicola Di Mauro, Floriana EspositoIIR 2012 · OpenReview

Abstract

This paper introduces a novel framework that redefines Collaborative Filtering (CF) as a link-prediction problem within "uncertain graphs." By encoding user-item relationships and similarities as probabilistic edges, the authors utilize a path-based query language to unify user-based, item-based, and hybrid recommendation strategies. Experimental results on benchmark datasets demonstrate that this approach captures complex, multi-hop relationships more effectively than traditional neighborhood models, leading to significant improvements in prediction accuracy.

Introduction

Collaborative Filtering is a fundamental technique in modern recommender systems, traditionally categorized into user-based and item-based approaches. Despite their success, these methods often struggle with data sparsity and are limited to capturing simple, direct relationships. They fail to leverage the rich, multi-hop connections inherent in social and interaction networks—such as a user similar to someone who liked an item similar to the one under consideration.

This research addresses these limitations by bridging the gap between simple neighborhood models and complex network analysis. The authors propose modeling the recommendation domain as an uncertain graph, where the inherent ambiguity of user behavior is mathematically represented through probabilistic edges.

Methodology

The proposed framework represents the recommendation environment as an Uncertain Graph where nodes represent users and items, and edges represent either known ratings or calculated similarities.

Graph Construction and Probabilistic Edges

Unlike deterministic graphs, edges in this model carry a probability $P(e)$. For rating edges, the probability reflects the strength of the interaction. Similarity probabilities are derived using a weighted Pearson correlation. This probabilistic approach naturally accounts for noise; for instance, a similarity based on fifty overlapping ratings is treated with higher certainty than one based on only two.

Language-Constrained Paths

The core innovation lies in using Context-Free Grammars (CFG) to define "valid" paths for recommendation. This allows different CF strategies to be expressed as specific "sentences" in a graph language. For example, a standard user-based recommendation follows the path: User -> simU -> User -> Rating -> Item.

Formal definitions of recommendation paths L1 through L8.

Inference via Possible Worlds

Calculating exact path probabilities in uncertain graphs is #P-complete. To ensure computational tractability, the authors employ a Monte Carlo sampling approach. This involves generating multiple "possible worlds"—snapshots of the graph where edges are sampled based on their probabilities—to estimate the likelihood of a link between a user and an item.

Experimental Results

The framework was evaluated on the MovieLens 100K and MovieLens 1M datasets, standard benchmarks for CF algorithms. Performance was measured using Mean Absolute Error (MAE).

Path Performance and Hybrid Superiority

The results indicate that hybrid and deeper paths consistently outperform simpler models. On MovieLens 100K, the hybrid path $L_7$, which combines both user and item similarities, achieved an MAE of 0.7676, a substantial improvement over the basic user-based path $L_1$ (0.9349).

Mean Absolute Error (MAE) results for different path constraints across 5 folds on MovieLens 100K.

Comparison with Baselines

On the larger MovieLens 1M dataset, the uncertain graph approach using a 4-hop neighborhood ($L_8$) achieved an MAE of 0.7198. This outperformed established baselines such as Pearson Correlation (0.7518) and Mean Squared Difference (0.7602). The data suggests that as the query language allows for more complex and deeper paths, the error rate consistently drops.

Conclusion and Future Work

By treating Collaborative Filtering as a path-query problem on uncertain graphs, this framework provides a powerful tool for unifying and extending recommendation strategies. The ability to explore deeper neighborhoods significantly enhances accuracy.

However, the computational cost of Monte Carlo sampling remains a challenge for real-time deployment at scale. Future research will focus on optimizing the graph construction phase—specifically how neighborhood size impacts quality—and developing more efficient inference algorithms to reduce reliance on heavy sampling.

Summary updated

BibTeX
@inproceedings{taranto2012uncertain,
  author = {Claudio Taranto and Nicola Di Mauro and Floriana Esposito},
  title = {{Uncertain Graphs meet Collaborative Filtering}},
  booktitle = {IIR},
  year = {2012},
  url = {https://openreview.net/forum?id=6ShPaaV29hT},
}
Figure