TY - GEN

T1 - Quickly finding a truss in a haystack

AU - Green, Oded

AU - Fox, James

AU - Kim, Euna

AU - Busato, Federico

AU - Bombieri, Nicola

AU - Lakhotia, Kartik

AU - Zhou, Shijie

AU - Singapura, Shreyas

AU - Zeng, Hanqing

AU - Kannan, Rajgopal

AU - Prasanna, Viktor

AU - Bader, David

N1 - Publisher Copyright:
© 2017 IEEE.

PY - 2017/10/30

Y1 - 2017/10/30

N2 - The k-truss of a graph is a subgraph such that each edge is tightly connected to the remaining elements in the k-truss. The k-truss of a graph can also represent an important community in the graph. Finding the k-truss of a graph can be done in a polynomial amount of time, in contrast finding other subgraphs such as cliques. While there are numerous formulations and algorithms for finding the maximal k-truss of a graph, many of these tend to be computationally expensive and do not scale well. Many algorithms are iterative and use static graph triangle counting in each iteration of the graph. In this work we present a novel algorithm for finding both the k-truss of the graph (for a given k), as well as the maximal k-truss using a dynamic graph formulation. Our algorithm has two main benefits. 1) Unlike many algorithms that rerun the static graph triangle counting after the removal of non-conforming edges, we use a new dynamic graph formulation that only requires updating the edges affected by the removal. As our updates are local, we only do a fraction of the work compared to the other algorithms. 2) Our algorithm is extremely scalable and is able to concurrently detect deleted triangles in contrast to past sequential approaches. While our algorithm is architecture independent, we show a CUDA based implementation for NVIDIA GPUs. In numerous instances, our new algorithm is anywhere from 100X-10000X faster than the Graph Challenge benchmark. Furthermore, our algorithm shows significant speedups, in some cases over 70X, over a recently developed sequential and highly optimized algorithm.

AB - The k-truss of a graph is a subgraph such that each edge is tightly connected to the remaining elements in the k-truss. The k-truss of a graph can also represent an important community in the graph. Finding the k-truss of a graph can be done in a polynomial amount of time, in contrast finding other subgraphs such as cliques. While there are numerous formulations and algorithms for finding the maximal k-truss of a graph, many of these tend to be computationally expensive and do not scale well. Many algorithms are iterative and use static graph triangle counting in each iteration of the graph. In this work we present a novel algorithm for finding both the k-truss of the graph (for a given k), as well as the maximal k-truss using a dynamic graph formulation. Our algorithm has two main benefits. 1) Unlike many algorithms that rerun the static graph triangle counting after the removal of non-conforming edges, we use a new dynamic graph formulation that only requires updating the edges affected by the removal. As our updates are local, we only do a fraction of the work compared to the other algorithms. 2) Our algorithm is extremely scalable and is able to concurrently detect deleted triangles in contrast to past sequential approaches. While our algorithm is architecture independent, we show a CUDA based implementation for NVIDIA GPUs. In numerous instances, our new algorithm is anywhere from 100X-10000X faster than the Graph Challenge benchmark. Furthermore, our algorithm shows significant speedups, in some cases over 70X, over a recently developed sequential and highly optimized algorithm.

UR - http://www.scopus.com/inward/record.url?scp=85041212490&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041212490&partnerID=8YFLogxK

U2 - 10.1109/HPEC.2017.8091038

DO - 10.1109/HPEC.2017.8091038

M3 - Conference contribution

AN - SCOPUS:85041212490

T3 - 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

BT - 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

Y2 - 12 September 2017 through 14 September 2017

ER -