Random Graphs in Machine Learning – GRandMa

The goal of project GrandMa is to explore the use of Random Graphs (RG) theory in modern Machine Learning (ML) methods on graphs. Large graphs indeed appear in many fields, and given their complexity, their statistical modelization is of primary importance. RG models thus have a long history in statistics and graph theory. Such modelling is however surprisingly absent from modern ML methods on graphs, such as graph kernels or the recently very popular Graph Neural Networks (GNN), and with it, classical ML tools such as generalization bounds or convergence rates of optimization methods. Such tools are nevertheless crucial to characterize the limitations of the algorithms and improve them. Project GrandMa therefore aims at advancing the fundamental understanding of ML algorithms on large graphs, in particular GNNs, understand their limitations, and leverage the theory to design efficient and powerful ML algorithms with guarantees on large random graphs.