Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with Quality Guarantees

Finding dense subgraphs is an important graph-mining task with many applications. Given that the direct optimization of edge density is not meaningful, as even a single edge achieves maximum density