LoNe Sampler: Graph node embeddings by coordinated local neighborhood sampling

Graphs are ubiquitous representation for structured data. They model naturally occurring relations between objects and, in a sense, generalize sequential data to more complex dependencies. Many algorithms originally designed for learning from sequential data are thus generalized to learning from graphs. Learning continuous vector representations of graph nodes, or node embeddings, have become an integral part of the graph learning toolbox, with applications ranging from link prediction [9] to graph compression [2]. The first algorithm [18] for learning node embeddings generates random walks, starting from each node in the graph, and then feeds the sequences of visited nodes into a word embedding learning algorithm such as word2vec [15]. The approach was extended to a more general setting where random walks can consider different properties of the local neighborhood [9, 26, 27]. An alternative method for training continuous node embeddings is based on matrix factorization of (powers of) the graph adjacency matrix. As an alternative, researchers proposed to use coordinated node sampling for training discrete node embeddings [28, 29]. In this setting, each sample is an independent estimator of the similarity between nodes.