A service provider system may implement an enterprise catalog service that manages software products and portfolios of software products on behalf of service provider customer organizations. A graph processing service of the enterprise catalog service may create a graph representation of the enterprise catalog service data, including principals, product listings, portfolios, and constraints (and the relationships between them) that may be used to manage access control, launch contexts, and searches within the enterprise catalog service. A primary (key-value) store may maintain an adjacency list and a secondary index of de-normalized edges. A secondary (document) store may maintain the de-normalized edges. In response to various queries directed to the graph processing service, the service may query the adjacency list or the secondary index. For example, one query may return a list of products that an end user can access, and another may return a count of products within a portfolio.