New algorithm advances graph mining for complex networks

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

Graph mining, a method of analyzing networks such as 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, called dense triangle subgraphs, within large networks, a critical problem in fields such as fraud detection, computational biology and data analysis.

The research, published in IEEE Transactions on Knowledge and Data Engineeringwas a collaboration led by Aritra Konar, 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 communicate frequently on social media. However, the researchers’ new method, known as the Triangle-Densest-k-Subgraph problem, goes a step further by examining connecting triangles, groups of three points where each pair is linked. This approach captures closer relationships, like small groups of friends that all interact with each other, or groups of genes that work together in biological processes.

“Our method is not limited to single connections, but also considers how groups of three elements interact, which is crucial for understanding more complex networks,” explained Sidiropoulos, 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 particularly challenging because it is difficult to solve them efficiently with traditional methods. But the new algorithm uses something called submodular relaxation, a clever shortcut that simplifies the problem just enough to make it faster to solve without losing important details.

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