Universality of path algebra for recommendation problems

Abstract

For many of their daily activities, people interact with on­line systems that offer an un­precedented variety of products and services. To help users make the best choice, rec­ommender systems come to the rescue. Early recommender systems assumed a sim­ple model that involved two types of entities: users (who receive recommendations) and items (that are recommended). As recent applications became more complex to better accommodate user needs, they now have access to richer, multi­dimensional data, and can involve several kinds of entities. Currently, existing work in the area provides an abundance of recommendation approaches that differ in their philosophy, algorithms, and overall characteristics that aim to tackle various recommendation use cases. Inevitably, this has resulted in an enormous number of solutions that seemingly address different problems, that involve a lot of replicated effort, and that have unclear differences. The main question of this thesis is whether it is possible to devise a small set of dimensions (i.e., operations) that could concisely describe the vast recommendation space, capturing any recommendation possibility? We argue that recommendations can be abstracted as a graph exploration problem and we describe a graph­-theoretic framework with two primary parts: (a) a recommendation graph to model all the elements of an (application) domain from a recommendation perspective, including the subjects of recommendation (that re­ceive recommendations) and its objects (recommended to subjects), as well as relation­ships among them; (b) a set of path operations to infer new edges, i.e., implicit or unknown relationships, by traversing and combining paths on the graph. These operations allow us to express a wide variety of different recommendations as graph explorations. This ap­proach departs from prior work on recommendation systems, where the graph perspective is mostly missing, and graph­-based systems, which are more generic and not targeted to­ wards recommendations. It provides an abstraction of the recommendation process that reveals a common foundation underlying most recommendation approaches and opens up the door to their efficient optimized implementation over a graph engine. The contribution of the thesis can be summarized as follows: 1. We introduce an elegant data model and a computational model to describe rec­ommendation problems as path problems and to build generic fine­tuned recom­menders. 2. We present a Datalog-­like query language that fits the proposed framework. 3. We show how different recommendation strategies can be captured uniformly within our model using the proposed operators. 4. We show examples of novel applications and how they can be represented with our model. 5. We present optimization opportunities in the derivation and execution of recommen­dations by examining properties of the operators of its computational model. 6. We implement a generic recommender prototype on top of the Neo4j graph system and perform a set of experiments on different recommendation paradigms where all the above benefits arise.

Οι άνθρωποι αλληλεπιδρούν με διαδικτυακά συστήματα σε καθημερινή βάση για πολλα­πλών ειδών δραστηριότητες. Τα συστήματα αυτά προσφέρουν μια πρωτόγνωρη πληθώρα προϊόντων και υπηρεσιών. Για να βοηθήσουν τους χρήστες να κάνουν την καλύτερη δυνατή επιλογή, τα συστήματα συστάσεων έρχονται να δώσουν λύση στην κατάσταση. Τα πρώιμα συστήματα συστάσεων υποθέτουν ένα απλό μοντέλο που περιλαμβάνει δύο ειδών οντότητες: χρήστες (που δέχονται τις συστάσεις) και αντικείμενα (που αποτελούν την σύσταση). Η εξέλιξη των σημερινών εφαρμογών ώστε να καλύπτουν όλο και καλύτερα νέες ανάγκες χρήσης, αύξησε την πολυπλοκότητά τους και άνοιξε την πρόσβαση σε πιο πλούσιους, πολυδιάσταστους τύπους δεδομένων που εμπλέκουν διαφορετικών τύπων οντότητες. Η υπάρχουσα δουλειά στην περιοχή αυτή τη στιγμή παρέχει μια πληθώρα προσεγγίσεων που διαφέρουν στη φιλοσοφία τους, στους αλγορίθμους που χρησιμοποι­ούν και στο σύνολο των χαρακτηριστικών τους, που προσπαθούν να αντιμετωπίσουν διάφορες περιπτώσεις χρήσης που σχετίζονται με παροχή συστάσεων. Αναπόφευκτα, αυτό έχει οδηγήσει σε ένα μεγάλο αριθμό από λύσεις που ενώ φαινομενικά αντιμετωπίζουν διαφορετικά προβλήματα, περιλαμβάνουν κοινά τμήματα στον τρόπο επίλυσης και οι δι­αφορές μεταξύ τους δεν είναι ξεκάθαρες. Στην παρούσα διατριβή εξετάζουμε εάν είναι δυνατόν να κατασκευάσει κάποιος ένα μικρό σύνολο διαστάσεων (δλδ. τελεστών), οι οποίες να περιγράφουν με ακρίβεια το χώρο των προβλημάτων συστάσεων, περιλαμβά­νοντας κάθε περίπτωση σύστασης. Επιχειρηματολογούμε ότι ένα πρόβλημα σύστασης μπορεί να γενικευθεί ως πρόβλημα εξερεύνησης γράφου, και περιγράφουμε ένα γραφο­-θεωρητικό πλαίσιο με δύο βασικά τμήματα: (α) ένα γράφο συστάσεων που μοντελοποιεί όλα τα στοιχεία μιας εφαρμογής εξετάζοντας τα από την οπτική γωνία της παροχής συστά­σεων και που περιλαμβάνει, τα υποκείμενα της σύστασης (που είναι οι αποδέκτες συστά­σεων), τα αντικείμενα της σύστασης (που προτείνονται στα υποκείμενα) και τις μεταξύ τους σχέσεις; (β) ένα σύνολο από τελεστές μονοπατιών που παράγει νέες ακμές, δλδ, έμμεσες ή άγνωστες συσχετίσεις, διασχίζοντας και συνδυάζοντας μονοπάτια πάνω στο γράφο. Αυτοί οι τελεστές μας επιτρέπουν να εκφράσουμε μια μεγάλη ποικιλία από διαφορετικά προβλήματα συστάσεων ως προβλήματα εξερεύνησης γράφου. Αυτή η προσέγγιση δι­αφέρει από προήγουμενες δουλειές στα συστήματα συστάσεων, όπου η προοπτική του γράφου είτε σε μεγάλο βαθμό λείπει, και στα συστήματα επεξεργασίας δεδομένων γράφου, που προορίζονται για πιο γενικές χρήσεις και δε στοχεύουν μόνο στην παραγωγή συ­στάσεων. Παρέχει μια γενίκευση της διαδικασίας που αποκαλύπτει μια κοινή βάση στις περσσότερες διαδικασίες παραγωγής συστάσεων, και που ανοίγει την πόρτα για πιο απο­δοτική βελτιστοποίηση πάνω από μια μηχανή γράφου. Η συνεισφορά της διδακτορικής διατριβής συνοψίζεται στα εξής σημεία:1. Παρουσίαση ενός κομψού μοντέλου δεδομένων και ενός μοντέλου υπολογισμού για την περιγραφή των προβλημάτων συστάσεων ως προβλήματα μονοπατιών και την ανάπτυξη γενικευμένων προσαρμόσιμων συστημάτων συστάσεων. 2. Παρουσίαση μια γλώσσας ερωτημάτων Datalog­τύπου που ταιριάζει στο συγκεκριμένο πλαίσιο. 3. Ανάπτυξη διαφορετικών στρατηγικών παραγωγής συστάσεων που αντιμετωπίζονται ομοιόμορφα με το μοντέλο μας και τη χρήση των προτεινόμενων τελεστών. 4. Ανάπτυξη παραδειγμάτων εφαρμογής του μοντέλου σε νέες, καινοφανείς εφαρμογές. 5. Παρουσίαση ευκαιριών βελτιστοποίησης στον τρόπο παραγωγής και εκτέλεσης συ­στάσεων, εξετάζοντας ισχύουσες ιδιότητες των τελεστών του μοντέλου υπολογισμού.6. Υλοποίηση ενός γενικευμένου πρωτότυπου συστήματος συστάσεων πάνω από το σύστημα επεξεργασίας γράφων Neo4j, και την εκτέλεση πειραμάτων διαφορετικώνπαραδειγμάτων σύστασης όπου όλα τα παραπάνω πλεονεκτήματα προκύπτουν.