cancel
Showing results for 
Search instead for 
Did you mean: 

Super nodes performance issue while running community detection algorithms

mlo
Node Link

I run community detection algorithms(unionFind, Louvain) to partition my graph database.

However, I recently encountered some performance problem because of super nodes.

I have the linking structure like below.

(:User)-[:DEVICE]->(:Device)

and other similar structures.

Basically, we want to use the property node(like device node) the users shared to link them.

Majority(99%) of the property nodes are only linked to ONE user.

However, some extreme ones link to 10K+ users which form super nodes.

Any suggested way to solve the super node performance issue?

11 REPLIES 11

Can you share your concrete model?
Not sure if you always need property nodes.

Which procedures did you run the one in graph algorithms?

The ones in APOC are deprecated and shouldn't be used anymore.

(:User)-[:DEVICE]->(:Device)
(:User)-[:PHONE]->(:Phone)
(:User)-[:EMAIL]->(:Email)
(:User)-[:SHIPPED]->(:Address)

Basically, I use these four models to link users.

I ran algo.unionFind and algo.louvain to partition the graph.

eg.

CALL algo.unionFind(
'MATCH (u1:User)
RETURN id(u1) as id',
'MATCH (u1:User)-[:DEVICE|:EMAIL|:PHONE|:SHIPPED]->(middle)<-[:DEVICE|:EMAIL|:PHONE|:SHIPPED]-(u2:User)
WHERE id(u1) < id(u2)
RETURN id(u1) as source, id(u2) as target',
{graph:'cypher', write: true, partitionProperty: 'group_label', concurrency: 16}
)

Hi,

When you say performance issue do you mean that the algorithm isn't returning a result or it's taking longer than you expect or something else? If it's slow do you know where exactly the problem is occurring?

Is it in the running of the algorithm or in the Cypher projection? How long does it take to run this query:

MATCH (u1:User)-[:DEVICE|:EMAIL|:PHONE|:SHIPPED]->(middle)<-[:DEVICE|:EMAIL|:PHONE|:SHIPPED]-(u2:User)
WHERE id(u1) < id(u2)
RETURN count(*)

mehdi_ajroud
Graph Buddy

Is there any news about this topic ? I am having the same issue ! or sall I create a new issue ?

I changed the way I model the data to avoid supernodes.

@mehdi.ajroud, you should create a new issue on that. If they can solve the supernode issue in community detection algorithm that will be wonderful.

mehdi_ajroud
Graph Buddy

ok ! I will recreate it since I didn't find any explanation

mehdi_ajroud
Graph Buddy

@mlo here is the link where I created the new issue , in case you want to follow the answer that I will get 😉

Better use label propagation or louvain, they are better at substructuring the graph.

I will try those ones and I will let you know about the final results ! Thanks Micheal 🙂

did you get a result to this @mehdi.ajroud? would be interested to hear if these other methods worked better at avoiding supernodes

@mio did you see Marks question?

You also didn't use distinct or count(*) in the edge-list statement, so you get a ton of duplicate pairs.

The answer to your question is to use USING JOIN ON d where it does a scan + expand on both sides and then a join on the middle node.