GRandMa: Random Graphs in Machine learning

(In construction)

Graphs have become popular objects to represent many kinds of structured and relational data. As a consequence, the field of *Graph Machine Learning* (ML) has grown exponentially in the last few decades, with popular tools such as graph kernels, graph signal processing, and Graph Neural Networks (GNN). Despite this, classical ML analyses such as generalization or optimization guarantees, and the associated sample complexities and rates, remain relatively limited for graph data. We argue that this is due to a lack of *statistical modelling*, in particular of large graphs, without which notions like generalization are ill-defined. On the other hand, *Random Graphs* (RG) represent a vast field in Statistics and Graph Theory, with a long history, but have been quite overlooked in modern Graph ML.

GRandMa (2022 - 2026) aims to fill this gap, by incorporating the use of Random Graphs in modern Graph ML algorithms. By improving our theoretical understanding of these algorithms and their limitations on large graphs, we hope to develop new, efficient graph ML algorithms.


Associated papers

  • N. Keriven, A. Bietti, S. Vaiter. On the Universality of Graph Neural Networks on Large Random Graphs NeurIPS 2021. Pdf

drawing drawing

  • N. Keriven, A. Bietti, S. Vaiter. Convergence and Stability of Graph Convolutional Network Networks on Large Random Graphs NeurIPS (Spotlight) 2020. Pdf

drawing drawing drawing