In this paper, we propose a novel object based graph framework for video representation. The proposed framework describes a video as a graph, in which objects are represented by nodes, and their relations between objects are represented by edges. We investigated several spatial and temporal features as the graph node attributes, and different features of spatial-temporal relationship between objects as the edge attributes. To overcome the influence of the camera motion on the detected object motion, a global motion estimation and correction approach is proposed to reveal the true object trajectory. We further propose to evaluate the similarity between two videos by establishing the object correspondence between two object graphs through graph matching. Results show that our method outperforms other video representation frameworks in matching videos with the same semantic content. The proposed framework provides a compact and robust semantic descriptor for a video, which has broad appeal to many video retrieval applications.