Research map / Learning theory and algorithms / Clustering

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability

ICML 2025 · Learning theory and algorithms › Clustering · approach: Correlation clustering

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces a cost function for hierarchical overlapping clustering (HOC) on graphs, proves approximation guarantees for a local-search recursive 2-OC bipartition algorithm, and proposes a scalable speed-up variant evaluated on synthetic OSBM graphs and SNAP datasets.

Problem

Hierarchical overlapping clustering on graphs lacks a principled cost function for evaluating hybrid structures where clusters are both nested and overlapping, and existing overlapping methods are either non-hierarchical or not scalable.

Approach

Extends Dasgupta's HC cost to HOC graphs (DAGs) by replacing LCA with minimal common ancestor sets weighted by node-to-node and edge-to-node belonging factors; solves recursive overlapping bipartitions with a hyper-parameter-free local search (2-OC) with a constant-factor guarantee for the dual problem.

Key results

• On OSBM graphs with k=4, the speed-up k-HOC algorithm achieves NMI almost 1.0 on dense graphs and above 0.95 on sparse graphs at both hierarchy levels.
• On Youtube (~1.13M nodes, ~3M edges), the speed-up algorithm runs in under 12 minutes on a personal computer, about 20% of cm+improve's runtime on a server cluster.
• Algorithm 1 achieves approximation factor 2/3*sqrt(6) - Θ((1+ε)/n) for the dual 2-OC problem, and Algorithm 2 extends this guarantee to dual k-HOC.

Measured effects reported in the paper

Surprising findings

• The trivial solution treating each edge's endpoints as a cluster achieves the minimum cost 2w(E), so the cost function needs width constraints to be meaningful.

Limitations

• Worst-case algorithm O(eps^-1 n^4 log m) is not efficient in practice, motivating heuristic speed-up without guarantees.
• Primal approximation guarantee only given for 2-OC, with factor depending on dmax/davg; no primal guarantee for k>2.
• OHC'20 and cm+improve baselines required modifications and cm+improve hyperparameters were only mildly tuned.

Experimental setup

Datasets: Amazon Youtube DBLP

Benchmarks: OSBM synthetic graphs Amazon Youtube DBLP

Metrics: NMI for overlapping clustering runtime HOC cost

Baselines: Dasgupta OHC'20 cm+improve

Builds on: Dasgupta cost function Moseley and Wang dual cost cm+improve (Orecchia et al., 2022) OHC'20 (Jeantet et al., 2020) overlapping modularity belonging factor (Nicosia et al., 2009)

Closest papers by meaning

• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs (NeurIPS 2021 · similarity 0.92)
• Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs (ICML 2023 · similarity 0.90)
• Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.89)
• Online Sparsification of Bipartite-Like Clusters in Graphs (ICML 2025 · similarity 0.88)
• New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.88)
• A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.87)