From embeddings to labelled maps