Automating the process of annotation of images is a crucial step towards efficient and effective management of increasingly high volume of content. It is proposed to extract shape context features to reduce computational expense. A graph-based approach for Automatic Image Annotation (AIA) is proposed which models both feature similarities and semantic relations in a single graph. This approach models the relationship between the images and words by an undirected graph. Semantic information is extracted from paired nodes. The quality of annotation is enhanced by introducing graph link weighting techniques. The proposed method is scalable and achieves fast solution by using incremental fast random walk with restart algorithm (IFRWR), without apparently affecting the accuracy of image annotation, whereas the present approaches suffer from scalability issue.