Recommender systems (RS) assist users in making decisions by filtering content that the user would likely find relevant. Standard techniques like collaborative filtering exploit user similarities to find the recommendations assuming that similar users are likely to be interested in the same items. On the other hand, graph RS borrow techniques from the field of graph signal processing to predict ratings for items that the users have not seen and utilize a graph representation of user similarities and their corresponding ratings. Recent studies indicated that simple RS could outperform the state-of-the-art RS. Therefore our paper contributes by analyzing the performance of a novel approach to RS - collaborative filtering that uses a total variation graph regularizer. We show that total variation can outperform its predecessor collaborative filtering by reducing the root mean squared error by 4.68%. However, further experiments with top-n recommendations indicated that traditional collaborative filtering could recommend more relevant content than the total variation, which is supported by a 2.20% increase in precision. The results indicate that total variation alone does not add more information to the RS to show noteworthy improvements to existing traditional baselines. However, building on discoveries that even some of the state-of-the-art RS cannot outperform well-defined baselines, a 4.68% increase in accuracy reveals the potential of RS supported by graph regularization.

Recommender systems help users to find items they presumably like based on data collected on that user. Collaborative filtering is arguably the most common recommendation system technique. It uses collected ratings to compute similarities between users and recommends items based on those similarities. With that, a problem arises when there are few ratings available for a user, also called the cold start problem. An even stricter setting is where no ratings of a user are available at all, called the pure cold start problem. Graphs are a natural way to represent data in this domain and Graph Neural Networks (GNNs) have proven to achieve state-of-the-art accuracies in the domain of recommender systems over the past few years. In this work, we address this problem from a graph perspective. In the current literature, the problem is alleviated by turning to external information, such as demographic or social information. Although these methods work, they cannot be deployed in situations where this information is not available. However, our approach uses only rating data. As ratings are unavailable for pure cold start users, their connectivity to the graph is unknown. To overcome this, we use a stochastic attachment model to infer connectivity. This model is composed of a Bernoulli random variable with the corresponding probability value and edge weight for each existing user. In this work, we propose to learn the parameters of a graph convolution model through empirical risk minimization using the stochastic attachment model to attach users who previously attached to the graph and their ratings, and use it to predict the same for unseen users. Furthermore, we propose to learn the probability and weight values of the stochastic attachment model jointly with the parameters of the graph convolution model. We compare these methods to several graph based and non-graph baselines. Furthermore, we compare different methods such as graph filters, GCNNs, and kNN. The experiments show significant improvements of the graph approaches compared to the non-graph baselines. Furthermore, we show that training on stochastically expanded graphs improves accuracy compared to only testing on them by induction.