Higher-Order Graph Databases

• URL: http://arxiv.org/abs/2506.19661v1
• Date: Tue, 24 Jun 2025 14:24:20 GMT
• Title: Higher-Order Graph Databases
• Authors: Maciej Besta, Shriram Chandran, Jakub Cudak, Patrick Iff, Marcin Copik, Robert Gerstenberger, Tomasz Szydlo, Jürgen Müller, Torsten Hoefler,
• Abstract summary: We introduce a new class of systems, higher-order graph databases (HO-GDBs)<n>We provide a theoretical analysis of OLAP and OLAP queries, ensuring correctness, scalability, and compliance.<n>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.<n>Our work ensures low latency and high throughput, and generalizes both ACID-compliant and eventually consistent systems.
• Score: 15.610611896545281
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities [19.352675865525395]
  This paper proposes GATE, high-tier proximity Graph with Adaptive Topology and Query AwarEness.<n>Gate achieves a 1.2-2.0X speed-up in query performance compared to state-of-the-art graph-based indexes.
  arXiv  Detail & Related papers  (2025-06-19T03:07:12Z)
• Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models [59.98982735197465]
  Tokenized Graph Learning Models (TGLMs) convert graphs into ordered token lists for scalable processing.<n>TGLMs rely on hand-designed token lists and their adaptability to diverse graph learning scenarios remains unexplored.<n>We propose Learnable Graph Token List (LGTL), a plug-and-play module to replace hand-designed token lists in TGLMs.
  arXiv  Detail & Related papers  (2025-05-19T06:25:33Z)
• RGL: A Graph-Centric, Modular Framework for Efficient Retrieval-Augmented Generation on Graphs [58.10503898336799]
  We introduce the RAG-on-Graphs Library (RGL), a modular framework that seamlessly integrates the complete RAG pipeline.<n>RGL addresses key challenges by supporting a variety of graph formats and integrating optimized implementations for essential components.<n>Our evaluations demonstrate that RGL not only accelerates the prototyping process but also enhances the performance and applicability of graph-based RAG systems.
  arXiv  Detail & Related papers  (2025-03-25T03:21:48Z)
• Graph Neural Networks for Databases: A Survey [40.25404188975937]
  Graph computation networks (GNNs) are powerful deep learning models for graph data, demonstrating remarkable success across diverse domains.<n>Recently, the database (DB) community has increasingly recognized the potentiality of GNNs, prompting a surge of researches focusing on improving database systems through GNN-based approaches.<n>This survey aims to bridge this gap by providing a structured and in-depth overview of GNNs for DB systems.
  arXiv  Detail & Related papers  (2025-02-18T14:51:50Z)
• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• Top Ten Challenges Towards Agentic Neural Graph Databases [56.92578700681306]
  Graph databases (GDBs) like Neo4j and TigerGraph excel at handling interconnected data but lack advanced inference capabilities.<n>This paper introduces Agentic Neural Graph Databases (Agentic NGDBs), which extend NGDBs with three core functionalities.
  arXiv  Detail & Related papers  (2025-01-24T04:06:50Z)
• Learning Topological Representations with Bidirectional Graph Attention Network for Solving Job Shop Scheduling Problem [27.904195034688257]
  Existing learning-based methods for solving job shop scheduling problems (JSSP) usually use off-the-shelf GNN models tailored to undirected graphs and neglect the rich and meaningful topological structures of disjunctive graphs (DGs) This paper proposes the topology-aware bidirectional graph attention network (TBGAT) to embed the DG for solving JSSP in a local search framework.
  arXiv  Detail & Related papers  (2024-02-27T15:33:20Z)
• GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection [44.501646702560635]
  GADBench is a benchmark tool dedicated to supervised anomalous node detection in static graphs. Our main finding is that tree ensembles with simple neighborhood aggregation can outperform the latest GNNs tailored for the GAD task.
  arXiv  Detail & Related papers  (2023-06-21T13:16:10Z)
• Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases [63.96793270418793]
  Complex logical query answering (CLQA) is a recently emerged task of graph machine learning. We introduce the concept of Neural Graph Database (NGDBs) NGDB consists of a Neural Graph Storage and a Neural Graph Engine.
  arXiv  Detail & Related papers  (2023-03-26T04:03:37Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.