Research to simplify big data graphs earns Best Paper Award at IEEE SSP 2023

Research by PhD student Neophytos Charalambides and Professor Alfred Hero addresses computational and storage bottlenecks for graphs used in statistical problems, signal processing, large networks, combinatorial optimization, and data analysis.
Neophytos Charalambides
Neophytos Charalambides.

ECE PhD student Neophytos Charalambides won a Best Paper Award at the 22nd IEEE Statistical Signal Processing Workshop (SSP).

Charalambides’ research focused on large graphs, which are common in applications of modern signal processing, statistics, engineering, and combinatorial optimization. These graphs can be particularly dense in modern applications, which causes both computational and storage bottlenecks. This problem can be addressed by working with a good approximation or sketch of the graph.

Spectral graph theory develops algorithms to approximate these large graphs, known as “sparsifying graphs” or “spectral sparsification.” Charalambides specifically used Randomized Numerical Linear Algebra (RandNLA) and Approximate Matrix Multiplication, to develop an intuitive and simple algorithm that is simpler and more effective than other similar sparsification algorithms.

The paper, “Graph Sparsification by Approximate Matrix Multiplication,” was co-authored by his advisor, Alfred Hero, the John H. Holland Distinguished University Professor of EECS and R. Jamison and Betty Williams Professor of Engineering. This work was conducted during Greg Bodwin’s course on the topic, who also helped at the initial stages.