  We investigate novel random graph embeddings that can be computed in expected
polynomial time and that are able to distinguish all non-isomorphic graphs in
expectation. Previous graph embeddings have limited expressiveness and either
cannot distinguish all graphs or cannot be computed efficiently for every
graph. To be able to approximate arbitrary functions on graphs, we are
interested in efficient alternatives that become arbitrarily expressive with
increasing resources. Our approach is based on Lov\'asz' characterisation of
graph isomorphism through an infinite dimensional vector of homomorphism
counts. Our empirical evaluation shows competitive results on several benchmark
graph learning tasks.
