  In the last two decades we are witnessing a huge increase of valuable big
data structured in the form of graphs or networks. To apply traditional machine
learning and data analytic techniques to such data it is necessary to transform
graphs into vector-based representations that preserve the most essential
structural properties of graphs. For this purpose, a large number of graph
embedding methods have been proposed in the literature. Most of them produce
general-purpose embeddings suitable for a variety of applications such as node
clustering, node classification, graph visualisation and link prediction. In
this paper, we propose two novel graph embedding algorithms based on random
walks that are specifically designed for the node classification problem.
Random walk sampling strategies of the proposed algorithms have been designed
to pay special attention to hubs -- high-degree nodes that have the most
critical role for the overall connectedness in large-scale graphs. The proposed
methods are experimentally evaluated by analyzing the classification
performance of three classification algorithms trained on embeddings of
real-world networks. The obtained results indicate that our methods
considerably improve the predictive power of examined classifiers compared to
currently the most popular random walk method for generating general-purpose
graph embeddings (node2vec).
