  Graph embedding maps a graph into a convenient vector-space representation
for graph analysis and machine learning applications. Many graph embedding
methods hinge on a sampling of context nodes based on random walks. However,
random walks can be a biased sampler due to the structural properties of
graphs. Most notably, random walks are biased by the degree of each node, where
a node is sampled proportionally to its degree. The implication of such biases
has not been clear, particularly in the context of graph representation
learning. Here, we investigate the impact of the random walks' bias on graph
embedding and propose residual2vec, a general graph embedding method that can
debias various structural biases in graphs by using random graphs. We
demonstrate that this debiasing not only improves link prediction and
clustering performance but also allows us to explicitly model salient
structural properties in graph embedding.
