Investigating Extensions to Random Walk Based Graph Embedding
This is an incremental improvement for researchers in graph embedding, addressing a known limitation in representing global graph structure.
The paper tackled the problem of random walk based graph embeddings failing to capture global structure by proposing an extension that removes least frequent nodes from walks to simulate distant connections. The results showed that such extensions, including their own, only slightly improved predictive performance, with minimal gains in tasks like node classification and link prediction.
Graph embedding has recently gained momentum in the research community, in particular after the introduction of random walk and neural network based approaches. However, most of the embedding approaches focus on representing the local neighborhood of nodes and fail to capture the global graph structure, i.e. to retain the relations to distant nodes. To counter that problem, we propose a novel extension to random walk based graph embedding, which removes a percentage of least frequent nodes from the walks at different levels. By this removal, we simulate farther distant nodes to reside in the close neighborhood of a node and hence explicitly represent their connection. Besides the common evaluation tasks for graph embeddings, such as node classification and link prediction, we evaluate and compare our approach against related methods on shortest path approximation. The results indicate, that extensions to random walk based methods (including our own) improve the predictive performance only slightly - if at all.