The generalization capability is usually recognized as the most desired feature of data-driven learning systems, such as classifiers. However, in many practical applications obtaining human-understandable information, relevant to the problem at hand, from the classidication model can be equally important. In this paper we propose a classification system able to fulfill these two requirements simultaneously for a generic image classification task. As a first preprocessing step, an input image to the classifier is represented by a labeled graph, relying on a segmentation algorithm. The graph is conceived to represent visual and topological information of the relevant segments of the image. Then, the graph is classified by a suited inductive inference engine. In the learning procedure all the training set images are represented by graphs, feeding a state-of-the-art classification system working on structured domains. The synthesis procedure consists in extracting characterizing subgraphs from the training set, which are used to embed the graphs into a vector space, enabling thus the applicability of well-known classifiers for feature-based patterns. Such characterizing subgraphs, which are derived in an unsupervised fashion, are interpretable by suitable field experts, allowing a semantic analysis of the discovered classification rules for the given problem at hand. The system is optimized with a genetic algorithm, which tunes the system parameters according to a cross-validation scheme. We show the validity of the approach by performing experiments considering some image classification problems derived from an on-line repository.