# Structural Node Embeddings with Homomorphism Counts

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 51 references that are in the map.
- First posted on arXiv 29 Aug 2023.

## Builds on (most cited first, 30 of 31)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning](https://mlsanity.com/paper/2308.02565/) (2023)
- [Robust Optimization as Data Augmentation for Large-scale Graphs](https://mlsanity.com/paper/2010.09891/) (2020)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Graph Neural Networks with Local Graph Parameters](https://mlsanity.com/paper/2106.06707/) (2021)
- [Graph Kernels: A Survey](https://mlsanity.com/paper/1904.12218/) (2019)
- [word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data](https://mlsanity.com/paper/2003.12590/) (2020)
- [Lov'asz Meets Weisfeiler and Leman](https://mlsanity.com/paper/1802.08876/) (2018)
- [Graph Homomorphism Convolution](https://mlsanity.com/paper/2005.01214/) (2020)
- [Optimization of Graph Neural Networks with Natural Gradient Descent](https://mlsanity.com/paper/2008.09624/) (2020)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [Network Representation Learning: From Preprocessing, Feature Extraction to Node Embedding](https://mlsanity.com/paper/2110.07582/) (2021)
- [Homomorphisms Are a Good Basis for Counting Small Subgraphs](https://mlsanity.com/paper/1705.01595/) (2017)
- [Expectation-Complete Graph Representations with Homomorphisms](https://mlsanity.com/paper/2306.05838/) (2023)
- [Lov'asz-Type Theorems and Game Comonads](https://mlsanity.com/paper/2105.03274/) (2021)
- [Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability](https://mlsanity.com/paper/2302.10538/) (2023)

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

- [Homomorphism Counts for Graph Neural Networks: All About That Basis](https://mlsanity.com/paper/2402.08595/) (2024)
- [Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs](https://mlsanity.com/paper/2511.03068/) (2025)
- [Expressive Power of Deep Homomorphism Networks over Relational Databases](https://mlsanity.com/paper/2605.22852/) (2026)
- [Omega-N: Interpretable Structural Node Descriptors and Their Applicability Domain](https://mlsanity.com/paper/2609.01633/) (2026)

## Abstract (arXiv)

Graph homomorphism counts, first explored by Lov'asz in 1967, have recently garnered interest as a powerful tool in graph-based machine learning. Grohe (PODS 2020) proposed the theoretical foundations for using homomorphism counts in machine learning on graph level as well as node level tasks. By their very nature, these capture local structural information, which enables the creation of robust structural embeddings. While a first approach for graph level tasks has been made by Nguyen and Maehara (ICML 2020), we experimentally show the effectiveness of homomorphism count based node embeddings. Enriched with node labels, node weights, and edge weights, these offer an interpretable representation of graph data, allowing for enhanced explainability of machine learning models. We propose a theoretical framework for isomorphism-invariant homomorphism count based embeddings which lend themselves to a wide variety of downstream tasks. Our approach capitalises on the efficient computability of graph homomorphism counts for bounded treewidth graph classes, rendering it a practical solution for real-world applications. We demonstrate their expressivity through experiments on benchmark datasets. Although our results do not match the accuracy of state-of-the-art neural architectures, they are comparable to other advanced graph learning models. Remarkably, our approach demarcates itself by ensuring explainability for each individual feature. By integrating interpretable machine learning algorithms like SVMs or Random Forests, we establish a seamless, end-to-end explainable pipeline. Our study contributes to the advancement of graph-based techniques that offer both performance and interpretability.