Most existing graph keyword search works assume that the graph data is complete and clean, that is, there are no missing information (such as keywords or edges) and contaminated information (such as keywords) on the graph. However, real-world graphs often suffer from missing or being contaminated, making the keyword search on graphs much more challenging. To solve the problem of keyword search on incomplete or contaminated graphs, we propose a transformation paradigm to convert the keyword search on the incomplete or contaminated graph into the approximate keyword query in an embedding space. Based on this paradigm, we designed a specific framework named DKS. DKS can simultaneously answer the keyword search on incomplete or contaminated graphs within polynomial time and space complexity. In offline, DKS first adopts a GNN-based model to clean the contaminated graph or complete the incomplete graph. And then, by capturing neighborhood keyword distribution and graph structure for each node on the graph, DKS obtains the representation of each node in the embedding space. In online, answers for the keyword search are obtained based on these node representations. We conduct experiments on 5 real-world datasets to evaluate the effectiveness and efficiency of DKS. The experimental results show that DKS can improve the accuracy by up to 2-5 times on contaminated graphs and 1-2.8 times on incomplete graphs compared to the state-of-the-art methods.