when calculating in and out similarity are equal to nin and nout respectively.

We discuss in-similarity first. Since f is the isomorphism, it maps all the inneighbors of node i to in-neighbors of node f(i). The weights xaf(a) of matching each in-neighbor a of i to in-neighbor f(a) of f(i) are equal to 1 by the inductive hypothesis, thus being maximal. So the matching of each in-neighbor a of i to in-neighbor f(a) of f(i) is optimal. Since there is nin in-neighbors, the weight of the optimal matching of in-neighbors is nin. Analogous reasoning is used to show that the weight of the optimal matching of out-neighbors is equal to nout.

Therefore, both in and out similarity of i and f(i) in step k + 1 are equal to 1 for all i ∈ VA and so, the similarity score x k+1 if(i)
is also equal to 1 for all i ∈ VA.

Since x k if(i) = 1 for all k ≥ 0, and i ∈ VA, the limit xif(i)is also 1 for all i ∈ VA.

In the case GA = GB where f is the trivial automorphism f(i) = i for all i ∈ VA, this theorem implies a simple corollary.

Corollary 1. For any graph GA and each node i ∈ VA*, it holds* xii = 1.

It is easy to check that the proven theorems hold for colored graphs too.

By the above statements, the neighbor matching method fulfills the first two requirements listed in Section 3. The matrix normalization is avoided and it is easy to produce examples of graphs with all the similarity values being 0 or all the similarity values being 1. Similarity of nodes due to lack of in or out neighbors is recognized because in that case in or out similarity will be equal to 1. So, we can conclude that all the requirements listed in Section 3 are met.

## 4.3. Measuring Similarity Of Graphs

The method of neighbor matching can be used to construct a similarity measure of two graphs in the way of Heymans and Singh [2]. When the similarity scores xij for graphs GA and GB are computed, the optimal matching between their nodes can be found by solving the assignment problem between the nodes from VA and VB with the weight of matching two nodes being the similarity of the nodes. Let f and g be enumeration functions for the optimal matching and n = min(|VA|, |VB|). Then, similarity of graphs GA and GB can be computed by

$$s(G_{A},G_{B})={\frac{1}{n}}\sum_{l=1}^{n}x_{f(l)g(l)}.$$
$$(2)$$
xf(l)g(l). (2)
By Theorem 1, the value of the similarity measure s is bounded in the interval
[0, 1]. As a simple corollary of theorem 2, if GA and GB are isomorphic, it holds s(GA, GB) = 1.

Of course, different similarity measures for graphs could be constructed based on the similarities of their nodes. For instance, the sum of weights of the optimal matching could be divided by max(|VA|, |VB|) instead of min(|VA|, |VB|). Such a choice would penalize the difference in size when comparing two graphs. Another interesting choice would be to take the average of all the values in the similarity matrix. In such a case, graphs with greater number of automorphisms would be