Systems, methods, and software described herein provide improvements to graph indexing. In one implementation, a graph management system may identify an event to generate a new vertex type to index a graph based on an attribute type in one or more vertices of the graph. In response to the event, the graph management system may generate one or more new indexing vertices that correspond to the new vertex type and may connect each of the one or more vertices to the one or more new indexing vertices based on an attribute in the vertex.