Semantic relatedness or semantic similarity between words is an important basic issue for many Natural Language Processing (NLP) applications, such as sentence retrieval, word sense disambiguation, question answering, and so on. This research issue attracts many researchers, but most of studies focus on improving the effectiveness, i.e., applying kinds of techniques to improve precision (effectiveness) but not efficiency. To tackle the problem, we propose to address the efficiency issue, that how to efficiently find top-k most semantic similar words to the query for a given dataset. This issue is very important for real applications especially for current big data. Efficient graph-based approaches on searching top-k semantic similar words are proposed in this paper. The results demonstrate that the proposed model can perform significantly better than baseline method.