CAREER: An Algorithm and System Co-Designed Framework for Graph Sampling and Random Walk on GPUs

Graph analytics is one of the key technologies to address the grand challenges of our time, such as understanding the spread of pandemics, designing extremely large-scale integrated circuits and uncovering software vulnerabilities among many others. However, as the size of the graph continues to grow, learning, mining and computing such gigantic graphs become ineffective, impractical, and potentially dire.

Fortunately, Graph Sampling and Random Walk can dramatically reduce the size of the original graphs, while still capturing the desired properties for downstream graph analytics tasks. But a comprehensive system that can perform graph sampling and random walk on real-world trillion-edge graphs at an acceptable speed is absent. This research pioneers the effort of uniting various graph sampling and random walk algorithms behind a user-friendly framework that can take advantage of world-class Graphics Processing Unit (GPU) computing facilities, including the future exascale ones, to rapidly handle trillion-edge graphs.

This project contributes to the U.S. national goal of increasing participation in science and engineering, which is crucial to America’s success in addressing global challenges, building a stronger and more diversified workforce, and meeting the needs of the global innovation economy. This project produces a high-performance software library that serves as a foundational tool for fellow science and engineering practitioners from academia, national laboratories and industry.

With a commitment to helping K-12, undergraduate, female, and Underrepresented Minority (URM) populations in the Science, Technology, Engineering, and Mathematics (STEM) field through the interesting investment and rewarding education plan, this project lays out a comprehensive road map to prepare the next-generation high-performance graph analytics professional workers and researchers. This project revamps and creates core courses in both graduate and undergraduate levels for the PI's home department.

To benefit the society at large, this project disseminates the project data, software, and publications to the broader research community at http://personal.stevens.edu/~hliu77/gsrw.html.

The overarching goal of this research is to make graph sampling and random walk fast, scalable and user-friendly. Towards that end, this career proposal advocates algorithm and system co-designed researches. First, this research introduces novel update and construction designs for transition probability of various major Monte Carlo methods that are essential for fast sampling.

Second, to fully unleash the potential of GPUs, this project formulates the key primitive into problems that can take advantage of general, and reserved tensor and ray tracing cores on GPUs. Third, based upon the asynchronous processing nature of graph sampling and random walk, this research exploits Remote Direct Memory Access (RDMA)-assisted task and partition adaptive scheduling mechanism to reduce the data transfers for scalable trillion-edge graph sampling and random walk.

Last but not the least, this career research delivers a bias-centric framework, which offers end users expressiveness to program not only a variety of exiting GSRW algorithms but also future ones, and simplicity by hiding the aforementioned advanced optimization techniques.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.