Statistics,
Computation and Learning with Graph Neural Networks

Joan Bruna Estrach, CIMS

Abstract:

Deep Learning, thanks mostly to Convolutional architectures, has recently transformed computer vision and speech recognition. Their ability to encode geometric stability priors, while offering enough expressive power, is at the core of their success. In such settings, geometric stability is expressed in terms of local deformations, and it is enforced thanks to localized convolutional operators that separate the estimation into scales.

Many problems across applied sciences, from particle physics to recommender systems, are formulated in terms of signals defined over non-Euclidean geometries, and also come with strong geometric stability priors. In this talk, I will present techniques that exploit geometric stability in general geometries with appropriate graph neural network architectures. We will show that these techniques can all be framed in terms of local graph generators such as the graph Laplacian. We will present some stability certificates, as well as applications to computer graphics, particle physics and graph estimation problems. In particular, we will describe how graph neural networks can be used to reach statistical detection thresholds in community detection, and attack hard combinatorial optimization problems, such as the Quadratic Assignment Problem.