AWARD    2017 Graph Challenge Student Innovation Award

Date released: August 7, 2017

  •  AWARD    2017 Graph Challenge Student Innovation Award
  • Date:

    August 4, 2017

  • Awarded to:

    David Zhuzhunashvili and Andrew Knyazev

  • Description:

    David Zhuzhunashvili, an undergraduate student at UC Boulder, Colorado, and Andrew Knyazev, Distinguished Research Scientist at MERL, received the 2017 Graph Challenge Student Innovation Award. Their poster "Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge" was accepted to the 2017 IEEE High Performance Extreme Computing Conference (HPEC '17), taking place 12-14 September 2017 (http://www.ieee-hpec.org/), and the paper was accepted to the IEEE Xplore HPEC proceedings.

    HPEC is the premier conference in the world on the convergence of High Performance and Embedded Computing. DARPA/Amazon/IEEE Graph Challenge is a special HPEC event. Graph Challenge encourages community approaches to developing new solutions for analyzing graphs derived from social media, sensor feeds, and scientific data to enable relationships between events to be discovered as they unfold in the field. The 2017 Streaming Graph Challenge is Stochastic Block Partition. This challenge seeks to identify optimal blocks (or clusters) in a larger graph with known ground-truth clusters, while performance is evaluated compared to baseline Python and C codes, provided by the Graph Challenge organizers.

    The proposed approach is spectral clustering that performs block partition of graphs using eigenvectors of a matrix representing the graph. Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) method iteratively approximates a few leading eigenvectors of the symmetric graph Laplacian for multi-way graph partitioning. Preliminary tests for all static cases for the Graph Challenge demonstrate 100% correctness of partition using any of the IEEE HPEC Graph Challenge metrics, while at the same time also being approximately 500-1000 times faster compared to the provided baseline code, e.g., 2M static graph is 100% correctly partitioned in ~2,100 sec. Warm-starts of LOBPCG further cut the execution time 2-3x for the streaming graphs.

  • External Link:

    http://graphchallenge.mit.edu/champions

  • Research Area:

    Machine Learning