For graphs and metadata, consider RDF

In a totally different direction Some kinds of information don't fit well into hierarchical trees. As XML is all about hierarchical tree structures, this should put up a warning flag that maybe XML isn't the right way to go.
RDF is about directed graphs and annotation RDF is very different from XML, expressing annotation and metadata rather than containment relationships. That makes it perfect for adding information about existing resources, as well as for representing structures that are more intricate than trees.
RDF uses an XML syntax, but RDF offers so much flexibility in its XML syntax that it can be very difficult to process RDF as XML. (RELAX NG schemas can describe; not much else is capable.) There are ways to process XML as RDF, but they generally depend on the XML following a tight set of rules.