In an example, a plurality of user profiles in a social networking service are accessed. A heterogeneous graph structure having a plurality of nodes connected by edges is generated, each node corresponding to a different entity in the social networking service, each edge representing a co-occurrence of entities represented by nodes on each side of the edge in at least one of the user profiles. Weights are calculated for each edge of the heterogeneous graph structure, the weights being based on co-occurrence counts reflecting a number of user profiles in the plurality of user profiles in which corresponding nodes co-occurred. The heterogeneous graph structure is embedded into a d-dimensional space. A machine-learned model is then used to calculate a similarity score between a first node and second node by computing distance between the first node and the second node in the d¬-dimensional space.