This research focuses on introducing new localized descriptions for segmentation, classification, and visual search. 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 descriptors. 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 searching through image databases for smaller objects/regions of interest that are not currently otherwise possible.

Further, such a representation also enables image search for specific spatial configurations of objects. The goal is to search the database for images that contain similar objects (image-patches) with a given spatial configuration, size and position. Our representations are robust to segmentation variations, and a sub-graph matching method is used to compare the query with the database items. In the third part of this thesis, we present a weakly-supervised approach to semantic segmentation. The goal is to assign pixel-level labels given only partial information, for example, image-level labels. This is an important problem in many application scenarios where it is difficult to get accurate segmentation or not feasible to obtain detailed annotations. We start with an initial coarse segmentation, followed by a spectral clustering approach that groups related image parts into communities.

A community-driven graph is then constructed that captures spatial and feature relationships between communities while a label graph captures correlations between image labels. Mapping the image level labels to appropriate communities is formulated as a convex optimization problem. Lastly, we present a novel framework for querying multi-modal data from a heterogeneous database containing images, textual tags, and GPS coordinates. We construct a bi-layer graph structure using localized image-parts and associated GPS locations and textual tags from the database. The proposed network model enables us to use flexible multi-modal queries on the database. In all the above cases, extensive experimental results show that the proposed methods outperform current state-of-the-art.