The update rule for similarity of nodes is then given in terms of similarities of the edges

$$x_{i j}^{k+1}\leftarrow\sum_{t(u)=i,t(v)=j}y_{u v}^{k}+\sum_{s(u)=i,s(v)=j}y_{u v}^{k}.$$

Matrix normalization of the similarity scores is applied in this approach too.

The approach by Heymans and Singh [2] is somewhat different and more complex than the described methods, and we only briefly mention its most important aspects. In order to estimate similarity in each iteration, similarity terms and dissimilarity terms are calculated, based on the similarity scores of the previous iteration. These terms average the similarities of the in-neighbor and similarities of the out-neighbors. Similarity terms are calculated both for the original graphs and their complements. Dissimilarity terms are calculated using one graph and the complement of the other, and vice versa. Dissimilarity terms are subtracted from similarity terms to obtain new estimate of similarity scores. The matrix normalization is performed after each iteration.

There are approaches that are designed for measuring similarity between the nodes of the same graph [11, 6]. We don't discuss these methods as they are less general than the former ones.

The described methods lack some desirable and natural properties. Of course, not all the method lack all the listed properties.

If the graphs is compared to itself, each node should be most similar to itself.

This is a natural property, expected for all similarity measures. Nevertheless, for all mentioned methods it is easy to construct graphs for which there is a node which is more similar to some other node of the same graph than to itself. This can easily occur, for instance, in methods where the update rule consists of simple summation of similarities of neighbor nodes. This results in nodes of higher degree having more terms in the summation and hence, higher similarity with other nodes [12].

Similarity scores should have a fixed range with similarity of a node to itself always taking the maximal value. It is customary for similarity measure in general
(not only for similarity measures for graphs) to have a fixed range (e.g., from 0 to 1 or from -1 to 1). Without the loss of generality, we will assume the range [0, 1]. Also, similarity of each object to itself should be 1. These properties facilitate intuitive understanding of similarity scores. Well-known examples of measures for which these requirements are fulfilled are cosine, correlation coefficient, Jaccard coefficient, etc. However, the mentioned methods for calculating graph node similarity lack this property. When the similarity scores are calculated for the nodes of the same graph, the similarity score of one node compared to itself can be different from the similarity score of some other node compared to itself. So, one node can be more similar to itself than the other.

It is reasonable to make even stricter requirement: if two graphs GA and GB are isomorphic, with isomorphism f : VA → VB, the similarity score xif(i)
should be 1 for all i ∈ VA.