# GASP, a generalized framework for agglomerative clustering of signed graphs and its application to Instance Segmentation

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2019.

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

- [Unsupervised Video Object Segmentation via Prototype Memory Network](https://mlsanity.com/paper/2209.03712/) (2022)
- [Iterative Next Boundary Detection for Instance Segmentation of Tree Rings in Microscopy Images of Shrub Cross Sections](https://mlsanity.com/paper/2212.03022/) (2022)
- [Large-Scale Multi-Hypotheses Cell Tracking Using Ultrametric Contours Maps](https://mlsanity.com/paper/2308.04526/) (2023)
- [Segmentation in large-scale cellular electron microscopy with deep learning: A literature survey](https://mlsanity.com/paper/2206.07171/) (2022)
- [ClusterFuG: Clustering Fully connected Graphs by Multicut](https://mlsanity.com/paper/2301.12159/) (2023)
- [Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network](https://mlsanity.com/paper/2502.14536/) (2025)
- [Unsupervised Source-Free Ranking of Biomedical Segmentation Models Under Distribution Shift](https://mlsanity.com/paper/2503.00450/) (2025)
- [From Instance Segmentation to 3D Growth Trajectory Reconstruction in Planktonic Foraminifera](https://mlsanity.com/paper/2511.02142/) (2025)

## Abstract (arXiv)

We propose a theoretical framework that generalizes simple and fast algorithms for hierarchical agglomerative clustering to weighted graphs with both attractive and repulsive interactions between the nodes. This framework defines GASP, a Generalized Algorithm for Signed graph Partitioning, and allows us to explore many combinations of different linkage criteria and cannot-link constraints. We prove the equivalence of existing clustering methods to some of those combinations and introduce new algorithms for combinations that have not been studied before. We study both theoretical and empirical properties of these combinations and prove that some of these define an ultrametric on the graph. We conduct a systematic comparison of various instantiations of GASP on a large variety of both synthetic and existing signed clustering problems, in terms of accuracy but also efficiency and robustness to noise. Lastly, we show that some of the algorithms included in our framework, when combined with the predictions from a CNN model, result in a simple bottom-up instance segmentation pipeline. Going all the way from pixels to final segments with a simple procedure, we achieve state-of-the-art accuracy on the CREMI 2016 EM segmentation benchmark without requiring domain-specific superpixels.