Showing results for 
Search instead for 
Did you mean: 

Label Propagation - Parallel Heuristics


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!


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

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.