Neo4j Knowledge Graphs for AI Agents: When Vectors Aren't Enough

Our production agent runs on 38,000+ embeddings. Vector search answers "find me documents about X" brilliantly. Then a user asks: "Which clients does Maria work with, and which of those have open tasks past their deadline?" Vector search returns documents that mention Maria and deadlines. It cannot walk the relationships. That question is a graph traversal, and no amount of embedding quality fixes it.

That's why we run Neo4j next to our vector store, not instead of it.

What the Graph Actually Stores

We keep the graph deliberately small and typed. In our system, syncing nine data sources, the node types are: Person, Company, Project, Task, Document, Email Thread. The edges carry the business logic:

• WORKS_WITH — person to company, extracted from task assignments and email participation
• BELONGS_TO — task/document to project to company
• MENTIONS — document to entity, extracted at ingest time
• BLOCKED_BY — task dependencies, straight from the task tracker

Everything else stays in Postgres and the vector store. The graph is an index of relationships, not a copy of your data warehouse. When we tried putting full document text into node properties early on, sync became a nightmare and query performance dropped. Store IDs and edges; join back to the source of truth for content.

Vectors vs Graph: The Division of Labor

The hybrid pattern is the most valuable one we've shipped: vector search finds entry-point documents, then a Cypher query expands one or two hops out to pull the people, tasks, and companies attached to those documents. The agent's answer stops being "here are three similar documents" and becomes "here's the document, the two people responsible, and the blocked task attached to it."

Letting the LLM Query the Graph

We do not let the model write free-form Cypher against production. Generated Cypher fails in ugly ways: hallucinated relationship types, cartesian explosions, queries that scan the whole graph. Instead we expose 8 parameterized query templates as tools — "entities connected to X within N hops", "shared connections between X and Y", "timeline of interactions with company X" — and let Claude pick the template and fill the parameters.

Constrained tools beat generated queries. The model chooses what to ask; the template guarantees how it's asked is safe and fast.

Each template has a hop limit and a LIMIT clause baked in. Worst-case latency stays under 200ms even on our densest subgraphs.

The Hard Part: Entity Resolution

Nobody warns you that the graph is only as good as your entity resolution. "Acme Corp" in the CRM, "Acme" in email signatures, and "ACME CORPORATION" in contracts must resolve to one node or every traversal silently misses connections. Our approach:

1. Deterministic matching first — email domains, tax IDs, exact source-system IDs cover ~85% of merges
2. Embedding similarity on names for candidates above 0.92 cosine similarity
3. An LLM pass on the ambiguous remainder, with merges logged for review

We rebuild resolution incrementally as sync workers land new records (tasks every 10 minutes, email every 15, documents hourly). A wrong merge is worse than a missed one — it fabricates relationships — so we bias conservative and keep an unmerge path.

When to Skip the Graph

• Fewer than ~3 data sources — a couple of SQL joins does the same job
• Your users only ever ask document-retrieval questions
• No one on the team will own entity resolution — a stale graph is worse than none

For us the tipping point was cross-system questions. The moment users expect the agent to know that a person in the email system is the same person in the task tracker, you're building a graph whether you call it one or not. Neo4j just makes it queryable.