Patterns/Retrieval Patterns

Graph Structure Can Be Poisoned Too

Why knowledge graph traversal combined with vector search has unique injection vectors

The Conventional Framing

Graph RAG combines knowledge graph traversal with vector search. The graph captures entity relationships; vector search finds relevant content. Together they enable structured reasoning over connected knowledge.

The pattern excels at multi-hop questions requiring relationship understanding.

Why Graph Structure Is Attack Surface

The knowledge graph itself is attack surface. Edges can be added or modified to create paths to malicious nodes. Entity properties can contain injections. Graph traversal follows the structure—if the structure is poisoned, traversal leads to poison.

Attackers who can influence the graph have persistent influence over all queries that traverse affected nodes.

Architecture

Components:

  • Entity extractor— identifies entities in query
  • Graph store— knowledge graph with relationships
  • Traverser— navigates graph from entities
  • Vector search— finds content related to nodes

Trust Boundaries

Knowledge Graph: [User] ──works_at──► [Company] ──has_policy──► [HR Doc] │ [INJECTED EDGE] │ ▼ [Malicious Node] Query about company policies traverses to malicious node. The edge was added by attacker.
  1. Query → Entity extraction — injection in query
  2. Graph structure → Traversal — poisoned edges or nodes
  3. Traversal → Results — malicious nodes returned

Threat Surface

ThreatVectorImpact
Graph poisoningAdd malicious nodes or edges to graphTraversal reaches attacker content
Entity hijackingManipulate entity extraction to reference attacker nodesQueries start from wrong nodes
Traversal path manipulationCreate edges that route traversal through malicious nodesClean queries hit poisoned content
Property injectionStore injections in node propertiesInjection enters via graph data, not documents

The ZIVIS Position

  • •
    Graph structure is first-class attack surface.Nodes, edges, and properties are all injection vectors. Graph integrity is a security requirement.
  • •
    Validate graph mutations.How are nodes and edges added? Who can modify the graph? Graph write access is high-value capability.
  • •
    Audit traversal paths.Log which paths were traversed for each query. Anomalous traversal patterns may indicate graph poisoning.

What We Tell Clients

Graph RAG adds the knowledge graph as attack surface alongside documents. Edges, nodes, and properties can all be poisoned. An attacker with graph write access has persistent influence over queries.

Treat graph integrity as critical. Control who can modify structure, validate graph updates, and monitor for unusual traversal patterns.

Related Patterns