Due to representative power of graphs, graph-based object recognition has received a great deal of research attention in literature. Given an object represented as a graph, performing graph matching with each member of the database in order to locate the graph which most resembles the query is inefficient especially when the size of the database is large. In this paper we propose an algorithm which represents the graphs belonging to a particular set as points through graph embedding and operates in the vector space to compute the representative of the set. We use the k-means clustering algorithm to learn centroids forming the representatives. Once the representative of each set is obtained, we embed the query into the vector space and compute the matching in this space. The query is classified into the most similar representative of a set. This way, we are able to overcome the complexity of graph matching and still perform the classification for the query effectively. Experimental evaluation of the proposed work demonstrates the efficiency, effectiveness, and stability of the overall approach. © 2013 Springer-Verlag.