Convergence of Graph Neural Networks with generic aggregation functions on random graphs

Description

We study the limit behavior of GNNs on large random graphs. We consider GNNs with a generic aggregation function and show that under mild regularity conditions, they converge to a "continuous" counterpart. We provide some non asymptotic bounds with high probability for this convergence which encompass several cases of aggregation such as, the mean, or the maximum

Abstract (French)

On s'intéresse au comportement limite des Réseaux de Neurones sur Graphes appliqués aux grands graphes aléatoires. On démontre que sous certaines hypothèses de régularité, un GNN converge vers un homologue «continu». L'originalité de ce travail est de considérer des fonctions d'agrégation abstraites et générales tandis que les études antérieures traitent de cas particuliers. On quantifie les convergences à l'aide de bornes non asymptotiques en probabilité basées sur l'inégalité de McDiarmid pour des agrégations ayant une régularité de type lipschitzienne. Le cas du maximum, non inclus dans cette catégorie, est traité à part.

Abstract

National audience

Additional details