morphological operations are applied. The result is thinned to obtain lines of one pixel width. Finally, graphs are extracted from the resulting denoised images by tracing the lines from end to end and detecting intersections as well as corners. Ending points, corners, intersections and circles are represented by vertices and labeled with a two-dimensional attribute giving their position. The vertices are connected by undirected edges which are labeled as line or arc. An additional attribute species the angle with respect to the horizontal direction or the diameter in case of arcs.

Fig. 2. GREC symbols: A sample image of each distortion level

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

Fingerprint Graphs. We consider a subset of 900 graphs from the test data set representing ngerprint images of the NIST-4 database [26]. The graphs are uniformly distributed over three classes left, right, and whorl. A fourth class (arch) is excluded in order to keep the data set balanced. Fingerprint images are converted into graphs by ltering the images and extracting regions that are relevant
[21]. Relevant regions are binarized and a noise removal and thinning procedure is applied. This results in a skeletonized representation of the extracted regions.

Ending points and bifurcation points of the skeletonized regions are represented by vertices. Additional vertices are inserted in regular intervals between ending points and bifurcation points. Finally, undirected edges are inserted to link vertices that are directly connected through a ridge in the skeleton. Each vertex is labeled with a two-dimensional attribute giving its position. Edges are attributed with an angle denoting the orientation of the edge with respect to the horizontal direction. Figure 3 shows ngerprints of each class.

Fig. 3. Fingerprints: (a) Left (b) Right (c) Arch (d) Whorl. Fingerprints of class arch

![0_image_1.png](0_image_1.png) are not considered.

Molecules. The mutagenicity data set consists of chemical molecules from two classes (mutagen, non-mutagen). The data set was originally compiled by [17]
and reprocessed by [22]. We consider a subset of 100 molecules from the test data