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.

2 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. 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.

3 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. Copyrights for components of this work owned by others than theauthor(s) must be honored.

4 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.

5 In predictionproblems on Networks this means that one has to construct a featurevector representation for the nodes and edges. 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.

6 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. 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 .

7 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. 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 .

8 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.

9 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.

10 We achieve this by developing a family of biased randomwalks, which efficiently explore diverse neighborhoods of a givennode. 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).