Node Similarity OOM

[RaoulBrueckler]

i tried to build a new edge for similarity with a score property. for a graph with ~2M Nodes and about ~8M edges, but it reaches the memorylimit with 32GB

I tried it with this query...

MATCH (b:Broadcast)
WITH b
MATCH p=(b)-[r:IS_TAGGED_WITH]->(t:Tag)
WITH project(p) AS subgraph
CALL node_similarity.jaccard(subgraph) YIELD node1, node2, similarity
WITH node1, node2, similarity
WHERE similarity > 0
MERGE (node1)-[:IS_SIMILAR {score: similarity}]->(node2)
RETURN node1, node2, similarity;

i also tried if with just 2 nodes like that, which works and which is pretty fast 2ms but if i remove the similarity > 0 check i see that it compares everything, not just the 2 broadcast nodes, it callculate as well the similarity for the tags and genres

MATCH (b:Broadcast)
WHERE b.id IN [36195333 , 36195268]
WITH b
MATCH p=(b)-[r:IS_TAGGED_WITH]->(t:Tag)
WITH project(p) AS subgraph
CALL node_similarity.jaccard(subgraph) YIELD node1, node2, similarity
WITH node1, node2, similarity
WHERE similarity > 0
MERGE (node1)-[:IS_SIMILAR {score: similarity}]->(node2)
RETURN node1, node2, similarity;

Here is a profile export

profile_summary.json

Is there a problem in my cypher or do i need more ram? or am i missing something else?

[Josipmrden]

hey @RaoulBrueckler .
Node similarity is a quadratic algorithm. Do you know how many nodes are there in the subgraph from query 1?
If there's around 1M nodes there, the algorithm will output 1M x 1M results which might be resulting in a higher memory consumption.

Solution involves:

1. Batching per Broadcast node from your side, since that's pretty light
2. Check how the algorithm runs without the merge clause -> if it still goes OOM, then node similarity is the problem. If the algorithm runs successfully, then MERGE is the problem (switch to IN_MEMORY_ANALYTICAL or USING PERIODIC COMMIT 10000)

Josip

[RaoulBrueckler]

Hi @Josipmrden

Count (Broadcasts): 1'438'618
MATCH (b:Broadcast) return count(b)

Count Broadcasts with tags: 6'802'945
MATCH (b:Broadcast)-[r:IS_TAGGED_WITH]->(t:Tag) return count(b)

-> Nearly 7 Mio must be wrong.... maybe there is a mistakt in the cypher?

Count distinct Broadcasts with tags: 1'207'884
MATCH (b:Broadcast)-[r:IS_TAGGED_WITH]->(t:Tag) return count(distinct b)

I tried the algorithm without the merge clause and it still goes OOM... so as a i saw in the documentation it would be enough to just use "USING PERIODIC COMMIT 1000" on the first line? or could as well be something wrong with my cypher as i mentioned above with the counts...

my plan is to get the similarity between nodes(broadcasts) which are tagged, based on the relations, if that makes sense

Raoul

[Josipmrden]

Nearly 7 Mio must be wrong.... maybe there is a mistakt in the cypher? 

-> This is the amount of edges (triplets) returned, so the actual count(distinct b) is the correct Cypher (the thing you have written below).

Since algorithm goes OOM even without the merge -> the issue is in the algorithm computation, not the writing (so you don't need to use USING PERIODIC COMMIT).

So currently, you would be doing a cartesian product. Are you trying to calculate pairwise similarity? If that's the case, you should check for:
https://memgraph.com/docs/advanced-algorithms/available-algorithms/node_similarity#jaccard_pairwise

Based on documentation

For each similarity measure, there are two functions, one that calculates similarity between all pairs of nodes and the other, pairwise function, that takes into account pairwise similarities between two set of nodes.

So you were basically calculating between all pairs, which is impossible to execute because it's 1M x 1M
I'm not sure what you're trying to calculate similarity on, but I guess it will involve 2 lists and then using jaccard_pairwise

[Josipmrden]

It would look something like this?

MATCH (b:Broadcast)-[r:IS_TAGGED_WITH]->(t:Tag)
WITH collect(b) as bs, collect(t) as ts
CALL node_similarity.jaccard_pairwise(bs, ts) YIELD node1, node2, similarity
WITH node1, node2, similarity
WHERE similarity > 0
MERGE (node1)-[:IS_SIMILAR {score: similarity}]->(node2)
RETURN node1, node2, similarity;

[RaoulBrueckler]

Hi @Josipmrden

This one you suggested works and needs about 15 seconds but it callculates the similarity between the tag and the broadcast, my goal is to callculate the similarity between all broadcast nodes. i want know, how similar this broadcast is to this one, so i can make suggestions to the user

[Josipmrden]

Thanks @RaoulBrueckler for providing the feedback. I don't think this is feasible for you to do since you have 1 million broadcast nodes. Calculating similarity between all of the pairs would yield 1 trillion similarity results. Do you have any post-processing logic to preserve only the most similar results?

[Josipmrden]

Node similarity is a full quadratic algorithm and the 1 trillion comes from calculating 1M x 1M similarities (therefore 10^12 similarities).

[RaoulBrueckler]

Hi @Josipmrden. Do you mean to just add the similarity if its greather than a specific value? or what do you mean with post-processing? if so, this would be absolute enough or like only create the similarity for the top10 similar nodes...

[Josipmrden]

Yes, in that case, we're currently designing the KNN module -> which is basically an upgraded node similarity algorithm
#668
https://neo4j.com/docs/graph-data-science/current/algorithms/knn/

In your case for now, I would do something like:

1. First query: Extract IDs of broadcast nodes:
   MATCH (b:Broadcast) RETURN ID(n) as broadcast_id.

2. Second query: do node similarity for one broadcast

MATCH (b:Broadcast) WHERE ID(b) = $broadcast_id
WITH b
MATCH (b2:Broadcast) WHERE b <> b2
WITH collect(b) as bs, collect(b2) as b2s
CALL node_similarity.jaccard_pairwise(bs, b2s) YIELD node1, node2, similarity
WITH node1, node2, similarity
WHERE similarity > 0.5 // use your treshold
WITH node1, node2, similarity ORDER BY node1 ASC, similarity DESC LIMIT 10
MERGE (node1)-[:IS_SIMILAR {score: similarity}]->(node2)

3. batch this in your programming language for every broadcast ID

[RaoulBrueckler]

@Josipmrden uuuh that sounds exactly what im searching :) when would this knn module be available?

ok so i will implement a batch processing in my language, thanks a lot for your help