First-Class Metadata in Property Graphs

We address the recurring need to represent and query metadata about individual graph assertions in property graphs, including provenance, temporal qualifiers, confidence, and audit information. We propose a stepwise generalization of labelled property graphs that (i) treats labels as properties without values (GPG), (ii) allows edges to serve as endpoints (GPG$_e$), (iii) gives property occurrences identity by modeling them as edges to value objects (GPG$_p$), and (iv) exposes components of structured values via dedicated component edges (GPG$_c$). This progression makes metadata uniformly attachable to relationship facts, property occurrences, and nested components of structured values. We also provide an empirical study in Neo4j that quantifies the storage, loading, and query-time overhead induced by increasingly expressive metadata representations.