New algorithm advances graph mining for complex networks

Good news! From pairwise to triwise comparisons! Two is a company, three is a crowd! 😊

"... 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," ... "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. ..."

From the abstract:

"We introduce the triangle-densest-k-subgraph problem (TDkS) for undirected graphs: given a size parameter k, compute a subset of k vertices that maximizes the number of induced triangles. The problem corresponds to the simplest generalization of the edge-based densest-k-subgraph problem (DkS) to the case of higher-order network motifs. We prove that TDkS is NP-hard and is not amenable to efficient approximation, in the worst-case. By judiciously exploiting the structure of the problem, we propose a relaxation algorithm for the purpose of obtaining high-quality, sub-optimal solutions. Our approach utilizes the fact that the cost function of TDkS is submodular to construct a convex relaxation for the problem based on the Lovasz extension for submodular functions. We ´ demonstrate that our approaches attain state-of-the-art performance on real-world graphs and can offer substantially improved exploration of the optimal density-size curve compared to sophisticated approximation baselines for DkS. We use document summarization to showcase why TDkS is a useful generalization of DkS"

New algorithm advances graph mining for complex networks "... has introduced a breakthrough in graph mining with the development of a new computational algorithm."

Mining Triangle-Dense Subgraphs of a Fixed Size: Hardness, Lovasz extension and ´ Applications (no public access)