Assume also that a collection of graphs with corresponding labels {(G i , y i )} n i=1 has been sampled independently from a target probability measure defined over G × Y, where G is the space of graphs and Y ⊂ R is the set of labels. From now on, we consider that a graph G is represented by a tuple (X G , A G ), with X G denoting the matrix with node features as rows and A G the adjacency matrix. The inputs of graph neural networks consist of such tuples, outputting predictions over the label space. In general, GNNs learn permutation invariant hypotheses that have consistent predictions for the same graph when presented with permuted nodes. This property is achieved through neighbourhood aggregation schemes and readouts that give rise to permutation invariant hypotheses. Formally, a function f defined over a graph G is called permutation invariant if there exists a permutation matrix P such that f (PX G , PA G P ⊤ ) = f (X G , A G ). The node features X G and the graph structure (adjacency matrix) A G are used to first learn representations of nodes h v , for all v ∈ V. Permutation invariance in the neighbourhood aggregation schemes is enforced by employing standard pooling functions -sum, mean, or maximum. As succinctly described in , typical neighbourhood aggregation schemes characteristic of GNNs can be described by two steps: