Abstract: In the problem for object tracking, most methods assume brightness constancy or subspace constancy. When both of the foreground and background are changed, the above assumes are violated in practice and the object will be lost. In this paper, the object tracking problem is considered as a transductive learning problem and a robust tracking method is proposed. In order to obtain good result, the object not only fits the object model but also has the same cluster as the previous objects. The previous objects are the labeled data and the candidates are considered as unlabeled data. The cost function is obtained with global and local constraints. Moreover, a novel graph is constructed over the positive samples and candidate patches, which can simultaneously learn the object's global appearance and the local intrinsic geometric structure of all the patches. The solution for minimizing the cost function can be solved by the simple linear algebra with graph Laplacian. The proposed method is tested on different videos, which undergo large pose, expression, illumination, and partial occlusion, and is compared with state-of-the-art algorithms. Experimental results and comparative studies are provided to demonstrate that the proposed method works well with these situations and tracks the object robustly.