Fabian Jogl presented the paper “Expectation-Complete Graph Representations with Homomorphisms” at the 40th International Conference on Machine Learning (ICML 2023) in Honolulu, Hawaii. The work introduces novel random graph embeddings that can be computed

in expected polynomial time and are able to distinguish all non-isomorphic graphs in expectation, based on Lovász’ characterisation of graph isomorphism through homomorphism counts. Empirical evaluation shows competitive results on several graph learning benchmarks.