mlsanityData to 14 Oct 2026

Expectation-Complete Graph Representations with Homomorphisms

arXiv 2306.05838 ↗First posted 9 Jun 2023cs.LG cs.DScited by 10

Not on the map. Why?

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.

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

22 of 52 references.

References · 22

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  4. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  5. 2016Automatic chemical design using a data-driven continuous representation of moleculescited by 765
  6. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  7. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  8. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  9. 2020Random Features Strengthen Graph Neural Networkscited by 186
  10. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 161
  11. 2019Relational Pooling for Graph Representationscited by 150
  12. 2019A Survey on Graph Kernelscited by 148
10 more
  1. 2021Graph Neural Networks with Local Graph Parameterscited by 52
  2. 2020word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Datacited by 38
  3. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  4. 2018Lov'asz Meets Weisfeiler and Lemancited by 27
  5. 2020Graph Homomorphism Convolutioncited by 27
  6. 2023Taming graph kernels with random featurescited by 17
  7. 2017Homomorphisms Are a Good Basis for Counting Small Subgraphscited by 14
  8. 2019Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embeddingcited by 8
  9. 2013Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)cited by 1
  10. 2020Fast Graph Kernel with Optical Random Featurescited by 1

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 4; 2025: 5.

10 papers.

  1. 2025Beyond Message Passing: Neural Graph Pattern Machinecited by 17
  2. 2024Homomorphism Counts for Graph Neural Networks: All About That Basiscited by 16
  3. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  4. 2025Generative Graph Pattern Machinecited by 11
  5. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 5
  6. 2023Structural Node Embeddings with Homomorphism Countscited by 4
  7. 2024Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learningcited by 2
  8. 2024Generalization of Graph Neural Networks through the Lens of Homomorphismcited by 1
  9. 2025Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphscited by 1
  10. 2025Message Passing on the Edge: Towards Scalable and Expressive GNNscited by 0