Computational Information Geometry Wonderland

Structural pattern matching has gained a lot of attention the past decades by considering structures on features. Matching structural features thus relies on underlying graph structures.
A simple metric on graphs P and Q can be defined by

where mcs denotes the maximum common subgraph.

This bounded distance satisfies the triangle inequality property (non-trivial proof, see ref below) but is NP-hard to compute.
Nevertheless it has been used successfully in applications.

@article{graphmetric-1998,
 author = {Bunke, Horst and Shearer, Kim},
 title = {A graph distance metric based on the maximal common subgraph},
 journal = {Pattern Recogn. Lett.},
 volume = {19},
 number = {3-4},
 year = {1998},
 issn = {0167-8655},
 pages = {255--259},
 doi = {http://dx.doi.org/10.1016/S0167-8655(97)00179-7},
 publisher = {Elsevier Science Inc.},
 address = {New York, NY, USA}
 }