Anonymous walk embeddings: the growth of anonymous walks with length

May 03, 2020 at 04:30 PM, by Mehdi
graph embedding data science representation learning node embedding

Graph embedding is a field of representation learning aiming to transform a graph into a vector of features (numbers) that captures the structural aspect of the graph and/or its node features. One of these techniques is the Anonymous Walk Embedding designed by Sergey Ivanov and Evgeny Burnaev. In their paper, the authors state: "Direct computation of AWE relies on the enumeration of all different random walks in graph G, which is shown below to grow exponentially with the number of steps". In this post, I will show you what is the relationship between the embedding size and the length of the generated random walks.