Measures on graphs : from similarity to density

In this thesis, we mainly consider two closely related classical and general problems in data mining and machine learning: (1) developing new similarity measures between graphs and between nodes of a graph, and (2) developing new density measures on nodes of a graph. In the first part of this thesis, we introduce three new graph kernels (which can be seen as similarity measures between graphs) and assess them on a graph classification task: using molecules from various origins as graphs, we try to classify them according to one of their property (mutagenicity,...). We then study the problem of quantifying the similarity between nodes of graphs. We define three new measures by assigning the forests present in the graph a probability of being sampled at random, favoring small (low-cost) forests against bigger ones. These measures are then assessed on a semi-supervised classification task, trying to infer missing node labels from the ones already present in the test datasets. From these similarity measures, we developed the Sum-over-Forests (SoF) density index presuming that, when picking forests (which are assigned a probability of sampling), if a node is present in many (preferably short) forests, it should lie in a dense region of the graph. This density index is then assessed in various ways, assessing its quality as a density estimator on graphs. At last, we developed two clustering algorithms based on the SoF density index, which are able to work directly on graphs without necessarily requiring a priori the number of clusters.Notre recherche doctorale s’intéresse principalement à deux problèmes étroitement liés, dans les domaines de l’analyse de données et de l’apprentissage automatique: (1) le développement de nouvelles mesures de similarité entre graphes et entre nœuds d’un graphe, et (2) le développement de nouvelles mesures de densité sur les nœuds d’un graphe. Dans la première partie de ce document, trois nouveaux noyaux sur graphes, pouvant être considérés comme des mesures de similarité entre graphes, sont introduits. Ces noyaux sont évalués sur une tâche de classification dont l’objectif est de classer des molécules d’origines diverses, modélisées sous forme de graphes, suivant une de leurs propriétés (mutagénicité,…). Dans notre recherche sur la quantification de la similarité entre nœuds d’un graphe, trois nouvelles mesures ont été définies en assignant aux forêts présentes dans le graphe une probabilité d’être choisies au hasard, favorisant les petites forêts (ayant un coût faible) au détriment des plus étendues. Ces mesures sont ensuite évaluées sur une tâche de classification semi-supervisée dont l’objectif est de prédire les étiquettes manquant sur certains nœuds à partir de celles attachées aux autres nœuds. De ces mesures de similarité, un indice de densité d’un nœud d’un graphe, appelé « Sum-over-Forests » (SoF), a été développé en supposant qu’un nœud présent sur beaucoup de forêts (de préférence petites – et donc avec une plus forte probabilité d’être choisies au hasard) devrait être situé dans une région dense du graphe. Cet indice de densité est ensuite testé de différentes manières, évaluant sa qualité en tant qu’estimateur de densité sur graphes. Enfin, deux méthodes de clustering de nœuds, basées sur l’indice de densité SoF, pouvant être appliquées directement sur des graphes et ne nécessitant pas a priori le nombre de clusters à obtenir, ont été mises au point.(ECGE - Sciences économiques et de gestion) -- UCL, 201