Offre de thèse 2020 : Vers une approche globale et dynamique de recommandation par graphes

Lieu : équipe KIWI (kiwi.loria.fr) du laboratoire LORIA (www.loria.fr), Université de Lorraine

Encadrant : Geoffray Bonnin – geoffray.bonnin@loria.fr

Directeur : Armelle Brun – armelle.brun@loria.fr

Démarrage : octobre 2020

Contexte

Les systèmes de recommandation constituent un domaine de recherche très actif dont l’objectif est de fournir des recommandations personnalisées à des utilisateurs, au sein d’un espace de données important. Ces systèmes connaissent un grand succès, les types de recommandations étant très divers : des films, de la musique, des ressources culturelles, des produits de e-commerce, des ressources pédagogiques et même des utilisateurs ; de même que l’objectif des recommandations : court, moyen ou long-terme, pour un utilisateur isolé ou en groupe, etc.

Les défis scientifiques de ce domaine sont très nombreux. Ils peuvent par exemple concerner la complexité des algorithmes, leur neutralité, leur explicabilité, leur inclusivité, l’adoption des recommandations, leur impact, etc.

Bien que proposée dès l’apparition des systèmes de recommandation en tant que domaine de recherche, l’une des approches les plus efficaces et la plus populaire est le filtrage collaboratif (Jannach et al., 2012), qui suit l’hypothèse dite d’homophilie. De façon générale, une approche par filtrage collaboratif recommande donc à un utilisateur les ressources appréciées ou accédées par le passé par les utilisateurs qui lui sont similaires.

Cependant, cette hypothèse peut ne pas être suffisante. En particulier, les appréciations peuvent inclure une part purement subjective (propre à l’individu), une part inter-subjective, c’est-à-dire influencée par les communautés auxquelles l’utilisateur appartient, et une part qui dépasse ces communautés. L’influence entre utilisateurs a été modélisée dans les systèmes de recommandation grâce aux mécanismes de propagation. Elle peut par exemple porter sur la notion de confiance entre utilisateurs et de son exploitation pour la recommandation [Jamali et Ester, 2010]. Ces systèmes reposent par ailleurs souvent sur une représentation des données sous la forme de graphes [Lee et Lee, 2015].

Problème et objectif

Bien que s’intéressant au lien entre les utilisateurs, la très grande majorité des systèmes de recommandation aborde la recommandation comme un problème à la foisstatiqueet local.Considérant un utilisateur actif, l’objectif est d’identifier les meilleures ressources à lui recommander afin de le satisfaire au moment de la recommandation (recommandation statique), sans tenir compte de l’impact de cette recommandation dans la durée, ni sur ses communautés ou sur l’ensemble des utilisateurs (recommandation locale).

Le problème traité dans cette thèse a une double originalité. Il vise à aborder le problème de la recommandation comme un problème dynamique, et notamment temporel, dans le sens où une recommandation peut avoir un impact temporellement plus éloigné que l’impact immédiat habituellement considéré. Il vise également à considérer l’impact d’une recommandation sur une communauté voire sur l’ensemble des utilisateurs.

Grâce à ces deux objectifs, il sera ainsi possible d’entrevoir des algorithmes de recommandation sous contrainte, que ce soit de temps, de nombre d’actions, etc. Par exemple, il sera possible de déterminer une politique de recommandation qui limite le nombre de recommandations, donc les intrusions dans un système, tout en garantissant que l’objectif visé est atteint effectivement à terme. Il sera également possible de chercher à atteindre un objectif sous contrainte d’horizon de temps pour atteindre cet objectif.

Ce problème modifie en profondeur l’approche de la recommandation, ce qui aura notamment un impact sur la complexité des algorithmes.

Nous pouvons partir de l’hypothèse classique que les données sont représentées sous la forme d’un graphe, un graphe social, et probablement temporel, et que la recommandation pourra être soit une recommandation de ressources, soit une recommandation de liens.

Le défi scientifique est donc le suivant : soit un graphe social à un temps t. Connaissant le graphe cible vers lequel on souhaite aller au temps t+n(ce graphe pouvant être sous-spécifié), comment définir une politique d’actions mener (au travers de recommandations), pour atteindre ce graphe ? Le modèle proposé pourra répondre à des contraintes de minimisation du temps, du nombre d’actions à mener, du nombre de nœuds sur lequel le modèle a un impact direct, etc.

De nouveaux modèles de recommandation et d’estimation de préférences et d’impact devront donc être proposés.

Ce sujet se situe donc à la jonction entre plusieurs problématiques de recherche : les graphes temporels, la propagation dans les graphes, la prédiction de liens, la recommandation, l’identification de communautés.

Bibliographie

[Jamali et Ester, 2010] Jamali, M., & Ester, M. (2010, September). A matrix factorization technique with trust propagation for recommendation in social networks. In Proceedings of the fourth ACM conference on Recommender systems(pp. 135-142).

[Jannach et al., 2012]  D. Jannach, M. Zanker, M. Ge et M. Gröning, «Recommender systems in computer science and information systems – a landscape of research,» chez Proc. EC-WEB, 2012

[Wang et al., 2018] Wang, H., Zhang, F., Wang, J., Zhao, M., Li, W., Xie, X., & Guo, M. (2018, October). Ripplenet: Propagating user preferences on the knowledge graph for recommender systems. InProceedings of the 27th ACM International Conference on Information and Knowledge Management(pp. 417-426).

[Lee et Lee, 2015] Lee, K., & Lee, K. (2015). Escaping your comfort zone: A graph-based recommender system for finding novel recommendations among relevant items. Expert Systems with Applications, 42(10), 4851-4858.

Logo d'Inria