Robustesse des réseaux neuronaux sur graphes

Abstract

Le graphe est une structure essentielle pour représenter des systèmes complexes, des réseaux sociaux aux interactions biologiques. L’apprentissage automatique sur graphes s’impose comme un outil clé pour extraire des représentations pertinentes de ces structures irrégulières. Pour relever ce défi, les réseaux neuronaux sur graphes (GNN), notamment les réseaux à propagation de messages (MPNN), ont été développés afin d’exploiter efficacement l’information contenue dans ces graphes. Par exemple, les atomes et les liaisons d’un graphe moléculaire, représentés respectivement par des noeuds et des liens contiennent de l’information exploitable par un GNN. Les MPNN rencontrent deux principales limitations : l’over-smoothing, où les représentations des noeuds tendent à converger vers une valeur unique à mesure que la propagation est répétée, et l’over-squashing, où, à travers la propagation, une quantité croissante d’information est comprimée dans les représentations des noeuds, limitant ainsi la qualité des interactions à longue distance. Ces phénomènes affectent la capacité des modèles à conserver des informations de haute fréquence et à propager efficacement les messages, ce qui nuit directement aux performances. Nos contributions s’articulent autour de trois axes : la formalisation de ces limitations sous un cadre topologique unifié, la création d’une tâche synthétique pour les évaluer empiriquement et l’étude de leur impact sur différentes architectures et topologies. Enfin, nous explorons des pistes exploitant l’information topologique pour atténuer ces limites, soulignant que la structure du graphe à l’étude joue un rôle fondamental dans la propagation des messages et que les solutions existantes restent insuffisantes. Graphs are a fundamental data structure for representing complex systems across various domains, from social networks to biological interactions. Graph-based machine learning has emerged as a key tool for extracting meaningful representations from these irregular structures, which differ significantly from tabular data, images, or textual sequences that exhibit more regular structures. To address this challenge, Graph Neural Networks (GNNs), and in particular, Message Passing Neural Networks (MPNNs), have been developed to extract and leverage the information embedded in graphs. In molecular graphs, atoms and bonds are represented as nodes and edges, respectively, allowing GNNs to exploit their structural information. MPNNs face two major limitations : over-smoothing, where node representations tend to converge to a single value as propagation is repeated, and over-squashing, where an excessive amount of information is compressed into node embeddings, restricting long-range interactions. These issues degrade the ability of models to preserve high-frequency information and propagate messages effectively, directly impacting their performance. Our contributions are structured around three main aspects : the formalization of these limitations within a unified topological framework, the creation of a synthetic task to empirically evaluate them, and the study of their impact on various architectures and graph topologies. Finally, we explore approaches leveraging topological information to mitigate these limitations. Our findings emphasize that graph structure plays a central role in message propagation and that existing solutions do not necessarily suffice to address these challenges.