The Triangle-Densest-K-Subgraph Problem: Hardness, Lovász Extension, and Application to Document Summarization

Authors

  • Aritra Konar University of Virginia
  • Nicholas D. Sidiropoulos University of Virginia

DOI:

https://doi.org/10.1609/aaai.v36i4.20325

Keywords:

Data Mining & Knowledge Management (DMKM)

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 Lovász 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.

Downloads

Published

2022-06-28

How to Cite

Konar, A., & Sidiropoulos, N. D. (2022). The Triangle-Densest-K-Subgraph Problem: Hardness, Lovász Extension, and Application to Document Summarization. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4), 4075-4082. https://doi.org/10.1609/aaai.v36i4.20325

Issue

Section

AAAI Technical Track on Data Mining and Knowledge Management