1. A computer-implemented method, comprising: receiving a query on graph data, where the query includes one or more selection criteria; expressing the query selection criteria in a tree representation of an abstract syntactic structure using metadata; analyzing the tree representation of the query selection criteria to collect properties and any terms or variables in subject or object positions with respect to the collected properties; accessing a security policy comprising data access constraints expressed as match pattern and apply pattern pairs to identify a match pattern corresponding to a collected property, term, or variable in the query selection criteria, where the match pattern binds one or more variables to corresponding data instances accessed in the query; selecting an apply pattern that is associated with the identified match pattern; rewriting the query to include security conditions specified in the apply pattern; and executing the rewritten query on the graph data to return data according to the security policy such that data instances returned by the rewritten query satisfy the data access constraints specified by the match pattern and apply pattern.