HXHelen Xu

Helen Xu

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Helen Xu has a total of 15 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    pdGRASS: A Fast Parallel Density-Aware Algorithm for Graph Spectral Sparsification

    by Tiancheng Zhao, Zekun Yin, Huihai An, Xiaoyu Yang, Zhou Jin, Jiasi Shen, Helen Xu

    Graph Spectral Sparsification (GSS) identifies an ultra-sparse subgraph, or sparsifier, whose Laplacian matrix closely approximates the spectral properties of the original graph, enabling substantial reductions in computational complexity for computationally intensive problems in scientific computing. The state-of-the-art method for efficient GSS is feGRASS, consisting of two steps: 1) spanning tree generation and 2) off-tree edge recovery. However, feGRASS suffers from two main issues: 1) difficulties in parallelizing the recovery step for strict data dependencies, and 2) performance degradation on skewed inputs, often requiring multiple passes to recover sufficient edges. To address these challenges, we propose parallel density-aware Graph Spectral Sparsification (pdGRASS), a parallel algorithm that organizes edges into disjoint subtasks without data dependencies between them, enabling efficient parallelization and sufficient edge recovery in a single pass. We empirically evaluate feGRASS and pdGRASS based on 1) off-tree edge-recovery runtime and 2) sparsifier quality, measured by the iteration count required for convergence in a preconditioned conjugate gradient (PCG) application. The evaluation demonstrates that, depending on the number of edges recovered, pdGRASS achieves average speedups ranging from 3.9x to 8.8x. The resulting sparsifiers also show between 1.2x higher and 1.8x lower PCG iteration counts, with further improvements as more edges are recovered. Additionally, pdGRASS mitigates the worst-case runtimes of feGRASS with over 1000x speedup. These results highlight pdGRASS's significant improvements in scalability and performance for the graph spectral sparsification problem.

  • Open Access

    Improving SpGEMM Performance Through Matrix Reordering and Cluster-wise Computation

    by Abdullah Al Raqibul Islam, Helen Xu, Dong Dai, Aydın Buluç

    Sparse matrix-sparse matrix multiplication (SpGEMM) is a key kernel in many scientific applications and graph workloads. Unfortunately, SpGEMM is bottlenecked by data movement due to its irregular memory access patterns. Significant work has been devoted to developing row reordering schemes towards improving locality in sparse operations, but prior studies mostly focus on the case of sparse-matrix vector multiplication (SpMV). In this paper, we address these issues with hierarchical clustering for SpGEMM that leverages both row reordering and cluster-wise computation to improve reuse in the second input (B) matrix with a novel row-clustered matrix format and access pattern in the first input (A) matrix. We find that hierarchical clustering can speed up SpGEMM by 1.39x on average with low preprocessing cost (less than 20x the cost of a single SpGEMM on about 90% of inputs). Furthermore, we decouple the reordering algorithm from the clustered matrix format so they can be applied as independent optimizations. Additionally, this paper sheds light on the role of both row reordering and clustering independently and together for SpGEMM with a comprehensive empirical study of the effect of 10 different reordering algorithms and 3 clustering schemes on SpGEMM performance on a suite of 110 matrices. We find that reordering based on graph partitioning provides better SpGEMM performance than existing alternatives at the cost of high preprocessing time. The evaluation demonstrates that the proposed hierarchical clustering method achieves greater average speedup compared to other reordering schemes with similar preprocessing times.

  • Open Access

    BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers

    by Brian Wheatman, Xiaojun Dong, Zheqi Shen, Laxman Dhulipala, Jakub Łącki, Prashant Pandey, Helen Xu

    A fundamental building block in any graph algorithm is a graph container - a data structure used to represent the graph. Ideally, a graph container enables efficient access to the underlying graph, has low space usage, and supports updating the graph efficiently. In this paper, we conduct an extensive empirical evaluation of graph containers designed to support running algorithms on large graphs. To our knowledge, this is the first apples-to-apples comparison of graph containers rather than overall systems, which include confounding factors such as differences in algorithm implementations and infrastructure. We measure the running time of 10 highly-optimized algorithms across over 20 different containers and 10 graphs. Somewhat surprisingly, we find that the average algorithm running time does not differ much across containers, especially those that support dynamic updates. Specifically, a simple container based on an off-the-shelf B-tree is only 1.22x slower on average than a highly optimized static one. Moreover, we observe that simplifying a graph-container Application Programming Interface (API) to only a few simple functions incurs a mere 1.16x slowdown compared to a complete API. Finally, we also measure batch-insert throughput in dynamic-graph containers for a full picture of their performance. To perform the benchmarks, we introduce BYO, a unified framework that standardizes evaluations of graph-algorithm performance across different graph containers. BYO extends the Graph Based Benchmark Suite (Dhulipala et al. 18), a state-of-the-art graph algorithm benchmark, to easily plug into different dynamic graph containers and enable fair comparisons between them on a large suite of graph algorithms. While several graph algorithm benchmarks have been developed to date, to the best of our knowledge, BYO is the first system designed to benchmark graph containers