Graph Degeneracy Studies for Advanced Learning Methods on Graphs and Theoretical Results

Autor: Limnios, Stratis
Přispěvatelé: Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Institut Polytechnique de Paris, Michalis Vazirgiannis, Dimitrios M. Thilikos
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Zdroj: Artificial Intelligence [cs.AI]. Institut Polytechnique de Paris, 2020. English. ⟨NNT : 2020IPPAX038⟩
Popis: Extracting Meaningful substructures from graphs has always been a key part in graph studies. In machine learning frameworks, supervised or unsupervised, as well as in theoretical graph analysis, finding dense subgraphs and specific decompositions is primordial in many social and biological applications among many others.In this thesis we aim at studying graph degeneracy, starting from a theoretical point of view, and building upon our results to find the most suited decompositions for the tasks at hand.Hence the first part of the thesis we work on structural results in graphs with bounded edge admissibility, proving that such graphs can be reconstructed by aggregating graphs with almost-bounded-edge-degree. We also provide computational complexity guarantees for the different degeneracy decompositions, i.e. if they are NP-complete or polynomial, depending on the length of the paths on which the given degeneracy is defined.In the second part we unify the degeneracy and admissibility frameworks based on degree and connectivity. Within those frameworks we pick the most expressive, on the one hand, and computationally efficient on the other hand, namely the 1-edge-connectivity degeneracy, to experiment on standard degeneracy tasks, such as finding influential spreaders.Following the previous results that proved to perform poorly we go back to using the k-core but plugging it in a supervised framework, i.e. graph kernels. Thus providing a general framework named core-kernel, we use the k-core decomposition as a preprocessing step for the kernel and apply the latter on every subgraph obtained by the decomposition for comparison. We are able to achieve state-of-the-art performance on graph classification for a small computational cost trade-off.Finally we design a novel degree degeneracy framework for hypergraphs and simultaneously on bipartite graphs as they are hypergraphs incidence graph. This decomposition is then applied directly to pretrained neural network architectures as they induce bipartite graphs and use the coreness of the neurons to re-initialize the neural network weights. This framework not only outperforms state-of-the-art initialization techniques but is also applicable to any pair of layers convolutional and linear thus being applicable however needed to any type of architecture.; L'extraction de sous-structures significatives a toujours été un élément clé de l’étude des graphes. Dans le cadre de l'apprentissage automatique, supervisé ou non, ainsi que dans l'analyse théorique des graphes, trouver des décompositions spécifiques et des sous-graphes denses est primordial dans de nombreuses applications comme entre autres la biologie ou les réseaux sociaux.Dans cette thèse, nous cherchons à étudier la dégénérescence de graphe, en partant d'un point de vue théorique, et en nous appuyant sur nos résultats pour trouver les décompositions les plus adaptées aux tâches à accomplir. C'est pourquoi, dans la première partie de la thèse, nous travaillons sur des résultats structurels des graphes à arête-admissibilité bornée, prouvant que de tels graphes peuvent être reconstruits en agrégeant des graphes à degré d’arête quasi-borné. Nous fournissons également des garanties de complexité de calcul pour les différentes décompositions de la dégénérescence, c'est-à-dire si elles sont NP-complètes ou polynomiales, selon la longueur des chemins sur lesquels la dégénérescence donnée est définie.Dans la deuxième partie, nous unifions les cadres de dégénérescence et d'admissibilité en fonction du degré et de la connectivité. Dans ces cadres, nous choisissons les plus expressifs, d'une part, et les plus efficaces en termes de calcul d'autre part, à savoir la dégénérescence 1-arête-connectivité pour expérimenter des tâches de dégénérescence standard, telle que la recherche d’influenceurs.Suite aux résultats précédents qui se sont avérés peu performants, nous revenons à l'utilisation du k-core mais en l’intégrant dans un cadre supervisé, i.e. les noyaux de graphes. Ainsi, en fournissant un cadre général appelé core-kernel, nous utilisons la décomposition k-core comme étape de prétraitement pour le noyau et appliquons ce dernier sur chaque sous-graphe obtenu par la décomposition pour comparaison. Nous sommes en mesure d'obtenir des performances à l’état de l’art sur la classification des graphes au prix d’une légère augmentation du coût de calcul.Enfin, nous concevons un nouveau cadre de dégénérescence de degré s’appliquant simultanément pour les hypergraphes et les graphes biparties, dans la mesure où ces derniers sont les graphes d’incidence des hypergraphes. Cette décomposition est ensuite appliquée directement à des architectures de réseaux de neurones pré-entrainés étant donné qu'elles induisent des graphes biparties et utilisent le core d'appartenance des neurones pour réinitialiser les poids du réseaux. Cette méthode est non seulement plus performant que les techniques d'initialisation de l’état de l’art, mais il est également applicable à toute paire de couches de convolution et linéaires, et donc adaptable à tout type d'architecture.
Databáze: OpenAIRE
Externí odkaz: