Parallel Jaccard and Related Graph Clustering Techniques
Author/Presenters
Event Type
Workshop
Algorithms
Exascale
Resiliency
SIGHPC Workshop
TimeMonday, November 13th12:30pm -
12:50pm
Location607
DescriptionWe propose to generalize Jaccard and related measures,
often used as similarity coefficients between two sets.
We define Jaccard, Dice-Sorensen and Tversky edge
weights on a graph and generalize them to account for
vertex weights. We develop an efficient parallel
algorithm for computing Jaccard edge and PageRank vertex
weights. We highlight that the weights computation can
obtain more than 10x speedup on the GPU versus CPU on
large realistic data sets. Also, we show that finding a
minimum balanced cut for modified weights can be related
to minimizing the sum of ratios of the intersection and
union of nodes on the boundary of clusters. Finally, we
show that the novel weights can improve the quality of
the graph clustering by about 15% and 80% for
multi-level and spectral graph partitioning and
clustering schemes, respectively.
