A Proof of Theorem 1 Let f be a layer of SMP: f(U, Y, A)[i,:,: ] = u(U, U j, y

We first present the formal version of the theorem: Theorem 3 (Representation power - formal). The fact that embeddings produced by isomorphic graphs are permutations one of another is a consequence of equivariance, so we are left to prove the first point. To do so, we will first ignore the features and prove that there is an SMP that maps the initial one-hot encoding of each node to an embedding that allows to reconstruct the adjacency matrix. The case of attributed graphs and the statement of the theorem will then follow easily. Consider a simple connected graph G = (V, E).