Methods, systems, and apparatus include computer programs encoded on a computer-readable storage medium for labeling user identifiers. A method includes: identifying a set of unlabeled identifiers, wherein an unlabeled identifier has an unknown classification as to a particular class in a multi-class demographic characteristic; determining for each unlabeled identifier a probability as to inclusion in a class of the multi-class demographic characteristic based on known user behavior producing a distribution of probabilities for the unlabeled identifier; for a given unlabeled identifier, adjusting the probability based on a known internet distribution of entities with respect to a given class in the multi-class demographic characteristic and distribution of the probabilities among the unlabeled identifiers; and assigning a label for a particular class in the multi-class demographic characteristic to the unlabeled identifier in accordance with the adjusting.