A metric between trees
The distance between objects of complex structure can be tricky. Consider a simpler example, when you got two sequences of words. How do you calculate the distance? In speech recognition, the distance between the groundtruth and recognized transcriptions is calculated as the word-error-rate based on the Levenstein distance between the aligned sentences. 

GRAAL is an extension of the alignment algorithm to the networks. However, it only considers the network topology. You might want to extend the node similarity degree to encounter the type and attributes of the nodes.