Learning Multigraph Node Embeddings Using Guided Lévy Flights

Roy, Aman; Kumar, Vinayak; Mukherjee, Debdoot; Chakraborty, Tanmoy

Learning efficient representation of graphs has recently been studied extensively for simple networks to facilitate various downstream applications. In this paper, we deal with a more generalized graph structure, called multigraph (multiple edges of different types connecting a pair of nodes) and propose Multigraph2Vec, a random walk based framework for learning multigraph network representation. Multigraph2Vec samples a heterogeneous neighborhood structure for each node by preserving the inter-layer interactions. It employs Lévy flight random walk strategy, which allows the random walker to travel across multiple layers and reach far-off nodes in a single step. The transition probabilities are learned in a supervised fashion as a function of node attributes (metadata based and/or network structure based). We compare Multigraph2Vec with four state-of-the-art baselines after suitably adopting to our setting on four datasets. Multigraph2Vec outperforms others in the task of link prediction, by beating the best baseline with 5.977% higher AUC score; while in the multi-class node classification task, it beats the best baseline with 5.28% higher accuracy. We also deployed Multigraph2Vec for friend recommendation on Hike Messenger.