| Titre : |
Towards expressive graph neural networks : Theory, algorithms, and applications |
| Type de document : |
Thèse/HDR |
| Auteurs : |
Georgios Dasoulas, Auteur ; Michalis Vazirgiannis, Directeur de thèse ; Aladin Virmaux, Directeur de thèse |
| Editeur : |
Paris : Institut Polytechnique de Paris |
| Année de publication : |
2022 |
| Note générale : |
bibliographie
These de doctorat de l’Institut Polytechnique de Paris préparée à l’Ecole Polytechnique, spécialité Informatique |
| Langues : |
Anglais (eng) |
| Descripteur : |
[Vedettes matières IGN] Intelligence artificielle
[Termes IGN] apprentissage automatique
[Termes IGN] attention (apprentissage automatique)
[Termes IGN] entropie
[Termes IGN] graphe
[Termes IGN] isomorphisme
[Termes IGN] noeud
[Termes IGN] réseau neuronal de graphes
[Termes IGN] théorie des graphes
|
| Index. décimale : |
THESE Thèses et HDR |
| Résumé : |
(auteur) As the technological evolution of machine learning is accelerating nowadays, data plays a vital role in building intelligent models, being able to simulate phenomena, predict values and make decisions. In an increasing number of applications, data take the form of networks. The inherent graph structure of network data motivated the evolution of the graph representation learning field. Its scope includes generating meaningful representations for graphs and their components, i.e., the nodes and the edges. The research on graph representation learning was accelerated with the success of message passing frameworks applied on graphs, namely the Graph Neural Networks. Learning informative and expressive representations on graphs plays a critical role in a wide range of real-world applications, from telecommunication and social networks, urban design, chemistry, and biology. In this thesis, we study various aspects from which Graph Neural Networks can be more expressive, and we propose novel approaches to improve their performance in standard graph learning tasks. The main branches of the present thesis include: the universality of graph representations, the increase of the receptive field of graph neural networks, the design of stable deeper graph learning models, and alternatives to the standard message-passing framework. Performing both theoretical and experimental studies, we show how the proposed approaches can become valuable and efficient tools for designing more powerful graph learning models.In the first part of the thesis, we study the quality of graph representations as a function of their discrimination power, i.e., how easily we can differentiate graphs that are not isomorphic. Firstly, we show that standard message-passing schemes are not universal due to the inability of simple aggregators to separate nodes with ambiguities (similar attribute vectors and neighborhood structures). Based on the found limitations, we propose a simple coloring scheme that can provide universal representations with theoretical guarantees and experimental validations of the performance superiority. Secondly, moving beyond the standard message-passing paradigm, we propose an approach for treating a corpus of graphs as a whole instead of examining graph pairs. To do so, we learn a soft permutation matrix for each graph, and we project all graphs in a common vector space, achieving a solid performance on graph classification tasks.In the second part of the thesis, our primary focus is concentrated around the receptive field of the graph neural networks, i.e., how much information a node has in order to update its representation. To begin with, we study the spectral properties of operators that encode adjacency information. We propose a novel parametric family of operators that can adapt throughout training and provide a flexible framework for data-dependent neighborhood representations. We show that the incorporation of this approach has a substantial impact on both node classification and graph classification tasks. Next, we study how considering the k-hop neighborhood information for a node representation can output more powerful graph neural network models. The resulted models are proven capable of identifying structural properties, such as connectivity and triangle-freeness.In the third part of the thesis, we address the problem of long-range interactions, where nodes that lie in distant parts of the graph can affect each other. In this problem, we either need the design of deeper models or the reformulation of how proximity is defined in the graph. Firstly, we study the design of deeper attention models, focusing on graph attention. We calibrate the gradient flow of the model by introducing a novel normalization that enforces Lipschitz continuity. Next, we propose a data augmentation method for enriching the node attributes with information that encloses structural information based on local entropy measures. |
| Note de contenu : |
1. Introduction
2. Preliminaries
I- Discrimination power
3. Universal approximation on graphs
4. Learning soft permutations for graph representations
II- Receptive field
5. Learning graph shift operators
6. Increasing the receptive field with multiple hops
III- Beyond local interactions
7. Lipschitz continuity of graph attention
8. Structural symmetries in graphs
9. Conclusions and outlook |
| Numéro de notice : |
24076 |
| Affiliation des auteurs : |
non IGN |
| Thématique : |
INFORMATIQUE/MATHEMATIQUE |
| Nature : |
Thèse française |
| Note de thèse : |
Thèse de doctorat : Informatique : Palaiseau : 2022 |
| DOI : |
sans |
| En ligne : |
https://theses.hal.science/tel-03666690 |
| Format de la ressource électronique : |
URL |
| Permalink : |
https://documentation.ensg.eu/index.php?lvl=notice_display&id=102200 |
|  |
Towards expressive graph neural networks : Theory, algorithms, and applications (2022)
