# Expectation-Complete Graph Representations with Homomorphisms

arXiv: https://arxiv.org/abs/2306.05838 · HTML: https://mlsanity.com/paper/2306.05838/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 52 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 22 of 22)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [Relational Pooling for Graph Representations](https://mlsanity.com/paper/1903.02541/) (2019)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Graph Neural Networks with Local Graph Parameters](https://mlsanity.com/paper/2106.06707/) (2021)
- [word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data](https://mlsanity.com/paper/2003.12590/) (2020)
- [Equivariant Polynomials for Graph Neural Networks](https://mlsanity.com/paper/2302.11556/) (2023)
- [Lov'asz Meets Weisfeiler and Leman](https://mlsanity.com/paper/1802.08876/) (2018)
- [Graph Homomorphism Convolution](https://mlsanity.com/paper/2005.01214/) (2020)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [Homomorphisms Are a Good Basis for Counting Small Subgraphs](https://mlsanity.com/paper/1705.01595/) (2017)
- [Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding](https://mlsanity.com/paper/1911.11119/) (2019)
- [Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)](https://mlsanity.com/paper/1307.2187/) (2013)
- [Fast Graph Kernel with Optical Random Features](https://mlsanity.com/paper/2010.08270/) (2020)

## Built on by (most cited first, 10 of 10)

- [Beyond Message Passing: Neural Graph Pattern Machine](https://mlsanity.com/paper/2501.18739/) (2025)
- [Homomorphism Counts for Graph Neural Networks: All About That Basis](https://mlsanity.com/paper/2402.08595/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [Generative Graph Pattern Machine](https://mlsanity.com/paper/2505.16130/) (2025)
- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [Structural Node Embeddings with Homomorphism Counts](https://mlsanity.com/paper/2308.15283/) (2023)
- [Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning](https://mlsanity.com/paper/2403.13749/) (2024)
- [Generalization of Graph Neural Networks through the Lens of Homomorphism](https://mlsanity.com/paper/2403.06079/) (2024)
- [Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs](https://mlsanity.com/paper/2511.03068/) (2025)
- [Message Passing on the Edge: Towards Scalable and Expressive GNNs](https://mlsanity.com/paper/2510.13615/) (2025)

## Abstract (arXiv)

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.