When Does a Knowledge Graph Beat Vector Search — and When Do You Actually Need Neo4j?

Almost every “chat with your data” system answers questions the same way: embed the documents, embed the question, return the nearest neighbors, let the model write an answer. For a huge class of questions that works beautifully. For another huge class, it quietly fails — and the failure is invisible until someone asks a question that depends on relationships between things rather than the things themselves.

“What language was the movie directed by Kismet’s director made in?” is not a similarity question. It’s a path: from a movie, to its director, to that director’s other films, to their languages. Vector search has no idea how to walk that path. It will hand you the documents that sound most like the question and confidently miss the answer.

So I measured exactly where the cliff is. I took a real knowledge graph, asked it 1,800 questions bucketed by how many hops the answer sits away, and ran three retrieval strategies head to head: pure vector search, graph traversal, and a hybrid of the two. Then, because the trendy answer to “I need a graph” is “install Neo4j,” I ran the graph part in both Neo4j and plain Postgres to see whether the dedicated graph database actually earns its place.

The result is the honest version of the GraphRAG pitch. Every number below is measured. The most useful parts are the places where each approach falls on its face.

The setup: one graph, real questions, two databases

I used MetaQA, a public benchmark built on a movie knowledge graph derived from WikiMovies. It’s a good test case precisely because it’s relational:

• 134,741 facts (triples like Pulp Fiction | directed_by | Quentin Tarantino)
• 43,234 entities — movies, people, genres, years, languages
• 9 relation types — directed_by, written_by, starred_actors, has_genre, in_language, and so on
• 1,800 real test questions, 600 each at 1-hop, 2-hop, and 3-hop, each labeled with the gold answers and the head entity it starts from

Every fact is an edge between two entities, so a single movie becomes a little star of typed relationships — its director, writer, cast, genre, and year all hanging off it:

Stitch 134,741 of those together and you get the graph. The hop count is then the whole point. A 1-hop question is “who directed [Kismet]” — one edge away. A 3-hop question is “the films that share directors with [Catch Me If You Can] were in which languages” — movie → director → other films → languages. Same graph, wildly different difficulty.

I loaded the identical graph into two systems:

• Postgres — an edges(src, rel, dst) table for traversal, plus a docs table with one embedded sentence per fact for vector search (pgvector, 768-dim nomic-embed-text embeddings).
• Neo4j 5.26 with APOC — the same 134k facts as nodes and relationships.

And I graded every method on numbers a non-specialist should care about:

• Hit-rate — did the correct answer end up in the candidate set at all? (Miss it here and no amount of clever LLM prompting downstream can recover it.)
• Recall — of all the gold answers, what fraction did we find?
• Candidate-set size — how much noise did we hand to the next stage? (Finding the answer inside 12,000 candidates is barely better than not finding it.)
• Latency — p50 and p95, warm.

Method 1: pure vector search — great, until it isn’t

The baseline everyone ships. Turn each fact into a sentence (“The movie Kismet was directed by William Dieterle”), embed all 134k of them, and at query time embed the question and pull the nearest neighbors:

SELECT src, dst
FROM docs
ORDER BY embedding <=> %(qvec)s::vector   -- cosine distance, HNSW index
LIMIT 50;

The candidate answers are the entities mentioned in those top-50 facts. Here’s how it did:

One hop, vector search is genuinely good — 0.86 recall. The fact that answers the question (“Kismet was directed by William Dieterle”) reads a lot like the question, so it ranks near the top.

Then it falls off a cliff. At two hops, recall collapses to 0.18. The reason is structural, not a tuning problem, and one real example makes it concrete. Take this 2-hop question from the dataset:

Q: which person directed the movies starred by Brandon Quinn? — the answer is Ingmar Bergman.

Here are the top 5 facts vector search actually returned:

1. The movie Thirst starred the actor Brandon Quinn.
2. The movie The Buccaneer was directed by Anthony Quinn.
3. The movie Instinct was written by Daniel Quinn.
4. The movie Road to Morocco starred the actor Anthony Quinn.
5. The movie Legends of the Fall is tagged with aidan quinn.

Look at what happened: it matched the word “Quinn.” It surfaced Anthony Quinn, Daniel Quinn, aidan quinn — every “Quinn” in the database — and never reached Ingmar Bergman, the actual answer, because Bergman’s facts don’t mention Brandon Quinn at all. There is no sentence in the corpus that is both semantically close to the question and contains the answer. Embeddings measure similarity; this question is about connection.

The picture says it in one glance: the answer is two solid edges away, but vector search wanders off down the dashed lines toward everything that merely reads like the question.

(*The 3-hop hit-rate ticks back up only because 3-hop questions have large answer sets — “all the languages of all the films sharing a director” can be a dozen entities — so some gold answer lands in the top 50 more often. Recall, the honest metric, stays on the floor at 0.29.)

Method 2: graph traversal — finds everything, and that’s the problem

If the question is a path, walk the path. Start at the head entity and traverse the graph outward to the right depth. In Postgres that’s a recursive CTE — no extension, no new system, just SQL:

WITH RECURSIVE reach(node, depth) AS (
    SELECT %(head)s::text, 0
  UNION
    SELECT nb.node, r.depth + 1
    FROM reach r
    JOIN LATERAL (
        SELECT dst AS node FROM edges WHERE src = r.node   -- follow edges forward
        UNION
        SELECT src AS node FROM edges WHERE dst = r.node    -- ...and backward
    ) nb ON true
    WHERE r.depth < %(depth)s
)
SELECT DISTINCT node FROM reach WHERE node <> %(head)s;

The traversal is undirected because questions go both ways — from a movie to its director, but also from an actor to their movies. And the result is striking:

Perfect recall at every depth. Of course it is — the answer sits at exactly that hop distance, so if you walk far enough you will reach it. That’s the fundamental thing a graph gives you that vectors can’t: completeness.

But look at the candidate count at three hops: a median of 11,674 entities — over a quarter of the entire 43,234-node graph. Take a concrete one. The question “the films that share directors with Catch Me If You Can were in which languages” has four answers — German, Japanese, Mende, Polish. Traversing three hops from Catch Me If You Can reaches 18,672 entities, 43% of the whole graph, and those four answers are buried in there alongside junk like Kevin Connolly, David Kross, ghibli, Scott Glenn, and Bengali. From one starting movie, three undirected hops touches every actor, their other films, those films’ entire casts, and every genre, year, and language along the way. You found the answer, and you found it inside eighteen thousand things. You found everything, which means you found nothing.

This is the trap with “just use a graph.” Recall without precision isn’t an answer; it’s a haystack with a guarantee.

Method 3: hybrid — graph for recall, vectors for precision

The two methods fail in opposite directions. Vector search is precise but can’t reach multi-hop answers. The graph reaches every answer but buries it. So combine them: let the graph guarantee the answer is present, then use the question embedding to rank the candidates and keep the top 20.

-- candidates came from the recursive CTE above; now rerank them by the question
SELECT entity, max(1 - (embedding <=> %(qvec)s::vector)) AS score
FROM (
    SELECT src AS entity, embedding FROM docs WHERE src = ANY(%(cands)s)
    UNION ALL
    SELECT dst AS entity, embedding FROM docs WHERE dst = ANY(%(cands)s)
) t
GROUP BY entity
ORDER BY score DESC
LIMIT 20;

This is the architecture. At two hops, hybrid lifts the answer hit-rate from 0.28 (pure vector) to 0.83 — while handing the next stage a clean shortlist of 20 candidates instead of a blob of 11,674. The graph supplies recall the vectors couldn’t; the vectors supply the ranking the graph couldn’t.

Back to Brandon Quinn. Pure vector search drowned in “Quinn” lookalikes and never found the director. The graph’s 2-hop traversal returned just 10 candidates and the answer was among them; the vector reranker then pulled Ingmar Bergman to second place in the shortlist. Same two tools that failed alone, working together.

Three hops stays genuinely hard — and I’m not going to pretend otherwise. Recall is 0.33 because these questions have large gold sets and a top-20 rerank simply can’t hold all of them. The honest read: a graph makes the answer reachable at any depth, but turning reachable into ranked at three hops needs a stronger reranker (a cross-encoder, or an LLM reasoning over the shortlist) than a single embedding dot-product. The graph did its job; the ranking is where the remaining work is.

Do you actually need Neo4j? Two answers.

When an engineer concludes “I need graph traversal,” the reflex is to reach for a graph database, and Neo4j is the default — it’s the most-used graph database by a wide margin. So I ran the graph workloads in both Neo4j (5.26 with APOC) and plain Postgres on the identical graph. The result isn’t “one of them wins.” It’s that they win different workloads — and the line between them is exactly the thing worth knowing.

Answer 1: for neighborhood reachability, Postgres wins

This is the traversal the hybrid retriever above actually needs: start at an entity, fan out a few hops, collect what you reach. Same breadth-first search in both engines:

MATCH (a:Entity {name: $head})
CALL apoc.path.subgraphNodes(a, {maxLevel: $depth}) YIELD node
RETURN node.name

Both return byte-identical candidate sets — same graph, same BFS, same answers. The difference is speed:

Postgres was roughly 4x faster — with no new database to run, back up, secure, or keep in sync with the data you already have. For neighborhood expansion, the graph already lives in your Postgres as two columns and an index.

Answer 2: for shortest path, Neo4j wins — and it isn’t close

Now ask a different question: how are these two specific things connected? This is the “degrees of separation” query — Kevin Bacon numbers, fraud rings, “is this account linked to that one.” Watch a real one from the data:

Four hops from Kevin Bacon to Scarlett Johansson. Finding that path took Neo4j 2 ms and Postgres 166 ms — Neo4j was 85x faster on this single pair. And it’s not a fluke. Across 150 actor pairs, bucketed by how far apart they actually are:

This is the mirror image of the reachability result, and the reason is structural. To find a shortest path, Postgres has to expand the entire frontier outward, level by level — and in a connected graph that frontier explodes (the same 11,674-then-everything blowup from before). Neo4j searches from both ends at once and stops the instant the two wavefronts meet. The farther apart the nodes, the more Postgres has to materialize and the more Neo4j’s bidirectional search pays off. Postgres climbs from 125 ms to 359 ms as distance grows; Neo4j barely moves off 2 ms.

The same gap shows up in path enumeration — “show me all the ways these two are connected.” Counting every path up to length 4 between co-stars (≈18 paths each), Neo4j ran at a p50 of 28 ms; the Postgres recursive CTE, dragging a path array through every branch, hit a p50 of 334 ms and a p95 of 1.8 seconds. And for genuine graph algorithms — PageRank, community detection, weighted shortest path — it isn’t a contest at all; that’s what a graph engine’s query planner and native traversal exist for, and expressing them in recursive SQL ranges from painful to impractical.

So the honest answer to “do you need Neo4j” is: match the engine to the traversal. Fan-out from a node to assemble context for RAG? Postgres recursive CTEs are faster and one less system. Pathfinding, link analysis, or graph algorithms between specific entities? That’s what Neo4j is built for, and the numbers say so.

So when is a graph the right tool?

The point of measuring all this isn’t “graphs good” or “vectors good.” It’s knowing which question you have:

• Reach for vector search when the question is semantic similarity over one hop — “find me documents about X,” “what’s the policy on Y.” It’s cheap, it’s one index, and it’s genuinely strong here (0.86 recall).
• Reach for a graph when the question is multi-hop and relational — “which customers are connected to this account through shared owners,” “what’s downstream of this component two dependencies out.” Vectors structurally cannot do this; the graph guarantees it can.
• Reach for the hybrid when you have both, which is most real systems — let the graph guarantee recall, let the vectors rank. That’s where the 0.28 → 0.83 jump lives.
• Reach for Neo4j when the traversal is pathfinding, link analysis, or graph algorithms — shortest path, degrees of separation, PageRank, community detection. That’s where it ran 85-135x faster. For plain neighborhood expansion to feed RAG, the recursive CTE in the database you already run is hard to beat.

And to be clear, none of this is an argument against graph databases. It’s an argument for reaching for one deliberately. There is a real, important class of problems — pathfinding, link analysis, fraud rings, recommendation over relationships, anything that leans on graph algorithms — where a dedicated graph engine is decisively the right tool and well worth its operational cost. Neo4j didn’t lose; it won the workloads it was built for, by two orders of magnitude. The mistake isn’t using a graph database. The mistake is standing up a second system for traversals your existing Postgres would have done faster — or, just as expensive, forcing genuine graph algorithms through recursive SQL because you didn’t want to run one.

Every number here came from a small, runnable experiment: 134k facts in Postgres and Neo4j, 1,800 hop-labeled questions, four retrieval strategies, measured. The data is a public movie graph, but the shape is the one that shows up in every customer-360, fraud-ring, supply-chain, and dealer-market-competitor problem I’ve seen: the valuable questions are about connections, and connections are not similarity.

If you’re staring at a “chat with our data” project and trying to decide between vector search, a knowledge graph, GraphRAG, and a pile of infrastructure to run it all — that decision is most of the battle, and the wrong call is expensive in both directions. That’s exactly the kind of architecture work I do. If that’s where you are, let’s talk.