UVA professor tackles graph mining challenges with new algorithm

University of Virginia School of Engineering and Applied Science professor Nikolaos Sidiropoulos has introduced a breakthrough in graph mining with the development of a new computational algorithm. 

Graph mining, a method of analyzing networks like social media connections or biological systems, helps researchers discover meaningful patterns in how different elements interact. The new algorithm addresses the long-standing challenge of finding tightly connected clusters, known as triangle-dense subgraphs, within large networks — a problem that is critical in fields such as fraud detection, computational biology and data analysis.

The research, published in IEEE Transactions on Knowledge and Data Engineering, was a collaboration led by Aritra Konar, an assistant professor of electrical engineering at KU Leuven in Belgium who was previously a research scientist at UVA.

Graph mining algorithms typically focus on finding dense connections between individual pairs of points, such as two people who frequently communicate on social media. However, the researchers’ new method, known as the Triangle-Densest-k-Subgraph problem, goes a step further by looking at triangles of connections — groups of three points where each pair is linked. This approach captures more tightly knit relationships, like small groups of friends who all interact with each other, or clusters of genes that work together in biological processes.

"Our method doesn’t just look at single connections but considers how groups of three elements interact, which is crucial for understanding more complex networks," explained Sidiropoulos, a professor in the Department of Electrical and Computer Engineering. "This allows us to find more meaningful patterns, even in massive datasets."

Finding triangle-dense subgraphs is especially challenging because it’s difficult to solve efficiently with traditional methods. But the new algorithm uses what’s called submodular relaxation, a clever shortcut that simplifies the problem just enough to make it quicker to solve without losing important details. 

This breakthrough opens new possibilities for understanding complex systems that rely on these deeper, multi-connection relationships. Locating subgroups and patterns could help uncover suspicious activity in fraud, identify community dynamics on social media, or help researchers analyze protein interactions or genetic relationships with greater precision. 

About UVA Engineering: As part of the top-ranked, comprehensive University of Virginia, UVA Engineering is one of the nation’s oldest and most respected engineering schools. Our mission is to make the world a better place by creating and disseminating knowledge and by preparing future engineering leaders. Outstanding students and faculty from around the world choose UVA Engineering because of our growing and internationally recognized education and research programs. UVA is the No. 1 public engineering school in the country for the percentage of women graduates, among schools with at least 75 degree earners; among the top engineering schools in the United States for the four-year graduation rate of undergraduate students; and among the top-growing public engineering schools in the country for the rate of Ph.D. enrollment growth. Our research program has grown by 95% since 2016. Learn more at engineering.virginia.edu.