We propose a novel theoretical framework that generalizes 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 which have not been studied. An extensive comparison is performed to evaluate properties of the clustering algorithms in the context of instance segmentation in images, including robustness to noise and efficiency. We show how one of the new algorithms proposed in our framework outperforms all previously known agglomerative methods for signed graphs, both on the competitive CREMI 2016 EM segmentation benchmark and on the CityScapes dataset.

介绍了一种理论框架，将层次聚类算法简化扩展到具有吸引和排斥相互作用的加权图中以及通过 GASP 这一更广泛的算法来实现分区。并在 CREMI 2016 EM 分割基准测试中展示了实现分割管道的方法，从像素到最终分割的简单程序，实现了最先进的准确性。

GASP：一种广义的聚类有向图框架及其在实例分割中的应用