Knowledge Graph Security for AI Platforms

TL;DR — Knowledge graphs power AI retrieval by encoding relationships between entities, but they introduce unique security challenges. Graph traversals can cross tenant boundaries through shared relationships. Properties on a single node may have different sensitivity levels. Access control must operate at four levels: node-level (who can see this entity), property-level (who can see this field), relationship-level (who can traverse this edge), and subgraph-level (who can reach this cluster of nodes). Implement RBAC with DENY precedence, query rewriting for row-level security, tenant partitioning, and audit logging. Use the knowledge graph for access-controlled, relationship-aware retrieval alongside a vector database for semantic search. Never allow unfiltered graph traversals in a multi-tenant environment.

Why Knowledge Graphs Need Different Security

Relational databases store data in rows and tables. Security is straightforward: row-level security filters rows, column-level security filters columns, and queries are bounded by JOINs that the developer explicitly writes.

Knowledge graphs store data as nodes and relationships. A single Cypher query can traverse thousands of relationships, crossing from public data to private data through shared nodes. A user who has access to a "Project" node might traverse an "owned_by" relationship to reach a "User" node containing PII — without ever explicitly querying for user data.

This makes knowledge graph security fundamentally different:

Four Levels of Graph Access Control

Level 1: Node-Level Security

Control which nodes a user can see based on their role. This is the graph equivalent of row-level security.

@node("Document")
@secured(
    read=["reader", "editor", "admin"],
    write=["editor", "admin"],
    create=["editor", "admin"],
    delete=["admin"]
)
class Document:
    id: str
    title: str
    content: str
    tenant_id: str
    sensitivity: str  # "public", "internal", "restricted"

Enforcement: filter nodes by role after query execution, or rewrite the query to include role-based predicates.

Level 2: Property-Level Security

Control which properties a user can see on a node they already have access to. A reader can see a Person's name and email but not their SSN.

@node("Person")
@secured(
    read=["reader", "editor", "admin"],
    deny_read_properties={
        "ssn": ["reader", "editor"],      # Only admin can read SSN
        "salary": ["reader", "editor"],   # Only admin can read salary
        "internal_notes": ["reader"]      # Editor and admin can read notes
    },
    deny_write_properties={
        "ssn": ["editor"]                 # Only admin can write SSN
    }
)
class Person:
    name: str
    email: str
    ssn: str
    salary: float
    internal_notes: str

DENY precedence: DENY always takes precedence over GRANT. If a property is denied for a role, no amount of grants on the node can override it.

Enforcement: Property filtering happens post-query (filter denied properties from returned nodes) or at query-time (rewrite the query to exclude denied properties). Post-query is simpler but less efficient — the database retrieves data that is then filtered out. Query-time is more efficient but requires query rewriting.

Level 3: Relationship-Level (Traversal) Security

Control which relationships a user can follow during a traversal. This is unique to graph databases and has no equivalent in relational databases.

@relationship("REFERENCES")
@secured(
    traverse=["reader", "editor", "admin"],
    create=["editor", "admin"],
    delete=["admin"]
)

@relationship("OWNED_BY")
@secured(
    traverse=["admin"],  # Only admin can traverse ownership
    create=["admin"],
    delete=["admin"]
)

Why this matters: A user with READ access to a Document node might traverse a "references" relationship to reach connected documents. Without traversal control, a single accessible node becomes a bridge to the entire graph.

Cross-tenant risk: In a multi-tenant graph, shared nodes (like a public taxonomy or a shared category) can become bridges between tenants. Traversal security prevents a user in tenant A from reaching tenant B's nodes through a shared "categorized_as" relationship.

Level 4: Subgraph-Level Security

Control which clusters of nodes a user can reach, considering the full traversal path. This is the most complex but most important level for multi-tenant environments.

def enforce_subgraph_security(query: str, user: User, tenant: Tenant) -> str:
    """Rewrite query to restrict traversals to the user's permitted subgraph."""

    # Inject tenant filter at every node match
    query = inject_tenant_filter(query, tenant.id)

    # Remove relationships that cross tenant boundaries
    query = remove_cross_tenant_traversals(query, tenant.id)

    # Add sensitivity filter based on user's clearance level
    query = inject_sensitivity_filter(query, user.clearance_level)

    return query

Example: A query that traverses from a Document through "owned_by" to a User, then through "member_of" to a Team, must be validated at every hop:
- Can the user read this Document? (node-level)
- Can the user traverse "owned_by"? (relationship-level)
- Can the user read this User? (node-level)
- Can the user traverse "member_of"? (relationship-level)
- Can the user read this Team? (node-level)

If any check fails, the traversal must stop — not return partial results that reveal the existence of the blocked node.

Tenant Isolation Strategies

Strategy 1: Separate Graphs Per Tenant (Strongest)

Each tenant gets their own graph database or graph namespace. No shared nodes, no cross-tenant traversals possible.

def get_graph_for_tenant(tenant_id: str) -> Graph:
    return Graph(f"graph:{tenant_id}")

# Tenant A's queries can never reach tenant B's data
graph_a = get_graph_for_tenant("tenant-a")
results = graph_a.query("MATCH (d:Document) RETURN d")

Pros: Strongest isolation, no cross-tenant leakage possible, simple security model.
Cons: Resource overhead (one graph per tenant), no shared knowledge (taxonomies, ontologies must be duplicated), harder to maintain consistency.

Strategy 2: Tenant-Labeled Nodes with Query Rewriting (Balanced)

All tenants share one graph, but every node has a tenant_id property. Every query is rewritten to filter by tenant.

-- Original query
MATCH (d:Document)-[:owned_by]->(u:User)
RETURN d, u

-- Rewritten query (tenant-a)
MATCH (d:Document {tenant_id: "tenant-a"})-[:owned_by]->(u:User {tenant_id: "tenant-a"})
RETURN d, u

Pros: Efficient resource usage, shared schema, simpler management.
Cons: Query rewriting must be bulletproof — a single unrewritten query leaks data. Shared nodes (taxonomies) create cross-tenant bridge risk.

Implementation:

def rewrite_query_with_tenant_filter(query: str, tenant_id: str) -> str:
    """Inject tenant_id filter into every node pattern in the query."""
    # Parse the Cypher query
    parsed = parse_cypher(query)

    # For every node pattern, add tenant_id property
    for node in parsed.node_patterns:
        if node.label in TENANT_SCOPED_LABELS:
            node.add_property("tenant_id", tenant_id)

    # For every relationship pattern, verify both endpoints have same tenant_id
    for rel in parsed.relationship_patterns:
        if rel.crosses_tenant_boundary:
            raise SecurityError("Cross-tenant traversal detected")

    return parsed.to_cypher()

Strategy 3: Shared Graph with Tenant-Scoped Traversals (Weakest)

All tenants share one graph, including some shared nodes. Traversals are scoped to the tenant's permitted subgraph.

Pros: Maximum flexibility, shared knowledge graphs, efficient.
Cons: Highest risk — shared nodes are bridges. Requires comprehensive traversal security. One bug in traversal filtering exposes all tenants.

Recommendation: Use Strategy 2 for most enterprise deployments. Use Strategy 1 for tenants with strict compliance requirements (healthcare, defense). Avoid Strategy 3 unless you have a dedicated security team.

Query Rewriting for Row-Level Security

Row-level security in graph databases requires query rewriting — automatically injecting security predicates into every query.

Cypher Query Rewriting

class GraphQueryRewriter:
    def __init__(self, security_context: SecurityContext):
        self.context = security_context

    def rewrite(self, query: str) -> str:
        parsed = parse_cypher(query)

        for match_clause in parsed.match_clauses:
            for node in match_clause.nodes:
                # Inject tenant filter
                if self.context.tenant_id:
                    node.add_property("tenant_id", self.context.tenant_id)

                # Inject sensitivity filter
                if self.context.clearance_level:
                    node.add_property_constraint(
                        "sensitivity", "<=", self.context.clearance_level
                    )

                # Inject owner filter for personal documents
                if node.label == "PersonalDocument":
                    node.add_property_constraint(
                        "owner", "=", self.context.user_id
                    )

        # Remove denied relationships from traversals
        for match_clause in parsed.match_clauses:
            for rel in match_clause.relationships:
                if rel.type in self.context.denied_traversals:
                    raise SecurityError(
                        f"Traversal denied for relationship type: {rel.type}"
                    )

        return parsed.to_cypher()

Example: Before and After Rewriting

Original query (user input):

MATCH (d:Document)-[:references]->(r:Document)
WHERE d.title CONTAINS "quarterly"
RETURN d, r

Rewritten query (after security injection):

MATCH (d:Document {
    tenant_id: "tenant-456",
    sensitivity: "internal"
})-[:references]->(r:Document {
    tenant_id: "tenant-456",
    sensitivity: "internal"
})
WHERE d.title CONTAINS "quarterly"
RETURN d.title, r.title

Note: property-level security also rewrites the RETURN clause to exclude denied properties.

Audit Logging for Graph Databases

Graph database audit logs must capture more than relational database logs:

{
  "timestamp": "2026-07-07T10:15:00Z",
  "user_id": "alice@company.com",
  "tenant_id": "tenant-456",
  "role": "analyst",
  "query": "MATCH (d:Document)-[:references]->(r:Document) WHERE d.title CONTAINS 'quarterly' RETURN d, r",
  "rewritten_query": "MATCH (d:Document {tenant_id: 'tenant-456', ...})...",
  "nodes_accessed": [
    {"id": "node-123", "label": "Document", "properties_read": ["title", "content"]},
    {"id": "node-456", "label": "Document", "properties_read": ["title"]}
  ],
  "relationships_traversed": [
    {"type": "references", "from": "node-123", "to": "node-456"}
  ],
  "nodes_denied": [
    {"id": "node-789", "label": "Document", "reason": "sensitivity_exceeds_clearance"}
  ],
  "properties_denied": [
    {"node_id": "node-123", "property": "internal_notes", "reason": "role_denied"}
  ],
  "result_count": 2,
  "execution_time_ms": 15
}

Key fields that graph audit logs must capture:
- Nodes accessed: Which nodes were returned, with which properties
- Relationships traversed: Which relationship types were followed
- Nodes denied: Which nodes were filtered out and why
- Properties denied: Which properties were redacted and why
- Rewritten query: The actual query executed after security injection

Knowledge Graph + Vector Database Architecture

For enterprise AI, the knowledge graph and vector database serve complementary roles:

User Query
    ↓
Knowledge Graph (access-controlled retrieval)
    ├── Resolve entity relationships
    ├── Enforce node/property/traversal permissions
    ├── Return permitted subgraph
    ↓
Vector Database (semantic search within permitted subgraph)
    ├── Embed permitted nodes
    ├── Semantic similarity search
    ├── Rank by relevance
    ↓
LLM (generation)
    ├── Grounded in permitted, relevant context
    └── Generate response with citations

Why this order matters: The knowledge graph filters first (access control), then the vector database ranks (relevance). If the vector database filters first, it might retrieve semantically relevant but access-denied content — which then must be filtered out, potentially leaking information through timing or result count side channels.

Per-Tenant Vector Partitions

Even with knowledge graph filtering, vector databases should use per-tenant partitions:

def search_vector_db(query_embedding: list, tenant_id: str, permitted_node_ids: list):
    # Search only within the tenant's partition and permitted nodes
    results = vector_db.search(
        query_embedding,
        filter={
            "tenant_id": tenant_id,
            "node_id": {"$in": permitted_node_ids}
        },
        top_k=10
    )
    return results

Per-Tenant Security Configuration

tenant_graph_security:
  tenant_id: "tenant-456"
  isolation_strategy: "labeled_nodes"  # or "separate_graphs"
  rbac:
    enabled: true
    deny_precedence: true
    role_hierarchy:
      - admin
      - editor
      - reader
      - PUBLIC
  property_level_security:
    enabled: true
    default_deny: ["ssn", "salary", "internal_notes"]
  traversal_security:
    enabled: true
    denied_traversals_for_reader:
      - "owned_by"
      - "accessed_by"
  query_rewriting:
    enabled: true
    inject_tenant_filter: true
    inject_sensitivity_filter: true
  audit:
    log_nodes_accessed: true
    log_traversals: true
    log_denials: true
    log_rewritten_queries: true
    retention_days: 365
  vector_db:
    per_tenant_partition: true
    search_after_graph_filter: true

Common Security Mistakes

Unfiltered Graph Traversals

Allowing users to write arbitrary Cypher queries without query rewriting. A user can traverse from an accessible node to any connected node, crossing tenant boundaries through shared relationships.

Fix: Never allow raw user queries. All queries must pass through the query rewriter that injects tenant and security filters.

Post-Query Property Filtering Only

Filtering denied properties after the query returns all data from the database. This means the database reads sensitive data into memory, even if it's filtered before returning to the user. A bug in the filtering logic exposes everything.

Fix: Use query-time property filtering (exclude denied properties from the RETURN clause) wherever possible. Post-query filtering should be a defense-in-depth layer, not the primary control.

Shared Nodes as Tenant Bridges

A shared taxonomy node ("Category: Finance") connected to documents from multiple tenants. A traversal from the shared node reaches all connected documents regardless of tenant.

Fix: Mark shared nodes as "non-traversable from" — users can match them directly but cannot traverse relationships from them to other nodes. Or duplicate shared nodes per tenant.

Missing Traversal Security

Implementing node-level and property-level security but forgetting relationship-level security. Users can traverse relationships they shouldn't, reaching nodes through paths that bypass node-level filters.

Fix: Explicitly define traversal permissions for every relationship type. Default-deny: if a relationship type is not explicitly granted, traversal is denied.

Inconsistent Query Paths

Different code paths for querying the graph — some go through the query rewriter, others don't. An unrewritten query bypasses all security.

Fix: Centralize all graph access through a single gateway that enforces query rewriting. No code should have direct access to the graph database client.

Implementation Checklist

• [ ] Implement node-level RBAC (READ, WRITE, CREATE, DELETE per role)
• [ ] Implement property-level security with DENY precedence
• [ ] Implement relationship-level (traversal) security
• [ ] Implement subgraph-level security for multi-tenant traversals
• [ ] Choose tenant isolation strategy (separate graphs or labeled nodes)
• [ ] Implement query rewriting for row-level security
• [ ] Inject tenant_id filter into every node pattern
• [ ] Inject sensitivity filter based on user clearance
• [ ] Block cross-tenant traversals through shared nodes
• [ ] Default-deny for unconfigured relationship traversals
• [ ] Centralize all graph access through a security gateway
• [ ] Never allow raw user Cypher/Gremlin queries
• [ ] Use query-time property filtering, not just post-query
• [ ] Log all nodes accessed, properties read, and traversals followed
• [ ] Log denied nodes, denied properties, and denied traversals
• [ ] Log rewritten queries for audit trail
• [ ] Configure per-tenant security policies
• [ ] Use knowledge graph filtering before vector database search
• [ ] Partition vector database per tenant
• [ ] Test cross-tenant traversal prevention with adversarial queries

Conclusion

Knowledge graphs are powerful tools for AI retrieval — they encode relationships that vector databases cannot. But their power is also their security risk: graph traversals can cross tenant boundaries, reach sensitive nodes through indirect paths, and expose properties that users should not see.

The defense is four-level access control: node-level (who can see this entity), property-level (who can see this field), relationship-level (who can traverse this edge), and subgraph-level (who can reach this cluster). Implement query rewriting that injects tenant and security filters into every query. Use DENY precedence for property-level security. Default-deny for traversal security. Centralize all graph access through a security gateway — never allow raw user queries.

For multi-tenant platforms, choose labeled nodes with query rewriting for balanced isolation, or separate graphs for strict compliance tenants. Never allow shared nodes to become tenant bridges. Use the knowledge graph for access-controlled retrieval before vector database search — permissions first, relevance second.

Enterprise customers will ask about graph traversal security in their review. Having a clear answer — four-level access control, query rewriting, tenant isolation, and comprehensive audit logging — is essential for closing enterprise deals.