Abstract: We introduce the triangle-densest-$k$-subgraph problem (TD$k$S) 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 (D$k$S) to the case of higher-order network motifs. We prove that TD$k$S 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 TD$k$S is submodular to construct a convex relaxation for the problem based on the Lov\'asz 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 D$k$S. We use document summarization to showcase why TD$k$S is a useful generalization of D$k$S.