cancel
Showing results for 
Search instead for 
Did you mean: 

Label Propagation - Parallel Heuristics

geo
Node

Hey! I'm investigating the label propagation algorithm as implemented in Neo4J's graph data science library. I think it's notable that it's possible to set concurrency parameters, even though the original (Raghavan et al.) paper on Label propagation does not specify explicitly a parallel algorithm. Is there any documentation how the parallel implementation works? Is the Staudt&Meyerhenke (PLP) version of the algorithm used, or some sort of coloring preprocessing?

Thanks in advance!

2 REPLIES 2

I asked the team to give some more detail, but until then you can look at the code here:

https://github.com/neo4j/graph-data-science/blob/master/algo/src/main/java/org/neo4j/gds/labelpropag...

Thanks for this! I dug through the code a little bit, and it looks like the nodes are evenly split into batches, which are then processed in parallel with a normal majority vote as in standard label propagation. So this looks similar to PLP.