DGML

Directed Graph Markup Language (DGML) is an XML-based file format for directed graphs.

[1] Here is what a simple directed graph with three nodes and two links between them looks like which looks like this:

The complete XSD schema for DGML is available at [1].

DGML not only allows describing nodes and links in a graph, but also annotating those nodes and links with any user defined property and/or category.