mlsanityData to 14 Oct 2026

Higher-Order Graph Databases

arXiv 2506.19661 ↗First posted 24 Jun 2025cs.DB cs.IR cs.LGcited by 0

Not on the map. Why?

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.

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

72 of 177 references.

References · 72

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  4. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  5. 2019Simplifying Graph Convolutional Networkscited by 1,477
  6. 2016Geometric deep learning: going beyond Euclidean datacited by 1,048
  7. 2019Strategies for Pre-training Graph Neural Networkscited by 971
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  9. 2018Junction Tree Variational Autoencoder for Molecular Graph Generationcited by 652
  10. 2018Hypergraph Neural Networkscited by 488
  11. 2017Representation Learning on Graphs: Methods and Applicationscited by 457
  12. 2018Deep Learning on Graphs: A Surveycited by 393
38 more
  1. 2019KG-BERT: BERT for Knowledge Graph Completioncited by 324
  2. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  3. 2019Hypergraph Convolution and Hypergraph Attentioncited by 228
  4. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
  5. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  6. 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
  7. 2022Topological Deep Learning: Going Beyond Graph Datacited by 97
  8. 2017Knowledge Graph Completion via Complex Tensor Factorizationcited by 80
  9. 2019A Re-evaluation of Knowledge Graph Completion Methodscited by 73
  10. 2020Cell Complex Neural Networkscited by 67
  11. 2017Open-World Knowledge Graph Completioncited by 64
  12. 2020Hierarchical Inter-Message Passing for Learning on Molecular Graphscited by 59
  13. 2020HyperSAGE: Generalizing Inductive Representation Learning on Hypergraphscited by 54
  14. 2020Heterogeneous Hypergraph Embedding for Graph Classificationcited by 52
  15. 2019Random Walks on Hypergraphs with Edge-Dependent Vertex Weightscited by 45
  16. 2020Realistic Re-evaluation of Knowledge Graph Completion Methods: An Experimental Studycited by 37
  17. 2022Cell Attention Networkscited by 35
  18. 2019Clustering in graphs and hypergraphs with categorical edge labelscited by 31
  19. 2020GoGNN: Graph of Graphs Neural Network for Predicting Structured Entity Interactionscited by 29
  20. 2022Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysiscited by 29
  21. 2016ProjE: Embedding Projection for Knowledge Graph Completioncited by 26
  22. 2020Evolutionary dynamics of higher-order interactions in social networkscited by 26
  23. 2020A Survey on Graph Neural Networks for Knowledge Graph Completioncited by 26
  24. 2016Foundations of Modern Query Languages for Graph Databasescited by 22
  25. 2019Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queriescited by 22
  26. 2020Hypergraph Random Walks, Laplacians, and Clusteringcited by 20
  27. 2021SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systemscited by 17
  28. 2019Random walks on hypergraphscited by 16
  29. 2020RDF2Vec Light -- A Lightweight Approach for Knowledge Graph Embeddingscited by 16
  30. 2017G-CORE: A Core for Future Graph Query Languagescited by 13
  31. 2022Message Passing Neural Networks for Hypergraphscited by 13
  32. 2018Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representationscited by 12
  33. 2019Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systemscited by 12
  34. 2016Scaling betweenness centrality using communication-efficient sparse matrix multiplicationcited by 11
  35. 2017An introduction to Graph Data Managementcited by 11
  36. 2020To Push or To Pull: On Reducing Communication and Synchronization in Graph Computationscited by 11
  37. 2019Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analyticscited by 10
  38. 2021GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebracited by 10

50 most cited of 72 All 72 (JSON)

Built on by

Not cited yet.