# Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling

arXiv: https://arxiv.org/abs/2306.04884 · HTML: https://mlsanity.com/paper/2306.04884/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 53 references that are in the map.
- First posted on arXiv 8 Jun 2023.

## Builds on (most cited first, 12 of 12)

- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering](https://mlsanity.com/paper/1712.05825/) (2017)
- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Scalable Community Detection via Parallel Correlation Clustering](https://mlsanity.com/paper/2108.01731/) (2021)
- [On the Relation of Strong Triadic Closure and Cluster Deletion](https://mlsanity.com/paper/1803.00807/) (2018)
- [Correlation Clustering Generalized](https://mlsanity.com/paper/1809.09493/) (2018)
- [Learning Resolution Parameters for Graph Clustering](https://mlsanity.com/paper/1903.05246/) (2019)
- [From acquaintance to best friend forever: robust and fine-grained inference of social tie strengths](https://mlsanity.com/paper/1802.03549/) (2018)
- [Inferring Tie Strength in Temporal Networks](https://mlsanity.com/paper/2206.11705/) (2022)

## Built on by (most cited first, 2 of 2)

- [Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better](https://mlsanity.com/paper/2404.16131/) (2024)
- [Inductive Correlation Clustering with Graph Neural Networks](https://mlsanity.com/paper/2608.27153/) (2026)

## Abstract (arXiv)

Graph clustering is a fundamental task in network analysis where the goal is to detect sets of nodes that are well-connected to each other but sparsely connected to the rest of the graph. We present faster approximation algorithms for an NP-hard parameterized clustering framework called LambdaCC, which is governed by a tunable resolution parameter and generalizes many other clustering objectives such as modularity, sparsest cut, and cluster deletion. Previous LambdaCC algorithms are either heuristics with no approximation guarantees, or computationally expensive approximation algorithms. We provide fast new approximation algorithms that can be made purely combinatorial. These rely on a new parameterized edge labeling problem we introduce that generalizes previous edge labeling problems that are based on the principle of strong triadic closure and are of independent interest in social network analysis. Our methods are orders of magnitude more scalable than previous approximation algorithms and our lower bounds allow us to obtain a posteriori approximation guarantees for previous heuristics that have no approximation guarantees of their own.