Compassionately Conservative Balanced Cuts for Image Segmentation
Nathan D. Cahill Tyler L. Hayes Renee T. Meinhold John F. Hamilton







Compassionately Conservative Balanced Cuts for Image Segmentation
    Nathan D. Cahill  Tyler L. Hayes  Renee T. Meinhold  John F. Hamilton 

Rochester Institute of Technology

{ndcsma, tlh6792, rtm9271, jfhsms}@rit.edu
    December 30, 2023
=========================================================================================================================================================





The Normalized Cut (NCut) objective function, widely used in data clustering and image segmentation, quantifies the cost of graph partitioning in a way that biases clusters or segments that are balanced towards having lower values than unbalanced partitionings. However, this bias is so strong that it avoids any singleton partitions, even when vertices are very weakly connected to the rest of the graph. Motivated by the Bühler-Hein family of balanced cut costs, we propose the family of Compassionately Conservative Balanced (CCB) Cut costs, which are indexed by a parameter that can be used to strike a compromise between the desire to avoid too many singleton partitions and the notion that all partitions should be balanced. We show that CCB-Cut minimization can be relaxed into an orthogonally constrained ℓ_τ-minimization problem that coincides with the problem of computing Piecewise Flat Embeddings (PFE) for one particular index value, and we present an algorithm for solving the relaxed problem by iteratively minimizing a sequence of reweighted Rayleigh quotients (IRRQ). Using images from the BSDS500 database, we show that image segmentation based on CCB-Cut minimization provides better accuracy with respect to ground truth and greater variability in region size than NCut-based image segmentation.  






§ INTRODUCTION


The Normalized Cut (NCut) graph partitioning cost function was first introduced over two decades ago to tackle the perceptual grouping problem <cit.>, and its approximate minimization via continuous relaxation into a generalized eigenvector problem has emerged as one of the fundamental techniques of data clustering <cit.>.  



The key observation that motivated the normalization of graph cut cost functions is that when graph partitioning is performed by minimizing the sum of the weights of edges that are cut (the Cut cost), the resulting partitions will be unbalanced; vertices that are weakly connected to the rest of the graph are likely to be separated to form singleton partitions, while the rest of the graph vertices are likely to remain in large partitions. Normalizing the cut cost by the degrees of each partition (NCut <cit.>), the size of each partition (Average Cut <cit.>), or the minimum of the size of each partition and its complement (Ratio or Cheeger Cut <cit.>) yield balanced partitions that have similar total degree or size when minimized.

Is it possible that these types of normalization go too far? Consider the example of Figure <ref>, in which we wish to partition the toy graph into two subgraphs. This graph (<ref>) contains seven vertices and nine edges; all but two of the edges have unit weight, and the two indicated edges have weight α/2 for α∈(0,1). Since α<1, the degree of the vertex sharing these two edges is guaranteed to be smaller than the degree of any other vertex in the graph. Hence, as shown in (<ref>), minimizing the Cut cost will separate that weakly-connected vertex from the rest of the graph. Minimizing the NCut cost creates a more balanced partitioning as shown in (<ref>); however, this partitioning will always have a lower-cost NCut than removing the weakly-connected vertex, even when α is infinitesimally small.   Perhaps the Ratio Cut (RCut) is a better choice: for this graph, α=2/3 is a critical value above which (<ref>) minimizes the RCut cost, and below which (<ref>) yields the minimum. But is there really anything special about α = 2/3?

If this graph represented an image to be segmented, one would want to use ground-truth segmentation maps from training images to suggest an optimal critical value for α, above which the more “balanced” partitioning is desired, and below which the weakly-connected vertex should be separated. The ground truth might dictate that even the Ratio Cut cost provides too much normalization, or instead, that it does not provide enough. 

One potential idea is to use the infinite families of balanced cost functions defined by Bühler and Hein <cit.> and indexed by a parameter p∈(1,∞). We refer to these families as the Bühler-Hein p-Normalized (BHN_p) and the Bühler-Hein p-Ratio (BHR_p) Cuts. BHN_p is equivalent to NCut for p=2 and the Normalized Cheeger (NCh) Cut as p→ 1^+, and BHR_p is equivalent to RCut for p=2 and the Ratio Cheeger (RCh) Cut as p→ 1^+, so both families of cut costs can be thought of as interpolating between different normalization factors. However, as shown in Fig. (<ref>), when we minimize BHN_p Cut and BHR_p Cut for the graph in Fig. (<ref>), there are substantial ranges of α for which no value of p will allow a bifurcation between solutions.   



In this paper, we show that although the Bühler-Hein costs provide a mechanism for interpolating between Normalized (or Ratio) Cuts and Normalized (or Ratio) Cheeger Cuts, they do not provide a path for interpolating all the way to the unnormalized Cut cost. However, a different set of infinite families of balanced cost functions can be constructed that do enable such interpolation. Our proposed families are called the Compassionately Conservative Normalized (CCN) Cut and the Compassionately Conservative Ratio (CCR) Cut. Both are indexed by a parameter τ∈(0,∞); CCN_τ is equivalent to NCut for τ=2 and the unnormalized Cut cost for τ=0, and CCR_τ is equivalent to RCut for τ=2 and the unnormalized Cut cost for τ=0. As we can see from Fig. (<ref>), when we minimize CCN_τ and CCR_τ for the graph in Fig. (<ref>), different ranges of τ can be selected that will allow a bifurcation between solutions for any value of α.
  


This paper makes four novel contributions to graph partitioning in computer vision:

	
  * presenting Compassionately Conservative Balanced (CCB) Cuts: families of cut costs that enable normalizations ranging from Normalized/Ratio Cuts to unnormalized Cuts and can be naturally extended to k-way partitionings with k>2;
	
  * presenting a continuous relaxation of CCB Cut minimization and illuminating its connection to computing Piecewise Flat Embeddings (PFE) <cit.>;
	
  * presenting an efficient algorithm for solving the relaxed problem via minimizing a succession of reweighted Rayleigh quotients (IRRQ); and
	
  * demonstrating empirical advantages of the CCB Cut costs and the IRRQ minimization algorithm for the application of image segmentation.





§ BALANCED CUT COSTS


Consider an undirected weighted graph 𝒢 = (V,E) that we wish to partition into two disjoint subgraphs 𝒢_i = (V_i,E_i), i = 1,2, by removing the edges connecting V_1 and V_2. A standard cost of partitioning 𝒢 is the Cut cost, defined as the total weight of the edges that have been removed:

    Cut(V_1,V_2)    = ∑_v_i∈ V_1, v_j∈ V_2w_i,j ,

where the vertex set V = {v_1,v_2,⋯,v_n}, and 𝐖 is the weighted adjacency matrix (or affinity matrix) of 𝒢.

Minimizing the Cut cost is undesirable, however, as it can often yield partitionings that simply disconnect one vertex from the rest of the graph <cit.>. More balanced partitions emerge if the Cut cost is normalized by some function of the total sizes or total degrees (volumes) of the subgraphs. Such balanced cut costs can be expressed generally by:

    BCut(V_1,V_2)    = Cut(V_1,V_2)/Θ(V_1,V_2) ,

where Θ(V_1,V_2) is a symmetric function that decreases with increasing differences in the sizes or degrees of V_1 and V_2. A variety of balanced cut costs have been proposed in the literature, including the Normalized Cut <cit.>, Average Cut <cit.>, Ratio Cut <cit.>, and Normalized and Ratio Cheeger Cuts <cit.>.

In Theorem 4.1 of <cit.>, Bühler and Hein show that there exists an infinite family of balanced cut costs that contains Normalized, Average, Ratio, and Cheeger Cuts. If we consider the following function:

    Φ_p(v)    = 2^p/((1/v)^1/p-1 + (1/1-v)^1/p-1)^p-1 ,

for p>1 and v∈(0,1), then BCut(V_1,V_2) with Θ(V_1,V_2) = Φ_p(|V_1|/|V|) is the aforementioned BHR_p Cut, and it approaches the Ratio Cheeger Cut as p→ 1^+ and equals the Average/Ratio Cuts for p=2. If Θ(V_1,V_2) = Φ_p(Vol(V_1)/Vol(V)), BCut(V_1,V_2) is the BHN_p Cut, and it approaches the Normalized Cheeger Cut as p→ 1^+ and equals the Normalized Cut for p=2. (The volume of a subgraph is defined as Vol(V_ℓ) = ∑_v_j∈ V_ℓd_j, where d_j = ∑_mw_j,m is the degree of vertex v_j.) Note that this is a rescaling of the balanced cut costs in <cit.>, defined so that the maximum value of Θ(V_1,V_2) is always unity.

In addition to providing a way to interpolate between Cheeger Cuts and Normalized/Ratio Cuts for 1<p<2, (<ref>) enables cut costs with normalizations that are slightly more conservative (closer to unity) than Normalized/Ratio Cuts by selecting p>2. It is straightforward to show this by noting that:   

    Φ_∞(v)    = lim_p→∞Φ_p(v) = √(4v(1-v)) = √(Φ_2(v)) ,

and so 1>Φ_∞(v)>Φ_2(v) for all v∈(0,1), v 1/2, which can be seen in the left side of Figure <ref>.

The behavior of (<ref>) as p→∞ suggests that there is room to define even more conservative normalization functions. We do so in this paper by considering the following transformation of Φ_p(v):

    Ψ_τ(v)    = Ψ_2/p-1(v) = (Φ_p(v))^1/p-1
       = 2^p/(p-1)/(1/v)^1/p-1 + (1/1-v)^1/p-1
    	= 2^1+τ/2/(1/v)^τ/2 + (1/1-v)^τ/2 ,

where τ = 2/(p-1). (The reason for switching parametrizations from p to τ will be addressed at the end of Section <ref>.) Clearly Ψ_2(v) = Φ_2(v), and so Normalized/Ratio Cuts arise from employing (<ref>) in place of (<ref>) for τ=2. More interestingly, however, is that Ψ_0(v) = 1, and so for 0<τ<2, defining BCut(V_1,V_2) with Θ(V_1,V_2) = Ψ_τ(|V_1|/|V|) or Ψ_τ(Vol(V_1)/Vol(V)) provides a way to interpolate between Normalized/Ratio Cuts and Cuts with no normalization at all. This behavior of increasing Ψ_τ(v) as τ→ 0^+ can be seen in the right side of Figure <ref>. 

Of pedagogical interest is that lim_τ→∞Ψ_τ(v) = δ(v-1/2), and so as τ→∞, employing (<ref>) to define Θ(V_1,V_2) would yield balanced cut costs that diverge whenever the sizes or degrees of V_1 and V_2 are unequal. Since our interest in this paper is to explore the impact of cut costs having more conservative normalizations than Normalized/Ratio Cuts, we will restrict our attention to the use of Ψ_τ(v) for τ∈(0,2).



In addition to enabling a greater range of conservative normalizations, the use of (<ref>) in place of (<ref>) yields an added benefit: the resulting Balanced Cut costs can be directly extended to form costs of partitionings into k>2 subgraphs. (As discussed in <cit.>, it is not obvious whether such a direct extension to the Bühler-Hein cut costs exists.) If we now consider that we wish to partition 𝒢 into k disjoint subgraphs 𝒢_i = (V_i,E_i), i = 1,2,…,k, then an unbalanced way to measure the cost of the partitioning is the multiway cut cost, defined in terms of pairwise cut costs as:

    Cut(V_1,…,V_k)    = 1/2∑_ℓ=1^kCut(V_ℓ,V\ V_ℓ) .


The family of multiway balanced cut costs that we propose is described generally by the Compassionately  Balanced Cut:

    CCB_τ(V_1,…,V_k)    = 1/2∑_ℓ=1^kCut(V_ℓ,V\ V_ℓ)/2^τ/2(∑_v_j∈ V_ℓπ_j)^τ/2 ,

where π = [π_1,… ,π_n]^𝐓 is a user-defined vector of positive weights. If π = 1_n, then ∑_v_j∈ V_ℓπ_j = |V_ℓ|, and we refer to (<ref>) as the Compassionately Conservative Ratio Cut (CCR_τ). If π = 𝐝 (the degree vector), then ∑_v_j∈ V_ℓπ_j = Vol(V_ℓ), and we refer to (<ref>) as the Compassionately Conservative Normalized Cut (CCN_τ). With some algebraic manipulation, it is straightforward to see that (<ref>) is a generalization of (<ref>); when k=2, (<ref>) reduces to (<ref>) with Θ(V_1,V_2) = Ψ_τ(∑_v_j∈ V_1π_j/∑_v_j∈ Vπ_j). Furthermore, (<ref>) generalizes multiclass cut costs presented in the research literature; CCB_2, CCR_2, and CCN_2 are scaled versions of the Multiclass Penalized Cut <cit.>, the Multiclass Ratio Cut <cit.>, and the Multiclass Normalized Cut <cit.>, respectively, and so choosing τ∈(0,2) generates Multiclass Balanced Cut costs that interpolate between (<ref>) and any of these previously developed costs.




§ RELAXING THE CCB CUT


As with many balanced cut costs, minimizing the CCB Cut is NP-hard. However, we can formulate a continuous relaxation of CCB_τ for all τ>0. Unfortunately, the spectral clustering relaxation of BHN_p and BHR_p in terms of the second eigenvector of the graph p-Laplacian <cit.> is of no help; it is only tight as p→ 0^+ (and therefore not for τ∈(0,2)), and furthermore, CCB Cuts are not even members of the Bühler-Hein family of cuts except for when τ=p=2. Hence, we must identify a different relaxation. 

To do so, we first reformulate CCB_τ to express it in terms of an n× k indicator matrix 𝐗 so that X_i,j = 1 if v_i∈ V_j and X_i,j = 0 otherwise. If 𝐱_i is the i^th column of 𝐗, then ∑_v_j∈ V_iπ_j can be written in terms of the diagonal matrix Π = diag(π) as 𝐱_i^𝐓Π𝐱_i, and the pairwise cut cost between V_i and V\ V_i can be written as Cut(V_i,V\ V_i) = 𝐱_i^𝐓𝐖(1-𝐱_i) = 𝐱_i^𝐓𝐝 - 𝐱_i^𝐓𝐖𝐱_i = 𝐱_i^𝐓𝐃𝐱_i - 𝐱_i^𝐓𝐖𝐱_i = 𝐱_i^𝐓𝐋𝐱_i, where 𝐋 = 𝐃 - 𝐖. This allows us to express (<ref>) as:

    CCB_τ(V_1,…,V_k)    = 
    		1/2∑_ℓ=1^k𝐱_ℓ^𝐓𝐋𝐱_ℓ/2^τ/2(𝐱_ℓ^𝐓Π𝐱_ℓ)^τ/2 .

Minimizing (<ref>) is equivalent to minimizing (<ref>) subject to the constraint that 𝐗^𝐓𝐗 is positive diagonal, which ensures that none of the V_i's will collapse to the empty set.

To guide us towards an appropriate CCB_τ relaxation, we first consider how the Multiclass Penalized Cut (CCB_2) can be relaxed. Using an argument similar to Yu and Shi <cit.>, we see that if 𝐘 = 𝐗(𝐗^𝐓Π𝐗)^-1/2, then 𝐘^𝐓Π𝐘=𝐈 and (<ref>) is equivalent to a scalar multiple of tr(𝐘^𝐓𝐋𝐘). Hence, the solution to minimizing a relaxed version of CCB_2 is Ỹ = 𝐔𝐐, where 𝐔 is the n× k matrix whose columns are the orthonormal eigenvectors 𝐮_2, …, 𝐮_k+1 corresponding to the smallest nontrivial eigenvalues of Π^-1/2𝐋Π^-1/2, and 𝐐 is an arbitrary k× k orthogonal matrix. The optimal solution 𝐗̃ to (<ref>) with τ=2 can then be approximated by k-means clustering <cit.>, nonmaximal suppression <cit.> or Procrustean rounding <cit.> on Ỹ. 

Note that if we define ŷ_i to be the transpose of the i^th row of 𝐘, then minimizing the relaxed version of CCB_2 is equivalent to solving the constrained minimization problem:

    min_𝐘∈ℝ^n× k     𝒥_2(𝐘) := ∑_i=1^n∑_j=1^nw_i,jŷ_i-ŷ_j_2^2
    subject to:     𝐘^𝐓Π𝐘=𝐈 , 
    	  𝐘^𝐓Π1=0 ,

which, when π=𝐝, is identical to the Laplacian Eigenmaps (LE) problem <cit.> for computing embeddings of data that are assumed to lie on a manifold. The balance constraint 𝐘^𝐓Π1=0 is necessary to avoid eigenvectors of Π^-1/2𝐋Π^-1/2 corresponding to the trivial eigenvalue.

Turning our attention now to the more general case where τ>0, if we define α_ℓ = (∑_iπ_ix_i,ℓ^2)^-1/2 for ℓ = 1, … , k, and we note that (𝐗^𝐓Π𝐗)^-1/2 = diag(α), we can write:

    CCB_τ   (V_1,…,V_k) 
    	= 1/2∑_ℓ=1^k∑_i,jw_i,j(x_i,ℓ-x_j,ℓ)^2/2^τ/2(∑_iπ_ix_i,ℓ^2)^τ/2
       = 1/2^1+τ/2∑_ℓ=1^kα^τ_ℓ∑_i,jw_i,j|x_i,ℓ-x_j,ℓ|^τ
       = 1/2^1+τ/2∑_i,jw_i,j(𝐗^𝐓𝐃𝐗)^-1/2(𝐱̂_i-𝐱̂_j)^τ_τ
       = 1/2^1+τ/2∑_i,jw_i,jŷ_i-ŷ_j^τ_τ .

Hence, the relaxation of (<ref>) is obtained by dropping the condition that 𝐘 = 𝐗(𝐗^𝐓Π𝐗)^-1/2 and solving the constrained minimization problem:

    min_𝐘∈ℝ^n× k     𝒥_τ(𝐘) := ∑_i=1^n∑_j=1^nw_i,jŷ_i-ŷ_j^τ_τ
    subject to:     𝐘^𝐓Π𝐘=𝐈 .

Note that the balance constraint 𝐘^𝐓Π1=0 is only necessary for the case τ=2.

Remarkably, in the special case where π = 𝐝 and τ=1, (<ref>) is exactly the Piecewise Flat Embedding (PFE) problem <cit.>, whose solution is an embedding in which the data are naturally clustered due to the promotion of sparsity in the differences between rows of 𝐘. It is for this reason that we choose to parametrize CCB Cuts in terms of τ and not p: solutions to the relaxed versions of CCB_τ for τ∈(0,1] can be expected to be piecewise constant, consistent with the sparse nature of solutions to ℓ_τ-minimization problems for τ∈(0,1].




§ IRRQ MINIMIZATION ALGORITHM


While (<ref>) with τ = 2 has a solution that can be written in terms of the eigenvectors corresponding to the smallest k nontrivial eigenvalues of Π^-1/2𝐋Π^-1/2, no analytical form of the solution is known for τ≠ 2. In <cit.>, Yu et al. proposed approximating the solution to (<ref>) with τ = 1 via the Splitting Orthogonality Constraint (SOC) algorithm <cit.>, which requires an initial estimate of 𝐘 and performs a nested iteration with parameters at each level that must be tuned. While it is possible to partially generalize this approach to handle (<ref>) with τ > 1, 𝒥_τ(𝐘) is non-convex for τ∈(0,1), and so the SOC algorithm is not applicable in this regime. Furthermore, even in the regime in which it is applicable, the use of splitting in the algorithm formulation means that the solutions will not strictly satisfy the orthogonality constraint 𝐘^𝐓𝐃𝐘=𝐈. 

Here, we propose an alternative algorithm for solving (<ref>) that can be applied for all τ∈(0,2], that does not require an initial estimate of 𝐘, and that does strictly satisfy the orthogonality constraint. Our alternative algorithm is motivated from the Iteratively Reweighted Least Squares (IRLS) algorithms commonly used to solve ℓ_1-minimization problems <cit.>. In IRLS, ℓ_1-minimization is performed by iteratively solving a succession of weighted least-squares (ℓ_2-minimization) problems, with the weights updated at each iteration so as to decrease the impact of large residual errors. IRLS algorithms do require initialization, but it is the weights that must be initialized as opposed to the solution. Weights are typically initialized to unity (although they can be initialized differently by an expert user), and in specific cases <cit.>, IRLS algorithms have provable convergence guarantees.

In our relaxed problem (<ref>), the presence of the orthogonality constraint renders IRLS algorithms invalid. However, solutions to (<ref>) can be approximated by iteratively solving a series of constrained weighted ℓ_2-minimization problems, each of the form:

    min_𝐘∈ℝ^n× k     𝒥^Γ_2(𝐘) := ∑_i=1^n∑_j=1^nw_i,jγ_i,jŷ_i-ŷ_j_2^2
    subject to:     𝐘^𝐓Π𝐘=𝐈 , 
    	  𝐘^𝐓Π1=0 ,

where Γ is the n× n matrix of weights (with entries γ_i,j) that is updated at each iteration in a manner similar to IRLS. 

To establish a connection between (<ref>) and (<ref>), we first eliminate the balance constraint from (<ref>) using the result of the following Lemma, which is proved in Appendix <ref>:
 
	Let

    𝒴   = {𝐘∈ℝ^n× k|𝐘^𝐓Π𝐘=𝐈 ,𝐘^𝐓Π1=0} , 
    𝒢   = {𝐆∈ℝ^(n-1)× k|𝐆^𝐓𝐆=𝐈} ,

and define ℵ(𝐆) = Π^-1/2𝐁𝐆 for 𝐆∈𝒢, where 𝐁 = 𝐌(𝐌^𝐓𝐌)^-1/2, 𝐌∈ℝ^n×(n-1) is a full rank matrix with null(𝐌^𝐓) = span(𝐪), and 𝐪 = Π^1/21/Π^1/21. Then ℵ is a bijection from 𝒢 to 𝒴.
 

Using this Lemma allows us to solve (<ref>) by first solving:

    Ĝ := min_𝐆^𝐓𝐆 = 𝐈𝒥_2^Γ(ℵ(𝐆))  ,

and then computing 𝐘 = ℵ(Ĝ).

An analogy to IRLS suggests that under the assumption that component-wise differences in the embedding do not vanish, the best choice of weights for (<ref>) would be γ_i,j = ŷ_i^∗-ŷ_j^∗^τ_τ/ŷ_i^∗-ŷ_j^∗^2_2 for i j, where 𝐘^∗ is the solution to (<ref>). This choice of weights would yield 𝒥_2^Γ(𝐘^∗) = 𝒥_τ(𝐘^∗). In practice, however, 𝐘^∗ is unknown, and many of the component-wise differences in the embedding will vanish. Hence, we propose using regularized weights as suggested in <cit.>:

    γ_i,j := [w_i,jŷ_i-ŷ_j_2^2 + ε^2]^-1+τ/2 ,

and we update ε according to the schedule prescribed by <cit.>, which suggests:

    ε←min(ε,n^-1r(𝐘)_κ+1)  ,

where r(𝐘)_κ is the κ^th largest element of {w^1/2_i,jŷ_i-ŷ_j_2, ∀ i,j = 1, … , n }. 

Combining the steps of solving (<ref>) and updating (<ref>)–(<ref>) into a sequence of iterations yields Algorithm <ref> for computing the solution to (<ref>). Since (<ref>) is equivalent to (<ref>), and (<ref>) can be transformed into an unconstrained minimization of a Rayleigh Quotient, we term this algorithm Iteratively Reweighted Rayleigh Quotient (IRRQ) Minimization. 



Unlike SOC, IRRQ requires tuning of only a single hyperparameter κ, it can be used for any τ∈(0,2), and it guarantees a solution in which the orthogonality constraint is strictly enforced. Furthermore, IRRQ does not require a preprocessing step to estimate an initial clustering; rather, only the weights γ_i,j must be initialized, and they can all be initialized to unity. Interestingly, this initialization is equivalent to implicitly using an initial clustering that corresponds to the solution of the relaxed NCut problem. This is because 𝒥_2^11^𝐓(𝐘) is equivalent to the LE objective function 𝒥_2(𝐘) in (<ref>). If different initializations are desired, for instance, by computing an initial embedding 𝐘^(0) using a Gaussian Mixture Model as in <cit.>, these can be incorporated by setting the initial weights to be γ_i,j^(0) = ŷ_i^(0)-ŷ_j^(0)_τ^τ/ŷ_i^(0)-ŷ_j^(0)_2^2 or γ_i,j^(0) = [w_i,jŷ_i^(0)-ŷ_j^(0)_2^2+ε_0^2]^-1+τ/2.



 §.§ Solving IRRQ Step (a)


Computing 𝐘^(m+1) in step (a) of the IRRQ minimization algorithm is nontrivial. From the relationship between (<ref>)–(<ref>), we can see that computing 𝐘^(m+1) is equivalent to solving

    Ĝ^(m+1) := min_𝐆^𝐓𝐆 = 𝐈𝒥_2^Γ^(m)(ℵ(𝐆))  ,

and then computing 𝐘^(m+1) = ℵ(Ĝ^(m+1)). Problem (<ref>) can be expressed as the Rayleigh quotient minimization:

    Ĝ^(m+1)   := mintr(𝐆^𝐓𝐁^𝐓Π^-1/2𝐋̂^(m)Π^-1/2𝐁𝐆. 
                       ·.(𝐆^𝐓𝐆)^-1)  ,

where 𝐋̂^(m) is the Laplacian of the graph having weight matrix 𝐖⊙Γ^(m) and ⊙ denotes Hadamard product. The solution to (<ref>) is given by Ĝ^(m+1) = 𝐔𝐇, where 𝐔∈ℝ^(n-1)× k is the matrix whose columns are the orthonormal eigenvectors 𝐮_1, …, 𝐮_k corresponding to the smallest eigenvalues of 𝐁^𝐓Π^-1/2𝐋̂^(m)Π^-1/2𝐁, and 𝐇∈ℝ^k× k is an arbitrary orthogonal matrix. (Note that by eliminating the balance constraint, we also eliminate the possibility of a trivial eigenvalue of 𝐁^𝐓Π^-1/2𝐋̂^(m)Π^-1/2𝐁. Such an eigenvalue would have eigenvector 𝐩 for which 𝐁𝐩 is in the direction of 𝐪; however, this is contradicted by the fact that range(𝐁) = range(𝐌^𝐓).)

The ability of this solution to scale to large n depends critically on the structure of 𝐌, and on whether or not 𝐁 must explicitly be constructed. Since we are free to choose any full-rank n×(n-1) matrix 𝐌 such that 𝐌^𝐓𝐪=0, we make the particular choice 𝐌^𝐓 = [𝐪̂ |-q_1𝐈_n-1], where 𝐪̂ = [q_2,q_3,… ,q_n]^𝐓 and 𝐈_n-1 is the (n-1)×(n-1) identity matrix. This particular choice of 𝐌 is sparse, and therefore, as shown in Appendix <ref>, the multiplication of an arbitrary vector by 𝐁^𝐓Π^-1/2𝐋̂^(m)Π^-1/2𝐁 can be performed efficiently without explicitly constructing 𝐁.

A final note is that the solution to step (a) is not actually unique: 𝐘^(m+1) can be postmultiplied by 𝐇^𝐓 and still be a valid solution (recalling that 𝐇 is orthogonal). This is not a problem for steps (b) and (c) of Algorithm <ref>, because r and γ_i,j are invariant to such transformations of 𝐘^(m+1). As a consequence, IRRQ minimization could yield an entire family of solutions to the PFE problem. This could be problematic because the ℓ_τ-norms/pseudo-norms are not invariant under orthogonal transformations for τ≠ 2. In practice, however, we have found that the ℓ_τ-norms/pseudo-norms are minimized for the choice 𝐇=𝐈 and we therefore suggest this choice. Proof that this is the best choice remains an open problem.



 §.§ Choosing κ for Rapid Convergence


In IRLS algorithms for ℓ_τ-minimization, linear convergence can typically be achieved for τ≥ 1 and super-linear convergence for τ∈(0,1) if κ is chosen large enough so that if the resulting solution is θ-sparse, then κ>θ. (Actually, there are much more sophisticated convergence results in <cit.>, but this is a good rule-of-thumb.) Without attempting to prove convergence results for the IRRQ algorithm, we use a similar strategy in choosing κ. In practice, the main difficulty in choosing κ is that θ is not known exactly until the problem is solved. To approximate θ, we use an estimate θ̂ equal to twice the number of graph edges that connect different clusters from a k-means clustering performed on the initial embedding 𝐘^(0). For “scale-free" behavior, we introduce the hyperparameter κ̃∈(0,1) that can then be mapped to κ by κ = θ̂ + κ̃(2|E|-θ̂), where |E| is the total number of edges in the graph.  




§ CCB CUTS FOR SEGMENTATION




To investigate the performance of CCB Cuts for image segmentation, we segment the 200 test images in the BSDS500 dataset <cit.>, each of which has a variety of manually-labeled segmentations with different numbers of segments that can be used as ground truth. We explore three different affinity constructions for each image:

	
  * Lab: a Gaussian kernel on squared Euclidean distances in L^*a^*b^* color space;
	
  * mPb: an exponentiated negative maximum of the multiscale probability of boundary (mPb) using the code provided with the BSDS500 dataset <cit.>; and, 
	
  * PMI: an exponentiated version of a statistic related to pointwise mutual information (PMI) used in crisp boundary detection <cit.>.

We use a 10-pixel radius to define neighborhoods for affinity construction. For efficiency, we downsample each affinity matrix by two scale levels (and subsequently upsample the computed embeddings) using the strategy in <cit.>.  

Figure <ref> illustrates segmentation results on a BSDS500 test image for both multi-way and hierarchical 2-way segmentation using various types of balanced cuts. Although different segmentations appear to have different numbers of regions, many of the regions are small/singleton, and all segmentation results have the same number of regions. Figure <ref> shows how hierarchical 2-way segmentation using CCN Cuts with τ = 1 does not exhibit the iterative “chopping” behavior common to hierarchical NCuts minimization.



 §.§ Quantitative Validation


Drawing any conclusions based on visual assessment of segmentation maps can be problematic in the absence of quantitative validation. First, to validate that CCB segmentation yields less balanced partitions than NCut and Cheeger Cut-based segmentation, we show in Figure <ref> the “degree spread" for segmentation results from various methods across all test images, as measured by the ratio of the standard deviation of the partition volumes to the mean partition volume.

Next, we evaluate segmentation performance with respect to ground truth using the three criteria discussed in <cit.> and used in <cit.>: Segmentation covering, Probabilistic Rand Index (PRI), and Variation of Information (VI). Covering and PRI increase and VI decreases as segmentations become closer to the ground truth. We segment each BSDS500 test image multiple times by minimizing CCB Cuts for various values of τ∈(0,2], once corresponding to each value of k (number of segments) reflected in one of the ground-truth segmentations, and once for each of k = 5, 10, 15, 20, and 25, if any of these are not reflected in the ground truth. Each multi-way segmentation algorithm proceeds by solving/approximating the corresponding embedding and then subsequently performing k-means clustering on the result. We also perform segmentation using hierarchical 2-way cuts; in this case, clustering is performed at each step by identifying the threshold that best minimizes the balanced cut cost in question. For comparison purposes, we also apply the inverse power method of <cit.>; this method hierarchically approximates 2-way cuts that minimize the Normalized/Ratio Cheeger costs.



In CCB Cut minimization (for both multi-way and hierarchical 2-way segmentation), we iterate until the relative change in cost between two iterations falls below 1%, or until a maximum of 50 iterations are performed, whichever occurs first. The hyperparameter κ̃ is set to 10^-4 for Lab affinities and to 0.2 for mPb and PMI affinities. Following the strategy of <cit.>, we report results for both a fixed scheme, in which we run the algorithm repeatedly with k corresponding to each number of segments in the ground-truth and average the performance results from the multiple runs, and the dynamic scheme, in which we choose the value of k from k = 5, 10, 15, 20, and 25 that yields the best performance for a particular image. Table <ref> shows the performance results for a subset of the cut costs; to save space, we excluded results from smaller values of τ, which typically performed worse than τ=1 but better than τ=2, and we excluded results from ratio-costs, which are similar to those of normalized-costs.



A few interesting conclusions can be drawn. First, the use of simple Lab affinities surprisingly yields superior results compared to the more complicated mPb and PMI affinities. Second, PRI values appear to indicate that greater degrees of balance are better, whereas VI and Covering values seem to indicate that CCN with τ = 1 provides the best results. Third, better results are found when hierarchical 2-way segmentation is performed as opposed to simultaneous multiway segmentation. However, in our MATLAB implementation, multiway segmentation is significantly faster than hierarchical 2-way segmentation, as shown in Table <ref>. In the future, it would be interesting to compare these results to those of hierarchical 2-way segmentation via minimizing ratios of differences of set functions <cit.>.







§ CONCLUSION


Compassionately Conservative Balanced Cuts enable normalizations ranging from Normalized/Ratio Cuts to unnormalized Cuts, allowing a tradeoff between generating partitions that are too similar in size/degree and avoiding all singletons. They can be directly applied to the k-way partitioning problem for any k≥ 2, and their minimization can be relaxed into a problem that can be solved by minimizing a succession of Rayleigh quotients. Image segmentation experiments show that minimizing the CCB Cut yields more accurate results than minimizing NCuts/RCuts and generates regions having  greater variability in size/degree.




§ CODE

Prototype implementations of algorithms in this paper are available at the MATLAB Central File Exchange under File ID #66158.





§ ACKNOWLEDGEMENTS


NDC thanks Thomas Bühler and Matthias Hein for helpful discussions.





§ PROOF OF LEMMA <REF>
 

Let 𝐆∈𝒢. First, note that (ℵ(𝐆))^𝐓Π1 = 𝐆^𝐓𝐁^𝐓Π^1/21 = 𝐆^𝐓(𝐌^𝐓𝐌)^-1/2𝐌^𝐓Π^1/21, which vanishes because 𝐌^𝐓 annihilates vectors in the direction of 𝐪. Second, note that (ℵ(𝐆))^𝐓Πℵ(𝐆) = 𝐆^𝐓𝐁^𝐓𝐁𝐆 = 𝐆^𝐓(𝐌^𝐓𝐌)^-1/2𝐌^𝐓𝐌(𝐌^𝐓𝐌)^-1/2𝐆 = 𝐆^𝐓𝐆 = 𝐈. From these two properties, we see that ℵ(𝐆)∈𝒴, and so ℵ:𝒢→𝒴^'⊆𝒴. 

Now, define ℶ(𝐘) = 𝐁^†Π^1/2𝐘 for 𝐘∈𝒴, where 𝐁^† = (𝐁^𝐓𝐁)^-1𝐁^𝐓 = (𝐌^𝐓𝐌)^-1/2𝐌^𝐓. Then (ℶ(𝐘))^𝐓ℶ(𝐘) = 𝐘^𝐓Π^1/2(𝐁^†)^𝐓𝐁^†Π^1/2𝐘 = 𝐘^𝐓Π^1/2𝐌(𝐌^𝐓𝐌)^-1𝐌^𝐓Π^1/2𝐘. Noting that 𝐌(𝐌^𝐓𝐌)^-1𝐌^𝐓 is the orthogonal projector onto the subspace orthogonal to 𝐪, and that this orthogonal projector can be expressed alternatively as 𝐈 - 𝐪𝐪^𝐓, we can write (ℶ(𝐘))^𝐓ℶ(𝐘) = 𝐘^𝐓Π𝐘 - 𝐘^𝐓Π^1/2𝐪𝐪^𝐓Π^1/2𝐘 = 𝐈_k because 𝐘^𝐓Π^1/2𝐪 = 𝐘^𝐓Π1/Π^1/21 = 0 for 𝐘∈𝒴. Hence, ℶ:𝒴→𝒢^'⊆𝒢. 

Now, suppose ∃𝐘^∗∈𝒴\𝒴^'. Then ∃𝐆^∗∈𝒢 such that 𝐆^∗ = ℶ(𝐘^∗). Note that ℵ(𝐆^∗) = ℵ∘ℶ(𝐘^∗) = Π^-1/2𝐁𝐁^†Π^1/2𝐘^∗ = Π^-1/2𝐁(𝐁^𝐓𝐁)^-1𝐁^𝐓Π^1/2𝐘^∗. Since 𝐁(𝐁^𝐓𝐁)^-1𝐁^𝐓
is the orthogonal projector onto the column space of 𝐁, and this column space is equivalent to the column space of 𝐌, 𝐁(𝐁^𝐓𝐁)^-1𝐁^𝐓 = 𝐈-𝐪𝐪^𝐓. Hence, ℵ(𝐆^∗) = Π^-1/2(𝐈-𝐪𝐪^𝐓)Π^1/2𝐘^∗ = 𝐘^∗∈𝒴^', a contradiction. Hence, 𝒴^'=𝒴, and therefore, ℵ is a surjection from 𝒢 to 𝒴.

Finally, ℶ∘ℵ(𝐆) = 𝐁^†Π^1/2Π^-1/2𝐁𝐆 = 𝐁^†𝐁𝐆 = 𝐆, and so ℵ is invertible. Hence, ℵ is a bijection from 𝒢 to 𝒴. 





§ COMPUTING 𝐁^𝐓Π^-1/2𝐋Π^-1/2𝐁𝐱
 
If 𝐌^𝐓 = [𝐪̂ |-q_1𝐈_n-1], it can be verified that (𝐌^𝐓𝐌)^-1/2𝐌^𝐓 = [𝐪̂ |-𝐈_n-1+𝐪̂𝐪̂^𝐓/(1+q_1)]. Hence, 𝐬 = 𝐁^𝐓Π^-1/2𝐋Π^-1/2𝐁𝐱 can be computed without constructing any dense matrix by performing the following steps:

	
  * 𝐩 := [𝐪̂^𝐓𝐱 |-𝐭^𝐓+(𝐪̂^𝐓𝐱/1+q_1)𝐪̂^𝐓]^𝐓,
	
  * 𝐫 := Π^-1/2𝐋Π^-1/2𝐩,
	
  * 𝐬 := (r_1+𝐫^𝐓𝐪/1+q_1)𝐪̂ - 𝐫̂, where 𝐫̂ = [r_2,r_3,… ,r_n]^𝐓.




ieee



