Machine learning techniques are used in combination with graph data structures to perform automated classification of accounts. Graphs may be constructed using a seed node and then expanded outward to second-degree nodes and third-degree nodes that are connected to a seed user account node via direct interaction between the accounts. Characterization information regarding the interaction between accounts can be stored in the graph (e.g., quantity of interactions, types of interactions) as well as other metrics and metadata. A classifier, using random forest or another technique, may be trained using a number of different graphs that can then be used to reach a determination as to whether a user account falls into one particular category or another. These techniques can identify accounts that may be violating terms of service, committing a security violation, and/or performing illegal actions in a way that is not ascertainable from human analysis.