ShortWalk: an approach to network embedding on directed graphs

In network embedding algorithms, long random walks are often used to convert the graph into ‘text’ so that node embeddings can be learned by skip-gram with negative sampling model. However, in a directed graph, long random walks can be trapped or interrupted, leading to low-quality embeddings. This paper proposes a new algorithm, called ShortWalk, to improve the directed graph network embeddings. ShortWalk performs short random walks that restart more frequently thus produces shorter traces. It also gives nodes equal weights by generating the training pairs using pair-wise combination of nodes on the traces. We validate our method on eight directed graphs with different sizes and structures. Experimental results confirm that ShortWalk outperforms DeepWalk consistently on all datasets in node classification and link prediction tasks.