Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entities, that the interactions between these entities are as informative as their individual properties, and that the task at hand does not depend on their ordering. While graph representations allow for effective learning, building graph neural networks that are both expressive and efficient poses important challenges. The primary focus of this dissertation is to advance the state-of-the-art in building permutation equivariant neural networks capable of handling large-scale data. To achieve this, we will first develop our understanding of permutation equivariance and its practical implications, and then propose novel algorithms that exploit the strengths of graph neural networks while circumventing challenging problems such as graph matching. In our first contribution, we propose the Structural Message-Passing (SMP) model. SMP introduces node identifiers in the form of a one-hot encoding, and processes them in a permutation equivariant way. The use of identifiers confers to the network a higher expressive power than standard Message-Passing Neural Networks, but retains its inductive bias towards learning local functions. Empirically, SMP demonstrates superior generalization capabilities compared to alternative expressive architectures that do not leverage the message-passing scheme. While architectures for learning representations of unordered data are well studied, we show in the next contributions that architectures for graph generation feature on the contrary still many open questions. We begin by examining an important component of many set and graph generation architectures, namely operators that transform vectors to sets. As permutations transform sets but not vectors, vector-to-set layers constitute a challenge for standard equivariance theory, which cannot be used when a group acts trivially on a function input. To address this challenge, we analyze the equivariance requirements in this setting and propose a novel vector to set layer called the Top-n creation layer. This layer can be plugged into several architectures as a replacement to other vector-to-set functions. We show that it improves generation quality on several set and graph generation tasks. We then show that performance can greatly be improved by building denoising diffusion models, i.e., architectures that iterative denoise a random set or graph. Specifically, we propose the DiGress model for graph generation and MiDi for jointly generating the 2D and 3D structure of molecules. These models exploit the discrete structure of graphs and are able to preserve their sparsity during diffusion. As a result, they can successfully model larger graphs than previous Gaussian diffusion models. Overall, the presented research shows that representing and generating graph data requires careful consideration. Using architectures developed for other data modalities, such as images, can lead to serious theoretical problems that are as demanding as isomorphism testing. By identifying these limitations, we are able propose novel methods that are more effective, paving the way to novel applications of graph neural networks in various scientific fields.