Super nodes performance issue while running community detection algorithms

[mlo]

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?

[michael_hunger]

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.

[mlo]

(: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}
)

[mark_needham]

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]

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

[mlo]

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]

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

[mehdi_ajroud]

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

After using unionFind I am getting a cluster with 10k node Neo4j Graph Platform

I used unionFind algo to divide my graph into clusters . I am getting many clusters but one of them looks weird since it has 10k nodes ( I have 40k nodes in total) !! Anyone has an explanation about that ? I heard also about the "SUPER NODE" but I didn't find a tutorial/forums . It could be maybe the node which is related to 10k node is my super node ?

[michael_hunger]

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

[mehdi_ajroud]

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

[benjamin_squire]

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

[michael_hunger]

@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.