We propose a novel self-supervised method for fine-tuning deep face representations called Face-Grouping on Graphs. We apply our method to automatic face grouping, where characters are to be separated based on their identity. To solve this problem, a graph structure with positive and negative edges over a set of face-tracks based on their temporal overlap and similarity constraints is in- duced, which requires no manual labor. We compute feature repre- sentations over sub-sequences of each track (sub-tracks) in order to obtain robust features whilst being able to utilize information contained in face variance. Each sub-track is given the ability to exchange information with adjacent sub-tracks via a typed graph neural network running over the induced graph. This allows us to push each representation in a direction in feature space that groups all representations of the same character together and separates representations of different characters. We show that our method is capable of improving clustering accuracy on popular video face clustering datasets The Big Bang Theory and Buffy the Vampire Slayer by 4.9% and 17.0% respectively compared to baseline performance, and 0.52% respective 5.55% com- pared to state-of-the-art methods. Additionally, we achieve 19.0% absolute increase in B3 F-Score on Harry Potter 1 (ACCIO) over other state-of-the-art unsupervised methods. We provide perfor- mance metrics on all episodes of The Big Bang Theory and Buffy the Vampire Slayer to enable further comparison in the future.