GASP, a generalized framework for agglomerative clustering of signed graphs and its application to Instance Segmentation
Alberto Bailoni Constantin Pape Nathan Hütsch Steffen Wolf Thorsten Beier Anna Kreshuk Fred A. Hamprecht


 










GASP, a generalized framework for agglomerative clustering of signed graphs and its application to Instance Segmentation
    Alberto Bailoni Heidelberg Collaboratory for Image Processing (HCI/IWR), Heidelberg, Germany. {name.surname}@iwr.uni-heidelberg.de  EMBL, Heidelberg, Germany. {name.surname}@embl.de
Constantin Pape Institute for Computer Science, University Göttingen, Germany.
constantin.pape@informatik.uni-goettingen.de  [2]  [1]
Nathan Hütsch [1]
Steffen Wolf MRC Laboratory of Molecular Biology, Cambridge, UK.  swolf@mrc-lmb.cam.ac.uk
Thorsten Beier derthorstenbeier@gmail.com
Anna Kreshuk [2]
Fred A. Hamprecht [1]  Corresponding author

    December 30, 2023
===================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================






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[Code available at: <https://github.com/abailoni/GASP>], 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.











§ INTRODUCTION

In computer vision, the partitioning of weighted graphs has been successfully applied to tasks as diverse as image segmentation, object tracking and pose estimation. 
Most graph clustering methods work with positive edge weights only, which can be interpreted as similarities or distances between the nodes. These methods require users to specify the desired numbers of clusters (as in spectral clustering) or a termination criterion (e.g. in iterated normalized cuts) or even to add a seed for each object  (e.g. seeded watershed or random walker).  

Other graph clustering methods work with so-called signed graphs, which feature both positive and negative edge weights corresponding to attraction and repulsion between nodes. The advantage of signed graphs over unsigned graphs is that balancing attraction and repulsion allows us to obtain a clustering without defining additional parameters. A canonical formulation of the signed graph partitioning problem is the multicut or correlation clustering problem <cit.>. This problem is NP-hard, though many approximate solvers have been proposed <cit.> together with greedy agglomerative clustering algorithms <cit.>. 
Agglomerative clustering algorithms for signed graphs have clear advantages: they are parameter-free and efficient. Despite the fact that a variety of these algorithms exist, no overarching study has so far been conducted to compare their robustness and efficiency or to provide guidelines for matching an algorithm to the partitioning problem at hand. 


Our first contribution is a simple theoretical framework that generalizes over agglomerative algorithms for signed graphs by linking them to hierarchical clustering (HC) on unsigned graphs (Section <ref>). This framework defines an underlying basic algorithm and allows us to explore its combinations with different linkage criteria and cannot-link constraints (see Fig. [fig:intro_figure]<ref>fig:intro_figurea, [fig:intro_figure]<ref>fig:intro_figureb, and Table <ref>). 
As second contribution, in Section <ref>, we formally prove that some of the combinations correspond to existing clustering algorithms, and introduce new algorithms for combinations which have not been explored before. By analyzing their theoretical properties, we also show that some of them define an ultrametric on the graph (see Table <ref>).

Third, we evaluate the algorithms on a large variety of both existing and synthetically generated signed graph clustering problems (Section <ref>). 
Fourth and finally, we also test the algorithms on instance segmentation – a computer vision task consisting of assigning each pixel of an image to an object instance – by partitioning graphs whose edge weights are estimated by a CNN (see Fig. [fig:intro_figure]<ref>fig:intro_figurec and Section <ref>).
Our experiments show that the choice of linkage criterion markedly influences how clusters are grown by the agglomerative algorithms (Fig. [fig:intro_figure]<ref>fig:intro_figured), making some linkage methods more suited for certain types of clustering problems.
We benchmark the clustering algorithms by focusing on their efficiency, robustness and tendency to over- or under-cluster. 
On instance segmentation, we show that the agglomerative algorithms outperform recently proposed spectral clustering methods, and that average-linkage based agglomerative algorithms achieve state of the art results on the CREMI 2016 challenge for neuron segmentation of 3D electron microscopy image volumes of brain tissue. 

[remember picture,overlay]
[green,line]((a)+(0,2ex))–((b)+(0.9ex,2ex))–((c)+(0.9ex,-1.5ex)) – ((d)+(1.4ex,-1.5ex)) – ((e)+(1.4ex,-1.2ex)) – ((f)+(-0.3ex,-1.2ex))–((g)+(-0.3ex,-1.2ex))–((a)+(0,-1.2ex))–cycle;



§ RELATED WORK
 

Proposal-free instance segmentation methods adopt a bottom-up approach by directly grouping pixels into instances. In the last years, there has been a growing interest in such  methods that do not involve object detection because, in certain types of data, object instances cannot be approximated by bounding boxes <cit.>. 
Some use metric learning to predict high-dimensional associative pixel embeddings that map pixels of the same instance close to each other <cit.>
and then retrieve final instances by applying a clustering algorithm <cit.>.
Other recent methods let the model predict the relative coordinates of the instance center <cit.> or, given a pixel (x,y), they train a model to generate the mask of the instance located at (x,y) <cit.>. 

Edge detection also experienced recent progress thanks to deep learning, both on natural images <cit.> and biological data <cit.>. In neuron segmentation for connectomics, a field of neuroscience we also address in our experiments, boundaries are converted to final instances with subsequent postprocessing and superpixel-merging:
some use a combinatorial framework <cit.>, others use loopy graphs <cit.> or trees <cit.> to represent the region merging hierarchy. Flood-filling networks <cit.> and MaskExtend <cit.> used a CNN to iteratively grow one region/neuron at the time.
A structured learning approach was also proposed in <cit.>.

Agglomerative graph clustering has often been applied to instance segmentation <cit.> because of its efficiency as compared to other divisive approaches like graph cuts. 
Novel termination criteria and merging strategies have often been proposed: the agglomeration in <cit.> deploys fixed sets of merge constraints; 
the popular graph-based method <cit.> stops the agglomeration when the merge costs exceed a measure of quality for the current clusters. 
The optimization approach in <cit.> performs greedy merge decisions that minimize a certain energy, while other pipelines use classical linkage criteria, e.g. average linkage <cit.>, median <cit.> or a linkage learned by a random forest classifier <cit.>.

Clustering of signed graphs has the goal of partitioning a graph with both attractive and repulsive cues. Finding an optimally balanced partitioning has a long history in combinatorial optimization <cit.>. 
NP-hardness of the correlation clustering problem was shown in <cit.>, while the connection with graph multicuts was made by <cit.>. Modern integer linear programming solvers can tackle problems of considerable size <cit.>, but accurate approximations <cit.>, greedy agglomerative algorithms <cit.> and persistence criteria <cit.> have been proposed for even larger graphs. 
Another line of research is given by spectral clustering methods that, on the other hand, require the user to specify the number of clusters in advance. Recently, some of these methods have been generalized to graphs with signed weights <cit.>, whereas others let the user specify must-link and cannot-link constraints between clusters <cit.>.

This work reformulates the clustering algorithms of <cit.> in a generalized framework and adopts ideas from the proposal-free instance segmentation methods <cit.> to predict edge weights of a graph.




§ GENERALIZED FRAMEWORK FOR AGGLOMERATIVE CLUSTERING OF SIGNED GRAPHS
 



 §.§ Notation
 

Graph formalism – We consider an undirected simple edge-weighted graph 𝒢(V,E,w^+, w^-) with both attractive and repulsive edge attributes.
The weight function w^+: E →ℝ^+ associates to every edge a positive scalar attribute w_e^+∈ℝ^+ representing a merge affinity or a similarity measure.
On the other hand, w^-: E →ℝ^+ associates to each edge a split tendency w_e^- ∈ℝ^+.
Graphs of the type 𝒢(V,E,w^+, w^-) are often defined as signed graphs 𝒢(V,E,), featuring positive and negative edge weights _e∈ℝ. Following the theoretical considerations in <cit.>, we define signed weights as _e = w_e^+ - w_e^-. 

Multicut objective – We call the set Π={S_1,…,S_K} a clustering or partitioning if V = ∪_S∈Π S, S ∩ S' = ∅ for different clusters S, S' and every cluster S ∈Π induces a connected subgraph of 𝒢. 
For any clustering Π of 𝒢, we denote as E^0_Π= { e_uv∈ E  | ∃ S ∈Π : u,v ∈ S } the set of edges linking nodes in the same cluster. Its complementary set E_Π^1= E ∖ E^0_Π of edges linking nodes belonging to distinct clusters, is known as the multicut of 𝒢 associated to clustering Π. The instance of the NP-hard minimum cost multicut problem w.r.t. 𝒢(V,E,w_e) is the task of finding a clustering that optimally balances the attraction and repulsion in the graph and is given by the following binary integer program:

    min_Π∑_e∈ E_e x_e^Π,      where   x^Π_e = 
      
     1    if  e∈ E^1_Π
    
     0    otherwise.



Linkage criteria and hierarchical trees – 
Let the interaction (S ∪ S')∈ℝ between two clusters S,S' be defined as a function, named linkage criterion, depending on the weights of all edges connecting clusters S and S'.
The linkage criteria tested in this article are listed and defined in Table <ref>.
A dendrogram T is a rooted binary tree[In general, one could look at trees that are not binary. However, the algorithms discussed in this paper always generate binary hierarchical trees, so nothing would be gained by this generalization.] representing the merging order of an agglomerative algorithm, such that the leaves of the tree are in one-to-one correspondence with V and each node of the tree represents a merge between two clusters. 
Let T_R,T_L⊂ T denote the subtrees rooted at the two children of the root node in T.
For any two leaves u,v ∈ V, let T[u ∨ v] be the subtree rooted at the least common ancestor (u ∨ v)∈ T of nodes u and v (furthest from the root), and let (T[u ∨ v])⊆ V be the set of leaves of this subtree. 
Given an agglomerative algorithm with merging tree T, let h_T:V × V →ℕ denote the dendrogram-height of each (u∨ v)∈ T, which is defined as the iteration number at which nodes u,v∈ V were merged by the algorithm (see example in Fig. <ref>a). We also define (u,v) as the signed interaction (S ∪ S') between the two clusters S,S' that were merged at iteration h_T(u, v): 

    (u,v) ≡( (T_R[u ∨ v])  ∪(T_L[u ∨ v]) )










 §.§ The  algorithm
  

Our main contribution is a generalized agglomerative algorithm for signed graph partitioning (GASP) that generalizes hierarchical clustering (HC) to signed graphs. 
The framework, defined in the following, encompasses several known and new agglomerative algorithms on display in Table <ref>, which are differentiated by the linkage criterion employed, similarly to HC.

In Algorithm <ref>, we provide simplified pseudo-code for the proposed  algorithm.  implements a bottom-up approach that starts by assigning each node to its own cluster and then iteratively merges pairs of adjacent clusters. The algorithm proceeds in three phases. 

In phase one,  selects the pair of clusters with the highest absolute interaction |(S  ∪  S')|, so that the most attractive and the most repulsive pairs are analyzed first. If the interaction is repulsive and the algorithm option addCannotLinkConstraints is , then the two clusters are constrained so that their members can never merge in subsequent steps of phase one. If the interaction is attractive, then the clusters are merged, provided that they were not previously constrained. 
After each merge, the interaction between the merged cluster and its neighbors is updated according to one of the linkage criteria (S ∪  S') listed in Table <ref>. Phase one terminates when all the remaining clusters are either constrained or share repulsive interactions. Note that, on unsigned graphs, in phase one all nodes are merged into a single cluster and  is then equivalent to a standard hierarchical clustering algorithm.

Phase two: Now that the clusters have grown in size, the algorithm removes the constraints previously introduced in phase one and merges all the clusters that still share an attractive interaction, merging the most attractive one first[Note that in the version of  without cannotLinkConstraints, nothing happens in phase two because all remaining interactions are repulsive.]. The final clustering Π^* returned by  is found at the end of phase two and it is then composed of clusters sharing only mutual repulsive interactions. 

Finally, in phase three, the algorithm keeps merging all clusters until only a single one is left and then returns the hierarchical tree T^* representing the full sequence of merging steps.
The algorithm was implemented using a standard HC implementation with computational complexity 𝒪(N^2 log N) (details left in Appendix 
<ref>). 
A6.1). 










 §.§ : New and existing algorithms
 


In this paper we focus on five linkage methods (see columns of Table <ref>). Many more linkage criteria have been applied to unsigned graphs <cit.>, involving median-based[Median linkage is also implemented in our library (see implementation details Appendix 
<ref>).
A6.1).
] or size-regularized methods, but we decided to focus this paper on those five criteria because they represent the most popular choices.  



  
Sum Linkage – 
On signed graphs, the sum of two attractive (or repulsive) interactions is still attractive (repulsive). On the other hand, on unsigned graphs, a strong attractive interaction could be obtained by summing many weak interactions, which depending on the application could be undesirable. This explains why, to our knowledge, an agglomerative algorithm with sum linkage has never been used on unsigned graphs. On signed graphs, such an algorithm was pioneered in <cit.> and was named Greedy Agglomerative Edge Contraction (GAEC)[An algorithm equivalent to GAEC was recently independently re-proposed in <cit.>.].  
GAEC always makes the greedy choice that most decreases the multicut objective defined in Eq. <ref> each time two clusters with positive interaction are merged[In general, GASP cannot be seen as a local search algorithm of the multicut problem (for details see Appendix 
<ref>).
A6.2).
]. The authors of <cit.> propose an algorithm named GreedyFixation, which is equivalent to phase one of  using cannot-link-constraints and a sum linkage. However, running both phase one and two of  with sum linkage (algorithm named HCC-Sum in this paper) performed better than GreedyFixation in our experiments.



  
AbsMax Linkage – This linkage method is also specific to signed graphs, since on unsigned graphs it would be equivalent to single linkage. Here, we prove that the Mutex Watershed Algorithm <cit.> can be seen as an agglomerative algorithm with AbsMax linkage (proofs of the following three propositions are given in Appendix 
<ref>):
A6.3): 
propabsmaxmutex

The  Algorithm <ref> with AbsMax linkage, with or without cannot link constraints, returns the same final clustering Π^*_AbsMax also returned by the Mutex Watershed Algorithm (MWS) <cit.>, which has empirical complexity 𝒪(N log N).





  
Average, Single, and Complete Linkage – These three linkage criteria have been thoroughly studied on unsigned graphs, but never - until very recently - on signed graphs. In concurrent independent related work <cit.>, the authors prove that applying these three linkage methods to a signed graph is equivalent to applying them to the unsigned graph obtained by shifting all edge weights by a constant.  Here, we prove which of the algorithms studied here are “intrinsically signed” and do not have this invariance-property:
propinvariantAlgs

We call an agglomerative algorithm “weight-shift invariant” if the dendrogram T returned by the algorithm is invariant w.r.t. a shift of all edge weights w_e  by a constant α∈ℝ. Among the variations of , only hierarchical clustering with Average (HC-Avg), Single (HC-Single), and Complete linkage (HC-Complete) are weight-shift-invariant (see green box in Table <ref>).

Although average and single linkage methods have been largely studied on unsigned graphs, to our knowledge, they have never been combined with cannot-link constraints on signed graphs[Note that Complete linkage methods return the same clustering whether constraints are enforced or not (proof in Lemma 
<ref>, 
A6.3, 
in Appendix).], so we name these algorithms HCC-Avg and HCC-Single. 





















  
Algorithms defining an ultrametric – 






The connection between agglomerative algorithms and ultrametrics[A metric space (X,d) is an ultrametric if, for every x,y,z ∈ X, d(x,y)≤max{d(x,z), d(y,z)}.] is well known. Usually, ultrametrics are associated to strictly positive similarity or dissimilarity measures on a graph. In our framework, a trivial ultrametric is always given by the height h_T of the dendrogram. However, for some of the  variations, we now define an ultrametric based on the edge weights and the signed interactions between clusters, generalizing what has been done for HC on unsigned graphs <cit.>. To define this measure and prove its ultrametric property, we first map the signed interaction  defined in Eq. <ref> to positive “pseudo-distances” d_T:V × V →ℝ^+:

    d_T(u,v)≡   
    0    if   u=v
    
    M-(u,v)    if   u≠ v
      ∀ u,v∈ V
    where       M ≡ϵ + max_u',v'∈ V, u'≠ v'(u',v')

and where ϵ > 0. 
We then prove the following proposition:
propsecondUltraMetricProperty

Among the algorithms included in the  framework (see Table <ref>), only Mutex Watershed and hierarchical clustering with Average (HC-Avg), Single (HC-Single) and Complete linkage (HC-Complete) define an ultrametric (V, d_T^*), where d_T^* is defined in Eq. <ref> and T^* is the tree returned by the  Algorithm <ref>.

In summary, in this section we have extended the family of HC algorithms <cit.> with “weight-based ultrametrics” to signed graphs. Next, we move to their empirical evaluation. 







      
            









        


            







§ EXPERIMENTS



 §.§ Signed graph clustering problems
 
We evaluate the agglomerative clustering algorithms included in our framework on a large collection of both synthetic and real-world graphs with very different structures. The size of the graphs ranges from a few hundred to hundreds of millions of edges. In this way, we will highlight the strengths and limitations of the different linkage criteria introduced in the last section. 

Synthetic SSBM graphs – We first consider synthetic graphs generated by a signed stochastic block model (SSBM). We use an Erdős-Rényi random graph model 𝒢(N,p) with N vertices and edge probability p. Following the approach in <cit.>, we partitioned the graph into k ground-truth clusters, such that edges connecting vertices belonging to the same cluster (different clusters, respectively) have Gaussian distributed edge weights centered at μ=1 (μ=-1, respectively) and with standard deviation σ=0.1. To model noise, the sign of the edge weights is flipped independently with probability η.


Existing signed graphs  – We use clustering instances from the OpenGM benchmark <cit.> as well as biomedical segmentation instances <cit.>. The dataset Image Segmentation contains planar region-adjacency-graphs (RAG) that are constructed from superpixel adjacencies of photographs. The Knott-3D datasets contains 3D-RAGs arising from volume images acquired by electron microscopy (EM). The set Modularity Clustering contains complete graphs constructed from clustering problems on small social networks. The Fruit-Fly 3D-RAG instances were generated from volume image scans of fruit fly brain matter. Instances Level 1-4 are progressively simplified versions of the global problem obtained via block-wise domain decomposition <cit.>.

Grid-graphs from CNN predictions – We also evaluate the clustering methods on the task of neuron segmentation in EM image volumes using training data from the CREMI 2016 EM Segmentation Challenge <cit.>.
We train a 3D U-Net <cit.> using the same architecture as <cit.> and predict long-and-short range affinities 
as described in <cit.>. The predicted affinities a_e∈[0,1], which represent how likely it is for a pair of pixels to belong to the same neuron segment, are then mapped to signed edge weights w_e=a_e-0.5, resulting in a 3D grid-graph having a node for each pixel/voxel of the  image[To map affinities to signed weights, we also tested the logarithmic mapping proposed in <cit.>, but it performed worse in our experiments.]. 
We divided the three CREMI training samples, consisting of ∼196 million voxels each, into five sub-blocks for a total of 15 clustering problems (named CREMI-gridGraph in Table <ref>). See Appendix 
<ref> 
A6.5 
for extended details about training, data augmentation, and how we remove tiny clusters left after running  on the CREMI-gridGraph clustering problems.

3D-RAG from CNN-predictions – Lastly, we use the predictions of our CNN model to generate three graph instances (one for each CREMI training sample, named CREMI-3D-RAG in Table <ref>), which have very similar structure to the Knott-3D and Fruit-Fly instances.  We obtain these problems by using a pipeline that is very common in neuron segmentation: a watershed algorithm generates superpixels and from those a 3D region-adjacency graph is built, where edge weights are given by the CNN predictions averaged over the boundaries of adjacent superpixels (details in Appendix 
<ref>). 
A6.5). 







 














 §.§ Comparison of results and discussion


Multicut objective values – In Table <ref>, we report the values of the multicut objective obtained for clustering with different  algorithms[Objective values achieved by Single and Complete linkage methods are much worse compared to other algorithms and are reported in Table 
<ref>, 
A5, 
in Appendix.]. Although many heuristics were proposed to better optimize this objective <cit.>, these methods are out of the scope of this paper, since they do not scale to the largest graph instances considered here. By looking at results in Table <ref>, we observe that GAEC almost always achieves the lowest objective values, expect in the CREMI-gridGraph instances. Despite this, on graphs where a ground truth clustering is known, GAEC does not achieve the lowest ARAND errors (see Tables <ref> and <ref>). 

Size of growing clusters: Sum vs Avg linkage –
In all the studied clustering problems, we empirically observe that sum-linkage algorithms like GAEC grow clusters one after the other, as shown in Fig. [fig:intro_figure]<ref>fig:intro_figured and Fig. <ref> by the agglomeration order of GAEC[This flooding agglomeration-strategy of GAEC was also observed in <cit.>.]. This is intuitively explained by the  following: initially, many of the most attractive edge weights have very similar values; when the two nodes u,v with the highest attraction are merged, there is a high chance that they will have a common neighboring node t belonging to the same cluster; thus, the interaction between the merged nodes uv and t is likely assigned to the highest priority, because it is given by the sum of two highly attractive edge weights. This will then start a “chain reaction” where only a single cluster is agglomerated at the time. 
In the following, we will show how this unique flooding strategy of the sum-linkage methods can be both an advantage or a disadvantage, depending on the type of clustering problem. 

Comparison to spectral clustering – 
The spectral clustering methods for signed graphs SPONGE_sym and SPONGE proposed by <cit.> achieved state of the art performances on SSBM synthetic graphs. Their competitive performances are also confirmed by our experiments in Fig. <ref>.
However, these methods do not scale up to the large graph instances considered here and they also require the user to specify the true number of clusters in advance, which is not known for other graph instances tested in this paper. In Appendix, Table 
<ref>, 
A6, 
we report the scores achieved by these methods on a much smaller sub-instance of the CREMI-gridGraph problem: even when the true number of clusters is specified in advance for the spectral methods, they perform much worse than other  algorithms, with an accuracy penalty of almost 50%. For these reasons, we exclude them from our other comparison experiments.  

GASP on synthetic SSBM graphs  – 
 algorithms using cannotLinkConstraints are not expected to perform well on these graphs, because of the type of employed sign noise, so we focus our comparison only on the GAEC, HC-Avg and MWS algorithms (using Sum, Average, and AbsMax linkage methods, respectively).
Empirically, we observe that GAEC is the agglomerative algorithm performing best on SSBM graphs, on par with spectral method SPONGE_sym (see Fig. <ref>). Given the simple properties of SSBM graphs, we can now give a detailed explanation of these empirical results. 
In SSBM graphs, the number of edges E_ij
connecting two clusters S_i,S_j is  proportional to the product |S_i|·|S_j| of cluster sizes. 
With Sum or Avg linkage methods, due to the law of large numbers, the flipping noise is “averaged out” as soon as the set E_ij becomes larger and clusters grow in size.
On the other hand, when clusters are small, it can happen that, for few clusters, several of their edges in E_ij are flipped and the algorithm makes a mistake by merging two clusters belonging to different ground truth communities. From this observation, it follows that the flooding strategy of the sum-linkage algorithm GAEC is a very good strategy on these types of graphs, because clusters are immediately grown in size (see dendrograms in Fig. <ref>). Average linkage method HC-Avg instead performs much worse on these graphs because it grows small equally-sized clusters and makes several wrong merge-decisions at the beginning. 
Lastly, the MWS algorithm is not expected to perform well on these graphs because of the high sensitivity of the AbsMax linkage to flipping noise. In Proposition 
<ref> 
A6.2 
(see Appendix), we prove that, at every iteration, the MWS algorithm makes a mistake with at least probability η, independently on the sizes of the two clusters that are popped from priority queue.
In summary, for the SSBM, we can obtain a deep understanding of the dynamics induced by various linkage criteria, and find that GAEC gives highest accuracy by a large margin.










 



Scores on CREMI instance-segmentation – 
SSBM graphs are non-planar, and every edge has the same probability to be present in the graph. On the other hand, the gridGraph and 3D-RAG graphs of Table <ref> are sparse and have a very regular structure: regardless of whether a node represents a pixel or a superpixel, it will only have edge connections with its neighbors in the image (up to a certain hop distance). 
Tables <ref>-<ref> show that average linkage methods (HC-Avg, HCC-Avg) strongly outperform other methods on CREMI-gridGraph instances and also achieve the best scores on CREMI-3D-rag graphs. Sum-based linkage methods (GAEC, HCC-Sum) have a two times higher ARAND error on grid-graphs and often return under-clustered segments (see failure cases in Fig. <ref>). This suggests that the flooding strategy observed previously in the sum-linkage methods does not work on grid-graphs, because in this setup edge weights are predicted by a CNN and noise is strongly spatially-correlated [This effect is not as strong on 3D-RAG graphs, because edge weights are computed by averaging CNN predictions (and noise) over the boundaries of adjacent supervoxels.].
To fully test this hypothesis, we conduct a set of experiments where the CNN predictions are perturbed by adding structured noise and simulating additional artifacts like “holes” in the boundary evidence[See Appendix 
<ref> 
A6.6 
for details about how we perturbed the CREMI-gridGraph problems by using Perlin noise <cit.>, which is one of the most common gradient noises used in procedural pattern generation.]. 
The plot in Fig. <ref> confirms that HC-Avg and HCC-Avg are very robust algorihtms on this data, followed by Sum-linkage algorithms and the Mutex Watershed algorithm (MWS). It is not a surprise that the AbsMax linkage used by MWS is not robust to this type of structured noise. However, the scores and runtimes in Table <ref> prove how MWS can achieve high accuracy with 70% lower runtime compared to HC-Avg. 

Complete and Single Linkage – We use these two linkage methods as baselines to highlight the difficulty of the studied graph clustering problems listed in Table <ref>. Scores in Tables <ref>-<ref> show their poor performance: Single linkage hierarchical clustering (HC-Single), which here is equivalent to thresholding the edge weights at w_e=0 and computing connected components in the graph, often returned few big under-segmented clusters. HC-Complete returned instead a lot of over-segmented clusters. 








Results on CREMI challenge – 
Table <ref> shows that the HCC-Avg and HC-Avg clustering algorithms achieve state-of-the-art accuracy on the CREMI challenge, when combined with predictions of our CNN.
Most of the other entries (apart from LSI-Masks <cit.>) employ super-pixels based post-processing pipelines and cluster 3D-region-adjacency graphs. As we show in Table  <ref>, using superpixels considerably reduces the size of the clustering problem and, consequently, the post-processing time. 
However, our method operating directly on pixels (gridGraph + HCC-Avg) achieves better performances than superpixel-based methods (3D-RAG + HCC-Avg) and does not require the parameter tuning necessary to obtain good super-pixels, which is usually highly dataset dependent.
To scale up our method operating on pixels, we divided each test-volume into four sub-blocks, and then combined the resulting clusterings by running the algorithms again on the combined graph.
The method 3D-RAG + LiftedMulticut based on the lifted multicut approximation of <cit.> achieves the best scores overall, but it takes into account different information through the lifted edge weights that also depend on additional raw-data and shape information from highly engineered super-pixels. 




































§ CONCLUSION

We have presented a unifying framework for agglomerative clustering of graphs with both positive and negative edge weights. This framework allowed us to explore new combinations of constraints and linkage criteria and to perform a consistent evaluation of all algorithms in it. 
We have then analyzed several theoretical and empirical properties of these algorithms. On instance segmentation, algorithms based on an average linkage criterion outperformed all the others: they proved to be simple and robust approaches to process short- and long-range predictions of a CNN.
On biological images, these simple average agglomeration algorithms achieve state-of-the-art results without requiring the user to spend much time tuning complex task-dependent pipelines based on super-pixels.


ieee_fullname














§ APPENDIX





 §.§ Implementation and complexity of 
 





  
*Update rules During the agglomerative process, the interaction between adjacent clusters has to be properly updated and recomputed, as shown in Algorithm <ref>.  
An efficient way of implementing these updates can be achieved by representing the agglomeration as a sequence of edge contractions in the graph. Given a graph 𝒢(V,E,) and a clustering Π, we define the associated contracted graph 𝒢̃_Π(Ṽ, Ẽ, ), such that there exists exactly one representative node |Ṽ∩ S| = 1 for every cluster S ∈Π . Edges in Ẽ represent adjacency-relationships between clusters 
and the signed edge weights _e are given by inter-cluster interactions (e_uv)=_S_u ∪ S_v, where S_u denotes the clustering including node u. 
For the linkage criteria tested in this article, when two clusters S_u and S_v are merged, the interactions between the new cluster S_u ∪ S_v and each of its neighbors depend only on the previous interactions involving S_u and S_v. Thus, we can recompute these interactions by using an update rule f that does not involve any loop over the edges of the original graph 𝒢:

    (S_u ∪ S_v  ∪ S_t) =    f[ (S_u  ∪  S_t), (S_v  ∪  S_t) ] 
    
      =    f((e_ut), (e_vt))

In Fig. <ref> we show an example of edge contraction and in Table <ref> we list the update rules associated to the linkage criteria we introduced in Table <ref>.

 
  [p]
    Implementation of  - Phase 1
   Input: 𝒢(V,E,w^+,w^-) with N nodes and M edges; boolean  

   Output: Final clustering 

     
    
     
      
    
  
  [p]
    Mutex Watershed Algorithm proposed by <cit.>
   Input: 𝒢(V,E,w^+,w^-) with N nodes and M edges 

   Output: Final clustering 

     
    
    
  
  




  
Implementation Our implementation of  is based on an union-find data structure and a heap allowing deletion of its elements. 
In Phases 2 and 3,  is equivalent to a standard hierarchical agglomerative clustering algorithm with complexity 𝒪(N^2 log N). In Algorithm <ref>, we show our implementation of phase 1, involving cannot-link constraints.
In phase 1, the algorithm starts with each node assigned to its own cluster and sorts all edges e∈ E in a heap/priority queue (PQ) by their absolute weight |_e|=|w_e^+ - w_e^-| in descending order, so that the most attractive and the most repulsive interactions are processed first. It then iteratively pops one edge e_uv from PQ and, depending on the priority _uv, does the following: in case of attractive interaction _uv>0, provided that e_uv was not flagged as a cannot-link constraint, merge the connected clusters, perform an edge contraction of e_uv in 𝒢̃_Π and update the priorities of new double edges as explained in Fig. <ref>. 
If, on the other hand, the interaction is repulsive (_uv≤ 0) and the option  of Alg. <ref> is , then the edge e_uv is flagged as cannot-link constraint.









  
*Complexity 
In the main loop of Phase 1, the algorithm iterates over all edges, but the only iterations presenting a complexity different from 𝒪(1) are the ones involving a merge of two clusters, which are at most N-1. By using a union-find data structure (with path compression and union by rank) the time complexity of (u, v) and (u) operations is 𝒪(α(N)), where α is the slowly growing inverse Ackerman function. The algorithm then iterates over the neighbors of the merged cluster (at most N) and updates/deletes values in the priority queue (𝒪(log |E|)). 
Therefore, 
similarly to a heap-based implementation of hierarchical agglomerative clustering, our implementation of  - Phase 1 has a complexity of 𝒪(N^2 log N). In the worst case, when the graph is dense and |E|=N^2, the algorithm requires 𝒪(N^2) memory. Nevertheless, in our practical applications the graph is much sparser, so 𝒪(|E|)=𝒪(N). 
With a single-linkage, corresponding to the choice of the Maximum update rule in our framework, the algorithm can be implemented by using the more efficient Kruskal's Minimum Spanning Tree algorithm with complexity 𝒪(N log N), but only when cannotLinkConstraints are not used. 
Moreover,  with Absolute Maximum linkage can be implemented more efficiently (see next section). 






  
*Efficiency of different GASP implementations with AbsMax linkage criteria 
In Fig. <ref>, we compare the runtimes of three implementations of the AbsMax criteria: the implementation from <cit.> for pixel graphs (Pixel-grid implementation) and for general graphs (Efficient graph implementation) as well as the HC implementation with AbsMax linkage (Naive graph implementation). The specialized implementations can exploit the properties of the underlying graph and are faster. But our generalization does not carry a large computational penalty and only requires a few extra seconds for partitioning graphs of a million nodes. Note that we have always used the most efficient implementation for the results reported in the paper. We will clarify this fact.



  
Median linkage We implemented median linkage in our library from the beginning but did not report on it in the main paper for two reasons: we consider the other criteria to span the range of interesting behavior well; and it performs no better than some of the other criteria (like average linkage) which are faster to evaluate.






 §.§ GASP relation to the multicut objective
 
For some of the linkage criteria, e.g. sum and average, GASP can be understood as a local search to the objective of the multicut optimization problem <ref>, see <cit.>. But this does not hold in general: the Abs Max linkage for example does not always decrease the MC objective (see counter example in Fig. <ref>). 
Moreover, GASP cannot be seen as a k-approximation, because it is a polynomial algorithm and Chawla, et al. Computational complexity, 2006

has shown that approximating the multicut objective with any constant factor is in itself NP-hard. 




 §.§ Proofs of Propositions <ref>, <ref>, <ref>, and <ref>



 
If  Algorithm <ref> with Complete linkage criteria enforces a constraint between two clusters in Phase 1, then the interaction between the clusters will never become positive over the course of the following agglomeration steps.


Two clusters are constrained in Phase 1 only if their interaction is repulsive and, with complete linkage,  the signed interaction between two clusters can only decrease over the course of the agglomeration. Thus, if two clusters are constrained by the algorithm, their negative interaction cannot increase and become positive later on in the agglomeration process.


 
If  Algorithm <ref> with AbsMax linkage criteria enforces a constraint between two clusters in Phase 1, then the interaction between the clusters will never become positive over the course of the following agglomeration steps.


During the agglomeration the interaction between two clusters can only increase in absolute value. Thus, the negative interaction (S_i ∪ S_j)<0 between two constrained clusters can possibly become positive over the course of next agglomeration steps only if there is at least another pair of clusters in the graph that has a positive interaction (S_l ∪ S_t)>0 higher in absolute value: |(S_l ∪ S_t)| > |(S_i ∪ S_j)|.
If such clusters S_l, S_t with positive interaction exist, we note that they must also be constrained (in the opposite case, the algorithm would have already merged them before to constrain S_i and S_j, because their priority is higher). In other words, a constrained negative interaction can become positive only if there is already another positive constrained interaction: but this can never be the case because initially all constrained interactions are negative.


 
In the  Algorithm <ref> with AbsMax or Complete linkage criteria (see linkage definition in Table <ref>), the same final clustering is returned whether or not cannot-link constraints are enforced.


In phase 1 of Algorithm <ref>, two clusters are merged only if the condition at line 9 is satisfied (i.e. when an interaction is both positive and not constrained). From Lemma <ref> and Lemma <ref> follows that with Complete and AbsMax linkage an interaction can never be both positive and constrained at the same time, so we directly conclude that the constrained and unconstrained versions of the algorithm will perform precisely the same agglomeration steps in phase 1.
In phase 2 (after constraints have been removed) no clusters are merged because all interactions are already negative (whether they previously constrained or not). Thus, both constrained and unconstrained versions of  return the same clustering Π^*.



*





From Lemma <ref> it directly follows that  with AbsMax linkage criterion returns the same final clustering whether or not cannot-link constraints are enforced. In the following, we prove that MWS (see pseudocode <ref>) and the constrained AbsMax version of  also return the same clustering.
Both algorithms sort edges in descending order of the absolute interactions |w_e| and then iterate over all of them. The only difference is that MWS, after merging two clusters, does not update the interactions between the new cluster and its neighbors. 
However, since with an Abs. Max. linkage the interaction between clusters is simply given by the edge with highest absolute weight |w_e|, the order by which edges are iterated over in  is never updated. Thus, both algorithms perform precisely the same steps and return the same clustering.





*

Theorem 1 in <cit.> proves that hierarchical clustering with Average (HC-Avg), Single (HC-Single), and Complete linkage (HC-Complete) are weight-shift invariant.

The same is not true for  with Sum linkage criteria (GAEC and HCC-Sum), because by adding a constant α to all edge weights w_e, the interaction between two clusters S_i and S_j is increased by a factor α |E_ij|, which depends on the number of edges  |E_ij| connecting the two clusters. Thus, when all edge weighs of the graph are shifted, the agglomeration order may change. For a simple example of this, it is enough to consider the toy graph in Fig. <ref>a and shift the weights of the graph by α=-3 (see Fig. <ref>).


The constrained versions of  (HCC-Avg and HCC-Single) are also not weight-shift invariant: here, the algorithm merges or constrains clusters in a given order, depending on the absolute interactions |(S_i ∪  S_j)| between clusters; so, when edge weights are shifted by a constant α, the sorting by absolute value can change arbitrarily together with the agglomeration order, as we show in the counter-example of Fig. <ref>.
Similarly, the Mutex Watershed algorithm is not weight-shift invariant because it uses a linkage criterion that compares weights by their absolute values (see again counter-example in Fig. <ref>.





propfirstUltraMetricProperty

Consider a graph 𝒢(V,E,w_e), a linkage criterion , and an agglomerative algorithm returning a binary rooted tree T with height h_T. Then, (V, d_T) defined in Eq. <ref> is an ultrametric if and only if the following is true:

    ∀ u,v,t ∈ V 
    
     h_T(u, v) < h_T(u, t) ⇒_T(u,v) ≥_T(u,t)

In words, condition <ref> means: if the algorithm merges nodes u,v before to merge nodes u,t, then the signed interaction _T(u,v) between u and v has to be higher or equal than _T(u,t).



From the definition of d_T, it follows that:

    d_T(u,u)    = 0        ∀ u∈ V 
     
    d_T(u,v)    ≥ 0        ∀ u,v ∈ V 
    
    d_T(u,v)    =d_T(v,u)        ∀ u,v ∈ V.

In order to show that (V, d_T) is an ultrametric, we only need to prove the ultrametric property:

    d_T(u,v) ≤max{d_T(u,t), d_T(v,t)}  ∀ u,v,t ∈ V.

When at least two of the three nodes u,v,t ∈ V are the same, this property follows from Eq. <ref> and Eq. <ref>. When nodes u,v,t∈ V are distinct, from the definition of d_T it follows that Eq. <ref> is equivalent to:

    _T(u,v) ≥min{_T(u,t), _T(v,t)}.

In the following, we prove both sides of the if and only if statement in the proposition. First, we prove the (⇐) side, i.e. that if assumption <ref> holds, then (V, d_T) is an ultrametric and <ref> holds. 

Case 1: in Eq. <ref>, t∈ V is part of the sub-tree T[u ∨ v]. In other words, the algorithm first merges node t with either node u or v, and then u and v are merged together. Let us assume that t is first merged with u (the following proof also holds for the opposite case in which t is first merged with v):

    h_T(u, t) < h_T(u, v) = h_T(v, t).

Thus, by combining the last equation with assumption (<ref>), it follows that

    _T(u, t) ≥_T(v, t)   and  _T(u, v) = _T(v, t)

and Eq. <ref> follows (becoming an equality in this case).

Case 2: in Eq. <ref>, t∈ V is not part of the sub-tree T[u ∨ v]. Thus, the algorithm first merges nodes u and v, and then it merges node t together with the cluster containing u and v:

    h_T(u, v) < h_T(u, t) = h_T(v, t).

Thus, from assumption <ref> we have that

    _T(u, v) ≥_T(u, t)   and  _T(u, v) ≥_T(v, t),

so also in this case Eq. <ref> follows.

Next, we are left to prove the (⇒) side of the if and only if statement: if (V, d_T) is an ultrametric, then assumption <ref> holds.
To prove this statement, we first rephrase it in the following equivalent form: if assumption <ref> does not hold, then (V, d_T) is not an ultrametric and <ref> does not hold. If we negate assumption <ref>, there must be at least three u,v,t ∈ V such that: 

    h_T(u, v) < h_T(u, t)   and  _T(u,v) < _T(u,t).

The first condition, in words, is again assuming that the algorithm first merges nodes u and v, and later it also merges node t with the cluster containing u and v. Thus, we can rephrase this assumption as:

    _T(u, v) < _T(u, t) = _T(v, t).

From this, it follows that

    _T(u, v) < min{_T(u, t), _T(v, t)},

which is exactly the negation of the ultrametric property <ref>.


*

Thanks to Prop. <ref>, we know that (V, d_T^*) is an ultrametric if and only if assumption <ref> holds. Thus, in the following, we will prove which variations of the  Algorithm <ref> satisfy assumption <ref>. 
In other words, we need to prove in which cases  merges clusters according to a monotonously decreasing order of signed interactions .

 puts clusters in a priority queue (Algorithm <ref>, lines 5 and 15) and merges them starting from those with the highest interaction (lines 9, 19, and 26). However, the priority queue is updated each time two clusters are merged (lines 10, 20, and 27). Thus, to ensure a monotonously decreasing merging order, updated interactions involving a merged cluster should always be lower or equal than previously existing interactions (condition 1):

    ∀ S_i ∈Π∖{S_1, S_2}, 
    (S_1 ∪ S_2 ∪  S_i)    ≤max{(S_1  ∪  S_i), (S_2  ∪  S_i)}

where Π is a clustering,  is a linkage criteria, and S_1,S_2∈Π are two clusters merged by the algorithm at a given iteration. If this condition is true then, in the following iterations,  can only merge clusters with lower (or equal) interaction values. 

We also note that, in phase 1, the algorithm skips interactions that are both positive and constraint (condition at line 8 in Algorithm <ref>) and merges them only later in phase 2 (line 19), when constraints are removed.
Clearly, whenever this happens, a decreasing merging order is no longer ensured. 
Thus, on top of condition 1, we also have that no merging decisions should be “delayed” from phase 1 to phase 2 (condition 2). 

Condition 1 always holds for Average, Single, Complete, and AbsMax linkage criteria, but not for a Sum linkage criteria, because the sum of two positive numbers a,b is always higher than max{a,b}. This is also demonstrated in the toy example of Fig. [fig:intro_figure]<ref>fig:intro_figurea, proving that, in general, Sum-linkage algorithms like GAEC or HCC-Sum do not define an ultrametric on the graph.

Thanks to Lemma <ref>, we have that condition 2 always holds for algorithms based on AbsMax and Complete linkage, proving that the Mutex Watershed and HC-Complete algorithms define an ultra-metric (whether or not cannot-link-constraints are enforced). On the other hand, condition 2 does not hold for other variations of  involving cannot-link-constraints (HCC-Sum, HCC-Avg, and HCC-Single), which do not then define an ultrametric. 

Finally, the remaining not constrained versions of  (HC-Avg, HC-Single, and HC-Complete) satisfy both conditions, so they define an ultrametric, confirming the well-known results of related work in hierarchical clustering on unsigned graphs <cit.>.



















 §.§ Mutex Watershed on SSBM graphs

 
Consider a graph generated by an Erdős-Rényi signed stochastic block model (SSBM) as described in Section <ref>, with N nodes, edges added with probability p, sign-flip probability η<0.5, k ground-truth clusters, and edge weights Gaussian-distributed with standard deviation σ. Then, at every iteration,  with Absolute Maximum linkage (or, in other words, the Mutex Watershed algorithm) always makes a mistake with at least probability η. 


Thanks to Lemma <ref> we know that  with Absolute Maximum linkage returns the same clustering whether or not cannot-link-constraints are used. Thus, in the following, we prove the proposition considering the version enforcing constraints.
Let us consider a generic iteration of the algorithm, where two clusters S_α and S_β have the highest priority and are popped from priority queue. Then, the MWS algorithm will either merge or constrain them depending on the fact that their interaction _AbsMax(S_α∪ S_β) is  positive or negative (note that, with AbsMax linkage, an interaction can never be positive and constrained, as shown in Lemma <ref>).
By construction of the SSBM, every edge e∈ E in the graph has a absolute weight distributed as |w_e|∼𝒩(1,σ^2). Thus, every edge e'∈(S_α× S_β)∩ E connecting the two clusters has the same probability to have the highest absolute weight, and the sign of the interaction _AbsMax(S_α∪  S_β) will only depend on the sign of this highest edge. Therefore, the probability that the MWS merges two clusters is simply given by the fraction of positive weighted edges connecting them.

Let Π̃={S̃_1,…,S̃_k} denote the ground truth clustering, and S̃_α i=S_α∩S̃_i denote the intersection between cluster S_α and a ground-truth cluster S̃_i.
If the generated graph is dense, i.e. p=1, then the total number of edges connecting clusters S_α and S_β that have a true attractive or repulsive weight is (according to the ground truth labels)

    ^+=∑_i=1^k |S̃_α i||S̃_β i|,   ^-=∑_i=1^k ∑_j=1,j≠ i^k |S̃_α i||S̃_β j|.

When the edges in the graph are randomly added with a probability p, then the actual number of true attractive and repulsive interactions connecting the two clusters is (according to the ground truth labels):

    ^+ ∼ℬ(^+,p),     ^- ∼ℬ(^-,p),

where ℬ(,p) is the binomial distribution:

    ℬ(;,p) =  !/! (-)! p^ (1-p)^-.

Here, we only assume that ^+ + ^- >0, i.e. there is at least one edge connecting the two clusters (otherwise their interaction would be zero and the MWS would not have popped them from priority queue). 

So far we have been talking about attractive and repulsive connections according to the ground truth labels. In our SSBM however every edge has a uniform probability η to have its sign flip, so  the actual number of attractive interactions connecting the two clusters will be instead given by the sum of the true attractive interactions ^+_nf∼ℬ(^+,1-η) that have not been flipped, plus the true negative interactions ^-_f∼ℬ(^-,η) that have been flipped.
Putting everything together, given two clusters with ^+ true attractive interactions and ^- true negative ones, the highest-absolute-weight edge connecting them has the following probability to be positive:

    ℙ[_AbsMax   (S_α∪  S_β)>0;^+,^-] = 
    
    =   ∑_^+_nf=0^^+∑_^-_f=0^^-ℬ(^-_f;^-,η) ℬ(^+_nf;^+,1-η)·
               ·(^+_nf+^-_f/^+ + ^-) 
    (*)=   ^+(1-η)+^-η/^+ + ^-
  
where in (*) we used the fact that the expected value of a binomial distribution ℬ(,η) is η.

Now we note that this probability is bounded in the interval [η, 1-η]. So, regardless of whether the two clusters S_α and S_β should be merged or constraint according to ground truth labels, the probability not to make the correct decision is always at least η.
Remarkably, while the exact probability in Eq. <ref> depends on the number of edges connecting the two clusters ^++^- and thus on the cluster sizes, the bounds do not. Thus, this result shows that, unlike Sum or Avg linkage methods, the MWS algorithm is unable to reliably correct for the sign flip noise even for big clusters linked by many edges.














 §.§ Application to neuron segmentation



  
Training and data augmentation The data from the CREMI challenge is highly anisotropic and contains artifacts like missing sections, staining precipitations and support film folds. 
To alleviate difficulties stemming from misalignment, we use a version of the data that was elastically realigned by the challenge organizers with the method of S.    Saalfeld, et al. Nature methods, 2012.

In addition to the standard data augmentation techniques of random rotations, random flips and  elastic deformations, we simulate data artifacts.
We randomly zero-out slices, decrease the contrast of slices, simulate tears, introduce alignment jitter and paste artifacts extracted from the training data. Both <cit.> and <cit.> have shown
that these kinds of augmentations can help to alleviate issues caused by EM-imaging artifacts.
We use L2 loss and Adam optimizer to train the network. The model was trained on all three samples with available ground truth labels.  



  
CREMI-gridRag instances 
Our 3D UNet model predicts the same set of 12 long-and-short range affinities as described in <cit.>. 
When building the pixel-grid graph, we add both direct neighbors connections and the long-range connections predicted by our model (every voxel is connected to other six voxels via direct connections and other 18 voxels via long-range edges).
Empirically, when long-range predictions of the CNN are added as long-range connections in the graph,  achieves better scores as compared to when only direct-neighbors predictions are used.
Our intuitive explanation of this is that, where there is a clear boundary evidence between two segments, the long-range predictions of the CNN model are more certain than the direct-neighbor ones, because it is often impossible to estimate the exact ground-truth label transition for pixels that are very close to a boundary evidence. 
However, empirically, we also find that  achieves the best scores when only 10% of the long-range connections are randomly sampled and added to the grid-graph. When all the long-range connections predicted by the CNN are added to the graph (18 connections for every voxel), all versions of  tend to perform more over-clustering errors.
In practice, we explain this by observing that many challenging parts of the studied neuron segmentation data involve thin and elongated segments, and our model sometimes fails to connect distant pairs of pixels that, according to the ground-truth labels, should belong to the same segment (even though, in this case, the direct neighboring predictions are correct).
To sum up, the scores we report in Tables <ref> are obtained by using only 10% of the long-range predictions, since this was the setup that performed the best.
After running , we use a simple post-processing step to delete small segments on the boundaries, most of which are given by single-voxel clusters. On the neuron segmentation predictions, we deleted all regions with less than 200 voxels and used a seeded watershed algorithm to expand the bigger segments.





  
CREMI-3D-rag instances 
We build these clustering problems by generating superpixels and then building a 3D region adjacency graph.
Due to the anisotropy of the data, we generate 2D superpixels by considering each 2D image in the stack singularly.
First, we generate a boundary-evidence map by taking an average over the two direct-neighbor predictions of the CNN model (one for each direction in the 2D image of the stack) and applying some additional smoothing. Then, we threshold the boundary map, compute a distance transform, and run a watershed algorithm seeded at the maxima of the distance transform (WSDT). The degree of smoothing was optimized such that each region receives as few seeds as possible, without however causing severe under-segmentation. 
The computed 2D superpixels are then used to build a 3D region-adjacency graph (3D-rag). The weights of the edges are given by averaging the CNN affinities over the boundaries of adjacent superpixels. 




 
 







 §.§ Adding structured noise to CNN predictions
 
Additionally to the comparison on the full training dataset, we performed more experiments on a crop of the more challenging CREMI training sample B, where we perturbed the predictions of the CNN with noise and we introduced additional artifacts like missing boundary evidences.

In the field of image processing there are several ways of adding noise to an image, among which the most common are Gaussian noise or Poisson shot noise. 
In these cases, the noise of one pixel does not correlate with its neighboring noise values. On the other hand, predictions of a CNN are known to be spatially correlated. 
Thus, we used Perlin noise[In our experiments, we used an open-source implementation of simplex noise <cit.>, which is an improved version of Perlin noise <cit.>], one of the most common gradient noises used in procedural pattern generation. This type of noise n(x)∈[0,1] generates spatial random patterns that are locally smooth but have large and diverse variations on bigger scales. We then combined it with the CNN predictions p(x) in the following way:

    F̃(x;𝒦)=F(x)+𝒦·max(N(x),0),

where  N(x)=Logit[n(x)]; F(x)=Logit[p(x)] and 𝒦∈ℝ^+ is a positive factor representing the amount of added noise. The resulting perturbed predictions F̃(x;𝒦) are then under-clustering biased, such that the probability for two pixels to be in the same cluster is increased only if N(x)>0 (see Fig. [fig:noisy_affs]<ref>fig:noisy_affsb and [fig:noisy_affs]<ref>fig:noisy_affsc). 
Note that in these experiments we focused only on predictions perturbed with under-clustering biased noise (and not over-clustering biased noise). The reason is that generating realistic over-clustering biased CNN predictions is more complex and cannot be simply done by adding Perlin noise: as we show in Fig. [fig:noisy_affs]<ref>fig:noisy_affsc, by adding Perlin noise we can easily “remove” parts of a boundary evidence, but it is not possible to generate random new realistic boundary evidence.  

In our experiments, each pixel is represented by a node in the grid-graph and it is linked to n_nb other nodes by short- and long-range edges. Thus, the output volume of our CNN model is a four-dimensional tensor with n_nb channels: for each pixel / voxel, the model outputs n_nb values representing affinities of different edge connections. We then generated a 4-dimensional Perlin noise tensor that matches the dimension of the CNN output. The data is highly anisotropic, i.e. it has a lower resolution in one of the dimensions. Due to this fact, we chose different smoothing parameters to generate the noise in different directions. 
























    
