Les progrès technologiques nous permettent aujourd’hui de recueillir des données de différentes modalités, telles que le texte, l'audio, l'image ou la vidéo, à une échelle sans précédent. L'apprentissage profond est l'outil principal qui permet de comprendre et d'exploiter ces collections de données massives. Les capacités actuelles incluant des tâches prédictives telles que l'analyse des sentiments dans les textes, la classification de la musique et des images, la segmentation des images ou la reconnaissance des actions dans les vidéos, ainsi que des tâches génératives telles que la génération de textes, d'images, de musique et même de vidéos. Le succès de l'apprentissage profond dans de nombreuses applications est largement attribué à la capacité des méthodes à exploiter la structure intrinsèque des données. Les tâches de traitement d'images, par exemple, ont donné naissance aux réseaux neuronaux convolutifs qui utilisent l'organisation spatiale des pixels. Cependant, l'analyse des séries temporelles a donné naissance aux réseaux neuronaux récurrents qui utilisent l'organisation temporelle dans leur traitement de l'information en utilisant, par exemple, des mécanismes de mémoire. Alors que ces modalités peuvent être représentées dans des domaines Euclidiens qui possèdent des propriétés théoriques relativement agréables, d'autres modalités toutes aussi intéressantes possédant une structure plus abstraite. Les données des réseaux sociaux, des moteurs de recherche, des petites molécules ou des protéines sont naturellement représentées par des graphes. L'apprentissage profond géométrique est dirigé vers la généralisation de réseaux neuronaux qui peuvent utiliser la structure à de tels domaines non-Euclidiens. Les principaux outils sont les réseaux neuronaux de graphes qui généralisent les principes des réseaux neuronaux convolutionnels dans le domaine de la vision au domaine des graphes. Cela a permis de développer des méthodes puissantes pour de diverses applications, telles que l'analyse des réseaux sociaux et l’analyse ou la génération de molécules. Toutefois, ces méthodes sont limitées par plusieurs défis fondamentaux liés au paradigme central de passage de messages, c'est-à-dire le calcul répété de moyennes d’information au niveau des sommets par rapport au voisinage de chaque sommet. En conséquence, les représentations locales au niveau des sommets deviennent soit trop similaires en raison des calculs de moyenne répétés, soit les champs récepteurs des modèles sont trop petits pour que les informations ne puissent pas être partagées entre les sommets distants. Cette thèse présentera des approches pour relever ces défis en commençant par analyser et comprendre des données pertinentes et en identifiant les propriétés structurelles qui permettent un apprentissage efficace des représentations des graphes. Nous formulons ensuite un cadre théorique basé sur la théorie du traitement des signaux de graphes qui nous permet de développer de nouvelles architectures GNN puissantes qui exploitent ces propriétés, tout en atténuant les défis courants. Nous constatons que les modèles hybrides qui combinent les méthodes existantes et les nouveaux principes présentés dans cette thèse sont particulièrement puissants. Nous fournissons des garanties théoriques qui établissent les capacités théoriques des architectures proposées et présentons une analyse empirique qui démontre l'efficacité de ces nouvelles architectures dans une variété d’applications telles que les réseaux sociaux, la biochimie et l'optimisation combinatoire. / Technological advances have enabled us to gather and store data from various modalities such as text, audio, image or video at unprecedented scale. Deep learning is the signature tool that allows to understand and leverage such massive data collections, enabling us to engage in challenging new endeavors. The capabilities range from predictive tasks such as sentiment analysis in text, music and image classification, image segmentation or action recognition in video to generative tasks like generation of text, images, music and even entire videos. The success of deep learning in many applications is largely attributed to the ability of commonly used neural network architectures to leverage the intrinsic structure of the data. Image processing tasks, for example, gave rise to convolutional neural networks that rely on spatial organization of pixels, while time series analysis gave rise to recurrent neural networks that leverage temporal organization in their information processing via feedback loops and memory mechanisms. While these modalities largely reside in relatively well behaved and often highly regular domains like Euclidean spaces, further modalities that possess more abstract structure have recently attracted much attention. Data from social networks, search engines, small molecules or proteins is naturally represented by graphs and so-called geometric deep learning (GDL) has made great strides towards generalizing the design of structure-aware neural networks to such non-Euclidean domains. Among the most promising methods are graph neural networks (GNNs) that generalize the design of convolutional neural networks in vision to the graph domain. Recent advances in GNN design have introduced increasingly powerful methods for various applications, such as social network analysis, molecular predictive modeling or molecule generation. However, graph representation learning is limited by several fundamental challenges that originate from the central GNN paradigm of message passing, that is repeated averaging of node-level information across node neighborhoods. As a result, local node-level representations become either too similar from excessive averaging, or otherwise, the receptive fields of the models are too small such that information cannot be shared between distant nodes, creating a complex trade-off between so-called oversmoothing and underreaching. This dissertation presents a principled way of tackling these challenges by first deepening our understanding of the relevant data and identifying the structural properties that allow for effective graph representation learning. We consequently develop a theoretical framework rooted in graph signal processing that allows us to design powerful novel GNN architectures that provably leverage those properties, while alleviating common challenges. We find that hybrid models that combine existing methods together with novel GNN principles are particularly powerful. We provide theoretical guarantees that establish the expressive power of the proposed architectures and present exhaustive empirical analysis that demonstrates the efficacy of these novel architectures in various applications such as social networks, bio-chemistry and combinatorial optimization.