Knowledge Graph Schema Design for MCP Agent Memory — Neptune Property Graph

Why graph memory over vector memory for MCP servers

Vector stores excel at semantic similarity search — finding the passages most similar to a query embedding. Property graphs excel at relational traversal — following named relationships from a known entity to its connected facts. The two are complementary, not competitive. A well-designed MCP agent uses both:

• Vector search (OpenSearch k-NN, Bedrock Knowledge Bases) for initial retrieval: "find chunks semantically similar to the user's query."
• Graph traversal (Neptune) for enrichment: "given the entities mentioned in those chunks, what other entities and facts connect to them in the knowledge base?"

Graph enrichment adds relational context that vector search misses. If the user asks "what are the dependencies of service X?", a vector search may return the service documentation, but a graph traversal can return the exact dependency chain: X → depends_on → Y → depends_on → Z → hosted_in → us-east-1. This level of relational precision is what makes MCP agent responses feel accurate rather than approximate.

Core schema: vertex labels and properties

Core schema: edge labels

MCP tool definitions for the knowledge graph

Design MCP tools to map directly to graph operations. Keep tool scope narrow — the LLM should compose multiple small tools rather than one monolithic tool that does entity extraction, relationship inference, and storage in a single call.

// Tool: store_entity — upsert an entity after extraction
{
  name: 'store_entity',
  inputSchema: {
    type: 'object',
    properties: {
      id: { type: 'string', description: 'Stable entity ID, e.g. entity::Service::aws-lambda' },
      name: { type: 'string' },
      entityType: { type: 'string', enum: ['Person', 'Organization', 'Service', 'Concept', 'Location'] },
      description: { type: 'string' },
      sourceDocumentId: { type: 'string', description: 'Document vertex ID this entity came from' },
    },
    required: ['id', 'name', 'entityType'],
  },
}

// Tool: add_relationship — connect two entities
{
  name: 'add_relationship',
  inputSchema: {
    type: 'object',
    properties: {
      fromId: { type: 'string' },
      toId: { type: 'string' },
      relationshipType: { type: 'string', description: 'Semantic label: depends_on, is_part_of, authored_by, etc.' },
      weight: { type: 'number', minimum: 0, maximum: 1, description: 'Confidence score 0–1' },
    },
    required: ['fromId', 'toId', 'relationshipType'],
  },
}

// Tool: get_entity_context — retrieve graph neighborhood for RAG enrichment
{
  name: 'get_entity_context',
  inputSchema: {
    type: 'object',
    properties: {
      entityId: { type: 'string' },
      hops: { type: 'integer', minimum: 1, maximum: 3, default: 2 },
      includeSourceChunks: { type: 'boolean', default: true },
    },
    required: ['entityId'],
  },
}

// Implementation of get_entity_context
async function getEntityContext(entityId: string, hops: number, includeSourceChunks: boolean) {
  const g = await getTraversalSource();

  // Get entity itself
  const entity = await g.V(entityId).valueMap(true).next();
  if (!entity.value) throw new Error(`Entity not found: ${entityId}`);

  // Get N-hop neighborhood
  const neighborhood = await g.V(entityId)
    .repeat(__.both('RELATES_TO').simplePath())
    .times(hops)
    .dedup()
    .limit(30)
    .project('entity', 'distance')
    .by(__.valueMap(true))
    .by(__.loops())   // loops() returns current traversal depth
    .toList();

  // Get source chunks if requested
  let sourceChunks: unknown[] = [];
  if (includeSourceChunks) {
    sourceChunks = await g.V(entityId)
      .in_('MENTIONS')               // Chunk that mentions this entity
      .has('tokenCount', P.lt(512))  // filter to shorter chunks that fit in context
      .limit(5)
      .values('text')
      .toList();
  }

  return {
    entity: entity.value,
    neighbors: neighborhood.map(n => ({ entity: n.entity, hops: n.distance })),
    sourceChunks,
  };
}

Temporal fact versioning

Facts in a knowledge graph change over time. The price of a service changes. An API endpoint is deprecated. An employee leaves a company. Neptune does not have a native time-travel feature — you model temporal validity with validFrom and validTo epoch-ms properties on edges and Fact vertices.

// Add a versioned fact
await g.addV('Fact')
  .property(T.id, `fact::${hash(claim)}`)
  .property('claim', claim)
  .property('confidence', 0.95)
  .property('validFrom', Date.now())
  .property('validTo', null)         // null = currently valid
  .next();

// Supersede an old fact with a new one
async function supersedeFact(oldFactId: string, newClaim: string) {
  const now = Date.now();

  // Mark old fact as expired
  await g.V(oldFactId)
    .property(cardinality.single, 'validTo', now)
    .next();

  // Create new fact
  const newFactId = `fact::${hash(newClaim)}`;
  await g.addV('Fact')
    .property(T.id, newFactId)
    .property('claim', newClaim)
    .property('validFrom', now)
    .property('validTo', null)
    .next();

  // Link them
  await g.addE('SUPERSEDES')
    .from_(g.V(newFactId))
    .to_(g.V(oldFactId))
    .property('supersededAt', now)
    .next();
}

// Query only currently valid facts
const currentFacts = await g.V()
  .hasLabel('Fact')
  .has('validTo', null)        // validTo is null for currently active facts
  .related(entityId, 'ABOUT')  // filter to facts about a specific entity
  .values('claim')
  .toList();

An alternative to null-terminated validity is using a sentinel value like Number.MAX_SAFE_INTEGER. The null approach is more readable but requires Neptune to handle null in has('validTo', null) — Neptune supports this correctly, unlike some graph databases that require a placeholder value.

Multi-tenant namespace isolation

When an MCP server serves multiple tenants (organizations or users), all sharing the same Neptune cluster, vertex IDs must be namespaced to prevent tenants from reading each other's data. Neptune has no row-level security equivalent — isolation is by ID prefix convention enforced at the application layer.

const TENANT_ID = process.env.TENANT_ID!;  // injected at deploy time, not from user input

function tenantId(type: string, name: string): string {
  // Hash the name so it's URL-safe and consistent
  return `${TENANT_ID}::${type}::${createHash('sha256').update(name).digest('hex').slice(0, 16)}`;
}

// All graph operations prefix IDs with tenant
async function storeEntityForTenant(name: string, entityType: string) {
  const id = tenantId('entity', `${entityType}::${name.toLowerCase()}`);
  return upsertEntity(id, name, entityType);
}

// All traversals scope to tenant's vertex ID prefix
async function getEntitiesForTenant(entityType: string, limit: number = 20) {
  return g.V()
    .hasLabel('Entity')
    .has(T.id, P.between(`${TENANT_ID}::entity::`, `${TENANT_ID}::entity::z`))
    .has('entityType', entityType)
    .limit(limit)
    .valueMap(true)
    .toList();
}

Neptune does support predicates on the special T.id property with P.between() and P.within(). This allows prefix-range scans, which are efficient because Neptune indexes vertex IDs. Prefix scanning is not a full-text search — it uses string ordering, so ensure your prefix is a fixed-width, sortable string.

Common failures