Skip to Main content Skip to Navigation

Etude de Dégénérescence de Graph appliqué à l'Apprentissage Automatique Avancé et Résultats Théoriques relatifs

Abstract : 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.
Complete list of metadata
Contributor : ABES STAR :  Contact
Submitted on : Tuesday, December 8, 2020 - 3:45:08 PM
Last modification on : Wednesday, December 9, 2020 - 3:39:27 AM
Long-term archiving on: : Tuesday, March 9, 2021 - 7:42:54 PM


Version validated by the jury (STAR)


  • HAL Id : tel-03046826, version 1



Stratis Limnios. Etude de Dégénérescence de Graph appliqué à l'Apprentissage Automatique Avancé et Résultats Théoriques relatifs. Artificial Intelligence [cs.AI]. Institut Polytechnique de Paris, 2020. English. ⟨NNT : 2020IPPAX038⟩. ⟨tel-03046826⟩



Record views


Files downloads