structure matching [5], construction of phylogenetic trees [2], analysis of social networks [6], etc.

In this paper, we try to identify desirable properties not present in the existing methods for measuring similarities of graph nodes. We propose a refinement of the notion of similarity of two nodes which leads to a new method for measuring similarities of graph nodes and similarities of graphs. We prove convergence of the proposed method and show that it has some additional desirable properties that, to our knowledge, the existing methods lack.

We implemented the proposed method and evaluated it on two problems in order to illustrate that our method can capture the notion of similarity useful in practical problems. The first test problem was finding a subgraph of a graph that is isomorphic to some other given graph. The second test problem was the classification of Boolean formulae based on their underlying graph structure.

The rest of the paper is organized as follows. In Section 2, we present the preliminaries used in this paper. Existing methods are described and analyzed in Section 3. In Section 4 we present our new method - the method of neighbor matching and prove its properties. Results of experimental evaluation and comparison to other methods are given in Section 5. In Section 6, we draw final conclusions and give some directions of the future work.

## 2. Preliminaries

A directed graph G = (*V, E*) is defined by its set of nodes V and its set of edges E. There is an edge between two nodes i and j if (*i, j*) ∈ E. For the edge e = (*i, j*), the *source node* is the node i, and the *terminating node* is the node j. We denote them respectively with s(e) and t(e). We say that the node i is an *in-neighbor* of node j and that node j is an *out-neighbor* of the node i if (*i, j*) ∈ E. An *in-degree* id(i) of the node i is the number of in-neighbors of i, and an *out-degree* od(i) of the node i is the number of out-neighbors of i. A
degree d(i) of the node i is the sum of in-degree and out-degree of i. Two graphs are *isomorphic* if there exists a bijection f : VA → VB, such that (*i, j*) ∈ EA if and only if (f(i), f(j)) ∈ EB. An isomorphism of a graph G to itself is called automorphism. A *colored graph* is a graph in which each node is assigned a color. For colored graphs, the definition of isomorphism additionally requests that nodes i and f(i) have the same color. A random Erd˝os–R´enyi graph Gn,p is a graph with n nodes in which each two nodes share an edge with probability p [7]. A graph GB is an *induced subgraph* of a graph GA if VB ⊆ VA and for each pair of nodes *i, j* ∈ VB it holds (*i, j*) ∈ EB if and only if (*i, j*) ∈ EA.

The *similarity measure* s is a function s : D1 × D2 → R where D1 and D2 are possibly equal sets of objects. A higher value of similarity measure should imply a higher similarity in some intuitive sense. Choice of a similarity measure to be used in some context is often guided by its usefulness in practice.

Similarity measure over the nodes of two graphs can be represented by a similarity matrix X = [xij ] of dimension |VA*| × |*VB| with the element xij denoting a similarity of the nodes i ∈ VA and j ∈ VB.