Directed Graph Embedding: an Algorithm based on Continuous Limits of Laplacian-type Operators

Dominique C. Perrault-joncas, Marina Meila

Advances in Neural Information Processing Systems 24 (NIPS 2011)

This paper considers the problem of embedding directed graphs in Euclidean space while retaining directional information. We model the observed graph as a sample from a manifold endowed with a vector field, and we design an algo- rithm that separates and recovers the features of this process: the geometry of the manifold, the data density and the vector field. The algorithm is motivated by our analysis of Laplacian-type operators and their continuous limit as generators of diffusions on a manifold. We illustrate the recovery algorithm on both artificially constructed and real data.