Enforcing Multi-Tenant Security in Spatial Graphs

Cross-tenant data leakage in spatial routing graphs rarely starts with broken authentication — it starts with an unscoped index. The symptom is a logistics route that returns a node belonging to another customer, or a point.distance filter that returns counts no single tenant could explain. The root cause is that geometric indexes (R-trees, geohash grids, native point indexes) rank candidates by proximity alone and know nothing about tenancy, so when the tenant predicate is evaluated after the spatial seek, the planner has already materialized cross-tenant candidate rows. This page resolves that by binding the tenant identifier to the spatial seek itself: a composite (tenant_id, location) access path, parameterized queries that the planner can push down, and a GDS projection scoped to one tenant’s subgraph so traversal can never escape the boundary.

This guide is part of Spatial Security Boundaries, and it builds directly on the node and edge spatial mapping contract — the zone/tenant tag added at ingestion is the seam enforced here.

Prerequisites & Versions

The implementation uses the async Neo4j driver, native point types, and the Graph Data Science plugin for tenant-scoped A* routing. Pin these minimums.

pip install "neo4j>=5.18"

Confirm every routable node already carries a tenant_id property and a WGS 84 location point before you build the index — back-filling tenancy after the fact leaves orphaned nodes that satisfy spatial predicates but escape the composite seek.

Implementation

A single class owns the whole boundary: it creates the composite index, validates request geometry client-side, projects a per-tenant GDS subgraph, and runs A* against that projection. Every Cypher call is parameterized — no f-string interpolation of tenant values — so the planner can reuse a cached plan and push the tenant predicate into the index seek.

import asyncio
import math
from typing import Any, Dict, List, Tuple

from neo4j import AsyncGraphDatabase


class TenantScopedSpatialRouter:
    def __init__(self, uri: str, user: str, password: str, max_pool: int = 100):
        self.driver = AsyncGraphDatabase.driver(
            uri,
            auth=(user, password),
            max_connection_pool_size=max_pool,
            liveness_check_timeout=30.0,
        )

    async def close(self) -> None:
        await self.driver.close()

    async def ensure_schema(self) -> None:
        """Composite index makes tenant + geometry one seek, not a seek + filter."""
        async with self.driver.session() as session:
            await session.run(
                """
                CREATE INDEX location_tenant_geo IF NOT EXISTS
                FOR (n:Location) ON (n.tenant_id, n.location)
                """
            )
            await session.run(
                """
                CREATE CONSTRAINT location_tenant_id IF NOT EXISTS
                FOR (n:Location) REQUIRE (n.tenant_id, n.id) IS UNIQUE
                """
            )

    @staticmethod
    def validate_spatial_bounds(
        start: Tuple[float, float], end: Tuple[float, float], max_radius_m: float
    ) -> bool:
        R = 6_371_000.0  # WGS84 mean radius in metres
        dlat = math.radians(end[0] - start[0])
        dlon = math.radians(end[1] - start[1])
        a = (
            math.sin(dlat / 2) ** 2
            + math.cos(math.radians(start[0]))
            * math.cos(math.radians(end[0]))
            * math.sin(dlon / 2) ** 2
        )
        return (2 * R * math.asin(math.sqrt(a))) <= max_radius_m

    async def project_tenant_graph(self, tenant_id: str) -> str:
        """Project ONLY this tenant's subgraph into GDS — isolation by construction."""
        graph_name = f"routing_{tenant_id}"
        cypher = """
        CALL gds.graph.exists($name) YIELD exists
        WITH exists WHERE NOT exists
        CALL gds.graph.project.cypher(
            $name,
            'MATCH (n:Location {tenant_id: $tid})
             RETURN id(n) AS id,
                    n.location.latitude  AS latitude,
                    n.location.longitude AS longitude',
            'MATCH (a:Location {tenant_id: $tid})-[r:CONNECTS]->(b:Location {tenant_id: $tid})
             RETURN id(a) AS source, id(b) AS target,
                    coalesce(r.distance_m, 1.0) AS weight',
            { parameters: { tid: $tid } }
        ) YIELD graphName
        RETURN graphName
        """
        async with self.driver.session() as session:
            await (await session.run(cypher, name=graph_name, tid=tenant_id)).consume()
        return graph_name

    async def compute_tenant_route(
        self,
        tenant_id: str,
        start_id: str,
        end_id: str,
        start: Tuple[float, float],
        end: Tuple[float, float],
    ) -> List[Dict[str, Any]]:
        if not self.validate_spatial_bounds(start, end, 50_000.0):
            raise ValueError("Route exceeds tenant spatial boundary constraints.")

        graph_name = await self.project_tenant_graph(tenant_id)

        # Anchor nodes are matched by (tenant_id, id) — the composite seek — then
        # handed to A*, which can only traverse the tenant-scoped projection.
        query = """
        MATCH (s:Location {tenant_id: $tenant_id, id: $start_id})
        MATCH (e:Location {tenant_id: $tenant_id, id: $end_id})
        CALL gds.shortestPath.astar.stream($graph, {
            sourceNode: s,
            targetNode: e,
            latitudeProperty: 'latitude',
            longitudeProperty: 'longitude',
            relationshipWeightProperty: 'weight'
        })
        YIELD totalCost, path
        RETURN totalCost, [n IN nodes(path) | n.id] AS route
        """
        async with self.driver.session() as session:
            result = await session.run(
                query,
                tenant_id=tenant_id,
                start_id=start_id,
                end_id=end_id,
                graph=graph_name,
            )
            return await result.data()

How It Works

Three mechanisms carry the isolation guarantee, each tied to a line in the code above.

• The composite index does the work. CREATE INDEX ... ON (n.tenant_id, n.location) gives the planner a single access path where tenant_id is the leading key. A MATCH (s:Location {tenant_id: $tenant_id, id: $start_id}) then resolves both predicates inside one seek, so non-tenant nodes are never read into a candidate set. Without the leading tenant key, the engine seeks on geometry and then drops other tenants — the window where a leak or a heap blow-up happens.
• Parameters keep the plan honest. Tenant context is always passed as $tenant_id, never interpolated. Beyond injection safety, this lets the planner cache and reuse a pushed-down plan; dynamic string queries disable that path and degrade into label scans. This is the same planner-seek discipline covered under graph query planner optimization.
• The projection is the hard wall. gds.graph.project.cypher is filtered to {tenant_id: $tid} on both the node and relationship queries. A* receives a graph that physically contains only one tenant’s nodes and edges, so even a logic bug in the anchor MATCH cannot route across the boundary — the foreign nodes do not exist in the projection.

Client-side validate_spatial_bounds rejects out-of-range requests with a Haversine check before any database round-trip, trimming wasted seeks under load.

Common Failure Patterns

1. Geometry-first index, tenant-second filter. If you create ON (n.location) alone, the planner seeks the bounding box and post-filters tenancy. Fix it by making tenant_id the leading composite key and confirming the plan with PROFILE:

PROFILE
MATCH (s:Location {tenant_id: $tenant_id, id: $start_id})
RETURN s.id
// The first operator must read NodeIndexSeek on location_tenant_geo,
// not NodeByLabelScan followed by a Filter on tenant_id.

2. Mixed coordinate reference systems inside one tenant. A geographic point({latitude, longitude}) (SRID 4326) and a Cartesian point({x, y}) (SRID 7203) are not comparable — point.distance across them returns null, and a null predicate silently drops rows, so a tenant sees fewer reachable nodes than it owns. Normalize CRS at ingestion, the same discipline applied by the spatial indexing strategies layer:

// Audit: any tenant node not stored as a geographic point is a routing hole
MATCH (n:Location {tenant_id: $tenant_id})
WHERE n.location.srid <> 4326
RETURN count(n) AS non_wgs84_nodes

3. Stale or shared GDS projections. Re-using one routing projection across tenants, or keeping a projection after re-ingestion, leaks topology and routes against pre-update edges. Name projections per tenant (routing_<tenant_id>) and drop them on data change:

CALL gds.graph.exists($name) YIELD exists
WITH exists WHERE exists
CALL gds.graph.drop($name) YIELD graphName
RETURN graphName

Performance Notes

The composite index adds write amplification: every insert updates both the geometric structure and the tenant-ordered key. Absorb it with partitioned batch loads (ingest a tenant’s data into its own pass, then merge edges), not per-row writes.

The decision that matters most is project-per-request versus cache-the-projection. A tenant subgraph of n nodes and m edges costs roughly

$$ C_{\text{project}} \approx \alpha,(n + m) $$

per projection, while each cached A* run costs about

$$ C_{\text{route}} \approx \beta,(m + n\log n) $$

If a tenant issues q routes between topology changes, projecting per request pays q \cdot C_{\text{project}} of avoidable scan cost; caching pays it once. Cache the projection for stable tenants (high q, infrequent edits) and project on demand only for high-churn tenants where the topology changes faster than it is queried. For very granular tenancy, hierarchical scoping (region_id → org_id → tenant_id) lets you route at the coarsest index tier that still satisfies isolation, avoiding the index fragmentation that thousands of tiny per-tenant partitions create. Connection lifecycle for these concurrent projections follows the Neo4j Python driver connection guide.

Related

• Spatial Security Boundaries — the boundary-aware routing patterns this tenant isolation extends.
• Spatial Indexing Strategies — choosing the index whose composite key carries the tenant seam.
• Graph Query Planner Optimization — making the planner seek the composite index instead of scanning the label.
• Node and Edge Spatial Mapping — where the per-tenant zone/tenant_id tag is first attached to the graph.

This guide is part of Spatial Security Boundaries, within Spatial Graph Database Fundamentals for Python.