Stevens Professor Plots Better Ways to Analyze Trillion-Edge Graph Data

Cutting-edge research is what drew Hang Liu to Stevens Institute of Technology in 2019. Today, the assistant professor in the Department of Electrical and Computer Engineering and leader of the High-Performance Data Analytics (HPDA) lab at Stevens is on the edge of his own breakthroughs as he works to improve analysis of trillion-edge graphs.

Liu’s research focuses on high-performance data analytics, which involves using computers to find patterns and insights in massive chunks of information. The goal is to quickly, efficiently, and effectively analyze trillion-edge graphs representing anything from social networks to genomics to product reviews to GPS directions.

So what is a trillion-edge graph? In the mathematical arena, a graph simply shows how things are connected. The things being considered are points on the graph, and the edges are the lines extending from those points to indicate relationships, or connections, to other points. And in our complicated world, anything from the possible relationships between people worldwide to the combinations of airports and incoming flights could potentially have trillions of connections, or edges.“Most of us have recommended two of our friends to also become friends,” Liu explained. “Now imagine you have an entire social network in your hand—how could you instantly make correct friend recommendations for all the users? As the size continues to grow, the process of learning, mining, and computing such gigantic graphs becomes ineffective, impractical, and potentially dire.”

To address that dilemma, he’s aiming to build a system that can quickly analyze and extract insights from trillion-edge graphs of data. It’s the topic of the research he’s undertaking in his recent National Science Foundation (NSF) CAREER project. An award of $584,001 was granted for his five-year project, "An Algorithm and System Co-Designed Framework for Graph Sampling and Random Walk on Graphics Processing Units (GPUs).” Liu will be pioneering the effort to create a user-friendly framework that can take advantage of future exascale-level supercomputers—that’s a computer that can perform a billion-billion operations per second.

“My CAREER project research will introduce novel algorithms, a scalable software system currently in development, and an expressive application programming interface for users to solve some of today’s biggest and most complicated questions with fewer lines of code.”

Liu tuned in early to making hardware easier and software more powerful

Solving complex problems is nothing new for Liu, whose first scientific research project involved a mission for higher-quality entertainment. “When I was a child, one of my neighbors bought a color television with more channels than we had,” he recalled. “I suspected it was because of the antenna, so I made my own. I tried different metals, and it turned out aluminum wires worked the best. I tried to mimic the shape of my neighbor’s antenna, and I cut a tall bamboo to lift it higher to receive more signals. Although the number of channels was still limited, it gave me better video quality.”

That experiment sparked Liu’s ongoing interest in electrical and computer engineering.

“Some logic, defined by the software, can be translated to action, performed by the hardware,” he said. “This is both very fascinating and very practically useful! Further, because the junction between software and hardware can always be complex, it offers me a big playground to explore, learn, and enjoy. At Stevens, I love that we have experts for a wide range of topics, ranging from circuits to applications, who are always willing to collaborate and offer constructive experience.”

Through the CAREER award funding, richer data insights are in sight

Liu has already made progress, which was showcased in November 2020 at the technical computing community’s flagship event, The International Conference for High Performance Computing, Networking, Storage and Analysis.

Working on his CAREER project with a Ph.D. student and an undergraduate student, Liu will continue to integrate and innovate upon his previous research on graph sampling and random walk methods to dramatically reduce the size of the graph and the power required to analyze the data. His research will accommodate both existing known algorithms and potentially future unknown ones, redesigning the sampling algorithms to use GPU hardware in brand new—and better—ways.

“With the help of emerging high-performance hardware and novel approaches to the powerful software,” he said, “we’re working to help academics, researchers, and industry leaders address the grand challenges of our time, such as designing extremely large-scale integrated circuits, uncovering software vulnerabilities, and even understanding the spread of pandemics.”