The present invention is a complete end-to-end video face recognition system. The invention performs a track-by-track labeling of all tracks within a video. A novel algorithm Mean Sequence SRC (MSSRC) is applied to a face track to perform video face recognition using a joint optimization to leverage all of the available video data and the knowledge that the face track frames belong to the same individual. Additionally the system constructs a probabilistic affinity graph combining appearance and co-occurrence similarities to model the relationship between face tracks in a video. Finally, using this relationship graph, random walk analysis is employed to propagate strong class predictions among similar face tracks, while dampening weak predictions.