Label Propagation - Parallel Heuristics

Neo4j Graph Platform
1

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

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/labelpropagation/LabelPropagation.java

3

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.