Thesis of Thomas Ricatte

Hypernode Graphs For Learning From Binary Relations Between Sets of Objects

Graphs are commonly used as a powerful abstract model to represent complex relationships between individuals. For (classical) graphs, pairwise relations are modeled by edges between vertices. This is for instance the case for social networks with the friendship relation, or for computer networks with the connection relation. The hypergraph formalism has been introduced in the 1970s for modeling complex problems where relationships are no longer binary, which is when they involve more than two individuals. Hypergraphs have been used for instance in bioinformatics, computer vision or natural language processing. But, graphs and hypergraphs are limited when it comes to consider relationships between sets of individual objects. A typical example is the case of multiplayer games where a game can be viewed as an established relationship between two (or more) teams of multiple players. Other examples include relationships between groups in social networks or between clusters in computer networks. For these problems, considering both the group level and the individual level is a requisite. We introduce and study a new data structure called hypernode graph specically designed to handle this type of higher-order relations. We show that we can extend the notion of graph Laplacian and graph Kernel to this new class of objects. This extension of the spectral learning framework is fully consistent with the graph case and allows us to design ecient learning algorithms on top of our new data structure. We also show that our newly dened Laplacians are strictly more expressive than graph Laplacians. Note that this property does not hold for instance in the case of hypergraphs. We use our new formalism in order to design a new skill rating algorithm for multiple players games. We estimate the relevance of the results using a predictive scheme (we predict new games using the skills estimated in the past). Experimental results have shown that we obtain very competitive results compared to specialized algorithms. We also study in detail some important properties of the undirected hypergraphs and bring into focus some fundamental links with the theory of signed graphs.

Jury

- Directeur : Rémi Gilleron (Professeur à l'Université de Lille) - Rapporteurs : Mark Herbster (Lecturer at University College London), Francois Denis (Professeur à l'Université d'Aix-Marseille) - Examinateurs : Sophie Tison (Professeur à l'Université de Lille), Marc Tommasi (Professeur à l'Université de Lille), Yannick Cras (Chief Development at SAP SE), Gemma Garriga (Data Scientist at Allianz SE)

Thesis of the team MAGNET defended on 23/01/2015