Project 6: Knowledge Graph Memory

Build a structured knowledge graph memory that supports entity-based and multi-hop retrieval.

Quick Reference

Attribute Value
Difficulty Level 3
Time Estimate 2-3 weeks
Main Programming Language Python (Alternatives: TypeScript, Kotlin)
Alternative Programming Languages TypeScript, Kotlin
Coolness Level Level 3
Business Potential Level 3
Prerequisites Basic graph concepts, entity extraction
Key Topics Knowledge graphs, entity resolution, multi-hop retrieval

1. Learning Objectives

By completing this project, you will:

  1. Extract entities and relations from text.
  2. Store them in a graph schema.
  3. Run multi-hop queries with bounded traversal.
  4. Resolve entity aliases and update stale edges.

2. All Theory Needed (Per-Concept Breakdown)

Knowledge Graph Memory and Entity Resolution

Fundamentals Knowledge graph memory stores facts as entities and relationships rather than raw text. This structure enables explicit queries like “Who does the user work for?” without relying on semantic similarity. The main challenges are entity resolution (deciding when two mentions refer to the same entity) and graph traversal (finding the right path without exploding search space). For agent memory, graphs are useful when relationships matter more than semantic similarity.

Deep Dive into the concept Vector memory is excellent for similarity, but it struggles with explicit relationships. A knowledge graph solves this by encoding memory as nodes (entities) and edges (relations). For example, “User works at Acme Corp” becomes a node for User, a node for Acme Corp, and an edge works_at. This structure enables precise retrieval even when the query is not semantically similar to the original text. Multi-hop queries allow reasoning across relationships, such as “What is the company’s cloud provider?” by traversing User -> works_at -> Company -> uses -> Provider.

Entity resolution is the hardest problem. The same entity may appear in different forms: “Acme,” “Acme Corp,” or “Acme, Inc.” Without resolution, the graph fragments and retrieval fails. Strategies include canonicalization (lowercasing, removing punctuation), alias tables, and confidence scoring. You must also handle ambiguity: two different entities may share a name. In that case, you need disambiguation based on context or source metadata.

Graph memory must also handle updates. Relationships can change over time; if the user changes jobs, the old edge should be deprecated or archived. Therefore, edges should carry timestamps and confidence, and retrieval policies should prefer recent edges. This mirrors the decay and versioning strategies from summary memory but applied to graph edges.

Traversal policies are another critical design choice. If you allow unlimited hops, the graph returns irrelevant paths and becomes unusable. You must define maximum hop depth, allowed relation types, and confidence thresholds. This creates a balance between recall and precision. For agent memory, 1-2 hops is usually enough for practical tasks. This project teaches you how to structure, update, and query a graph memory system reliably.

From a systems perspective, this concept must be treated as a first-class interface between data and behavior. That means you need explicit invariants (what must always be true), observability (how you know it is true), and failure signatures (how it breaks when it is not). In practice, engineers often skip this and rely on ad-hoc fixes, which creates hidden coupling between the memory subsystem and the rest of the agent stack. A better approach is to model the concept as a pipeline stage with clear inputs, outputs, and preconditions: if inputs violate the contract, the stage should fail fast rather than silently corrupt memory. This is especially important because memory errors are long-lived and compound over time. You should also define operational metrics that reveal drift early. Examples include: the percentage of memory entries that lack required metadata, the ratio of retrieved memories that are later unused by the model, or the fraction of queries that trigger a fallback route because the primary memory store is empty. These metrics are not just for dashboards; they are design constraints that force you to keep the system testable and predictable.

Another critical dimension is lifecycle management. The concept may work well at small scale but degrade as the memory grows. This is where policies and thresholds matter: you need rules for promotion, demotion, merging, or deletion that prevent the memory from becoming a landfill. The policy should be deterministic and versioned. When it changes, you should be able to replay historical inputs and measure the delta in outputs. This is the same discipline used in data engineering for schema changes and backfills, and it applies equally to memory systems. Finally, remember that memory is an interface to user trust. If the memory system is noisy, the agent feels unreliable; if it is overly strict, the agent feels forgetful. The best designs expose these trade-offs explicitly, so you can tune them according to product goals rather than guessing in the dark.

How this fits on projects This concept is central to Project 6 and complements Projects 3 and 5.

Definitions & key terms

  • Entity: Node representing a person, place, or concept.
  • Relation: Edge describing how entities connect.
  • Entity resolution: Process of merging duplicate entities.
  • Multi-hop query: Traversal across multiple edges.

Mental model diagram (ASCII)

User --works_at--> Acme Corp --uses--> AWS
   \--prefers--> Rust

How It Works (Step-by-Step)

  1. Extract entities and relations from text.
  2. Resolve entities to canonical IDs.
  3. Insert nodes and edges into graph tables.
  4. Query graph with bounded hop depth.
  5. Return paths with confidence and recency.

Minimal Concrete Example

edge:
  source: User
  relation: works_at
  target: Acme Corp
  ts: 2026-01-01
  confidence: 0.9

Common Misconceptions

  • “Graphs replace vector memory.” (False: they complement it.)
  • “Entity resolution can be skipped.” (False: it is essential for correctness.)

Check-Your-Understanding Questions

  1. Why is entity resolution critical?
  2. What is the risk of unlimited traversal?
  3. When should graph memory be preferred over vector memory?

Check-Your-Understanding Answers

  1. Without resolution, the graph fragments and queries fail.
  2. It returns irrelevant paths and increases noise.
  3. When explicit relationships matter (e.g., ownership, affiliation).

Real-World Applications

  • Knowledge bases in enterprise assistants.
  • Reasoning over customer relationships.

Where You’ll Apply It

  • In this project: §5.4 Concepts You Must Understand First and §6 Testing Strategy.
  • Also used in: Project 3, Project 5.

References

  • A-MEM (knowledge graph memory) - https://arxiv.org/abs/2502.12110

Key Insights Graph memory gives you explicit, auditable relationships that embeddings cannot guarantee.

Summary Knowledge graphs are structured memory systems that enable precise, multi-hop retrieval when relationships matter.

Homework/Exercises to Practice the Concept

  1. Design a small graph schema for a personal assistant.
  2. Write three multi-hop queries and predict the paths.

Solutions to the Homework/Exercises

  1. Entities: User, Company, Tool; Relations: works_at, uses, prefers.
  2. Example: User -> works_at -> Company -> uses -> Tool.

3. Project Specification

3.1 What You Will Build

A knowledge graph memory system that:

  • Extracts entities and relationships
  • Stores them in graph tables
  • Supports multi-hop queries
  • Tracks edge confidence and timestamps

3.2 Functional Requirements

  1. Entity Extraction: Identify entities and relations from text.
  2. Entity Resolution: Merge aliases into canonical nodes.
  3. Graph Query: Support 1-2 hop traversal.
  4. Update Rules: Timestamp edges and deprecate stale ones.

3.3 Non-Functional Requirements

  • Performance: Queries under 200ms for 10k edges.
  • Reliability: Deterministic graph traversal with fixed rules.
  • Usability: Clear query output with path traces.

3.4 Example Usage / Output

$ kg add --text "User works at Acme Corp"
[OK] nodes=2 edges=1

$ kg query --path "User -> works_at -> ?"
User -> works_at -> Acme Corp

3.5 Data Formats / Schemas / Protocols

edge:
  source_id: USER-001
  relation: works_at
  target_id: ORG-012
  ts: 2026-01-01
  confidence: 0.9

3.6 Edge Cases

  • Ambiguous entity names
  • Conflicting relations
  • Cyclic graph paths

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

$ kg add --text "User works at Acme Corp"
$ kg query --path "User -> works_at -> ?"

3.7.2 Golden Path Demo (Deterministic)

$ kg query --path "User -> works_at -> ?"
User -> works_at -> Acme Corp
exit_code=0

3.7.3 Failure Demo (Deterministic)

$ kg query --path "User -> founded -> ?"
[ERROR] relation not found
exit_code=2

4. Solution Architecture

4.1 High-Level Design

Text -> Entity Extractor -> Resolver -> Graph Store -> Query Engine

4.2 Key Components

Component Responsibility Key Decisions
Extractor Identify entities and relations Prompt or rules
Resolver Merge aliases Canonicalization
Graph Store Persist nodes/edges Schema design
Query Engine Multi-hop traversal Hop limits

4.3 Data Structures (No Full Code)

Node:
  id: string
  label: string
  aliases: list

4.4 Algorithm Overview

  1. Extract entities and relations.
  2. Resolve to canonical IDs.
  3. Insert nodes and edges.
  4. Traverse graph with hop limit.

Complexity Analysis: O(E) for bounded traversal.

5. Implementation Guide

5.1 Development Environment Setup

- Configure entity extractor
- Prepare graph tables

5.2 Project Structure

project-root/
├── src/
│   ├── extract/
│   ├── resolve/
│   ├── graph/
│   └── query/

5.3 The Core Question You’re Answering

“How do I store and retrieve structured relationships as memory?”

5.4 Concepts You Must Understand First

  1. Entity resolution
  2. Graph traversal

5.5 Questions to Guide Your Design

  1. How will you disambiguate entities?
  2. What hop depth is safe?

5.6 Thinking Exercise

Draw a small graph from a conversation and query it.

5.7 The Interview Questions They’ll Ask

  1. “Why use graphs in memory systems?”
  2. “How do you handle entity resolution?”
  3. “What is a multi-hop query?”
  4. “How do you avoid graph noise?”
  5. “How do you update stale edges?”

5.8 Hints in Layers

Hint 1: Start with a small schema Hint 2: Add alias lists Hint 3: Enforce hop limits Hint 4: Add confidence filters

5.9 Books That Will Help

Topic Book Chapter
Graph algorithms “Algorithms” by Sedgewick/Wayne Ch. 4
Architecture “Fundamentals of Software Architecture” Ch. 2

5.10 Implementation Phases

Phase 1: Foundation

  • Build extractor and graph schema

Phase 2: Core

  • Implement resolution and query engine

Phase 3: Polish

  • Add confidence and decay rules

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Resolution Rule-based / ML Rule-based Deterministic and auditable
Hop depth 1 / 2 / 3 2 Balances recall and noise

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Resolver tests Alias handling
Integration End-to-end query Add + query
Edge Cycles Infinite loop prevention

6.2 Critical Test Cases

  1. Alias resolution merges nodes.
  2. Hop limit enforced.
  3. Conflicting edges handled.

6.3 Test Data

text: "User works at Acme Corp"

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
No resolution Duplicate entities Canonicalization
Unbounded traversal Noisy results Hop limits
Stale edges Wrong answers Decay rules

7.2 Debugging Strategies

  • Visualize graph paths.
  • Inspect edge timestamps.

7.3 Performance Traps

  • Traversing large graphs without indexes.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add relation types

8.2 Intermediate Extensions

  • Add edge confidence scoring

8.3 Advanced Extensions

  • Add graph-based reranking

9. Real-World Connections

9.1 Industry Applications

  • Knowledge graphs in enterprise assistants
  • Neo4j (for reference)

9.3 Interview Relevance

  • Graph modeling and entity resolution are common topics.

10. Resources

10.1 Essential Reading

  • A-MEM paper

10.2 Video Resources

  • Talks on knowledge graphs in AI

10.3 Tools & Documentation

  • SQLite graph modeling guides

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain entity resolution and multi-hop queries.

11.2 Implementation

  • Graph queries work correctly.

11.3 Growth

  • I can justify hop limits and resolution rules.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Entity extraction and graph queries working

Full Completion:

  • Resolution and decay rules implemented

Excellence (Going Above & Beyond):

  • Reranking and confidence-based traversal