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.

Subjects: 12. Machine Learning and Discovery; 1.10 Information Retrieval

Submitted: Oct 15, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.