Similarity scores should be meaningful in absolute terms. Due to the normalization of the similarity matrix, one similarity score xij can change only if other similarity scores change accordingly. This makes additional interdependence between similarity scores that is not a result of the topology of two graphs alone.

It actually means that similarity scores can only reflect similarity of nodes of two graphs relative to each other. We can't conclude if two nodes are similar, but only if one pair of nodes is more similar than some other pair of nodes.

Consider the following special case. Suppose that all the nodes of one graph are equally similar to all the nodes of the second graph. In a normalized matrix it is impossible that all the similarity scores are equal to 0, or that all the similarity scores are equal to 1. Because of the normalization constraint, we can't differentiate between all possible levels of similarity. All we can say is that the nodes of one graph are equally similar to all the nodes of the second graph, but not how much.

It would be good if similarity scores don't represent relative magnitudes of similarities of pairs of nodes, but in a way "absolute" magnitudes with possibility of all scores having 0 or the maximal value.

The lack of this property, also makes it harder to use similarity scores of the nodes to construct the similarity measure of whole graphs. Heymans and Singh [2] were able to achieve this because they use similarity scores that can be negative (as the consequence of subtracting dissimilarity scores that they use),
but as discussed in the previous special case, it would not be possible with other methods.

If two nodes don't have ingoing or outgoing edges, they should be considered similar. To our knowledge, this property is present only in the method of Heymans and Singh. We believe that concepts of in-similarity and out-similarity should be recognized. Moreover, in-similarity and out-similarity should be 1 if there are no in-neighbors or out-neighbors.

## 4. Method Of Neighbor Matching

In this section we refine the notion of node similarity. Based on that refinement, we describe a new method (we call this method the method of neighbor matching) for measuring similarity of nodes of graphs and prove its properties.

Then, we define a measure of similarity of whole graphs based on the similarities of their nodes.

## 4.1. Notion Of Similarity Of Graph Nodes

In the existing methods, the calculation of similarity xij is based on adding or averaging the similarities of all the neighbors of node i ∈ VA to all the neighbors of node j ∈ VB. We propose a modification to that approach, illustrated by the following intuition. We perceive our two hands to be very similar, but not because all the fingers of the left hand are very similar to all the fingers of the right hand, but rather because of the property that to each finger of the