Network embedding algorithms are able to learn latent feature representations of nodes, transforming networks into lower dimensional vector representations. Typical key applications, which have effectively been addressed using network embeddings, include link prediction, multilabel classification and community detection. In this paper, we propose Biased-Walk, a scalable, unsupervised feature learning algorithm that is based on biased random walks to sample context information about each node in the network. Our random-walk based sampling can behave as Breath-First-Search (BFS) and Depth-First-Search (DFS) samplings with the goal to capture homophily and role equivalence between the nodes in the network. We have performed a detailed experimental evaluation comparing the performance of the proposed algorithm against various baseline methods, on several datasets and learning tasks. The experiment results show that the proposed method outperforms the baseline ones in most of the tasks and datasets.
As we will present later on, the proposed method which is called BiasedWalk, is also based on the Skip-gram model. The core of BiasedWalk is a node sampling procedure which is able to generate biased (and first-order) random walks that behave as actual depth-first-search (DFS) and breath-first-search (BFS) explorations -- thus, helping towards capturing important structural properties, such as community information and structural roles of nodes. It should be noted that node2vec @cite_11 also aims to sample nodes based on DFS and BFS random walks, but it cannot control the distances between sampling nodes and the source node. Controlling the distances is crucial as in many specific tasks, such as the one of link prediction, nodes close to the source should have higher probability to form a link from it. Similarly, in the community detection task, given a fixed sampling budget we prefer to visit as many community-wide nodes as possible.
@cite_11
2962756421
Prediction tasks over nodes and edges in networks require careful effort in engineering features used by learning algorithms. Recent research in the broader field of representation learning has led to significant progress in automating prediction by learning the features themselves. However, present feature learning approaches are not expressive enough to capture the diversity of connectivity patterns observed in networks. Here we propose node2vec, an algorithmic framework for learning continuous feature representations for nodes in networks. In node2vec, we learn a mapping of nodes to a low-dimensional space of features that maximizes the likelihood of preserving network neighborhoods of nodes. We define a flexible notion of a node's network neighborhood and design a biased random walk procedure, which efficiently explores diverse neighborhoods. Our algorithm generalizes prior work which is based on rigid notions of network neighborhoods, and we argue that the added flexibility in exploring neighborhoods is the key to learning richer representations. We demonstrate the efficacy of node2vec over existing state-of-the-art techniques on multi-label classification and link prediction in several real-world networks from diverse domains. Taken together, our work represents a new way for efficiently learning state-of-the-art task-independent representations in complex networks.