Role-Based Graph Embeddings
Nesreen K. Ahmed, Ryan A. Rossi, John Boaz Lee, Theodore L. Willke, Rong Zhou, Xiangnan Kong, Hoda Eldardiry · IEEE Transactions on Knowledge and Data Engineering · 2020
Random walks are at the heart of many existing node embedding and network representation learning methods. However, such methods have many limitations that arise from the use of traditional random walks, e.g., the embeddings resulting from these methods capture proximity (communities) among the vertices as opposed to structural similarity (roles). Furthermore, the embeddings are unable to transfer to new nodes and graphs as they are tied to node identity. To overcome these limitations, we introduce theRole2Vecframework based on the proposed notion ofattributed random walksto learn structural role-based embeddings. Notably, the framework serves as a basis for generalizing any walk-based method. TheRole2Vecframework enables these methods to be more widely applicable by learning inductive functions that capture the structural roles in the graph. Furthermore, the original methods are recovered as a special case of the framework when each vertex is mapped to its own function that uniquely identifies it. Finally, theRole2Vecframework is shown to be effective with an average AUC improvement of 17.8 percent for link prediction while requiring on average 853x less space than existing methods on a variety of graphs from different domains.