Although graph databases are conceived schema-less, additional knowledge about the data's structure and/or semantics is beneficial in many graph database management tasks, from efficient storage, over query optimization, up to data integration. Today's commonly used graph data models do not represent primal suspects regarding their lack of schema prior to data population. More than 20 years ago, also semistructured data has been introduced without an a-priori conceptual modeling phase. Neat models, called schema graphs, have been proposed and proven useful, yet heavily relying on the employed data model, which had been rooted labeled graphs. We generalize schema graphs in two respects: (1) Our notions are based on labeled graphs because the root node assumption is invalid in the spirit of modern graph data models. (2) We propose and study modal schema graphs to increase the expressive power of the original model. Modal schema graphs allow for (conditional) structural requirements without an otherwise necessary logical device. Furthermore, we elaborate on the consequences of our expressiveness enhancement with respect to applications and algorithmic complexity.

%8 10/2019