In a graph database, entities are presented as nodes and relationships between those entities are presented as edges in a view of the relational graph maintained by the graph database. The relational graph may be periodically queried by users via graph queries to learn about the relationships between entities and to discover related entities. For example, a user may issue a graph query to find friends or contacts within a social network, the documents that a given user has interacted with, the users that a given document has been accessed by, the entities that satisfy various search criteria, etc. The graph query produces a subgraph of the queried relational graph that satisfies the query, which may be further analyzed by the user. Graph queries, however, may span graph entities that the querying user lack permission to access as nodes, or as properties/relationships thereof. Even if these entities are scrubbed from the results, the fact that other entities were discovered via the non-permitted or forbidden graph entities can expose information to the querying user, and requires the expenditure of additional computing resources.