  Graph embedding methods represent nodes in a continuous vector space,
preserving information from the graph (e.g. by sampling random walks). There
are many hyper-parameters to these methods (such as random walk length) which
have to be manually tuned for every graph. In this paper, we replace random
walk hyper-parameters with trainable parameters that we automatically learn via
backpropagation. In particular, we learn a novel attention model on the power
series of the transition matrix, which guides the random walk to optimize an
upstream objective. Unlike previous approaches to attention models, the method
that we propose utilizes attention parameters exclusively on the data (e.g. on
the random walk), and not used by the model for inference. We experiment on
link prediction tasks, as we aim to produce embeddings that best-preserve the
graph structure, generalizing to unseen information. We improve
state-of-the-art on a comprehensive suite of real world datasets including
social, collaboration, and biological networks. Adding attention to random
walks can reduce the error by 20% to 45% on datasets we attempted. Further, our
learned attention parameters are different for every graph, and our
automatically-found values agree with the optimal choice of hyper-parameter if
we manually tune existing methods.
