Résumé

Nous considérons le problème de l’étiquetage de noeuds dans un multi-graphe- ou graphe multi-relationnel- dans lequel les noeuds peuvent être connectés simultanément par dif- férents types de relations. De nombreux problèmes se modélisent ainsi, comme par exemple les réseaux sociaux ou bien les bases de données bibliographiques. Les relations peuvent être expli- cites (par exemple amitié dans un réseau social) ou bien implicite (par exemple des similarités de contenu calculées sur les données). Nous proposons ici un algorithme d’apprentissage per- mettant d’exploiter l’information multi-relationnelle pour la tâche d’étiquetage automatique. Cette méthode est capable d’apprendre à combiner de manière optimale l’influence des dif- férents types de relations sur la propagation des étiquettes entre les noeuds du graphe. Nous décrivons des expériences sur quatre corpus qui montrent la capacité du modèle à tirer parti de l’information multi-relationnelle pour des tâches d’étiquetage complexes.

Abstract

We consider the problem of labeling nodes in a multi-graph where the nodes may be connected with different types of relations. This type of problem occurs in many situations like for example the analysis of social networks or bibliographic data. Relations may be provided (e.g. friends) or computed (e.g. similarity). We propose a new learning algorithm for exploiting the rich multi-relational information in the labeling task. This method is able to optimally learn combining the influence of different relation types. It is one of the very first algorithms able to handle multi-graph information for this classification task. We describe experiments on four datasets which show the model ability to deal with complex relationships and to take benefit of multi-relational information for complex labeling problems.