Graphs are ubiquitous. They represent data in many domains and applications such as, social networks, chemistry, biology, recommendation systems, etc.

With the tremendous success that deep learning achieved for all kinds of regular data structures (images, video scenes, audio, …),  extending machine learning algorithms to deal with such a largely used data representation aroused a lot of interest. This gave rise to a new class of deep neural networks, namely GNNs, which stands for graph neural networks. These neural networks are a generalization of deep neural networks to graph structured data, and they have shown to be extremely effective for tasks such as graph classification, node classification, and link prediction. Yet they have some limitations, especially about scalability problems. In fact, GNNs suffer from extensive memory consumption that goes with the depth of the model, along with the oversmoothing problem which consists of the nodes representations to collapse to a single point that makes it very hard to get accurate results from the model. 

In this thesis, we raise some fundamental questions about GNNs, explore new approaches to improve them, and finally, study some use cases of GNNs.