The reliance on the internet has made it possible for a number of internet net- works to arise, each with a distinct user base. Intentionally or not, we are all members of a wide range of social networks. Online interpersonal and professional interactions are significantly influenced by social networking. It has a tremendous effect on a global scale and an individual one, affecting a wide range of industries including education, healthcare, entertainment, bank- ing, and telecommunications. As their dependency on social media increases, users are publishing a lot of information about themselves online, leaving their data and themselves vulnerable to the outside world and making them ideal targets for criminals which not only jeopardizes the security of the social net- work’s data but also make way to a slew of other potentially harmful situations, ranging from identity theft to major cybercrime such as hacking, cyber-bullying cyber threats, and even national security threats such as terrorism. This neces- sitated the development of methods and strategies to detect fraudulent users or abnormalities on social media. A graph framework is the most prominent form of mathematical modeling of a social network, hence deducing methods to identify abnormalities from a graph is critical. This paper gives a thorough review of graph-based anomaly detection methods, with a focus on identifying anomalous subgraphs. Since anomaly detection on subgraphs has received lit- tle attention from the researchers’ community in contrast to other anomalous units, we examine the numerous research problems and outstanding questions in this domain.