A metric between trees I have certain tree structures. I am not an expert in machine learning.

As I would with take KNN, I would calculate distances via metric function and a new data point and the points from the training set. Okay, understood.

Now let's consider the data points aren't tuples but trees. How would one calculate the distances between two graphs.

For instance, I want the following

I have several stereotypical trees like:

|
 - &lt;form class="xyz"&gt;
   |
    - &lt;input type="text"&gt;
    - &lt;button value="Click here"&gt;


between all these node, there could be arbitrary other nodes, the value of the button-node could be different, the type of the input node could be different, even the button-node could be a different node type, like input, the form-node will be surrounded by arbitrary nodes.

How would one calculate such a distance 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.