HotCSE Seminar
Computational Science & Engineering
Wednesday Oct 04, 12pm-1pm, 1116-E Klaus

Finding a k-Truss: Fast and Scalable Subgraph Isomorphism using Dynamic Graph Techniques

James Fox
Advisor: Prof. David Bader


Finding well-connected subgraphs is a common graph analysis goal. However, well-known formulations such as the k-Clique are computationally intractable and often too restrictive. The k-Truss of a graph is defined in terms of minimal triangle counts, and is computationally tractable. We present a novel algorithm and scalable implementation for finding the k-Truss of a graph, by combining dynamic graph data structure with dynamic triangle counting techniques. Our approach won an Innovation Award for the DARPA-HIVE GraphChallenge, and performs anywhere from 100x to 10000x faster than GraphChallenge baseline benchmarks.


James Fox is a 2nd year Ph.D. student in CS, advised by Dr. David Bader. He earned his bachelor’s degree in CS at UC Berkeley. His research interests are currently in applying HPC towards large-scale graph analytics.