Computer implemented methods are disclosed for detecting bot-user groups that send spam email over a web-based email service. Embodiments of the present system employ a two-prong approach to detecting bot-user groups. The first prong employs a historical-based approach for detecting anomalous changes in user account information, such as aggressive bot-user signups. The second prong of the present system entails constructing a large user-user relationship graph, which identifies bot-user sub-graphs through finding tightly connected subgraph components.