  The knowledge of the label noise transition matrix, characterizing the
probabilities of a training instance being wrongly annotated, is crucial to
designing popular solutions to learning with noisy labels, including loss
correction and loss reweighting approaches. Existing works heavily rely on the
existence of "anchor points" or their approximates, defined as instances that
belong to a particular class almost surely. Nonetheless, finding anchor points
remains a non-trivial task, and the estimation accuracy is also often throttled
by the number of available anchor points. In this paper, we propose an
alternative option to the above task. Our main contribution is the discovery of
an efficient estimation procedure based on a clusterability condition. We prove
that with clusterable representations of features, using up to third-order
consensuses of noisy labels among neighbor representations is sufficient to
estimate a unique transition matrix. Compared with methods using anchor points,
our approach uses substantially more instances and benefits from a much better
sample complexity. We demonstrate the estimation accuracy and advantages of our
estimates using both synthetic noisy labels (on CIFAR-10/100) and real
human-level noisy labels (on Clothing1M and our self-collected human-annotated
CIFAR-10).
