Summary: Visual database engines are usually based on predefined criteria for retrieving the images in response to a given query. In this paper, we propose a novel approach based on neural networks by which the retrieval criterion is derived on the basis of learning from examples. In particular, the proposed approach uses a graph-based image representation that denotes the relationships among regions in the image and on recursive neural networks which can process directed ordered acyclic graphs. The graph-based representation combines structural and subsymbolic features of the image, while recursive neural networks can discover the optimal representation for searching the image database. A set of preliminary experiments on artificial images clearly indicate that the proposed approach is very promising.