According to embodiments of the present invention, similarity metrics or measures of similarity may be combined using an adaptive weighting scheme. A subset of entities from a first set of entities that have a known relationship is randomly selected. The subset is combined with a second set of entities that have an unknown relationship to each other and/or to the first set of entities. At least two different measures of similarity (similarity metrics) between the first set and the combined second set (including the subset) is determined for each entity in the second set. For each entity in the second set, the at least two different measures of similarity are compared, and a weight is assigned adaptively to each measure of similarity based on the magnitude of the measure of similarity. The weighted measures of similarity are combined to determine an aggregate adaptively weighted similarity score for each entity.