Learning Graph Node Embeddings by Smooth Pair Sampling

Representation learning from graphs has been an active research area over the past decade. DeepWalk [24], one of the pioneering approaches in this field, learns node embeddings by generating random walks on the graph. A standard and highly efficient method for optimizing the embedding objective is to train a binary classification model that distinguishes between positive and negative node pairs, known as the negative sampling approach. Positive pairs are generated by applying the skip-gram model [21] to the node sequences and represent nodes whose embeddings should be similar, in contrast to negative pairs. Many works have since extended the original DeepWalk algorithm in three main directions: i) presenting different (random) walk strategies for traversing the graph and generating node sequences [1, 9, 10, 25, 29, 31, 39, 41], ii) designing new embedding learning models [1, 2, 11, 12, 26], and iii) designing new techniques for negative pair sampling [3, 16, 19, 35]. Inspired by observations on real graphs, we take a different approach and propose a general regularization technique that adjusts the frequency distribution of positive node pairs. In the standard negative sampling setting, when a positive pair u, v is generated, we also sample k 1 negative pairs u, x, where the node x is selected at random from some distribution on the graph nodes.