New algorithm advances graph mining for complex networks

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.