An approach is described for automatically tagging a single image or multiple images. The approach, in one example embodiment, is based on a graph-based framework that exploits both visual similarity between images and tag correlation within individual images. The problem is formulated in the context of semi-supervised learning, where a graph modeled as a Gaussian Markov Random Field (MRF) is solved by minimizing an objective function (the image tag score function) using an iterative approach. The iterative approach, in one embodiment, comprises: (1) fixing tags and propagating image tag likelihood values from labeled images to unlabeled images, and (2) fixing images and propagating image tag likelihood based on tag correlation.