Over the last decade, the growing popularity of Online Social Networks has attracted a pervasive presence of social spammers. While this presence has started with spam advertising and common scams, the recent years have seen this escalate to the far more concerning mass manipulation attempts. This targeted and largely automated abuse of social platforms is risking the credibility and usefulness of the information disseminated on these platforms. The social spam detection problem has been traditionally modeled as a supervised problem where the goal is to classify individual social accounts. This common choice is problematic for two reasons. First, the dynamic and adversarial nature of social spam makes the performance achieved by features-based supervised systems hard to maintain. Second, features-based modeling of individual social accounts discards the collusive context in which social attacks are increasingly undertaken. Acting synchronously allows spammers to gain greater exposure and efficiently disseminate their content. Thus, even when spammers change their characteristics, they continue to act collusively, inevitably creating links between collusive spammingaccounts. This constitutes an unsupervised signal that is relatively easy to maintain and hard to evade. It is therefore beneficial to find a suitable similarity measure that captures this collusive behavior. Accordingly, we propose in this work to cast the social spam detection problem in probabilistic terms using the undirected graphical models framework. Instead of the individual detection paradigm that is commonly used in the literature, we aim to model the classi_cation task as one of joint inference. In this context, accounts are represented as random variables and the dependency between these variables is encoded in a graphical structure. This probabilistic setting allows to model theuncertainty that is inherent to classification systems while simultaneously leveraging the dependency that _ows from the similarity induced by the spammers collusive behavior. We propose two graphical models: the Markov Random Field with inference performed via Loopy Belief Propagation, and the Conditional Random Field with a setting that is more adapted to the classification problem, namely by adopting the Tree Reweighted message passing algorithm for inference and a loss that minimizes theempirical risk. Both models, evaluated on Twitter, demonstrate an increase in classification performance compared to state-of-the-art supervised classifiers. Compared to the Markov Random Field, the proposed Conditional Random Field framework offers a better classification performance and a higher robustness to changes in spammers input distribution.