  We present an end-to-end system for detecting and clustering faces by
identity in full-length movies. Unlike works that start with a predefined set
of detected faces, we consider the end-to-end problem of detection and
clustering together. We make three separate contributions. First, we combine a
state-of-the-art face detector with a generic tracker to extract high quality
face tracklets. We then introduce a novel clustering method, motivated by the
classic graph theory results of Erd\H{o}s and R\'enyi. It is based on the
observations that large clusters can be fully connected by joining just a small
fraction of their point pairs, while just a single connection between two
different people can lead to poor clustering results. This suggests clustering
using a verification system with very few false positives but perhaps moderate
recall. We introduce a novel verification method, rank-1 counts verification,
that has this property, and use it in a link-based clustering scheme. Finally,
we define a novel end-to-end detection and clustering evaluation metric
allowing us to assess the accuracy of the entire end-to-end system. We present
state-of-the-art results on multiple video data sets and also on standard face
databases.
