Facing scalability: Naming faces in an online social network

Automatically naming faces in online social networks enables us to search for photos and build user face models. We consider two common weakly supervised settings where: (1) users are linked to photos, not to faces and (2) photos are not labeled but part of a user's album. The focus is on algorithms that scale up to an entire online social network. We extensively evaluate different graph-based strategies to label faces in both settings and consider dependencies. We achieve results on a par with a recent multi-person approach, but with 60 times less computation time on a set of 300K weakly labeled faces and 1.4 M faces in user albums. A subset of the faces can be labeled with a speed-up of over three orders of magnitude.