Sun receives NSF CAREER award for work on graph algorithms
Sun receives NSF CAREER award for work on graph algorithms Heading link
Assistant Professor Xiaorui Sun received a National Science Foundation (NSF) CAREER award, 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.
As an example, Sun said if you look at the whole of the internet, including all the different websites, it’s important to look at Google, Amazon, Netflix, and other large sites, because they connect with a lot of other users or edges. A niche blog writer with 17 followers wouldn’t be as essential.
“I want to focus on those key nodes so that I can understand what happens between them,” Sun said. “Then it’s much easier for me to understand what happens within the entire network.”
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.
Sun, who came to UIC in 2018, became interested in algorithm design during his PhD studies, noting that he likes to be at the intersection of theory, application, and practice.
The project, “On Non-Linear Graph Eliminations,” is receiving $560,962 and runs from February 2023 to January 2028.