To generate an embedding model for entities in an online system, a first set of partitions is generated. Each partition of the first set of partitions includes a subset of entities of the online system. Each partition of at least a subset of partitions of the first set of partitions is assigned to embedding workers. Each of the embedding worker determines embedding vectors for each entity in the partition assigned to the embedding worker. A second set of partitions is generated. Each partition of at least a subset of partitions of the second set of partitions are assigned to embedding workers. Each embedding worker retrieves embedding vectors for the entities in the partition assigned to embedding worker, and determines updated embedding vectors for each of the entities based on the retrieved embedding vectors and information about interaction between the entities.