An application of bicriterion shortest paths to collaborative filtering

Item-based collaborative filtering is one of most widely used and successful neighborhood-based collaborative recommendation approaches. The main idea of item-based algorithms is to compute predictions using the similarity between items. In such approaches, two items are similar if several users of the system have rated these items in a similar fashion. Traditional item-based collaborative filtering algorithms suffer from the lack of available ratings. When the rating data is sparse, as it happens in practice, many items without any rating in common are present. Thus similarity weights may be computed using only a small number of ratings and consequently the item-based approach will make predictions using incomplete data, resulting in biased recommendations. In this paper we present a two phase method to find the similarity between items. In the first phase a similarity matrix is found by using a traditional method. In the second phase we improve the similarity matrix by using a bicreterion path approach. This approach introduces additional similarity links by combining two or more existing links. The two criteria take into account on the one hand the distance between items on a suitable graph (min sum criterion), on the other hand the estimate of the information reliability (max min criterion). Experimental results on the Netflix and Movielens datasets showed that our approach is able to burst the accuracy of existing item-based algorithms and to outperform other algorithms.