Exact Distributed Stochastic Block Partitioning

dc.contributor.authorWanye, Franken
dc.contributor.authorGleyzer, Vitaliyen
dc.contributor.authorKao, Edwarden
dc.contributor.authorFeng, Wu-chunen
dc.date.accessioned2024-03-04T15:54:17Zen
dc.date.available2024-03-04T15:54:17Zen
dc.date.issued2023-01-01en
dc.description.abstractStochastic block partitioning (SBP) is a community detection algorithm that is highly accurate even on graphs with a complex community structure, but its inherently serial nature hinders its widespread adoption by the wider scientific community. To make it practical to analyze large real-world graphs with SBP, there is a growing need to parallelize and distribute the algorithm. The current state-of-the-art distributed SBP algorithm is a divide-and-conquer approach that limits communication between compute nodes until the end of inference. This leads to the breaking of computational dependencies, which causes convergence issues as the number of compute nodes increases and when the graph is sufficiently sparse. To address this shortcoming, we introduce EDiSt - an exact distributed stochastic block partitioning algorithm. Under EDiSt, compute nodes periodically share community assignments during inference. Due to this additional communication, EDiSt improves upon the divide-and-conquer algorithm by allowing it to scale out to a larger number of compute nodes without suffering from convergence issues, even on sparse graphs. We show that EDiSt provides speedups of up to 26.9× over the divide-and-conquer approach and speedups up to 44.0× over shared memory parallel SBP when scaled out to 64 compute nodes.en
dc.description.versionAccepted versionen
dc.format.extentPages 25-36en
dc.identifier.doihttps://doi.org/10.1109/CLUSTER52292.2023.00010en
dc.identifier.isbn9798350307924en
dc.identifier.issn1552-5244en
dc.identifier.orcidFeng, Wu-chun [0000-0002-6015-0727]en
dc.identifier.urihttps://hdl.handle.net/10919/118259en
dc.publisherIEEEen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleExact Distributed Stochastic Block Partitioningen
dc.title.serialProceedings - IEEE International Conference on Cluster Computing, ICCCen
dc.typeConference proceedingen
dc.type.otherConference Proceedingen
pubs.finish-date2023-11-03en
pubs.organisational-group/Virginia Techen
pubs.organisational-group/Virginia Tech/Engineeringen
pubs.organisational-group/Virginia Tech/Engineering/Computer Scienceen
pubs.organisational-group/Virginia Tech/Faculty of Health Sciencesen
pubs.organisational-group/Virginia Tech/All T&R Facultyen
pubs.organisational-group/Virginia Tech/Engineering/COE T&R Facultyen
pubs.start-date2023-10-31en

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Feng-Cluster23-EDist.pdf
Size:
676.25 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
License bundle
Now showing 1 - 1 of 1
Name:
license.txt
Size:
1.5 KB
Format:
Plain Text
Description: