Similarity

Similarity Algorithms in GDS

GDS has two primary similarity algorithms:

Choice of Similarity Metric

Both Node Similarity and KNN provide choices between different similarity metrics. Node Similarity has choices between Jaccard and Overlap similarity. KNN choice of metric is driven by the node property types. List of integers are subject to Jaccard and Overlap, list of floating point numbers to Cosine Similarity, Pearson, and Euclidean. Using different metrics will of course alter the similarity score and change the interpretation slightly. You can read more about the different metrics for Node Similarity in the Node Similarity documentation and for KNN in the K-Nearest Neighbors documentation.

Controlling Scope of Comparisons

Comparing every node to every other node in the graph is a computationally expensive task of roughly O(n^2) complexity. The GDS implementations for both Node Similarity and KNN have internal mechanisms to intelligently select node pairs for comparison allowing them to work faster and scale better. They also have parameters that can be adjusted by the user to tune how node pairs are sampled and selected for comparison.

Node Similarity has a degreeCutOff parameter for nodes which allows you to set a lower limit on the degree centrality for nodes to be selected.

KNN has various parameters that can be tuned to affect the speed vs completeness trade-off of node comparisons, including sampling rate, initial sampler methodology, random join counts between iteration, and a few others. You can read more about how these work in the K-Nearest Neighbors documentation.

Controlling Scope of Results

For similarity comparisons we may also want to control the number of results returned to only consider the most relevant node pairs. Both Node Similarity and KNN have a topK parameter to limit the number similarity comparisons returned per node. With node similarity there is also the capability to limit the results globally as opposed to just a per node basis.

Applied Example with KNN

Let’s take the embeddings we calculated from the node embedding lesson and use them to determine similarity between the actors and directors based on movies they have been involved with. You can regenerate the projection with the below:

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

We will then run FastRP like in the last lesson except in mutate mode so the embeddings will be saved in the projection.

CALL gds.fastRP.mutate('proj',  {
    embeddingDimension:64,
    randomSeed:7474,
    mutateProperty:'embedding'
})

After that we can run similarity. We will use the default cosine metric. For purposes of demonstration, I will limit topK to one so we can see the top pairs for each node.

CALL gds.knn.stream('proj', {nodeLabels:['Person'], nodeProperties:['embedding'], topK:1})
YIELD  node1, node2, similarity
RETURN gds.util.asNode(node1).name AS actorName1,
    gds.util.asNode(node2).name AS actorName2,
    similarity
LIMIT 10

Similarity Functions

In addition to the node similarity and KNN algorithms, GDS also provides a set of functions that can be used to calculate similarity between two arrays of numbers using various similarity metrics including jaccard, overlap, pearson, cosine similarity and a few others. The full documentation can be found in the Similarity Functions documentation. These functions are useful when you are interested in measuring similarity between a single select node pair at a time as opposed to calculating similarity over the entire graph.