node2vec: Scalable Feature Learning for Networks

1 node2vec : Scalable Feature Learning for NetworksAditya GroverStanford LeskovecStanford tasks over nodes and edges in Networks require carefuleffort in engineering features used by Learning algorithms. Recentresearch in the broader field of representation Learning has led tosignificant progress in automating prediction by Learning the fea-tures themselves. However, present Feature Learning approachesare not expressive enough to capture the diversity of connectivitypatterns observed in we proposenode2vec, an algorithmic framework for learn-ing continuous Feature representations for nodes in Networks . Innode2vec, we learn a mapping of nodes to a low-dimensional spaceof features that maximizes the likelihood of preserving networkneighborhoods of nodes. We define a flexible notion of a node snetwork neighborhood and design a biased random walk procedure,which efficiently explores diverse neighborhoods. Our algorithmgeneralizes prior work which is based on rigid notions of networkneighborhoods, and we argue that the added flexibility in exploringneighborhoods is the key to Learning richer demonstrate the efficacy ofnode2vecover existing state-of-the-art techniques on multi-label classification and link predictionin several real-world Networks from diverse domains.

2 Taken to-gether, our work represents a new way for efficiently Learning state-of-the-art task-independent representations in complex and Subject [Database Manage-ment]: Database applications Data mining; [Artificial In-telligence]: LearningGeneral Terms:Algorithms; :Information Networks , Feature Learning , Node embed-dings, Graph INTRODUCTIONMany important tasks in network analysis involve predictionsover nodes and edges. In a typical node classification task, weare interested in predicting the most probable labels of nodes ina network [33]. For example, in a social network, we might beinterested in predicting interests of users, or in a protein-protein in-teraction network we might be interested in predicting functionallabels of proteins [25, 37]. Similarly, in link prediction, we wish toPermission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page.

3 Copyrights for components of this work owned by others than theauthor(s) must be honored. Abstracting with credit is permitted. To copy otherwise, orrepublish, to post on servers or to redistribute to lists, requires prior specific permissionand/or a fee. Request permissions from 16, August 13 - 17, 2016, San Francisco, CA, USAc 2016 Copyright held by the owner/author(s). Publication rights licensed to 978-1-4503-4232-2/16/08.. $ : whether a pair of nodes in a network should have an edgeconnecting them [18]. Link prediction is useful in a wide varietyof domains; for instance, in genomics, it helps us discover novelinteractions between genes, and in social Networks , it can identifyreal-world friends [2, 34].Any supervised machine Learning algorithm requires a set of in-formative, discriminating, and independent features. In predictionproblems on Networks this means that one has to construct a featurevector representation for the nodes and edges.

4 A typical solution in-volves hand-engineering domain-specific features based on expertknowledge. Even if one discounts the tedious effort required forfeature engineering, such features are usually designed for specifictasks and do not generalize across different prediction alternative approach is tolearnfeature representations bysolving an optimization problem [4]. The challenge in Feature learn-ing is defining an objective function, which involves a trade-offin balancing computational efficiency and predictive accuracy. Onone side of the spectrum, one could directly aim to find a featurerepresentation that optimizes performance of a downstream predic-tion task. While this supervised procedure results in good accu-racy, it comes at the cost of high training time complexity due to ablowup in the number of parameters that need to be estimated. Atthe other extreme, the objective function can be defined to be inde-pendent of the downstream prediction task and the representationscan be learned in a purely unsupervised way.

5 This makes the op-timization computationally efficient and with a carefully designedobjective, it results in task-independent features that closely matchtask-specific approaches in predictive accuracy [21, 23].However, current techniques fail to satisfactorily define and opti-mize a reasonable objective required for Scalable unsupervised fea-ture Learning in Networks . Classic approaches based on linear andnon-linear dimensionality reduction techniques such as PrincipalComponent Analysis, Multi-Dimensional Scaling and their exten-sions [3, 27, 30, 35] optimize an objective that transforms a repre-sentative data matrix of the network such that it maximizes the vari-ance of the data representation. Consequently, these approaches in-variably involve eigendecomposition of the appropriate data matrixwhich is expensive for large real-world Networks . Moreover, theresulting latent representations give poor performance on variousprediction tasks over , we can design an objective that seeks to preservelocal neighborhoods of nodes.

6 The objective can be efficiently op-timized using stochastic gradient descent (SGD) akin to backpro-pogation on just single hidden-layer feedforward neural attempts in this direction [24, 28] propose efficient algo-rithms but rely on a rigid notion of a network neighborhood, whichresults in these approaches being largely insensitive to connectiv-ity patterns unique to Networks . Specifically, nodes in networkscould be organized based on communities they belong to ( ,ho-mophily); in other cases, the organization could be based on thestructural roles of nodes in the network ( ,structural equiva-lence) [7, 10, 36]. For instance, in Figure 1, we observe nodesuands1belonging to the same tightly knit community of nodes,while the nodesuands6in the two distinct communities share thesame structural role of a hub node. Real-world Networks commonlyexhibit a mixture of such equivalences. Thus, it is essential to allowfor a flexible algorithm that can learn node representations obeyingboth principles: ability to learn representations that embed nodesfrom the same network community closely together, as well as tolearn representations where nodes that share similar roles have sim-ilar embeddings.

7 This would allow Feature Learning algorithms togeneralize across a wide variety of domains and prediction proposenode2vec, a semi-supervised algorithmfor Scalable Feature Learning in Networks . We optimize a customgraph-based objective function using SGD motivated by prior workon natural language processing [21]. Intuitively, our approach re-turns Feature representations that maximize the likelihood of pre-serving network neighborhoods of nodes in ad-dimensional fea-ture space. We use a 2ndorder random walk approach to generate(sample) network neighborhoods for key contribution is in defining a flexible notion of a node snetwork neighborhood. By choosing an appropriate notion of aneighborhood,node2veccan learn representations that organizenodes based on their network roles and/or communities they be-long to. We achieve this by developing a family of biased randomwalks, which efficiently explore diverse neighborhoods of a givennode.

8 The resulting algorithm is flexible, giving us control over thesearch space through tunable parameters, in contrast to rigid searchprocedures in prior work [24, 28]. Consequently, our method gen-eralizes prior work and can model the full spectrum of equivalencesobserved in Networks . The parameters governing our search strat-egy have an intuitive interpretation and bias the walk towards dif-ferent network exploration strategies. These parameters can alsobe learned directly using a tiny fraction of labeled data in a semi-supervised also show how Feature representations of individual nodescan be extended to pairs of nodes ( , edges). In order to generatefeature representations of edges, we compose the learned featurerepresentations of the individual nodes using simple binary oper-ators. This compositionality lendsnode2vecto prediction tasksinvolving nodes as well as experiments focus on two common prediction tasks in net-works: a multi-label classification task, where every node is as-signed one or more class labels and a link prediction task, where wepredict the existence of an edge given a pair of nodes.

9 We contrastthe performance ofnode2vecwith state-of-the-art Feature learningalgorithms [24, 28]. We experiment with several real-world net-works from diverse domains, such as social Networks , informationnetworks, as well as Networks from systems biology. Experimentsdemonstrate thatnode2vecoutperforms state-of-the-art methods byup to on multi-label classification and up to on linkprediction. The algorithm shows competitive performance witheven 10% labeled data and is also robust to perturbations in theform of noisy or missing edges. Computationally, the major phasesofnode2vecare trivially parallelizable, and it can scale to largenetworks with millions of nodes in a few our paper makes the following contributions:1. We proposenode2vec, an efficient Scalable algorithm forfeature Learning in Networks that efficiently optimizes a novelnetwork-aware, neighborhood preserving objective using We show hownode2vecis in accordance with establishedu s3 s2 s1 s4 s8 s9 s6 s7 s5 BFS DFS Figure 1: BFS and DFS search strategies from nodeu(k= 3).

10 Principles in network science, providing flexibility in discov-ering representations conforming to different We extendnode2vecand other Feature Learning methods basedon neighborhood preserving objectives, from nodes to pairsof nodes for edge-based prediction We empirically evaluatenode2vecfor multi-label classifica-tion and link prediction on several real-world rest of the paper is structured as follows. In Section 2, webriefly survey related work in Feature Learning for Networks . Wepresent the technical details for Feature Learning usingnode2vecin Section 3. In Section 4, we empirically evaluatenode2veconprediction tasks over nodes and edges on various real-world net-works and assess the parameter sensitivity, perturbation analysis,and scalability aspects of our algorithm. We conclude with a dis-cussion of thenode2vecframework and highlight some promis-ing directions for future work in Section 5. Datasets and a refer-ence implementation ofnode2vecare available on the project page: RELATED WORKF eature engineering has been extensively studied by the machinelearning community under various headings.