Transductively Learning from Positive Examples Only

Kristiaan Pelckmans, Johan A. K. SuykensESANN 2009

Introduction

In many real-world recommendation scenarios, such as movie or product suggestions, data is characterized by a significant selection bias: we typically only observe "positive" interactions. We know what a user liked, but we rarely have a representative sample of what they dislike, as users generally avoid content they expect to be unappealing. This "positive-only" data environment violates the standard independent and identically distributed (i.i.d.) assumption of many machine learning models. Furthermore, in recommendation systems, the cost of a false positive (recommending irrelevant content) often outweighs the cost of a false negative. This paper addresses these challenges by proposing a graph-based transductive learning framework designed to maximize precision in sparse, biased environments.

Methodology

The authors frame the recommendation task as a transductive inference problem on a graph, optimizing for precision rather than standard classification error.

Graph Representation and Objective

Items are represented as nodes in a weighted undirected graph where edge weights denote similarity. The goal is to find a labeling that is "smooth" across the graph—meaning similar items should share labels—while maximizing precision. The objective function balances three components:

  1. Graph Cut (Smoothness): Minimizing the total weight of edges connecting positive and negative labels.
  2. Label Fidelity: A penalty (controlled by parameter $\gamma$) for misclassifying the few known positive examples.
  3. Sparsity Constraint: A penalty (controlled by parameter $\lambda$) on the total number of positive predictions to prevent the trivial solution of labeling all items as positive.

S-T Mincut Reformulation

A core contribution of the paper is showing that this optimization problem can be reformulated as a combinatorial S-T min-cut problem. By introducing a virtual source node ($v^-$) and a sink node ($v^+$), the task becomes finding the maximum flow in the network. This allows the use of efficient algorithms like the push-relabel maximum flow algorithm, which operates in $O(n^2|E|)$ time, making it computationally feasible for large-scale item graphs.

Experimental Evaluation

The approach was tested on both synthetic and real-world datasets to evaluate its ability to recover positive labels from minimal initial data.

Artificial Dataset

The authors created a synthetic 2D dataset of 300 nodes, consisting of 280 negative and 20 positive examples sampled from two Gaussians. To simulate extreme sparsity, the algorithm was provided with only 3 positive labels.

MovieLens Dataset

The MovieLens dataset (943 users, 1,682 movies) was used to evaluate real-world performance. A graph was constructed where edge weights were determined by the co-occurrence of high ratings (4+ stars) between movies. This method successfully connected 75% of the movies in the dataset.

Results and Discussion

On the artificial dataset, the algorithm demonstrated robust recovery of the positive class. Despite having only 3 initial labels, it achieved 69% precision and 72% recall, effectively identifying the cluster of positive examples.

True vs. estimated labels on a synthetic 2D dataset using only 3 initial positive labels.

In the MovieLens experiments, the system achieved an average precision of 8.45% and recall of 16.98%. While these absolute values reflect the inherent difficulty of the task, the model significantly outperformed a baseline of recommending the 10 most closely connected movies (6.12% precision), validating the effectiveness of the min-cut optimization for precision-focused tasks.

Conclusion

This work highlights that the selection mechanism of labels in recommendation systems is fundamentally different from random sampling. By explicitly optimizing for precision and leveraging the structural properties of item similarity graphs via S-T min-cuts, the proposed method provides a mathematically grounded and efficient solution for learning from positive-only data. Future work remains in automating the selection of trade-off parameters and evaluating the system in active, online environments.

Summary updated

BibTeX
@inproceedings{pelckmans2009transductively,
  author = {Kristiaan Pelckmans and Johan A. K. Suykens},
  title = {{Transductively Learning from Positive Examples Only}},
  booktitle = {ESANN},
  year = {2009},
}
Figure