Systems, methods, and software described herein provide enhancements for managing permissions in a shared graph. In one implementation, a graph management system identifies a request to classify a first subgraph in the graph for access by a tenant of a plurality of tenants, wherein the request indicates one or more vertex types and/or one or more edge types for the first subgraph. The graph management system further identifies one or more vertices and/or one or more edges in the graph that qualify for the first subgraph based on the indicated one or more vertex types and/or one or more edge types, and allocates permissions to at least one user associated with the tenant to access the first subgraph.