Contact



Since its publication in 2016 by Aditya Grover and Jure Leskovec, Node2vec has become the go-to algorithm to easily compute embeddings for nodes in a graph/network. Working with embeddings has really been a game changer in Machine learning in general and particularly in NLP, CV or Graph analysis. Using a continuous vector representation (embedding) of a symbolic/discrete element makes it easy any data manipulation and allows for fast computation with modern processing platforms.

This post will explore node2vec’s ability to compute authors’ similarity from arXiv metadata. I’ve shared the code for this post so anyone can play with this example. All you have to do is follow the project’s README.md instructions. To visualise the data we will use TensorFlow projector online tool and have a closer look at the embedding and surrounding neighbors of node2vec’s main author – Aditya Grover.

Understanding node2vec

Node2vec’s principle is simple: nodes that are closely related in the graph should have a close embedding. It is a direct extension of Word2vec algorithm but instead of computing embedding vectors for words from a sequence of words (sentence), it computes vectors for nodes from a sequence of nodes (path).

Word2vec trains word embeddings by optimizing a loss function with gradient descent, just like any other deep learning model. In word2vec, the loss function can be computed using two approaches:

  • CBOW (Continuous Bag-Of-Words): measuring how well a certain word can be predicted using its surrounding words.
  • Skip-gram: measuring how well a certain word can predict its surrounding words.

Take the sentence “I like cats more than dogs”. The example below illustrates the two approaches with a shifting contextual window size of 2 (that is to say, 2 words preceding “I”, “like” and two words “more”, “than” following the word of interest: “cat”).

Node2vec is a simple but effective way to leverage the principle put forward by word2vec but applied to graphs. It first creates a sequence of nodes (similar to a sentence of words) using random walks and then feeds these node sequences to word2vec model.

As an introduction to the data we will use later, consider a set of 3 scholarly papers written by certain authors in given domains. Node2vec starts with computing the transition probabilities between nodes (in an unweighted graph, this is the number of links between the two nodes divided by the out-degree of the source node). It then starts a given number of walks from every node in the graph. In the figure below you see one random walk of length 7 starting from the node “Aditya Grover” (the main author of the node2vec paper).

As an output, we get a sequence of nodes that can be processed straight forwardly using the word2vec method. Depending on the window size, long graph range dependencies can be learned. The end result is a vector representation for each node in the graph that keeps nodes that are close in the graph, close in the embedding space. Using that property, the vectors can typically help tasks such as node similarity or clustering. As a node embedding technique, node2vec has a limitation: it disregards edge labels (relationship types). Other node and edge embedding techniques overcome that problem.

The ArXiv Dataset

To compute author’s similarity using node2vec, we will use the Arxiv dataset published on Kaggle. The dataset contains metadata about 41,000 papers (yes, the title of their dataset page is misleading!) published between 1992 to 2018, mostly in the domain of machine learning.

Here is the record for the node2vec paper:

{
  "id": "1607.00653v1",
  "author": "[{'name': 'Aditya Grover'}, {'name': 'Jure Leskovec'}]",
  "link": "[{'rel': 'alternate', 'href': 'http://arxiv.org/abs/1607.00653v1', 'type': 'text/html'}, {'rel': 'related', 'href': 'http://arxiv.org/pdf/1607.00653v1', 'type': 'application/pdf', 'title': 'pdf'}]",
  "title": "node2vec: Scalable Feature Learning for Networks",
  "summary": "Prediction tasks over nodes and edges in networks require careful effort in\nengineering features used by learning algorithms. Recent research in the\nbroader field of representation learning has led to significant progress in\nautomating prediction by learning the features themselves. However, present\nfeature learning approaches are not expressive enough to capture the diversity\nof connectivity patterns observed in networks. Here we propose node2vec, an\nalgorithmic framework for learning continuous feature representations for nodes\nin networks. In node2vec, we learn a mapping of nodes to a low-dimensional\nspace of features that maximizes the likelihood of preserving network\nneighborhoods of nodes. We define a flexible notion of a node's network\nneighborhood and design a biased random walk procedure, which efficiently\nexplores diverse neighborhoods. Our algorithm generalizes prior work which is\nbased on rigid notions of network neighborhoods, and we argue that the added\nflexibility in exploring neighborhoods is the key to learning richer\nrepresentations. We demonstrate the efficacy of node2vec over existing\nstate-of-the-art techniques on multi-label classification and link prediction\nin several real-world networks from diverse domains. Taken together, our work\nrepresents a new way for efficiently learning state-of-the-art task-independent\nrepresentations in complex networks.",
  "tag": "[{'term': 'cs.SI', 'scheme': 'http://arxiv.org/schemas/atom', 'label': None}, {'term': 'cs.LG', 'scheme': 'http://arxiv.org/schemas/atom', 'label': None}, {'term': 'stat.ML', 'scheme': 'http://arxiv.org/schemas/atom', 'label': None}]",
  "year": 2016,
  "month": 7,
  "day": 3
}

Each paper has:

  • an identifier `id`
  • a list of authors identified by their full names. Without author’s organisation or email this leads to potential ambiguities but for the sake of this experiment we will disregard that issue.
  • links to the publications URLs
  • the article title
  • the article abstract (called summary)
  • the domain tags such as stat.ML for Machine Learning
  • the year, month and day of publication

ArXiv knowledge graph construction

From this dataset, several graph modeling options can come to mind such as materialising directly the co-authorships. Here I chose to keep a paper-centric view linking a paper with each author using a relation type “has author” and linking with each tag/domain using a relation type “has tag”. The rest of the information (links, title, abstract and publication date) although interesting are not used for this experiment. We end up with the following representation of the node2vec paper:

After transformation, the arXiv knowledge graph has the following statistics:

Property Value
Number of statements 213,539
Number of relationship types 2
– hasAuthor relation 132,960
– hasTag relation 80,579
Number of entity types 3
– Author entity type 59,889
– Paper entity type 41,000
– Tag/Domain entity type 2,293

Node embedding visualisation

For the visualisation, I am using TensorFlow Projector online tool. It’s a fast way to visualise the data using various dimensionality reduction methods like PCS or T-SNE. The tool allows as well to search among the labels and get the top-k nearest neighbours for a given node. After loading our embeddings data along with their labels, we can look for the main node2vec author: Aditya Grover. The resulting visualisation is provided below.

Interestingly when we look at the top 10 closest authors (using cosine distance), we find not only some expected co-authors from our dataset (compared in the table below with co-authors in Scopus) but as well authors that are not direct co-authors of Aditya Grover. Marshall Burke, Shengjia Zhao, Jiaming Song, George Azzari and Jon Conrad have co-authored articles with Stefano Ermon which has co-authored papers with Aditya Grover. Node2vec learns from long range relationships and not only from local ones. This means that if an author has never co-authored a paper but has its paper linked to a known tag/domain, it will be placed close to other authors from the same domain. This is a great feature of node2vec overcoming the cold start problem.

Top10 distance-based closest Authors Co-author position in Scopus
Manik Dhar 7
Ankit Anand 4
Stefano Ermon 1
Mausam 3
Parag Singla 2
Marshall Burke
Shengjia Zhao
Jon Conrad
Jiaming Song
George Azzari

Beside graph features used by node2vec we could have used information carried by the paper title and summary or even its date of publication. This could lead to systems that learn from both topological features of the graph and natural language features. Something we will explore in a future post.