Compréhension de la sur-squeezing et des goulets d'étranglement sur les graphes via la courbure

La plupart des réseaux de neurones sur graphes (GNNs) reposent sur le paradigme d’échange de messages, dans lequel les caractéristiques des nœuds sont propagées sur le graphe d’entrée. Des travaux récents ont identifié la distorsion de l’information provenant de nœuds éloignés comme un facteur limitant l’efficacité de l’échange de messages pour les tâches reposant sur des interactions à longue portée. Ce phénomène, désigné sous le terme de « sur-écrasement » (over-squashing), a été heuristiquement attribué à des goulets d’étranglement dans le graphe, où le nombre de voisins à k-étapes croît rapidement avec k. Nous fournissons une description précise du phénomène de sur-écrasement dans les GNNs et analysons comment il émerge à partir des goulets d’étranglement présents dans le graphe. À cet effet, nous introduisons une nouvelle courbure combinatoire basée sur les arêtes et démontrons que les arêtes à courbure négative sont responsables du problème de sur-écrasement. Nous proposons également une méthode de réarraisonnement de graphe fondée sur la courbure, que nous expérimentons et validons empiriquement afin de atténuer le sur-écrasement.