Abstract
This paper introduces and analyzes the Triangle-Densest-$k$-Subgraph (TDkS) problem, which aims to find a subset of $k$ nodes in a graph that maximizes the number of induced triangles. While identifying dense subgraphs is a fundamental task in graph mining, the transition from edge-based density to higher-order motifs like triangles introduces significant computational complexity. We prove that TDkS is NP-hard and exhibits a higher degree of approximation difficulty compared to the standard Densest-$k$-Subgraph (DkS) problem. To address this, we utilize submodular optimization and the Lovász extension, deriving a closed-form analytical expression that enables efficient continuous relaxation. Our proposed Mirror Descent algorithm demonstrates superior performance on diverse real-world datasets and proves effective in a novel document summarization application.
Introduction
Traditional graph mining techniques often rely on edge density to identify cohesive communities. However, pairwise connections frequently fail to capture the complex, higher-order structures inherent in social, biological, and information networks. Triangles, representing the simplest non-trivial clique, serve as a much stronger indicator of community cohesion.
The Triangle-Densest-$k$-Subgraph (TDkS) problem addresses the need for finding small, highly-interconnected clusters by imposing a size constraint $k$ on the triangle-density maximization. While the unconstrained Densest Subgraph problem is solvable in polynomial time, the addition of the size constraint $k$ renders it NP-hard. The shift from edges to triangles further exacerbates this hardness, necessitating sophisticated algorithmic strategies.
Methodology
Our approach leverages the mathematical properties of submodular functions to develop a scalable optimization framework.
Submodularity and the Lovász Extension
We observe that the function $f(S)$ counting the number of triangles induced by a node set $S$ is submodular. This property allows us to utilize the Lovász extension, a continuous convex function that acts as a bridge between discrete and continuous optimization. Minimizing the Lovász extension over a convex set provides a principled relaxation for the discrete TDkS problem.
Analytical Breakthrough and Mirror Descent
A key contribution of this work is the derivation of a closed-form analytical expression for the Lovász extension of the triangle-counting function. This eliminates the need for the computationally expensive greedy sorting typically required in each iteration of submodular optimization.
To solve the resulting optimization problem, we employ a Mirror Descent (MD) algorithm using Kullback-Leibler (KL) divergence. This choice is motivated by the geometry of the problem; unlike standard Euclidean Gradient Descent, Mirror Descent with KL divergence achieves a convergence rate that scales logarithmically with the number of nodes $n$, making it suitable for massive graphs.
Experimental Evaluation
We evaluated the proposed Mirror Descent approach against several state-of-the-art baselines on diverse real-world datasets, including biological (PPI-Human), social (Facebook), web (Stanford, Google), and infrastructure (CAIDA) networks.
Key Results
As shown in Figure 1, the Mirror Descent (MD + Proj.) algorithm consistently identifies subgraphs with higher triangle density than edge-based DkS methods across all tested datasets. For smaller subgraph sizes ($k \le 100$), the algorithm frequently reaches the theoretical upper bound, indicating that it finds near-optimal solutions.
An important finding is the "50% threshold": when the edge density of a graph falls below 50%, triangle-based methods become markedly more effective at uncovering latent structure than edge-based counterparts. This aligns with theoretical predictions from Turán’s theorem regarding the existence of cliques in sparse graphs.
Application: Document Summarization
Beyond traditional graph mining, we applied TDkS to document summarization by constructing "graph-of-words" models. In this context, nodes represent words and triangles represent tri-gram co-occurrences. TDkS successfully extracted thematic, descriptive terms that formed more coherent and human-readable summaries compared to edge-based methods, which tended to select more generic vocabulary.
Conclusion
The TDkS problem offers a powerful framework for identifying cohesive structures in complex networks. By combining submodular optimization with an efficient Mirror Descent algorithm, we provide a scalable solution that overcomes the inherent hardness of the problem. Future work will explore extending this framework to even higher-order motifs, such as 4-cliques or specific network motifs, to further enhance our ability to summarize and analyze large-scale graph data.
Summary updated