This paper presents a novel localized visual image feature motivated by image segmentation. The proposed feature embeds relative spatial information by learning different image parts while having a compact representation. First, an attributed graph representation of an image is created based on segmentation and localized image features. Subsequently, communities of image regions are discovered based on their spatial and visual characteristics over all images. The community detection problem is modeled as a spectral graph partitioning problem. This results in finding meaningful image part groupings. A histogram of communities forms a robust and spatially localized representation for each image in the database. Such a region-based representation enables one to search for queries that might not have been possible with global image representations. We apply this representation to image classification and search and retrieval tasks. Extensive experiments on three challenging datasets, including the large-scale ImageNet dataset, demonstrate that the proposed representation achieves promising results compared to the current state-of-the-art methods.