# Higher-Order Graph Databases

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 72 of its 177 references that are in the map.
- First posted on arXiv 24 Jun 2025.

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

- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [KG-BERT: BERT for Knowledge Graph Completion](https://mlsanity.com/paper/1909.03193/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Hypergraph Convolution and Hypergraph Attention](https://mlsanity.com/paper/1901.08150/) (2019)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [Topological Deep Learning: Going Beyond Graph Data](https://mlsanity.com/paper/2206.00606/) (2022)
- [Knowledge Graph Completion via Complex Tensor Factorization](https://mlsanity.com/paper/1702.06879/) (2017)
- [A Re-evaluation of Knowledge Graph Completion Methods](https://mlsanity.com/paper/1911.03903/) (2019)
- [Cell Complex Neural Networks](https://mlsanity.com/paper/2010.00743/) (2020)
- [Open-World Knowledge Graph Completion](https://mlsanity.com/paper/1711.03438/) (2017)
- [Hierarchical Inter-Message Passing for Learning on Molecular Graphs](https://mlsanity.com/paper/2006.12179/) (2020)
- [HyperSAGE: Generalizing Inductive Representation Learning on Hypergraphs](https://mlsanity.com/paper/2010.04558/) (2020)
- [Heterogeneous Hypergraph Embedding for Graph Classification](https://mlsanity.com/paper/2010.10728/) (2020)
- [Random Walks on Hypergraphs with Edge-Dependent Vertex Weights](https://mlsanity.com/paper/1905.08287/) (2019)
- [Realistic Re-evaluation of Knowledge Graph Completion Methods: An Experimental Study](https://mlsanity.com/paper/2003.08001/) (2020)
- [Cell Attention Networks](https://mlsanity.com/paper/2209.08179/) (2022)
- [Clustering in graphs and hypergraphs with categorical edge labels](https://mlsanity.com/paper/1910.09943/) (2019)

## Abstract (arXiv)

Recent advances in graph databases (GDBs) have been driving interest in large-scale analytics, yet current systems fail to support higher-order (HO) interactions beyond first-order (one-hop) relations, which are crucial for tasks such as subgraph counting, polyadic modeling, and HO graph learning. We address this by introducing a new class of systems, higher-order graph databases (HO-GDBs) that use lifting and lowering paradigms to seamlessly extend traditional GDBs with HO. We provide a theoretical analysis of OLTP and OLAP queries, ensuring correctness, scalability, and ACID compliance. We implement a lightweight, modular, and parallelizable HO-GDB prototype that offers native support for hypergraphs, node-tuples, subgraphs, and other HO structures under a unified API. The prototype scales to large HO OLTP & OLAP workloads and shows how HO improves analytical tasks, for example enhancing accuracy of graph neural networks within a GDB by 44%. Our work ensures low latency and high query throughput, and generalizes both ACID-compliant and eventually consistent systems.