This talk presents the Online Manifold Tracking method and demonstrate its application to online face recognition with minimal feedback. In contrast to the current methods for face recognition that build on sophisticated features, our approach is based on an adaptively bui It similarity graph of unlabeled samples. We focus on the two problems that arise in practical scenarios and implementations. First, when data arrive in a stream, we need to deal the problems of computation and storage. We therefore describe a fast approximate online algorithm that solves for the harmonic sol uti on on an approximate graph. We show, that good behavior can be achieved by collapsing nearby points into a set of local representative points that minimize distortion. Second, compared to the benchmark datasets, real-world data involve many outliers. To address them, we show how to regularize the harmonic solution and I imit generalization so that we do not extrapolate the labels to the outliers.