Investigating Extensions to Random Walk Based Graph Embedding
  Graph embedding has recently gained momentum in the research community, in
particular after the introduction of random walk and neural network based
approaches. However, most of the embedding approaches focus on representing the
local neighborhood of nodes and fail to capture the global graph structure,
i.e. to retain the relations to distant nodes. To counter that problem, we
propose a novel extension to random walk based graph embedding, which removes a
percentage of least frequent nodes from the walks at different levels. By this
removal, we simulate farther distant nodes to reside in the close neighborhood
of a node and hence explicitly represent their connection. Besides the common
evaluation tasks for graph embeddings, such as node classification and link
prediction, we evaluate and compare our approach against related methods on
shortest path approximation. The results indicate, that extensions to random
walk based methods (including our own) improve the predictive performance only
slightly - if at all.
