7.5.5. The Overlap Similarity algorithm

This section describes the Overlap Similarity algorithm in the Neo4j Labs Graph Algorithms library.

Overlap similarity measures overlap between two sets. It is defined as the size of the intersection of two sets, divided by the size of the smaller of the two sets.

The Overlap Similarity algorithm was developed by the Neo4j Labs team and is not officially supported.

This section includes:

7.5.5.1. History and explanation

Overlap similarity is computed using the following formula:

overlap

The library contains both procedures and functions to calculate similarity between sets of data. The function is best used when calculating the similarity between small numbers of sets. The procedures parallelize the computation, and are therefore more appropriate for computing similarities on bigger datasets.

7.5.5.2. Use-cases - when to use the Overlap Similarity algorithm

We can use the Overlap Similarity algorithm to work out which things are subsets of others. We might then use these computed subsets to learn a taxonomy from tagged data, as described by Jesús Barrasa.

7.5.5.3. Overlap Similarity algorithm function sample

The following will return the Overlap similarity of two lists of numbers: 

RETURN algo.similarity.overlap([1,2,3], [1,2,4,5]) AS similarity

Table 7.138. Results
similarity

0.66

These two lists of numbers have an overlap similarity of 0.66. We can see how this result is derived by breaking down the formula:

O(A,B) = (∣A ∩ B∣) / (min(∣A|,|B|))
O(A,B) = 2 / min(3,4)
       = 2 / 3
       = 0.66

7.5.5.4. Overlap Similarity algorithm procedures sample

The following will create a sample graph: 

MERGE (fahrenheit451:Book {title:'Fahrenheit 451'})
MERGE (dune:Book {title:'Dune'})
MERGE (hungerGames:Book {title:'The Hunger Games'})
MERGE (nineteen84:Book {title:'1984'})
MERGE (gatsby:Book {title:'The Great Gatsby'})

MERGE (scienceFiction:Genre {name: "Science Fiction"})
MERGE (fantasy:Genre {name: "Fantasy"})
MERGE (dystopia:Genre {name: "Dystopia"})
MERGE (classics:Genre {name: "Classics"})

MERGE (fahrenheit451)-[:HAS_GENRE]->(dystopia)
MERGE (fahrenheit451)-[:HAS_GENRE]->(scienceFiction)
MERGE (fahrenheit451)-[:HAS_GENRE]->(fantasy)
MERGE (fahrenheit451)-[:HAS_GENRE]->(classics)

MERGE (hungerGames)-[:HAS_GENRE]->(scienceFiction)
MERGE (hungerGames)-[:HAS_GENRE]->(fantasy)
MERGE (hungerGames)-[:HAS_GENRE]->(romance)

MERGE (nineteen84)-[:HAS_GENRE]->(scienceFiction)
MERGE (nineteen84)-[:HAS_GENRE]->(dystopia)
MERGE (nineteen84)-[:HAS_GENRE]->(classics)

MERGE (dune)-[:HAS_GENRE]->(scienceFiction)
MERGE (dune)-[:HAS_GENRE]->(fantasy)
MERGE (dune)-[:HAS_GENRE]->(classics)

MERGE (gatsby)-[:HAS_GENRE]->(classics)

The following will return a stream of node pairs, along with their intersection and overlap similarities: 

MATCH (book:Book)-[:HAS_GENRE]->(genre)
WITH {item:id(genre), categories: collect(id(book))} as userData
WITH collect(userData) as data
CALL algo.similarity.overlap.stream(data)
YIELD item1, item2, count1, count2, intersection, similarity
RETURN algo.asNode(item1).name AS from, algo.asNode(item2).name AS to,
       count1, count2, intersection, similarity
ORDER BY similarity DESC

Table 7.139. Results
from to count1 count2 intersection similarity

Fantasy

Science Fiction

3

4

3

1.0

Dystopia

Science Fiction

2

4

2

1.0

Dystopia

Classics

2

4

2

1.0

Science Fiction

Classics

4

4

3

0.75

Fantasy

Classics

3

4

2

0.66

Dystopia

Fantasy

2

3

1

0.5

Fantasy and Dystopia are both clear subgenres of Science Fiction - 100% of the books that list those as genres also list Science Fiction as a genre. Dystopia is also a subgenre of Classics. The others are less obvious; Dystopia probably isn’t a subgenre of Fantasy, but the other two pairs could be subgenres.

The following will return a stream of node pairs that have a similarity of at least 0.75, along with their intersection and overlap similarities: 

MATCH (book:Book)-[:HAS_GENRE]->(genre)
WITH {item:id(genre), categories: collect(id(book))} as userData
WITH collect(userData) as data
CALL algo.similarity.overlap.stream(data, {similarityCutoff: 0.75})
YIELD item1, item2, count1, count2, intersection, similarity
RETURN algo.asNode(item1).name AS from, algo.asNode(item2).name AS to,
       count1, count2, intersection, similarity
ORDER BY similarity DESC

Table 7.140. Results
from to count1 count2 intersection similarity

Fantasy

Science Fiction

3

4

3

1.0

Dystopia

Science Fiction

2

4

2

1.0

Dystopia

Classics

2

4

2

1.0

Science Fiction

Classics

4

4

3

0.75

We can see that those genres with lower similarity have been filtered out. If we’re implementing a k-Nearest Neighbors type query we might instead want to find the most similar k super genres for a given genre. We can do that by passing in the topK parameter.

The following will return a stream of genres, along with the two most similar super genres to them (i.e. k=2): 

MATCH (book:Book)-[:HAS_GENRE]->(genre)
WITH {item:id(genre), categories: collect(id(book))} as userData
WITH collect(userData) as data
CALL algo.similarity.overlap.stream(data, {topK: 2})
YIELD item1, item2, count1, count2, intersection, similarity
RETURN algo.asNode(item1).name AS from, algo.asNode(item2).name AS to,
       count1, count2, intersection, similarity
ORDER BY from

Table 7.141. Results
from to count1 count2 intersection similarity

Dystopia

Classics

2

4

2

1.0

Dystopia

Science Fiction

2

4

2

1.0

Fantasy

Science Fiction

3

4

3

1.0

Fantasy

Classics

3

4

2

0.6666666666666666

Science Fiction

Classics

4

4

3

0.75

The following will find the most similar genre for each genre, and store a relationship between those genres: 

MATCH (book:Book)-[:HAS_GENRE]->(genre)
WITH {item:id(genre), categories: collect(id(book))} as userData
WITH collect(userData) as data
CALL algo.similarity.overlap(data, {topK: 2, similarityCutoff: 0.5, write:true})
YIELD nodes, similarityPairs, write, writeRelationshipType, writeProperty, min, max, mean, stdDev, p25, p50, p75, p90, p95, p99, p999, p100
RETURN nodes, similarityPairs, write, writeRelationshipType, writeProperty, min, max, mean, p95

Table 7.142. Results
nodes similarityPairs write writeRelationshipType writeProperty min max mean p95

4

5

TRUE

NARROWER_THAN

score

0.6666641235351562

1.0000038146972656

0.8833351135253906

1.0000038146972656

We then could write a query to find out the genre hierarchy for a specific genre.

The following will find the genre hierarchy for the Fantasy genre. 

MATCH path = (fantasy:Genre {name: "Fantasy"})-[:NARROWER_THAN*]->(genre)
RETURN [node in nodes(path) | node.name] AS hierarchy
ORDER BY length(path)

Table 7.143. Results
hierarchy

["Fantasy", "Science Fiction"]

["Fantasy", "Classics"]

["Fantasy", "Science Fiction", "Classics"]

7.5.5.5. Specifying source and target ids

Sometimes, we don’t want to compute all pairs similarity, but would rather specify subsets of items to compare to each other. We do this using the sourceIds and targetIds keys in the config.

We could use this technique to compute the similarity of a subset of items to all other items.

The following will return the super genres for the Fantasy and Classics genres: 

MATCH (book:Book)-[:HAS_GENRE]->(genre)
WITH {item:id(genre), name: genre.name, categories: collect(id(book))} as userData
WITH collect(userData) as data

// create sourceIds list containing ids for Fantasy and Classics
WITH data,
     [value in data WHERE value.name IN ["Fantasy", "Classics"] | value.item ] AS sourceIds

CALL algo.similarity.overlap.stream(data, {sourceIds: sourceIds})
YIELD item1, item2, count1, count2, intersection, similarity
RETURN algo.getNodeById(item1).name AS from, algo.getNodeById(item2).name AS to, similarity
ORDER BY similarity DESC

Table 7.144. Results
from to similarity

Fantasy

Science Fiction

1.0

Classics

Science Fiction

0.75

Fantasy

Classics

0.6666666666666666

7.5.5.6. Syntax

The following will run the algorithm and write back results: 

CALL algo.similarity.overlap(userData:List<Map>, {
    topK: 1, similarityCutoff: 0.1, write:true, writeProperty: "overlapSimilarity"
})
YIELD nodes, similarityPairs, write, writeRelationshipType, writeProperty, min, max, mean, stdDev, p25, p50, p75, p90, p95, p99, p999, p100

Table 7.145. Parameters
Name Type Default Optional Description

data

list

null

no

A list of maps of the following structure: {item: nodeId, categories: [nodeId, nodeId, nodeId]}.

top

int

0

yes

The number of similar pairs to return. If 0, it will return as many as it finds.

topK

int

0

yes

The number of similar values to return per node. If 0, it will return as many as it finds.

similarityCutoff

int

-1

yes

The threshold for Overlap similarity. Values below this will not be returned.

degreeCutoff

int

0

yes

The threshold for the number of items in the targets list. If the list contains less than this amount, that node will be excluded from the calculation.

concurrency

int

available CPUs

yes

The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'.

readConcurrency

int

value of 'concurrency'

yes

The number of concurrent threads used for reading the graph.

writeConcurrency

int

value of 'concurrency'

yes

The number of concurrent threads used for writing the result.

write

boolean

false

yes

Indicates whether results should be stored.

writeRelationshipType

string

NARROWER_THAN

yes

The relationship type to use when storing results.

writeProperty

string

score

yes

The property to use when storing results.

sourceIds

long[]

null

yes

The ids of items from which we need to compute similarities. Defaults to all the items provided in the data parameter.

targetIds

long[]

null

yes

The ids of items to which we need to compute similarities. Defaults to all the items provided in the data parameter.

Table 7.146. Results
Name Type Description

nodes

int

The number of nodes passed in.

similarityPairs

int

The number of pairs of similar nodes computed.

write

boolean

Indicates whether results were stored.

writeRelationshipType

string

The relationship type used when storing results.

writeProperty

string

The property used when storing results.

min

double

The minimum similarity score computed.

max

double

The maximum similarity score computed.

mean

double

The mean of similarities scores computed.

stdDev

double

The standard deviation of similarities scores computed.

p25

double

The 25 percentile of similarities scores computed.

p50

double

The 50 percentile of similarities scores computed.

p75

double

The 75 percentile of similarities scores computed.

p90

double

The 90 percentile of similarities scores computed.

p95

double

The 95 percentile of similarities scores computed.

p99

double

The 99 percentile of similarities scores computed.

p999

double

The 99.9 percentile of similarities scores computed.

p100

double

The 25 percentile of similarities scores computed.

The following will run the algorithm and stream results: 

CALL algo.similarity.overlap.stream(userData:List<Map>, {
    degreeCutoff: 10, similarityCutoff: 0.1, concurrency:4
})
YIELD item1, item2, count1, count2, similarity

Table 7.147. Parameters
Name Type Default Optional Description

data

list

null

no

A list of maps of the following structure: {item: nodeId, categories: [nodeId, nodeId, nodeId]}.

top

int

0

yes

The number of similar pairs to return. If 0, it will return as many as it finds.

topK

int

0

yes

The number of similar values to return per node. If 0, it will return as many as it finds.

similarityCutoff

int

-1

yes

The threshold for Overlap similarity. Values below this will not be returned.

degreeCutoff

int

0

yes

The threshold for the number of items in the targets list. If the list contains less than this amount, that node will be excluded from the calculation.

concurrency

int

available CPUs

yes

The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency'.

readConcurrency

int

value of 'concurrency'

yes

The number of concurrent threads used for reading the graph.

sourceIds

long[]

null

yes

The ids of items from which we need to compute similarities. Defaults to all the items provided in the data parameter.

targetIds

long[]

null

yes

The ids of items to which we need to compute similarities. Defaults to all the items provided in the data parameter.

Table 7.148. Results
Name Type Description

item1

int

The ID of one node in the similarity pair.

item2

int

The ID of other node in the similarity pair.

count1

int

The size of the targets list of one node.

count2

int

The size of the targets list of other node.

intersection

int

The number of intersecting values in the two nodes targets lists.

similarity

int

The Overlap similarity of the two nodes.