NSF CAREER Award

MIE graduate student Rukmava Chatterjee in professor Sushant Anand's research lab.
College of Engineering/Jim Young

Assistant Professor Xiaorui Sun received a National Science Foundation (NSF) CAREER award this year, the most prestigious award in support of early-career faculty, to develop faster graph algorithms crucial to machine learning, data mining, and computational biology, through a process known as graph sparsification.

Graphs are widely used to model data in many fields, such as the study of social networks, human brain neuron systems, and in deep neural networks. As the size of graphs increase, tracking how these graphs change and grow is essential.

“Graph algorithms play a central role in understanding graph structures,” Sun said. “In the big data era, the amount of data supplied is unbelievable – information used to double in a few years, now it’s happening in a few weeks or a few days.”

From an algorithm design aspect, traditional graph algorithms are not efficient enough to handle this explosion of data. Also, this huge amount of data cannot be stored in a single machine or place, it’s stored in a distributed way, all over the world, creating additional challenges for graph algorithms.

 

Sun uses a technique called the sparsification of the graphs, which aims to compress the graph from one to another graph with fewer vertices and edges but maintains the key features of the original graph so that the computation performed under the small graph still generates meaningful results.

Reducing the size of the graph algorithm is nonlinear: a targeted approach must be used to pare down the information to what’s important. Sun is using nonlinear graph eliminations to achieve this. He uses two different techniques: edge sparsification, which keeps all the vertices of the original graph, but makes the number of edges smaller, and vertex sparsification, to reduce the number of vertices and edges in the graph.

Sun wants to advance graph sparsification as a new paradigm of graph algorithms and provide new sparsification-based software for graph problems crucial to machine learning, data mining, and computational biology.