An emerging tension between expressive power, computational complexity and the retention of fundamental inductive biases characterises the design of Neural Networks for graph-structured data. In this thesis we introduce principled approaches that can strike an effective balance between the aforementioned set of desiderata. We propose and analyse methods of provable expressiveness which respect the symmetries of the objects they process, whilst featuring a computational complexity which reflects their inherent sparsity.

First, we design principled neural architectures on simplicial complexes, generalisation of graphs which account for group-wise interactions. We propose to ``lift'' graphs to simplicial complexes by considering complete subgraphs, and to process them with our proposed architecture. This approach results in a local, hierarchical message-passing procedure beyond the capabilities of the node-centric paradigm of Message Passing Neural Networks on graphs (MPNNs).

We broaden the application of this paradigm by considering regular cell complexes. We propose lifting graphs to these more general spaces via transformations that additionally consider structures such as simple and induced cycles. Our approach exhibits strong discriminative power and finds tractable and particularly effective application in molecular modelling tasks.

Then, we propose an alternative approach which prescribes modelling graphs as bags of subgraphs from predefined selection policies. We design an architecture to process these objects in a way to respect their inherent symmetries. We show it obtains provable expressiveness even when subgraphs are selected by domain-agnostic, contained policies and are processed with ``weak'', efficient message-passing-based encoders.

Last, we provide a deeper theoretical characterisation of the aforementioned paradigm, reconciling a series of contemporary works implicitly sharing this underlying `bags-of-subgraphs' approach. We perform a novel symmetry analysis which allows to derive an upper-bound on the expressive power of noteworthy subgraph methods, and to conceive a design space to guide the development of novel architectures in this overall family.