Given an untrimmed video and a query sentence, cross-modal video moment retrieval aims to localize a video moment that best matches the query sentence. Pioneering work typically learns the representations of the textual and visual content separately and then obtains the interactions or alignments between different modalities. However, the performance of existing methods suffer from the insufficient representation learning since they neglect the relation among objects in both the video and the query sentence. Toward this end, we contribute a multi-modal relational graph to capture the interactions among objects from the visual and textual content. Specifically, we first introduce a visual relational graph and a textual relational graph to form relation-aware representations via message propagation. Thereafter, a multi-task pre-training is designed to capture domain-specific knowledge about objects and relations, enhancing the structured visual representation. Finally, the graph matching and boundary regression are employed to perform the cross-modal retrieval. We conduct extensive experiments on two datasets about daily activities and cooking activities, demonstrating significant improvements over state-of-the-art solutions.