Accuracy-Diversity Trade-off in Recommender Systems via Graph Convolutions

This repository contains the code of the paper "Accuracy-Diversity Trade-off in Recommender Systems via Graph Convolutions". For any question or suggestion, please e-mail Matteo Pocchiari at [email protected] or Elvin Isufi at [email protected].

Parts of this code are taken verbatim from the source code of the paper "Rating Prediction via Graph Signal Processing" (Huang et al., 2018) available here, while the graph neural networks part is inspired to the GNN library implemented by Fernando Gama, available here.

When using part of this code, please cite the following paper

Elvin Isufi, Matteo Pocchiari, Alan Hanjalic, "Accuracy-Diversity Trade-off in Recommender Systems via Graph Convolutions", in Information Processing and Management (2021).

1. Introduction
2. Accounting For Disimilar Furthest Neighbors
3. Code

1. Introduction

We work with a set of users , with and a set of items , with . Each user can give a rating to the items in . We write the available ratings in matrix form, by filling the user-item matrix (UIM) , where entry contains the rating user u gave to item i. The goal is to predict the missing ratings of the UIM, to obtain the matrix with all the predictions.

Consider a graph defined by a set of nodes and a set of edges . On top of the graph we define a graph signal which associates a scalar to each node in . We use graph signal processing tools to predict the missing entries of the UIM and obtain . We define the user-similarity graph , which can be particularized according to the specific item i with the adjacency matrix and the graph signal . Likewise, the item-similarity graph is described by the user specific adjacency matrix and the graph signal .

We use graph convolutional filters both in linear and nonlinear (see figure below) fashion to predict the missing ratings. In the user setting, we use the graph convolutional filter described by the set of coefficients to predict the ratings specific to item i: the vector contains the predictions all users in would give to item i. Similarly for the item case, we work with the graph convolutional filter to predict the ratings a specific user u would give to all the items in ; therefore all the predictions for the user u are contained in the vector . To generalize, we work with a map which can be a plain graph convolutional filter or a graph convolutional neural network.

2. Accounting For Disimilar Furthest Neighbors

We propose to use graph convolutions for establishing a novel accuracy-diversity trade-off for RS, by means of a novel accuracy-diversity trade-off framework for RS via graph convolutions. The model jointly operates on a NN graph to improve accuracy and on a FN graph to improve diversity. Each graph can capture user-user or item-item relationships, allowing to also include the hybrid settings, such as a user-NN and an item-FN graph. We develop design strategies that estimate the joint model parameters in view of both accuracy and diversity. These design strategies are versatile to both rating and ranking frameworks. In the rating case, they optimize the mean square error between the prediction and the true rating and consider the accuracy-diversity trade-off as a regularizer. In the ranking case, they optimize the Bayesian personalized ranking criterion proposed by Rendle et al., to account for the final order in the recommendation list, and the accuracy-diversity trade-off is also considered the regularizer.

Leveraging Negative Correlations

We work with a NN similarity-graph and a FN dissimilarity-graph . The dissimilarity graph is built by following the opposite principles of NNs, i.e., connecting each entity to its top-n most negatively related ones. On each graph and we have a convolutional module and , outputting an estimate of the user-item matrix and , respectively. We combine the two outputs in the joint estimate , where scalar balances the influence of the similar and dissimilar connections.

Each graph or can be a user or an item graph and the graph convolutional modules can be linear or nonlinear. This framework yields eights combinations to investigate the trade-off. To ease exposition, we shall discuss the theoretical methods with the hybrid combination user NN graph (i.e., with adjacency matrix for item i) and item FN graph (i.e., with adjacency matrix for user u). This setting implies we predict rating by learning, on one side, from the coupling , and, on the other side, from the coupling .

Learning For Rating

We estimate the joint model parameters w.r.t. the mean squared error (MSE) criterion. Analyzing the MSE quantifies also the trade-off for all items in the dataset (unbiasing the results from the user preferences in the list). To this end, consider a training set of user-item pairs T={(u,i)} for the available ratings in X. Consider also the user-similarity graph , the item-dissimilarity graph (i.e., , and their respective graph convolutions and . We estimate parameters and by solving the regularized problem

where measures the fitting error w.r.t. the available ratings , while the second term acts as an accuracy-diversity regularizer. The two filters and can be either two plain graph convolutional filters, or two GCNNs, with implications about optimality and expressivity, which we discuss thoroughly in the paper.

Learning For Ranking

We considered the Bayesian personalized ranking (BPR), which is a state-of-the-art learn-to-ranking framework (Rendle et al.). BPR considers the rating difference a user u has given to two items i and j. The term is used in the loss function

where is the sigmoid function. More details about the BPR criterion and its derivation can be found in the paper. As in the case of rating optimization, the convolutions and used in the prediction can be either two plain graph convolutional filters or two GCNNs.

3. Code

The code is written in Python 3. Model with linear optimization rely on NumPy and SciPy, while models with nonlinear optimization make use of PyTorch. Linear rating optimization is taken from the source code of the paper "Rating Prediction via Graph Signal Processing" (Huang et al., 2018) available here. Linear ranking optimization is inspired to the BPR implmentation from the code of the paper "Bayesian Personalized Ranking with Multi-Channel User Feedback (Loni et al., 2016)", available here. Nonlinear rating and ranking optimization is inspired to the GNN implementation of Fernando Gama, available here.

Dependecies

To run the code, the following libraries are required: os, argparse, torch, sys, numpy, scipy, ast, time, datetime, math, itertools, pickle.

Usage

The code is divided into four main files: linearRating, linearRanking, nonlinearRating, nonlinearRanking, corresponding to the four possible aforementioned combinations. To run the code, download/clone the repository on your desktop, open the terminal in the folder and run from the terminal: python [selected_mode] [parameters].

The list of parameters is the following:

• -method [string: UU (default), UI, IU, II]: defines the combination of users/items to use. The first letter defines the similarity source, while the second defines the dissimilarity source (U for users, I for Items).
• -simOrd [int: default 1]: defines the order of the graph filter applied on the similarity graph.
• -disOrd [int: default 1]: defines the order of the graph filter applied on the dissimilarity graph.
• -simNeigh [int: default 30]: defines the number of neighbors in the similarity graph.
• -disNeigh [int: default 40]: defines the number of neighbors in the dissilarity graph.
• -mu [float: default 1.0]: defines the parameter responsible for the overfitting in the optimization function.
• -alpha [float: default 0.1]: defines the value of alpha, i.e. how much importance should be given to the dissimilarity graph.
• -dataset [string: ml100k (deafult), ml1m, douban, flixster]: defines the dataset to use.
• -epochs [int: default 1]: defines the number of epochs, i.e. how many times the dataset is traversed in the training.
• -lr [float: default 0.001]: defines the learning rate.
• -batch [int: default 1]: defines the batch size.
• -neg [int: default 4]: defines the number of "negative" samples to consider in the BPR, in case of ranking optimization.
• -feat [list: default [1,2]]: defines the number of features of the GCNN.

The script linearRating.py accepts as parameters -method, -simOrd, -disOrd, -simNeigh, -disNeigh, -mu, -alpha, -dataset;

The script linearRanking.py accepts as parameters -method, -simOrd, -disOrd, -mu, -alpha, -dataset, -epochs, -batch, -neg, -lr;

The script nonlinearRating.py accepts as parameters -method, -simOrd, -disOrd, -mu, -alpha, -dataset, -epochs, -batch, -lr, -feat;

The script nonlinearRanking.py accepts as parameters -method, -simOrd, -disOrd, -mu, -alpha, -dataset, -epochs, -batch, -lr, -feat, -neg;

Examples

• Linear rating optimization: python linearRating.py -method UI -simOrd 3 -disOrd 2 -simNeigh 30 -disNeigh 40 -mu 0.5 -alpha 0.1 -dataset ml100k
• Linear ranking optimization: python linearRanking.py -method UI -simOrd 1 -disOrd 2 mu 0.5 -alpha 0.1 -dataset ml100k -epochs 1 -batch 1 -neg 4 -lr 0.00001
• Nonlinear rating optimization: python nonlinearRating.py -method UI -simOrd 1 -disOrd 2 mu 0.5 -alpha 0.1 -dataset ml100k -epochs 1 -batch 1 -lr 0.00001 -feat [1,4]
• Nonlinear ranking optimization: python nonlinearRating.py -method UI -simOrd 1 -disOrd 2 mu 0.5 -alpha 0.1 -dataset ml100k -epochs 1 -batch 1 -lr 0.00001 -feat [1,4] -neg 4