Graph embedding learns low-dimensional representations for nodes in a graph
and effectively preserves the graph structure. Recently, a significant amount
of progress has been made toward this emerging research area. However, there
are several fundamental problems that remain open. First, existing methods fail
to preserve the out-degree distributions on directed graphs. Second, many
existing methods employ random walk based proximities and thus suffer from
conflicting optimization goals on undirected graphs. Finally, existing
factorization methods are unable to achieve scalability and non-linearity
simultaneously.
This paper presents an in-depth study on graph embedding techniques on both
directed and undirected graphs. We analyze the fundamental reasons that lead to
the distortion of out-degree distributions and to the conflicting optimization
goals. We propose {\em transpose proximity}, a unified approach that solves
both problems. Based on the concept of transpose proximity, we design \strap, a
factorization based graph embedding algorithm that achieves scalability and
non-linearity simultaneously. \strap makes use of the {\em backward push}
algorithm to efficiently compute the sparse {\em Personalized PageRank (PPR)}
as its transpose proximities. By imposing the sparsity constraint, we are able
to apply non-linear operations to the proximity matrix and perform efficient
matrix factorization to derive the embedding vectors. Finally, we present an
extensive experimental study that evaluates the effectiveness of various graph
embedding algorithms, and we show that \strap outperforms the state-of-the-art
methods in terms of effectiveness and scalability.

本文研究了在有向和无向图上进行图嵌入技术的基础方法和存在的问题，提出了一个新的方法叫做转置接近度，以解决现有方法无法保持有向图外度分布和无向图优化目标冲突的问题，并且展示了该方法在各种图嵌入算法中的高效性和优越性。