In contrast to still image analysis, motion information offers a powerful means to analyze video. In particular, motion trajectories determined from keypoints have become very popular in recent years for a variety of video analysis tasks, including search, retrieval and classification. Additionally, cloud-based analysis of media content has been gaining momentum, so efficient communication of salient video information to perform the necessary analysis of video at the cloud server is needed. In this paper, we propose a novel graph transformation to efficiently represent the keypoint trajectories, motivated by the fact that keypoints are distributed irregularly across the images. Compared to conventional DCT-like transformation, it is easier for graph transform to compact the energy and make the coding efficiently. Experimental results on several popular datasets including Stanford MAR, Hopkin155, KITTI, etc. demonstrate a significant rate saving between 26% and 42% with our proposed trajectory coding approaches relative to a DCT based transformation approach, provided that the coding errors are between 2 pixels to 4 pixels.