Classification dans les graphes hétérogènes et multi-relationnels avec contenu : Application aux réseaux sociaux
Institution:
Paris 6Disciplines:
Directors:
Abstract EN:
L'émergence du Web 2. 0 a vu apparaître une grande quantité de données qui peuvent naturellement se représenter sous forme de graphes complexes. Plusieurs tâches d'analyse, de prédiction et de recherche d'informations ont pour objet ces données, alors que les modèles de l'état de l'art ne sont pas adaptés à ce type d'information. Dans cette thèse, nous nous intéressons à la problématique de classification/étiquetage automatique de noeuds dans des réseaux de contenu partiellement étiquetés et complexes. Cette tâche générique trouve de nombreuses applications par exemple pour l'annotation de photos/vidéos dans les réseaux sociaux, la détection du spam sur le Web ou bien l'étiquetage de grands réseaux d'utilisateurs. L'originalité de notre travail est de se focaliser sur deux types particuliers de réseaux peu abordés dans la littérature: les graphes multi-relationnels composés de plusieurs types de relation, et les graphes hétérogènes, composés de plusieurs types de noeud, et donc de plusieurs problématiques conjointes d'étiquetage. Dans un premier temps nous avons proposé deux nouveaux algorithmes pour l'étiquetage dans les graphes multi-relationnels. Ces algorithmes apprennent à pondérer les différents types de relation dans le processus de propagation des étiquettes selon leur utilité pour la tâche visée. Ils permettent d'apprendre à combiner les différents types de relation de manière optimale pour la classification, tout en utilisant l'information de contenu des noeuds. Dans un second temps, nous proposons un algorithme pour l'étiquetage dans les graphes hétérogènes. Ici, une difficulté particulière demeure dans le fait que chaque type de noeud possède son propre jeu d'étiquettes: par exemple des tags visuels pour une photo et des groupes pour un utilisateur, et qu'il faut donc résoudre ces différents problèmes de classification simultanément en s'aidant de la structure du graphe. Notre algorithme est basé sur l'utilisation d'une représentation latente commune à tous les types de noeud permettant de traiter les différents types de noeud de manière uniformisée. Les résultats expérimentaux montrent que ce modèle est capable de prendre en compte les corrélations entre les étiquettes de noeuds de type différent.
Abstract FR:
The emergence of the Web 2. 0 has seen the apparition of a large quantity of data that can easily be represented as complex graphs. There is many tasks of information analysis, prediction and retrieval on these data, while the state-of-the-art models are not adapted. In this thesis, we consider the task of node classification/labeling in complex partially labeled content networks. The applications for this task are for instance video/photo annotation in the Web 2. 0 websites, web spam detection or user labeling in social networks. The originality of our work is that we focus on two types of complex networks rarely considered in existing works: \textbf{multi-relationnal graphs} composed of multiple relation types and \textbf{heterogeneous networks} composed of multiple node types then of multiple joint labeling problems. First, we proposed two new algorithms for multi-relationnal graph labeling. These algorithms learn to weight the different relation types in the label propagation process according to their usefullness for the labeling task. They learn to combine the different relation types in an optimal manner for classification, while using the node content information. Then, we proposed an algorithm for heterogeneous graph labeling. Here, a specific problem is that each type of node has it own label set: for instance visual tags for a photo and groups for an user, then we must solve these different classification problems simultaneously using the graph structure. Our algorithm is based on the usage of a latent representation common to all node types allowing to process the different node types in an uniformized manner. Our experimental results show that this model is able to take in account the correlations between labels of different node types.