Micro-blog, as one of the most popular Online Social Networks (OSNs), has attracted more and more spammers. The spammers can achieve their illegal benefits by sending spam, spreading rumors, or performing other illicit activities. Most of the existing methods utilize machine learning techniques to detect Micro-blog spammer, but the machine learning features ever used are vulnerable to be evaded by spammers’ hidden policy. In this paper, we proposed several new detection features based on the user’s relationship graph. Spammers can change their own blogs and behavior to escape detecting, but it is difficult to change their position in the micro-blog network. Thus, the relationship graph will be more accurate in detecting spammers, compared with the user’s content features and behavior features. The network datasets were crawled from the Sina platform, and then extracted the user’s attribute features, time features and relationship graph features. Finally, the improved Naive Bayes classification algorithm was used to detect the micro-blog spammers. The simulation results show that the accuracy and recall of this method up to 90%. The detecting precision with new features is significantly higher the existing method, and it proved the validity of relationship graph features in spammers detecting.