Quickly finding a truss in a haystack

Oded Green, James Fox, Euna Kim, Federico Busato, Nicola Bombieri, Kartik Lakhotia, Shijie Zhou, Shreyas Singapura, Hanqing Zeng, Rajgopal Kannan, Viktor Prasanna, David Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2017 IEEE High Performance Extreme Computing Conference, HPEC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538634721
DOIs
StatePublished - Oct 30 2017
Externally publishedYes
Event2017 IEEE High Performance Extreme Computing Conference, HPEC 2017 - Waltham, United States
Duration: Sep 12 2017Sep 14 2017

Publication series

Name2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

Conference

Conference2017 IEEE High Performance Extreme Computing Conference, HPEC 2017
Country/TerritoryUnited States
CityWaltham
Period9/12/179/14/17

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Quickly finding a truss in a haystack'. Together they form a unique fingerprint.

Cite this