Advances in sensor technology have enabled the rapid generation of large volumes of visual data. Visual data representation and extraction of meaningful semantics from raw pixels continue to be major research problems in computer vision. This dissertation focuses on exploring novel techniques for the construction of graph-based models for visual classification and retrieval. The first part of this work will discuss the integration of multiple features for multi-label classification in a graph framework. We show that by construction of a bi-relational graph with heterogeneous nodes and edges, feature complementariness and label correlation can be exploited simultaneously to obtain better classification results. In the second part, we focus on modeling the high-order (among three of more objects) relationship of visual data with a hypergraph representation. This is in contrast with the more conventional graph model where only pairwise connectivity between objects is described. We show that the local grouping information captured by the neighborhood structure in a hypergraph model is beneficial for image retrieval. In the third part, we propose extending the graph-based framework for search in a distributed camera network. We model the cross-camera linkage with a set of linear regression functions based on local motion in each pair of camera regions. Quantitative and qualitative experiments are conducted in a real world distributed camera network to demonstrate the effectiveness of our framework.