Embedding Directed Graphs in Potential Fields Using FastMap-D
This addresses a computational limitation for researchers and practitioners working with directed graph data, though it appears incremental as it builds on an existing method for undirected graphs.
The paper tackles the problem of embedding directed graphs in Euclidean space by introducing FastMap-D, a generalization of FastMap that uses a potential field to capture asymmetric distances, and demonstrates its advantage over other approaches in experiments.
Embedding undirected graphs in a Euclidean space has many computational benefits. FastMap is an efficient embedding algorithm that facilitates a geometric interpretation of problems posed on undirected graphs. However, Euclidean distances are inherently symmetric and, thus, Euclidean embeddings cannot be used for directed graphs. In this paper, we present FastMap-D, an efficient generalization of FastMap to directed graphs. FastMap-D embeds vertices using a potential field to capture the asymmetry between the pairwise distances in directed graphs. FastMap-D learns a potential function to define the potential field using a machine learning module. In experiments on various kinds of directed graphs, we demonstrate the advantage of FastMap-D over other approaches.