BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20230124T171525Z
LOCATION:C141-143-149
DTSTART;TZID=America/Chicago:20221116T133000
DTEND;TZID=America/Chicago:20221116T140000
UID:submissions.supercomputing.org_SC22_sess145_pap248@linklings.com
SUMMARY:ProbGraph: High-Performance and High-Accuracy Graph Mining with Pr
obabilistic Set Representations
DESCRIPTION:Paper\n\nProbGraph: High-Performance and High-Accuracy Graph M
ining with Probabilistic Set Representations\n\nBesta, Miglioli, Sylos Lab
ini, Tětek, Iff...\n\nImportant graph mining problems such as Clustering a
re computationally demanding. To significantly accelerate these problems,
we propose ProbGraph: a graph representation that enables simple and fast
approximate parallel graph mining with strong theoretical guarantees on wo
rk, depth, and result accuracy. The key idea is to represent sets of verti
ces using probabilistic set representations such as Bloom filters. These r
epresentations are much faster to process than the original vertex sets th
anks to vectorizability and small size. We use these representations as bu
ilding blocks in important parallel graph mining algorithms such as Clique
Counting or Clustering. When enhanced with ProbGraph, these algorithms si
gnificantly outperform tuned parallel exact baselines (up to nearly 50x on
32 cores) while ensuring accuracy of more than 90% for many input graph d
atasets. Our novel bounds and algorithms based on probabilistic set repres
entations with desirable statistical properties are of separate interest f
or the data analytics community.\n\nSession Format: Recorded\n\nTag: Big D
ata, Computational Science\n\nRegistration Category: Tech Program Reg Pass
\n\nAward Finalist: Best Paper Finalist\n\nReproducibility Badges: Artifac
t Available, Artifact Functional, Results Reproduced
END:VEVENT
END:VCALENDAR