Enormous hope in the efficacy of vaccines became recently a successful\nreality in the fight against the COVID-19 pandemic. However, vaccine hesitancy,\nfueled by exposure to social media misinformation about COVID-19 vaccines\nbecame a major hurdle. Therefore, it is essential to automatically detect where\nmisinformation about COVID-19 vaccines on social media is spread and what kind\nof misinformation is discussed, such that inoculation interventions can be\ndelivered at the right time and in the right place, in addition to\ninterventions designed to address vaccine hesitancy. This paper is addressing\nthe first step in tackling hesitancy against COVID-19 vaccines, namely the\nautomatic detection of known misinformation about the vaccines on Twitter, the\nsocial media platform that has the highest volume of conversations about\nCOVID-19 and its vaccines. We present CoVaxLies, a new dataset of tweets judged\nrelevant to several misinformation targets about COVID-19 vaccines on which a\nnovel method of detecting misinformation was developed. Our method organizes\nCoVaxLies in a Misinformation Knowledge Graph as it casts misinformation\ndetection as a graph link prediction problem. The misinformation detection\nmethod detailed in this paper takes advantage of the link scoring functions\nprovided by several knowledge embedding methods. The experimental results\ndemonstrate the superiority of this method when compared with\nclassification-based methods, widely used currently.\n