Node Embedding

Intuition

The below figure illustrates the concept behind node embedding, whereby nodes that are close together in the graph end up being close together in the 2-dimensional embedding space. The embedding thus took the structure from the graph, the n-dimensional adjacency matrix, and approximated it in 2-dimensional vectors for each node. The embedding vectors are much more efficient to use for downstream process due to significantly reduced dimensionality. They could be used for cluster analysis for example, or as features to train a node classification or link prediction model.

Figure 1. Concept Behind Node Embeddings

Of course, in real-world problems node embeddings will usually be larger than 2 dimensions, often ending up in the hundreds or larger, especially when applied to bigger graphs with millions or billions of nodes. Node embedding also doesn’t have to base similarity strictly on node proximity in the graph. While similarity based on distance in relationship hops and common neighbors is perhaps most common in application, node embedding can also consider node properties and other "global-view" node attributes when calculating embedding vectors.

Use Cases

Node embedding has applications across multiple use cases, from recommendations, to anomaly and fraud detection, entity resolution and other forms of knowledge graph completion.

Node embedding vectors don’t offer insights by themselves, they are created to enable or scale other analytics. Common workflows include:

FastRP

GDS offers a custom implementation of a node embedding technique called Fast Random Projection, or FastRP for short. FastRP leverages probabilistic sampling techniques to generate sparse representations of the graph allowing for extremely fast calculation of embedding vectors that are comparative in quality to those produced with traditional random walk and neural net techniques such as Node2vec and GraphSage. This makes FastRP a great choice for getting started with exploring embedding on your graph in GDS.

There are multiple tuning parameters for FastRP and in real-world applications these can be important to take into account. A couple of considerable note below:

There are other parameters that control strength of normalization and node self-influence. As always, you can reference these in detail in the docs.

A last important note on FastRP is that, while we won’t cover it here, it has the ability to consider node and relationship property weights when generating embeddings. This can be useful for generating embedding vectors that encapsulate signal from both a weighted graph structure and other properties/attributes in the data. As always, you can reference the parameters and various configuration in more detail in the docs.

FastRP Example

Below is an example of generating FastRP embeddings on person nodes in the movies graph based on the movies they acted in and/or directed.

As always we will start with the graph projection

CALL gds.graph.project('proj', ['Movie', 'Person'], {
    ACTED_IN:{orientation:'UNDIRECTED'},
    DIRECTED:{orientation:'UNDIRECTED'}
});

After that we will run FastRP. For demonstration purposes we will just use an embedding dimension of 64. We have the option of setting a randomSeed here as well to control consistency between runs.

CALL gds.fastRP.stream('proj',  {embeddingDimension:64, randomSeed:7474})
YIELD nodeId, embedding
WITH gds.util.asNode(nodeId) AS n, embedding
WHERE n:Person
RETURN id(n), n.name, embedding LIMIT 10

These embeddings, can, in theory, be used for similarity measurements to understand which actors are most similar and can be used in a content recommendation system to recommend movies to users based on the actors and/or directors for movies they recently viewed.

Other Node Embedding Algorithms

GDS has also implemented Node2Vec, which computes a vector representation of a node based on random walks in the graph, and GraphSage, which is an inductive modeling approach for computing node embeddings using node properties and graph structure.