Feature learning for representing sparse networks based on random walks

Abstract

Identifying features to represent graphs such as social networks, protein graphs is increasingly common in both research and business communities, thanks to the fact that data has increased not only in quantity but also in complexity. This results in the graphs to be sparser because not all nodes are fully connected. In addition, if this whole graph is used as input data for learning algorithms e.g. neural network, a lot of training time will be required. Substantial efforts have been made to convert the graphs to better yet compact representations, among of which is graph embedding. The traditional methods used to map the original graph to its embedding representation had not yielded significant results until deep learning was invented. Many good approaches in this direction, as examples, are DeepWalk, node2vec. However, their general weakness is many important connections in the original graph could be lost. In this paper, we propose another approach to retain more edge information while ensuring the embedding graph is still sufficiently small, compared to the original one. Our experiment results show that the method also increases the accuracy of latter learning models.