Design a Knowledge Graph Construction and Query System — System Design Interview Practice

Interview prompt

Design a knowledge-graph platform that extracts entities and relations from unstructured sources, resolves identities, tracks provenance and confidence, supports graph reasoning, and answers authorized complex queries.

• Keep source documents, extraction hypotheses, canonical entities, graph edges, provenance, and review decisions distinct.
• Use candidate generation and human or rule-based resolution thresholds; never silently merge uncertain identities.
• Version ontology and extraction models, make ingestion replayable, and constrain LLM-generated queries to an authorized graph schema.
• Explain temporal facts, contradictory sources, deletion, tenant permissions, embeddings, query cost, and confidence calibration.

Requirements and scale assumptions

• Ingest documents, extract entities and relations, resolve candidates, approve ontology mappings, and publish graph versions.
• Query paths and neighborhoods, answer natural-language questions with citations, and return confidence and provenance.
• Support source deletion, reprocessing, corrections, tenant-scoped graphs, review queues, and embedding rebuilds.
• Target entity-resolution precision above 95% on approved evaluation sets and keep interactive graph queries below 2 seconds p95.
• Process millions of documents asynchronously with graph and embedding partitions that isolate hot entities.
• Make extraction, resolution, graph publication, and answer generation traceable and safe to retry.
• Fall back to structured graph search or an explicit no-answer response when LLM or embedding services fail.
• Index 100 million source documents, 1 billion graph edges, and serve 10,000 interactive queries per second.
• Partition by tenant, graph namespace, entity ID, and time; isolate highly connected entities and large ingestion jobs.
• Retain source evidence, graph versions, provenance, review outcomes, and model artifacts while bounding query caches.

• Peak scale: Integrate with LLMs for natural language querying — Capacity assumption that drives partitioning and backpressure.
• Latency target: Entity resolution precision above 95% — User-facing budget for the primary request or read path.
• Durable boundary: Committed before async — The source of truth is Extract entities and relations from text; Perform entity resolution and deduplication.
• Async boundary: At-least-once workers — Keep Use NER + relation extraction pipelines for graph construction, Implement graph databases (Neo4j, ArangoDB) for storage, Use TransE/RotatE for knowledge graph embeddings off the synchronous path.

Key entities

• DocumentVersiondocumentId, sourceVersion, contentHash, aclVersion, language, updatedAt

  Canonical knowledge graph construction and query system content and access-policy version used for indexing.

• IndexGenerationgenerationId, sourceWatermark, schemaVersion, status, alias, createdAt

  Rebuildable knowledge graph construction and query system index generation that can be validated before an atomic alias swap.

• QuerySessionqueryId, tenantId, normalizedQuery, filters, generationId, nextCursor

  Auditable knowledge graph construction and query system query context with filters, cursor, and the generation used to answer it.

• RankingFeedbackqueryId, documentId, position, action, modelVersion, occurredAt

  Privacy-scoped knowledge graph construction and query system relevance signal for offline evaluation and ranking improvement.

Data flow

1. 1. Accept and authorize source changesThe knowledge graph construction and query system ingestion boundary validates content, tenant ownership, ACLs, versions, and idempotency before publishing a document change.
2. 2. Retrieve and rank candidatesThe query service applies authorization filters, retrieves from the active knowledge graph construction and query system generation, ranks within the latency budget, and returns generation freshness.
3. 3. Build a safe index generationPartitioned workers transform knowledge graph construction and query system documents, checkpoint progress, validate counts and ACL parity, then atomically swap the serving alias.
4. 4. Handle freshness and deletesTombstones and ACL changes propagate through the same pipeline so deleted or newly restricted knowledge graph construction and query system content is not left searchable.
5. 5. Measure relevance and recoverFeedback, query traces, lag, and failed partitions drive knowledge graph construction and query system ranking evaluation, replay, and bounded degraded behavior.

Deep dives and trade-offs

• ACL correctness and index generationsFilter knowledge graph construction and query system results by tenant and effective ACL, or prove the active generation contains the same policy snapshot. Build shadow generations and swap aliases atomically so partial reindexes are never visible. Keep source versions and ACL snapshots for replay when permissions or content change.
• Latency, cursors, and graceful degradationUse bounded candidate retrieval, stable sort keys, and generation-aware cursors for knowledge graph construction and query system pagination. Serve the last healthy generation when a new build is incomplete, but expose freshness and avoid silently violating authorization. Protect the query path with timeouts, circuit breakers, and per-tenant quotas.
• Relevance feedback without leakageSeparate knowledge graph construction and query system click or conversion signals from personally identifying data and honor retention or deletion requests. Evaluate ranking by query class and tail latency, not only aggregate click-through. Use replayable query sets and staged model or synonym changes before production rollout.
• Synchronous indexing versus queued indexingCommit the source version synchronously and index asynchronously with a visible freshness contract. Waiting for index mutation makes writes fragile and cannot guarantee immediate consistency at scale.
• Denormalized ACL fields versus filter-time checksDenormalize safe, versioned authorization facts when it meets the policy model, while retaining a source-of-truth check for sensitive results. Stale permissions can become a data-leak path if index updates are treated as authoritative.
• Lexical, vector, or hybrid retrievalStart with the retrieval method that matches the corpus and latency budget, then add hybrid ranking behind an experiment and rollback boundary. Adding embeddings without freshness, explainability, or access-control design increases cost without improving user trust.