Latent factor models for link prediction problems
Institution:
Paris 6Disciplines:
Directors:
Abstract EN:
Avec la croissance d'Internet et celle des médias sociaux, les données relationnelles, qui décrivent un ensemble d'objets liés entre eux par différents relations, sont devenues courantes. En conséquence, une grande variété d'applications, telles que les systèmes de recommandation, l'analyse de réseaux sociaux, la fouille de données Web ou la bioinformatique, ont motivé l'étude de techniques d'apprentissage relationnel. Parmi le large éventail de ces techniques, nous traitons dans cette thèse le problème de prédiction de liens. Le problème de la prédiction de liens est une tache fondamentale de l'apprentissage relationnel, consistant à prédire la présence ou l'absence de liens entre objets, à partir de la topologie du réseau et/ou les attributs des objets. Cependant, la complexité et la sparsité des réseaux font de cette tache un problème ardu. Dans cette thèse, nous proposons des solutions pour faciliter l'apprentissage dans le cas de différentes applications. Dans le chapitre 3, nous présentons un cadre unifié afin de traiter le problème générique de prédiction de liens. Nous discutons les différentes caractéristiques des modèles des points de vue probabiliste et computationnel. Ensuite, en se focalisant sur les applications traitées dans cette thèse, nous proposons des modèles à facteurs latents pour deux types de taches de prédiction de liens: (i) prédiction structurelle de liens et (ii) prédiction temporelle de liens. Concernant la prédiction structurelle de liens, nous proposons dans le chapitre 4 une nouvelle application que nous appellons Prédiction de Motifs de Liens (PML). Nous introduisons un facteur latent spécifique pour différents types de relations en plus de facteurs latents pour caractériser les objets. Nous présentons un modèle de actorisation tensorielle dans un cadre Bayésien pour révéler la causalité intrinsèque de l'interaction sociale dans les réseaux multi-relationnels. De plus, étant donné la structure complexe des données relationnelles, nous proposons dans le chapitre 5 un modèle qui incorpore simultanément l'effet des facteurs de caractéristiques latentes et l'impact de la structure en blocs du réseau. Concernant la prédiction temporelle de liens dans les réseaux dynamiques, nous proposons dans le Chapitre 6 un modèle latent unifié qui intègre des sources d'information multiples, la topologie globale du réseau, les attributs des noeuds et les informations de proximité du réseau afin de capturer les motifs d'évolution temporelle des liens. Ce modèle joint repose sur la factorisation latente de matrices et sur une techniques de régularisation pour graphes. Chaque modèle proposé dans cette thèse a des performances comparables ou supérieures aux méthodes existantes. Des évaluations complètes sont conduites sur des jeux de données réels pour démontrer leur performances supérieures sur les méthodes de base. La quasi-totalité d'entre eux ont fait l'objet d'une publication dans des conférences nationales ou internationales.
Abstract FR:
With the rising of Internet as well as modern social media, relational data has become ubiquitous, which consists of those kinds of data where the objects are linked to each other with various relation types. Accordingly, various relational learning techniques have been studied in a large variety of applications with relational data, such as recommender systems, social network analysis, Web mining or bioinformatic. Among a wide range of tasks encompassed by relational learning, we address the problem of link prediction in this thesis. Link prediction has arisen as a fundamental task in relational learning, which considers to predict the presence or absence of links between objects in the relational data based on the topological structure of the network and/or the attributes of objects. However, the complexity and sparsity of network structure make this a great challenging problem. In this thesis, we propose solutions to reduce the difficulties in learning and fit various models into corresponding applications. Basically, in Chapter 3 we present a unified framework of latent factor models to address the generic link prediction problem, in which we specifically discuss various configurations in the models from computational perspective and probabilistic view. Then, according to the applications addressed in this dissertation, we propose different latentfactor models for two classes of link prediction problems: (i) structural link prediction. (ii) temporal link prediction. In terms of structural link prediction problem, in Chapter 4 we define a new task called Link Pattern Prediction (LPP) in multi-relational networks. By introducing a specific latent factor for different relation types in addition to using latent feature factors to characterize objects, we develop a computational tensor factorization model, and the probabilistic version with its Bayesian treatment to reveal the intrinsic causality of interaction patterns in multi-relational networks. Moreover, considering the complex structural patterns in relational data, in Chapter 5 we propose a novel model that simultaneously incorporates the effect of latent feature factors and the impact from the latent cluster structures in the network, and also develop an optimization transfer algorithm to facilitate the model learning procedure. In terms of temporal link prediction problem in time-evolving networks, in Chapter 6 we propose a unified latent factor model which integrates multiple information sources in the network, including the global network structure, the content of objects and the graph proximity information from the network to capture the time-evolving patterns of links. This joint model is constructed based on matrix factorization and graph regularization technique. Each model proposed in this thesis achieves state-of-the-art performances, extensive experiments are conducted on real world datasets to demonstrate their significant improvements over baseline methods. Almost all of themhave been published in international or national peer-reviewed conference proceedings.