Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases

Hongyu Ren, Mikhail Galkin, Michael Cochez, Zhaocheng Zhu, Jure Leskovec

Our new work (65-pager 👀) on rethinking graph databases in the era of GNNs and neural reasoners where we explore the concept of Neural Graph Databases (NGDBs).

1️⃣ Why do we need NGDBs and what do current graph DBs lack? The biggest motivation is incompleteness - symbolic SPARQL/Cypher-like engines can’t cope with incomplete graphs at scale. In fact, in some cases, SPARQL reasoners might run indefinitely. Neural graph reasoning, however, is already mature enough to work in large and noisy incomplete graphs.

2️⃣ What are NGDBs? While their architecture might look similar to traditional DBs, the essential difference is in ditching symbolic edge traversal and answering queries in the latent space (including logical operators). Broadly, NGDBs are equipped to answer both “what is there?” and “what is missing?” queries whereas standard graph DBs are limited to traversal-only scenarios assuming the graph is complete.

3️⃣ In the NGDB framework, we create a taxonomy and survey 40+ neural graph reasoning models that can potentially serve as Neural Query Engines under 3 main categories: Graphs (theory and expressiveness), Modeling (graph learning), and Queries (what can we answer).

4️⃣ Finally, we outline a handful of key challenges and open problems in the area of Graph ML + Databases and for NGDBs in particular. Lots of cool stuff to work on! (especially if you are in an existential crisis after GPT-4, eg, designing LLM interfaces for NGDBs and how to let NGDBs improve structure, compress and accelerate LLMs are also promising directions)

There is much more to tell about this work so we prepared more resources to learn about NGDBs:

📚 blog post with a gentle intro and images

📜 arxiv preprint

🛠️ github repo with the taxonomy and curated list of relevant papers