In the modern life, SMS (Short Message Service) is one of the most necessary services on mobile devices. Because of its popularity, many companies use SMS as an effective marketing and advertising tool. Also, the popularity gives hackers chances to abuse SMS to cheat mobile users and steal personal information in their mobile phones, for example. In this paper, we propose a method to detect spam SMS on mobile devices and smart phones. Our approach is based on improving a graph-based algorithm and utilizing the KNN Algorithm - one of the simplest and most effective classification algorithms. The experimentation is carried out on SMS message collections and the results ensures the efficiency of the proposed method, with high accuracy and small processing time enough for detecting spam messages directly on mobile phones in real time.