We performed the classification of Boolean formulae using our similarity measure for graphs on their graph representation. We used 149 structured instances from SAT competition 2002 benchmark set (which is one of the standard benchmarks sets for SAT).4 Most of the formulae had up to 1000 nodes, but 25 of them were larger (up to 5280 nodes). Formulae were grouped in 9 classes corresponding to the problems the formulae originate from. Graphs corresponding to the formulae had from 122 to 5280 nodes. Differences in graph size of order of magnitude were present within each class too. The classification was performed using the k nearest neighbors algorithm with leave one out evaluation procedure - for each formula F, its graph similarity to the remaining formulae was computed, and the set N(k) of k most similar formulae was determined.

Formula F is classified to the class that has the most representatives in the set N(k). For the evaluation of the classification performance, we measured the accuracy of the classification - number of correctly classified formulae divided by the total number of formulae being classified.

The best accuracy of the classification was 93% for k = 7. The best accuracy for a domain specific approach from [14] on the same set is 96% for k = 1. Only slightly more accurate, the domain specific approach is based on long lasting research in the field [15, 16, 14]. It is interesting to see that the general approach, not designed specifically for this purpose, can achieve a very high accuracy. Most importantly, we confirmed that our similarity measure can capture a meaningful similarity in a real world problem.

A very interesting remark concerning this experiment is that the difference in size of the compared graphs did not influence the adequateness of the similarity measure. This kind of robustness might be interesting for practical applications.

## 6. Conclusions And Future Work

We proposed a refined notion of similarity of graph nodes, and based on that refinement we developed a new iterative method for measuring similarity of nodes of two graphs. This method was extended to a method for measuring similarity of whole graphs. We proved the convergence of the method and showed that it has several desirable properties (listed in Section 3) that, to our knowledge, the existing methods lack.

We implemented the method and evaluated the implementation on two test problems. On one test problem (the isomorphic subgraph matching problem),
we confirmed that the proposed method performs better than other methods.

On the second one, it is confirmed that the graph similarity measure is able to capture a meaningful similarity in a real world problem. The method showed to be robust to differences in graph size. The performance on dense graphs can be significantly boosted by measuring the similarity of nodes of complement graphs.

This modification can significantly reduce the running time of the method.

4The benchmarks are available from http://www.satcompetition.org.