
| data set                                                   | #(graphs) #(classes) avg(nodes) max(nodes) avg(edges) max(edges)   |    |      |    |      |    |
|------------------------------------------------------------|--------------------------------------------------------------------|----|------|----|------|----|
| letter                                                     | 750                                                                | 15 | 4.7  | 8  | 3.1  | 6  |
| grec                                                       | 528                                                                | 22 | 11.5 | 24 | 11.9 | 29 |
| ngerprint                                                  | 900                                                                | 3  | 8.3  | 26 | 14.1 | 48 |
| molecules                                                  | 100                                                                | 2  | 24.6 | 40 | 25.2 | 44 |
| Table 1. Summary of main characteristics of the data sets. |                                                                    |    |      |    |      |    |

## 5 Experiments

This section reports the results of running k-means and Elkan's k-means on four graph data sets.

## 5.1 Data.

We selected four data sets described in [22]. The data sets are publicly available at [11]. Each data set is divided into a training, validation, and a test set. In all four cases, we considered data from the test set only. The description of the data sets are mainly excerpts from [22]. Table 1 provides a summary of the main characteristics of the data sets.

Letter Graphs. We consider all 750 graphs from the test data set representing distorted letter drawings from the Roman alphabet that consist of straight lines only (A, E, F, H, I, K, L, M, N, T, V, W, X, Y, Z). The graphs are uniformly distributed over the 15 classes (letters). The letter drawings are obtained by distorting prototype letters at low distortion level. Lines of a letter are represented by edges and ending points of lines by vertices. Each vertex is labeled with a two-dimensional vector giving the position of its end point relative to a reference coordinate system. Edges are labeled with weight 1. Figure 1 shows a prototype letter and distorted version at various distortion levels.

Fig. 1. Example of letter drawings: Prototype of letter A and distorted copies generated

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

![0_image_2.png](0_image_2.png)

by imposing low, medium, and high distortion (from left to right) on prototype A.

GREC Graphs. The GREC data set [4] consists of graphs representing symbols from architectural and electronic drawings. We use all 528 graphs from the test data set uniformly distributed over 22 classes. The images occur at ve dierent distortion levels. In Figure 2 for each distortion level one example of a drawing is given. Depending on the distortion level, either erosion, dilation, or other