Séminaire Image : « Hierarchical decimation for graph learning », Stevan Stanovic

Nous aurons le plaisir d’écouter Stevan Stanovic, doctorant de l’équipe Image.
Il donnera un séminaire IMAGE le jeudi 12 juin 2025 à 14h en salle de séminaire F-200.

Titre : « Hierarchical decimation for graph learning »

Résumé :
This presentation focuses on hierarchical pooling in graph neural networks (GNNs), a key operation aimed at reducing the size of graphs while preserving their relevant information. Existing methods typically rely either on selecting a subset of vertices, discarding the others, or on loosely constrained clustering, which ignores the original graph structure. These approaches suffer from several limitations : loss of information, lack of consideration for the original graph structure, and excessive densification of the reduced graphs. Moreover, deep GNNs face two major phenomena : over-smoothing, where node representations tend to converge towards a predetermined representation regardless of their initial features, and over-squashing, which refers to the difficulty in efficiently propagating information across long distances within the graph. In this manuscript, we propose several hierarchical pooling methods based on maximal independent sets, which preserve the graph structure while maintaining vertex attributes. Additionally, we provide a theoretical and empirical study of these approaches, highlighting their positive impact on over-smoothing and over-squashing. Our experimental results not only confirm the value of using maximal independent sets for defining pooling operations but also demonstrate their crucial role in mitigating over-smoothing and over-squashing.

Keywords: Graph neural networks, Graph Pooling, Graph decimation, Maximal Independent Set, Over-smoothing, Over-squashing.