A synchronization system is described herein that synchronizes two environments by correctly matching identity objects in a source environment with related objects in a target environment. In addition to matching identities based on primitive attributes, the system matches identities across multiple heterogeneous environments based on their relative positions in an identity graph. The system builds the identity graph by first matching some identity objects based on primitive attribute value comparisons. The system fills in the remainder of the identity graph by comparing references to/from the matched identity objects. The combination of attribute value comparisons and comparing references enables identity-aware applications to complete a single identity graph, determine the equivalency of identities in this graph, and apply policy based on this new relationship.