This paper presents a graph-theoretic approach for region-based image retrieval. When dealing with image matching problem, we propose converting the region correspondence estimation into an attributed graph matching problem and measuring the image similarity in terms of both the region correspondence and the low-level features. In addition, during the relevance feedback, we propose using a maximum likelihood method to re-estimate region features and region importance while retaining its inherent spatial organization. Experimental results show that the proposed graph-theoretic matching criterion outperforms other existing methods which include no spatial information in the matching criterion. The experiments also show that the performance can be further improved with our proposed relevance feedback scheme.