Research

Clique Counting

Counting certain patterns in large search graphs is a computationally complex problem in graph mining. Cliques, graphs where all vertices are connected to each other, are an example of an important pattern with applications to social network analysis. At the time of this work, the state-of-the-art parallel algorithm did not scale well on large, sparse graphs with millions of vertices. After conducting experiments to find bottlenecks, I was able to change the data structure layout to become more memory-friendly and achieve near-linear parallel scaling. A more detailed description of our work is posted on arXiv.

Sparse Tensor Decompositions

Tensors are multi-dimensional arrays. Similar to Singular Value Decomposition (SVD) for matrices, tensors can be decomposed to reveal important data in the underlying structure. MTTKRP is the most computationally expensive step in the Alternating Least Squares algorithm for decomposing sparse tensors. We conducted different performance analyses to identify the bottlenecks of this kernel.