Politicians lie. Frequently. Depending on the country they are from, politicians may lie more frequently on some topics than others. We develop the novel concept of a tripartite "VAT"graph (Video-Article-Topic) with three types of nodes: videos (with a politician featured in each), news articles that mention the politician, and topics discussed in the videos or articles. We develop several novel types of audio and video deception scores for each audio/video, as well as a topic deception score and an edge deception score for each edge in the graph. Our POLLY (POLitical LYing) system builds upon past work by others to generate predictions for whether a politician is lying or not. We test POLLY on a novel dataset (which will be made publicly available upon publication of this paper) consisting of 146 videos and 6337 news articles involving 73 politicians from 18 countries from all major continents. We show that POLLY achieves AUC and F1 scores over 77%, beating out several baselines. We further show that POLLY is robust to translation errors made by Google Translate.