Recently, Applied Mathematics graduate student Alec Dunton and his team won the Graph Challenge as a part of his summer internship at Lawrence Livermore National Laboratory. The GraphChallenge, as explained on the challenge’s website, is a curated and open scalable graph analysis competition which “encourages community approaches to developing new solutions for analyzing graphs and sparse data derived from social media, sensor feeds, and scientific data to enable relationships between events to be discovered as they unfold in the field.” It has been a yearly fixture at the IEEE High Performance Extreme Computing (HPEC) conference since 2017, and solicits innovative advances to pressing problems such as counting subgraph isomorphisms and clustering streaming graphs.
Alec’s team, composed of Benjamin W. Priest (Postdoctoral Researcher, Lawrence Livermore National Laboratory) and Geoffrey Sanders (APPM PhD Alumnus), published the winning paper (titled: Scaling Graph Clustering with Distributed Sketches) in which the team proposes “a graph clustering algorithm which circumvents scalability issues inherent in traditional methods such as spectral clustering.” The underlying goal of the challenge was to identify optimal clusters in a large graph stored in distributed memory. In order to achieve this, Alec explains:
“The unsupervised learning of community structure is a canonical, well studied problem in graph analysis. Our contribution is an algorithm which utilizes random projection to produce embeddings which achieve performant clustering results for fully-dynamic streaming graph models. Instead of relying on an expensive eigendecomposition computation as in spectral clustering approaches, we use the fast Johnson-Lindenstrauss and CountSketch transforms directly to embed a graph-dependent matrix. These linear dimension reduction approaches, used in tandem with the nonlinear embedding algorithm UMAP, produce low dimensional representations which enable efficient clustering of large-scale graphs. Our method could significantly improve graph clustering performance in distributed memory.”
The Department congratulates Alec on this impressive achievement!