Directed Graph Embedding

Mo Chen, Qiong Yang, Xiaoou Tang

In this paper, we propose the Directed Graph Em-bedding (DGE) method that embeds vertices on a directed graph into a vector space by considering the link structure of graphs. The basic idea is to preserve the locality property of vertices on a di-rected graph in the embedded space. We use the transition probability together with the stationary distribution of Markov random walks to measure such locality property. It turns out that by exploring the directed links of the graph using random walks, we can get an optimal embedding on the vector space that preserves the local affinity which is in-herent in the directed graph. Experiments on both synthetic data and real-world Web page data are considered. The application of our method to Web page classification problems gets a significant im-provement comparing with state-of-art methods.