# Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural Networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 69 references that are in the map.
- First posted on arXiv 2 Mar 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation](https://mlsanity.com/paper/2106.04399/) (2021)
- [KEPLER: A Unified Model for Knowledge Embedding and Pre-trained Language Representation](https://mlsanity.com/paper/1911.06136/) (2019)
- [Knowledge Graph Embedding for Link Prediction: A Comparative Analysis](https://mlsanity.com/paper/2002.00819/) (2020)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [Incorporating Literals into Knowledge Graph Embeddings](https://mlsanity.com/paper/1802.00934/) (2018)
- [DeepDB: Learn from Data, not from Queries!](https://mlsanity.com/paper/1909.00607/) (2019)
- [RDF2Vec Light -- A Lightweight Approach for Knowledge Graph Embeddings](https://mlsanity.com/paper/2009.07659/) (2020)
- [An Analytical Study of Large SPARQL Query Logs](https://mlsanity.com/paper/1708.00363/) (2017)
- [pyRDF2Vec: A Python Implementation and Extension of RDF2Vec](https://mlsanity.com/paper/2205.02283/) (2022)
- [An Approach Based on Bayesian Networks for Query Selectivity Estimation](https://mlsanity.com/paper/1907.06295/) (2019)
- [Estimating the Cardinality of Conjunctive Queries over RDF Data Using Graph Summarisation](https://mlsanity.com/paper/1801.09619/) (2018)
- [LMKG: Learned Models for Cardinality Estimation in Knowledge Graphs](https://mlsanity.com/paper/2102.10588/) (2021)
- [A Software Framework and Datasets for the Analysis of Graph Measures on RDF Graphs](https://mlsanity.com/paper/1907.01885/) (2019)
- [Degree Sequence Bound For Join Cardinality Estimation](https://mlsanity.com/paper/2201.04166/) (2022)

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

- [Graph Neural Networks for Databases: A Survey](https://mlsanity.com/paper/2502.12908/) (2025)
- [Gradient-Based Join Ordering](https://mlsanity.com/paper/2511.14482/) (2025)
- [Fully Inductive Cardinality Estimation](https://mlsanity.com/paper/2607.28311/) (2026)

## Abstract (arXiv)

Cardinality Estimation over Knowledge Graphs (KG) is crucial for query optimization, yet remains a challenging task due to the semi-structured nature and complex correlations of typical Knowledge Graphs. In this work, we propose GNCE, a novel approach that leverages knowledge graph embeddings and Graph Neural Networks (GNN) to accurately predict the cardinality of conjunctive queries. GNCE first creates semantically meaningful embeddings for all entities in the KG, which are then integrated into the given query, which is processed by a GNN to estimate the cardinality of the query. We evaluate GNCE on several KGs in terms of q-Error and demonstrate that it outperforms state-of-the-art approaches based on sampling, summaries, and (machine) learning in terms of estimation accuracy while also having lower execution time and less parameters. Additionally, we show that GNCE can inductively generalise to unseen entities, making it suitable for use in dynamic query processing scenarios. Our proposed approach has the potential to significantly improve query optimization and related applications that rely on accurate cardinality estimates of conjunctive queries.