Graph Cuts with Arbitrary Size Constraints Through Optimal Transport
Authors: Chakib Fettal
lazhar labiod
Mohamed Nadif
Venue: Accepted by TMLR ()

Abstract: A common way of partitioning graphs is through minimum cuts. One drawback of classical minimum cut methods is that they tend to produce small groups, which is why more balanced variants such as normalized and ratio cuts have seen more success. However, we believe that with these variants, the balance constraints can be too restrictive for some applications like for clustering of imbalanced datasets, while not being restrictive enough for when searching for perfectly balanced partitions. Here, we propose a new graph cut algorithm for partitioning graphs under arbitrary size constraints. We formulate the graph cut problem as a Gromov-Wasserstein with a concave regularizer problem. We then propose to solve it using an accelerated proximal GD algorithm which guarantees global convergence to a critical point, results in sparse solutions and only incurs an additional ratio of $\mathcal{O}(\log(n))$ compared to the classical spectral clustering algorithm but was seen to be more efficient.

Published in Transactions on Machine Learning Research (09/2024)
Graph Cuts with Arbitrary Size Constraints Through Optimal Transport
Chakib Fettal
chakib. thabib.fettal@eet...weo parris
CDC Informatique
Centre Borelli, UMR 9010, Université Paris Cité
Lazhar Labiod
lozhar labiod Io-ppii.
Centre Borelli, UMR 9010, Université Paris Cité
Mohamed Nadif
mohamed Sohamed.nadiffuuu paris.
Centre Borelli, UMR 9010, Université Paris Cité
Reviewed on OpenReview: https: // openreviee.. net/ forum? id= UG7rtrsuaT
Abstract
A common way of partitioning graphs is through minimum cuts. One drawback of classi- cal minimum cut methods is that they tend to produce small groups, which is why more balanced variants such as normalized and ratio cuts have seen more success. However, we believe that with these variants, the balance constraints can be too restrictive for some ap- plications like for clustering of imbalanced datasets, while not being restrictive enough for when searching for perfectly balanced partitions. Here, we propose a new graph cut algo- rithm for partitioning graphs under arbitrary size constraints. We formulate the graph cut problem
Ktomov-Wassersterr with concave regularizer problem. We then propose to solve it using an accelerated proximal GD algorithm which guarantees global convergence to a critical point, results in sparse solutions and only incurs an additional ratio of O(log(n)) compared to the classical spectral clustering algorithm but was seen to be more efficient.
1 Introduction
Clustering an important task in the field unsupervised machine learning. For example, the context of compuler vision, image clustering consists in grouping images into clusters such that the images within the same clusters are similar to each other, while those in different clusters are dissimilar. Applications are diverse and wide ranging, including, for example, content-basel image retrieval (Bhunia et al., 2020), image annotation (Cheng et al., 2018; Cai et al,, 2013), and image indexing (Cao et al., 2013). A popular image dataset is through creating graph from input images and partitioning it using
way of clustering techniques such as spectral clustering which solves the minimum cut (min-cut) problem. This is notably the case in subspace clustering where a self-represnntation matrix learned according to the subspaces in which images lie and a graph is built from this matrix (Tu al., 2012; Elhamifar & Vidal, 2013; Cai et al., 2022; et al., 2017; Zhou et al., 2018).
However, in practice, algorithms associated with the min-cut problem suffer from the formation of some small groups which leads to bad performance. As result, other versions of min-cut were proposed that take into account the size of the resulting groups, in order to make resulting partitions more balancod. This notion of size is variable, for example, in the Normalized Cut (ncut) (Shi & Malik, 2000), size refers to the total volume of a cluster, while in the Ratio Cut (rcut) problem (Hagen Kahng, 1992), it refers to the cardinality of cluster. A common method for solving the neut and reut problems is the spectral clustering approach (Von Luxburg, 2007; Ng et al., 2001) which is popular due often showing good empirical performance and being somewhat efficient.

---

Published in Transactions on Machine Learning Research (09/2024)
However, there are some weaknesses that apply to the spectral clustering algorithms and to most approaches tackling the ncut and rcut problems. A first one is that, for some applications, the cluster balancing is not strict enough, meaning that even if we include the size regularization into the min-cut problem, the groups are still not necessarily of similar size, which is why several truly balanced clustering algorithm have been proposed in the literature (Chen et al., 2017; et al., 2018; Chen et al., 2019). Another problem is that the balance constraint is too restrictive for many real world datascts, for example, a recent trend computer vision is to propose approaches dealing with long-tailed datasets which are datasets that contain head classes that represent most of the overall dataset and then have tail classes that represent small fraction of the overall dataset (Xu et al., 2022; Zhu et al., 2014). Some approaches propose integrating generic size constraints to the objective like in Genevay et al. (2019); Höppner & Klawonn (2008); Zhu et al. (2010), however these approaches directly deal with euclidean data instead of graphs.
In this paper; we propose a novel framework that can incorporate generic size constraints in a strict manner into min-cut problem using Optimal Transport. We sum up our contributions in this work as follows:
We introduce a GW problem with concave regularizer and frame it as graph cuts problem with an arbitrarily defined notion of size instead of specifically the volume or cardinality as is traditionally done in spectral clustering.
We then propose new way to solve this constrained graph cut problem using a nonconvex accel- crated proximal gradient scheme which guarantoes global convergence to critical point for specific step sizes.
Comprehensive experiments on real-life graphs and graphs built from image datasets using subspace clustering are performed. Results showcase the effectiveness of the proposed method in terms of obtaining the desired cluster sizes, clustcring performance and computational efficiency. For repro- ducibility purposes, we release our code
The rest of this paper is organized as follows: is discussed in section 3. The OT-cut problem and algorithm along with their analysis and links to prior research are given in section 4. We present experimental results and analysis section 5. Conclusions are then given in section 6.
Preliminaries are presented in Section 2. Some related work
2 Related Work
Our work is related with balanced clustering, as the latter is a special case of it, as well as with the more generic problem of constrained clustering, and GW based graph partitioning.
2.1 Balanced Clustering
A common class of constrained clustering problems is balanced clustering where we wish to obtain a partition with clusters of the same size. For example, DeSieno (1988) introduced conscience mechanism which penalizes clusters relative to their size, Ahalt et al. (1990), then employed it to develop the Frequency Sensitive Competitive Learning (FSCL) algorithm. In Li et al. (2018), authors proposed to leverage the exclusive lasso on the k-means and min-cut problems to regulate the balance degree of the clustering results. In Chen et al. (2017), authors proposed self-balanced min-cut algorithm for image clustering implicitly using exclusive lasso as balance regularizer in order to produce balanced partitions. Lin et al. (2019) proposed simplex algorithm to solve a minimum cost flow problem similar to k-means. Pei et al. (2020) proposes a clustering algorithm based on a unified framework of k-means and ratio-cut and balanced partitions. The time and space complexity of our method are both lincar with respect to the number .Wu et al. (2021) explores a balanced graph- based clustering model, named exponential-cut, via redesigning the intercluster compactness based on an exponential transformation. Liu et al. (2022) proposes to introduce novel balanced constraint to regularize the clustering results and constrain the size of clusters in spectral
httpp://g@tthub.ccm//tb hwt.://a...ccccccaaaaaaoo//rreee
2

---

Published in Transactions on Machine Learning Research (09/2024)
clustering. Wang et al. (2023) introduces discrete and balanced spectral clustering with scalability model that integrates the learning the continuous relaxation mairix and the discrete cluster indicator matrix into a single step. Nie et al. (2020) proposes to use balanced clustering algorithms to learn embeddings
2.2 Constrained Clustering
Some clustering approaches with generic size constraints, which be seen extension of balanced clustering, also exist. In Zhu et al. (2010), heuristic algorithm to transform size constrained clustering problems into integer linear programming problems was proposed. Authors in Ganganath et al. (2014) introduced a modified k-means algorithm which can be used to obtain clusters of preferred sizes. Clustering paradigms based on OT generally offer the possibility to set a target distribution for resulting partitions. In Nie et al. (2024), a parameter- carammetr-insensitivee min cut clustering with flexible size constraints is proposed. Genevay et al. (2019) proposed a doep clustering algorithm through optimal transport with entropic regularization. In Laclau et al. (2017); Titouan al. (2020); Fettal et al. (2022), authors proposed to lackle co-clustering and biclustering problems using OT demonstrating good empirical performance.
2.3 Gomov-Wasserstei Graph Clustering
The Gromov- Wasserstein (GW) partitioning paradigm S-GWL (Xu et al., 2019) supposes that the Gromov- Wasserstein discrepancy can uncover the clustering structure of the observed source graph & when the target graph Gdc only contains weighted self-connected isolated nodes, this means that the adjacency matrix of Gde is diagonal. The weights of this diagonal matrix well the source and target distribution are special fune- tions of the node degrees. Their approach uses regularized proximal gradient method well as a recursive partitioning scheme and can be used in multi-view clustering setting. The problem with this approach is its sensitivity to the hyperparameter setting which is problematic since it is an unsupervised method. Abrishami et al. (2020) proposes an OT metric with a component based view partitioning by assigning cost proportional to transport distance over graph edges. Another approach, SpecGWL (Chowdhury & Needham, 2021) generalizes spectral clustering using Gromov-Wassersterr discrepancy and heat kernels but suffers from high computational complexity. Given graph with node, its optimization procodure involves the computation of gradient which is in O(n log(n)) and an eigendecompostion O(n)) and therefore is not usable for large scale graphs. Liu & Wang (2022) leverages the OT probability to seek the edges of the graph that characterizes the local nonlinear structure of the original feature. recent approach (Yan et al., 2024) uses a spectral optimal transport barycenter model, which learns spectral embeddings by solving a barycenter problem equipped with an optimal transport discrepancy and guidance of data.
3 Preliminaries
In what follows, A = E M IT = 1} denotes the re-limensional standard simplex. 11(w, = (Z e RT* Z1 Z v) denotes the transportation polytope, where A and v A are the marginals of the joint distribution Z and Il is a vector of ones, its size can be inferred from the context. Matrices are denoted with uppercase boldface letters, and vectors with lowercase boldface letters. For a matrix M, its i-th row is m; and maj is the j-th entry of row i. Tr refers to the trace of a square matrix. ||-|| refers to the Frobenius norm.
3.1 Graph Cuts and Spectral Clustering
Minimum-cut Problem. Given an undirected graph g = (V,E) with weighted adjacency matrix W e
gaxn with n = =V1, cut is a partition of its vertices V into two disjoint subsets A and Á. The value of a cut is given by
cut(A)=
Σ Wij.
(1)
AEA.EEE
The goal of the minimum k-cut problem find a partition (A1,... Ax) of the set of vertices V into k different groups that is minimal in some metric. Intuitively, we wish for the edges between different subsets
3

---

Published in Transactions on Machine Learning Research (09/2024)
to have small weights, and for the edges within subset have large weights. Formally, it is defined as
min-cut(W, k)
min AR
Σ cut(AA))
(2)
This problem can also be stated trace minimization problem by representing the resulting partition A using an assignment matrix X such that for each row i, we have that
Tij {1 if vertex i is in Aj, otherwise.
(3)
This condition is equivalent to introducing two constraints which are X E 10, and X n. The minimum k-cut problem can then be formulated as
min-cut (W,
min Xe(O,1)nxa X1=1
LX),,
(4)
where L - W refers to the graph Laplacian of the graph G and D is the diagonal matrix of degree of W, ie., di E,
Eg Wij-
Normalized K-Cut Problem. In practice, solutions to the minimum k-cut problem do not yield satisfac- tory partitions due to the formation of small groups vertices. Consequently, versions of the problem that take inlo account some notion of 'size' for these groups have been proposed. The most commonly used one is normalized cut (Shi & Malik, 2000):
cut(AA)
ncut ncut(W. W. = min Ai....AA vol(A.)
(5)
where the volume can be conveniently written vol(A,) = x Dx, Another variant which is referred to as the ratio cut problem due to the different groups being normalized by their cardinality instead of their volumes:
k cut(A.)
rcut(W,K min
(6)
[Ai
where |A. = xf'x, This variant can be recovered from the normalized graph cut problem by replacing D with I in the computation of the volume.
Spectral Clustering. A common approach to solving the normalized graph cut problems, spectral clus- tering, relaxes the partition constraints on X and instcad considers a form of semi-orthgonnllity constraints. In the case of reut, we have reut written as a trace optimization problem:
rcut WW
k) min X
Tr (x)
x x X=I
On the other hand for ncut, the partition matrix X is substituted with H = D1/2X and a semi-orthogonality constraint is placod on this H. i.c.
neut (W min Tr 1//2D L1D'-1
(8)
HeR
H H=I
A solution H for the nout problem is formed by stacking the first k-eigenvectors the symmetrically normalized Laplacian L, = D D 1//LDDD/// its columns, and then applying clustering algorithm such k-means on its rows and assign the original data points accordingly (Ng et al., 2001). The principle is the same for solving reut but instead using the unnormalized Laplacian.
4

---

Published in Transactions on Machine Learning Research (09/2024)
3.2 Optimal Transport
Discrete optimal transport. The goal of the optimal transport problem is to find a minimal cost. trans- port plan X between a source probability distribution of w and target probability distribution v. Here we are interested the discrete Kantorovich formulation of OT (Kantorovich, 1942). When dealing with discrete probability distributions, said formulation is
OT w. v) min XeI((w.v)
(M,
(9)
where (...) the Frobenius product, M E Ruxk xk the cost matrix, and my quantifies the effort needed transport probability mass from W, Vy. Regularization can be introduced to further speed up computation of OT. Examples include entropic regularization (Cuturi, 2013; Altschuler et al., 2017) and low-rank regularization (Scetbon & marco cuturi, 2022), well as, other types of approximations (Quanrud, 2019; Jambulapati et al., 2019).
Discrete Gromov- Wasserstein Discrepancy. The discrete Gromov- Wasserstein (GW) discrepancy (Peyró et al., 2016) is an extension of optimal transport to the case where the source and target distri- butions are defined on different metric spaces:
M,,V) = min & = Σ L(maer MIy Xell(w,v)
(10)
where M E R=x" and M E R Rxk are similarity matrices defined on the source space and target space respectively, and L R IR a divergence measure between scalars, [(M,, symbolizes the nxnxkxk tensor of all pairwise divergences between the elements of M and M. & denotes tensor-matrix product. Different approximation schemes have been explored for this problem Altschuler et al. (2018).
4 Proposed Methodology
In this section, we derive our OT-based constrained graph cut problem and propose a nonconvex proximal GD algorithm which guarantees global convergence to critical point.
4.1 Normalized Cuts via Optimal Transport
As already mentioned, the good performance of the normalized cut algorithm comes from the normalization by the volume of cach group in the cut. However, the size constraint is not hard one, meaning that obtained groups are not of exactly the same volume. This leads us to propose to replace the volume normalization by strict balancing constraint as follows:
min Σ cut( s.t. vol(Ai) =... vol(A)).
(11)
this problem can be rewritten as the following trace minimization problem:
min Tr(X LX)
subject to:
X E RT*
(12)
X1 = D1,
(x; sums to the degree of node i) (clusters are balanced w.r.t degrees)
x Σ, du 1,
V v/|xx|lo- =
(a node belongs to unique cluster.)
Here, I1-Ilo is the zero norm that returns the number of nonzero elements in its argument. This problem may not have feasible solutions. However, by dropping the fourth constraint, this problem becomes instance
5

---

Published in Transactions on Machine Learning Research (09/2024)
problem with an l loss which is always feasible. Specifically, the first, second of the constraints are equivalent to defining X to be an element of the transportation polytope with a
and third
uniform target distribution and a source distribution consisting of the degrees of the nodes. These degrees can be represented as proportions instead of absolute quantitics by dividing them over their sum, yiclding the following problem:
min
Trx
(13)
Xell
Σ
D1
D1 A
This formulation is special case of the Gromov- Wasserstein problem for source space whose similarity matrix in the initial space is M = -L and whose similarity matrix in the destination space is M =I=I Note that ratio cut version can be obtained by replacing the volume constraint with
A -... AA
(14)
in problem 11, and similarly in problem 13, by substituting the identity matrix I for the degree matrix D, giving rise to:
min xe
Lx(X
(15)
4.2 Graph Cuts with Arbitrary Size Constraints
From the previous problem, it is casy to see that target distribution does not need to be uniform, and such, any distribution can be considered, leading to further applications like imbalanced dataset clustering. Another observation is that any notion of size can be considered and not only the volume cardinality of the formed node groups. We formulate an initial version of the generic optimal transport graph cut problem as:
min XEII(T
Tr(X LX) = min x²)
X)X,X),
(16)
XeII(T"
where тे the relative 'size' of the element i and πÿJ is the desired relative 'size' of the group j. Through the form that uses the Frobenius product, it is casy to see how our problem is related to the Gromov-Wassersten Wasserstein problem.
4.3 Regularization for Sparse Solutions
We wish to obtain sparse solutions in order to easily interpret them partition matrices of the input graph. We do so by aiming to find solutions over the extreme points of the transportation polytope which are matrices that have at most n + k - non-zero entries (Peyré et al., 2019). We do so by introducing a regularization term to problem 16. Consequently, we consider the following problem which we coin OT-cut:
min OT-cut(X, TT) XxII("",mm))
Tr(X
||XKK
(17)
where A E R is the regularization trade-off parameter. It should be noted that our regularizer is concave. We also define two special cases of this problem, which are based on the neut and rcut problems. The first one which we call OT-ncut is obtained by fixing the hyper-parameter T, DD D1 while the second one OT-rcut is obtained by substituting the D in the previous formula with I and forcing the target to be uniform. Figure 1 shows the evolution of the objective on different datasets.
4.4 Optimization, Convergence and Complexity
We wish to solve problem 17 which is nonconvex, but algorithms with convergence guarantees exist for problems of this form. Specifically, we will be using a nonconvex proximal gradient descent based on Li & Lin (2015). The pseudocode is given in algorithm 1.
Proposition 1. For step size a thx the iterates ((t) generated by the nonconver PGD algorithm for our problem are all extreme points of the transporation polytope, and as such, have at most n + k nonzero entries.

---

Published in Transactions on Machine Learning Research (09/2024)
Proof. Problem 17 can be equivalently stated by writing the constraint term in the loss function:
min
Tr(X LX)
/I( X|2
(18)
S(x)
9(X)
where Te is the characteristic function of set C i.e.
{ 0, i C,
lc
+00, C
Since we use proximal descent scheme, we show how compute the proximal operator for our loss function:
prox (()) - -V -prxx
(x TV
( (x())()))
prox ar aimm m+))) -1
(I (I-20L)x(0)=
arg min
1
Z (1-2aL)X(0)
- |Z|2
x** 20
arg min
| 2
1
(I
2x
1 Tr Z (I (1-2aL)X(o) - 1
Z . 2a
2a
We assumed that obtain:
22 by substituting for x into the previous formula and dropping the constant term,
arg min Tr (z (2aL -2xL- arg min x=)
(z. (2aL 12aL-1)a I)x(").
Z xx²)
This is the classical OT problem. Its resolution possible by stating as the earth-mover's s distance (EMD) linear program (Hitchcock, 1941) and using the network simplex algorithm (Bonneel et al., 2011).
Proposition 2. Algorithm 1 globally converges for step size a where is the smoothness constant of TrX LX).
Proof. Here, we have that f is proper and s-smooth i.e. Vf s-Lipschitz. g proper and lower semi- continuous. Additionally, f + g is cocrcive. Then, according to theorem in Li & Lin (2015), nonconvex accelerated proximal GD globally converges for <
Proposition 3. For graph with nodes, the complecity of iteration of the proposed algorithm is O (kn² log.).
Proof. We note that in practice n >> k and that the complexity of the network simplex algorithm for some graph GEMD (VEND, VEMD) is in D(IVEMD|\EEM) has [VEDL = n + (since n >> k we can drop the k) and |ΣED3] = nk. The other operation that is performed during each iteration is the matrix multiplication whose complexity in O(k[E)) where [[] is the number of edges the original graph. In the worst case when matrix L fully dense, we have that =
log (EED (Orlin, 1997). In our case, this graph
5
Experiments
We evaluated the clustering performance of our two variants 0T-ncut and OT-rcut algorithms against the spectral clustering algorithm and state-of-the-art OT-based graph clustering approaches.
5.1
Datasets
We perform experiments on graphs constructed from image datasets, namely, MNIST (Deng, 2012), Fashion- MNIST (Xiao et al., 2017) and KMNIST (Clanuwat et al., 2018). We generate these graphs using three subspace clustering approaches: low-rank subspace clustering (LRSC) (Vidal & Favaro, 2014), least-square regression subspace clustering (LSR) (Lu et al., 2012) and elastic net subspace clustering (ENSC) (You
7

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm 1: Nonconvex Accelerated PGD for OT-cut
Data: Adjacency matrix, π node size distribution, x' cluster size distribution, Ginit initial partition matrix, a = 2X < + step size, mazlter maximum number of iterations. Result: G partition of the graph.
Construct Laplacian matrix L from the adjacency matrix A; X arg OT (G inits T,, x²);
2 + x ( ( t (
C + 0, c 1;
while mazlter not reached do
(()) (() + --1 ( (Z (()) (x(11(((1)) x(=I)));
(((-1) = arg OT a
at (22LL - I) n²; ,²',") )
v(+1) arg OT ((aaL I)x(!), TT", T²);
G+1 = (V4c) + 1 1)/2;
((+11 1(++)), if loss (z(+ < loss (V(++2)
v((+)), otherwise.
end
Generate partition matrix G by assigning each node to the (arg max, x,)-th partition.;
Table 1: Dataset Statistics. The balance ratio is the ratio of the most frequent class over the least frequent one.
Type
Dataset
Nodes
Graph & Edges
Sparsity
Clusters
Balance Ratio
LRSC (100,000,000)
0.0%
MNIST
10,000
LSR (100,000,000)
0.0%
10
1.272
ENSC (785,744)
99.2%
Graphs
LRSC (100,000,000)
0.0%
Built From Images
Fashion-MNIST
10,000
LSR (100,000,000)
0.0%
10
1.0
ENSC (458,390)
99.5%
LSR (100,000,000)
0.0%
KMNIST
10,000
LRSC (100,000,000)
0.0%
1.0
ENSC (817,124)
99.2%
ACM
3,025
2,210,761
75.8%
1.099
Naturally
DBLP
4,057
6,772,278
58.9%
1.607
Occuring
Graphs
Village
1,991
16,800
99.6%
12
3.792
EU-Email
1,005
32,770
96.8%
42
109.0
et al., 2016). We also consider four graph datasets: DBLP, a co-term citation network; and ACM, a co- author citation networks (Fan al., 2020). EU-Email an email network from large European rescarch institution (Leskovee & Krevl, 2014). Indian Indian-Village describes interactions among villagers in Indian villages (Banerjee al., 2013). The statiltical summaries of these datasets available in Table 1.

---

Published in Transactions on Machine Learning Research (09/2024)
Table 2: Average (#sd) clustering performance and running times on the graph built from images. The best performance is highlighted bold, the lowest (highest) runtime is highlighted in blue (red).
MNIST
Fashion-MNIST
KMNIST
Graph
Method
ARI
Time
ARI
Time
ARI
Time
Spectral
0.4134 20.0003
10.28
0.1742
20.0003
10.51
0,4067
#0.0
9.83
S-GWL
0.0488 10.0
7.88
0.0188
10.0
7.84
0.0560
10.0
7.98
LRSC
SpecGWL
0.0248 +0.0
453.19
0.0111
397.19
0.0145
+0.0
383.23
OT-rcut
0.4516 +0.0273
5.58
0.2231 10.0051
5.82
0.4157
20.0154
6.15
OT-neut
0.4751 =0.0383
6.12
0.2291
#0.01488
6.11
0.3832
#0.0279
5.88
Spectral
0.311 #0.0002
8.82
0.1486
#0.0001
10.19
0.3631
+0.0001
9.72
S-GWL
0.0628 20.0
8.2
0.0357 #0.0
7.93
0.0593
20.0
8.01
LSR
SpecGWL
0.1127 40.0
454.06
0.0341
454.26
0.0267
4.000
407.55
OT-reut
0.3723 #0.0377
6.23
0.1771
#0.0164
6.61
0.4335
#0.0105
6.01
OT-neut
0.3458 +0.0267
5.77
0.1915
+0.0131
5.72
0.4301
+0.0075
5.87
Spectral
0.1206
+0.0001
13.28
0.1164
+.000
12.62
0.4321
+-000007
13.6
S-GWL
0.0798 +0.0
8.05
0.0362 #0.0
7.85
0.0422
=0.0
7.96
ENSC
SpecGWL 0.5444
20.0
268.12
0.1082
288.75
0.4020
10.0
287.06
OT-reut
0.4228
+-000994
5.47
0.2113
+-0.0257
6.18
0.2924
+-0.5589
6.27
OT-ncut
0.3882 10.0718
5.68
0.2251
10.0191
5.77
0.2771
1:000226
5.83
Table 3: Average (#sd) clustering performance and rumning times on the graph datasets. Same legend
for Table 2.
EU-Email
Village
ACM
DBLP
Method
ARI
Time
ARI
Time
ARI
Time
ARI
Time
Spectral
0.2445 +0.0133
1.13
0.3892
+0.1934
0.76
0.1599
#0.003
1.83
0.0039 #0.0053
16.49
Greedy
0.1711 10.0
2.28
0.0002
10.0
1.15
0.0 20.0
37.59
0.1375 10.0
144.21
Infomap
0.3087 +0.0
0.09
-0.0001
30.71
S-GWL
0,2684 #0.0
2.11
0,5333
#0.0
4.26
0.1873 =0.0
2.09
0.0 +0.0
18.42
SpecGWL
0.1125 =0.0
0.59
0,5887
10.0
0.89
0.008 20.0
4.65
0.2891 #0.0
13.66
OT-reut
0.2629
1:0.0096
0.22
0.5969
40.0505
0.27
0.26443
4.00249
0.69
0.3119 =0.0279
1.45
OT-ncut
0.2687 #0.0094
0.20
0.4819
+0.0369
0.30
0.2167
20.045
0.77
0.1721
#0.0674
1.33
5.2 Performance Metrics
We adopt Adjusted Rand Index (ART) (Hubert & Arabie, 1985) to evaluate clustering performance. It takes values between and -0.5; larger values signify better performance. To evaluate the concordance of the desired and the obtained cluster distributions, we use the Kullback-Leibler (KL) divergence (Kullback & Leibler, 1951). The KL divergence between two perfectly matching distributions will be equal to zero. Otherwise, it would be greater than zero. Smaller KL values signify better concordance.
5.3 Experimental settings
Our two variants, OT-ncut and OT-rcut are implemented via the Python optimal transport package (POT) (Flamary et al., 2021). We use random initialization and use uniform target distributions unless explicitly stated otherwise. We also set a = 1/2 and the number of iterations to 30 for the image graphs and 20 for the other graphs. We also use normalized laplacian matrices. For the basclines, we use the Scikit-Learn (Pedregosa al., 2011) implementation of spectral clustering. We use the official implementations of S-GWL (Xu et al., 2019) and SpecGWT. (Chowdhury & Needham, 2021). Furthermore, considered the baselines

---

Published in Transactions on Machine Learning Research (09/2024)
20
25
20
25
25 Baration
20
25
6
10
15 Bonaainn
10
15
20
Foar aloon
(a) OT-nnuu on Village
(b) OT-neut on EU-Email
(c) OT-nnuut on DBLP
(d) OT-nnuut on ACM
20
25 Iaration
20
25
25
20
25
10 15
10
15
20
25
Iarraton
Itoradion
lbarado1
(e) OT-rrct on Village
(f) OT--rcut on EU-Email
(g)
OT-reut on DBLP
(h) OT-reut on ACM
Figure Evolution of the objective as function of the number iterations.
Table 4: Faithfulness to the constraints: KL divergence between the desired and the resulting cluster distri- butions. A value of zero reflects perfect match between the constraint and the result.
Datasct
Graph
OT-reut
OT-ncut
Dataset
Graph
OT-rcut
OT-neut
LRSC
0.0 10.0
0.0 20.0
LRSC
0.0 10.0
0.0001 10.0001
KMNIST
LSR
0.0 #0.0
0.0001 10.0001
MNIST
LSR
0.0 20.0
0.0001 20.0001
ENSC
0.0 4.0.0
0.0 40000
ENSC
0.0 +0.0
0.0 =0.0
ACM
0.0 10.0
0.0 10.0
LRSC
0.0 +0.00
0.0001 #0.0001
DBLP
0.0 40.0
0.00.0 20.0021
LSR
0.0 10.0
0.0001 10.0001
Village
0.0 40.0
0.0011 +000027
ENSC
0.0 20.0
0.0 =0.0
EU-Email
0.0 10.0
0.0004 10.0007
used Chowdhury & Ncodham (2021), namely, Fluid (Parés al., 2018), Louvain (Blondel al., 2008).
Infomap (Rosvall et al., 2009) and Greedy (Clauset al., 2004):
1. We reported results on the naturally occuring graphs only due to excessive run times over the image graphs.
2. Louvain and Tnfomap do not allow specify the number of clusters. Comparison between partitions with different number of clusters using ARI is not meaningful. As such, only reported results on datasets for which those algorithms manage to recover the ground truth-nunber of clusters (for all runs). Louvain was dropped since it never managed to find the ground-trute number of clusters.
Fluid was dropped because it requires graphs that have a single connected component. This not the case for any of the naturally occurring graphs.
4. We use the implementations of Louvain, Fluid, and Greedy provided in the networkx package (Hag- berg et al., 2008). We use the implementation of Infomap provided in Edler et al. (2024).
All experiments were run five times and were performed on a 64gb RAM machine with 12th Gen Intel(R) CTre(TM) 19-12950HX (24 CPUs) processor with frequency of 2.3GHz.
10

---

Published in Transactions on Machine Learning Research (09/2024)
Specre
132
682
(a) Number of nodes.
(b) Number of clusters.
Figure 2: Running times of Spectral clustering and OT-neut on subsets of MNIST as function of the number of nodes and the number of clusters.
(a) O'T-neut on a graph built using a k-nn graph.
(b) O'T-reut on graph built using the RBF kernel.
Figure OT-nneu and OT-rreu results on toy datasets.
5.4 Results
Toy Datasets. Our algorithm deals with a graph cut-like criterion which means that it should partition a dataset according to its connectivity. This means that should work on datasets on which metric clustering approaches such as k-means fail. Two toy examples are given Figure and Figure 3b.
Clustering Performance. Table 3 presents the clustering performance the graph datasets. In all cases, one of our two variants has the best results in terms of ARI except on EU-Email where Infomap has the best performance. Table describes results obtained on image graph datasets. One of our two variants gives the best results on all three datasets with the graphs generated by LRSC and LSR. On the graphs gencrated by ENSC, the best result is obtained only on PAshi while SpeeGWI has the best results MNIST. Spectral clustering gives the best performance on KMNIST. Note that better results can also be obtained with our variants by trading-off some computational efficiency. Specifically, this can be done by using several different initializations and taking the one that leads to minimizing the objective the most.
Imbalanced Datascts. Results on long-tailod versions of CIFAR-10 are reported in table 5. We notice that using ground truth cluster distribution constraints leads to better results when comparing to the traditional spectral clustering algorithm.
Statistical Significance Testing Figure 5 shows the performance ranks of the different methods aver- aged over all the runs on the datascts we considered terms of ARI. The Nemónyi post-hoc rank test (Nemenyi, 1963) shows that OT-reut and OT-neut perform similarly and outperform the other approaches for confidence level of 95%. Other approaches perform similarly.
11

---

Published in Transactions on Machine Learning Research (09/2024)
CD
2
3
5
Table 5: Image clustering performance in terms ARI on the long-tailed CIFAR-10 10 datasets. Values are the averages over five runs.
OT-rcut
GWL SpecGWL
OT-ncut Spectral
Balance
5
10
50
100
Spectral
0.0566
0.0622
0.0584
0.0682
OT-neut
0.0831
0.0730
0.0794
0.0693
Figure 5: Neményi post-hoc rank test results. OT-reut and OT-neut outperform the baselines in statistically significant manner.
OT-rcut
0.0731
0.0779
0.0752
0.0574
Concordance of the Desired & Resulting Cluster Sizes. To evaluate algorithm's ability to produce a partition with the desired group size distribution, we use the KL divergence metric. Specifically, we compare the distribution obtained by our OT-reut and OT-neut variants against the target distribution specified as a hyperparameter (T'). Table 4 presents the KL divergences for both variants on various datasets. Predictably, our approaches achieve near-perfect performance on most datasets. Notably, OT-reut is always able to perfectly recover the desired group sizes. This has do with the fact that, up to constant, all the entries the solutions the reut problem are integers. This is not necessarily the case for ncut but the KL divergence is still very small due to the sparsity of the solutions.
Running Times. As shown in Table and Table 2, OT-neut and OT-reut are the fastest in terms of execution times compared other approaches on all datasets. As the graphs got larger, SpecGWT. consistently had the largest runtimes. We also report the rumning times of spectral clustering and our OT-neut approach on subsets of increasing size of MNIST well for increasing numbers of clusters in fig 2. The efficiency of our approach becomes increasingly significant. compared to spectral clustering the number of nodes grows. However, spectral clustering matches our approach's efficiency as the number of clusters increases. Our approach can be made more efficient by adopting sparse representations of the optimal transport plans when doing matrix multiplication.
6 Conclusion
In this paper we proposed a new graph cut algorithm for partitioning with arbitrary size constraints through optimal transport. This approach generalizes the concept of the normalized and ratio cut to arbitrary size distributions to any notion of size. We derived an algorithm that results in sparse solutions and guarantees global convergence to a critical point. Experiments on balanced and imbalanced datasets showed the supe- riority of our approach both in terms of clustering performance and empirical execution times compared to spectral clustering and other ba--based graph clustering approaches. They also demonstrated our approach's ability to recover partitions that match the desired ones which is valuable for practical problems where we wish to obtain balanced or constrained partitions.
7 Limitations
The node and cluster size distribution parameters can oither be set using prior domain knowledge or through luning them by trying different possible values and then selecting the best one via internal clustering quality metrics such as Davies-Bouldin index (Davies Bouldin, 1979). In cases where no domain knowledge exits and parameter tuning is impossible, we can weigh each node by its degree and give clusters uniform sizes. This option is similar what is done normalized cuts where no prior knowledge on size distributions is explicitly available Shi & Malik (2000). This issue will be studied in future works.
12

---

Published in Transactions on Machine Learning Research (09/2024)
References
Tara Abrishami, Nestor Guillen, Parker Rule, Zachary Schutzman, Justin Solomon, Thomas Weighill, and Si Wu. Geometry of graph partitions via optimal transport. SIAM Journal Scientific Compuling, 42 11.A3340-A3366 2020.
Stanley C Ahalt, Ashok K Krishnamurthy, Prakoon Chen, and Douglas E Melton. Competitive learning algorithms for vector quantization. Neural networks, 3(3):277-290, 1990.
Jason Altschuler, Jonathan Weed, and Philippe Rigollet. Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. Advances in newral information processing systems,, 30, 2017.
Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Weod. Approximating the quadratic trans- portation metric in near- hear-linear time. arXiv preprint arXiv:1810.1004; 10046, 2018
Abhijit Banerjee, Arun G Chandrasekhar, Esther Duflo, and Matthew O Jackson. The diffusion of microfi- nance. Science, 341 (2144))) 2013.
Ayan Kumar Bhunia, Yongxin Yang, Timothy M Hospedales, Tao Xiang, and Yi-Zhe Song. Sketch less for morc: On-tho-fly fine-grained skotch-based image retricval. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9779-9788, 9788, 2020.
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotle, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P1000: 2008.
Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement interpolation using lagrangian mass transport. In Proceedings of the 2011 SIGGRAPH Asía conference, pp. 1-12, 2011.
Jinyu Cai, Jicong Fan, Wenzhong Guo, Shiping Wang, Yunhe Zhang, and Zhao Zhang. Efficient deep embedded subspace clustering. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 10, 2022.
Xiao Cai, Feiping Nie, Weidong Cai, and Heng Huang, New graph structured sparsity model for multi- label image annotations. In Proceedings of the IEEE International Conference on Computer Vision, pp. 801- 801-808, 2013.
Jie Cao, Zhiang Wu, Junjie Wu, and Wenjie Liu. Towards information-thcoretin k-means clustering for image indexing. Signal Processing, 93(7):2026 2037, 2013.
Xisojun Chen, Joshua Zhexue Haung, Feiping Nie, Renjie Chen, and Qingyao Wu. A self-balanced min-cut algorithm for image clustering. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2061-2069, 2017.
Xiaojun Chen, Renjie Chen, Qingyao Wu, Yixiang Fang, Feiping Nie, and Joshua Zhexue Huang. Labin: balanced min cut for large-scale data. IEEE transactions on neural networks and learning systems, 31(3): 725-736, 2019.
Qimin Cheng, Qian Zhang, Peng Fu, Conghuan Tu, and Sen Li. survey and analysis on automatic image annotation. Pattern Recognition, 022222259.. 2018.
Samir Chowdhury and Tom Needham. Generalized spectral clustering via gromov-wasserstein learning. Tn International Conference on Artificial Intelligence and Statistics, pp. 712 720. PMLR, 2021.
Tarin Clanuwat, Mikel Bober-Lrizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature. arXiv preprint arXiv:1812.01114 2018.
Aaron Clauset, Mark EJ Newman, and Cristopher Moore. Finding community structure in very large networks. Physical Review E SSalistical, Nondinear, and Soft Maller Physics, 70(6):066111, 2004.
13

---

Published in Transactions on Machine Learning Research (09/2024)
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural
information processing systems, 26, 2013.
David L Davies and Donald W Bouldin. A cluster separation measure. IEEE transactions on pottern analysis and machine intelligence, (2):224-222 1979.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6)1141-142, 2012.
Duane DeSieno. Adding a conscience to competitive learning. In JCNN, volume 1, 1988.
Daniel Edler, Anton Holmgren, and Martin Rosvall. The MapEquation software package. https: / //mapequation. org, 2024.
Ehsan Elhamifar and René Vidal. Sparse subspace clustering: Algorithm, theory, and applications. JEEE transactions on pottern analysis and machine intelligence, 35(11):2765 2781, 2013.
Shaohua Fan, Xiao Wang, Chuan Shi, Emiao Lu, Ken Lin, and Bai Wang. One2multi graph autoencoder for multi-view graph clustering. In proceedings of the web conference 2020, pp. 3070 3076, 2020.
Chakib Fettal, Lazhar Labiod, and Mohamed Nadif. Efficient and effective optimal transport-based biclus- tering. Advances in Neural Information Processing Systems, 35:32989 33000, 2022.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurelic Boisbunon, Stanislas Cham- bon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. The Journal of Machine Leurning Research, 22(1), jan 2021. ISSN 1532-4435.
Nuwan Ganganath, Chi-Tsun Cheng, and K Tse Chi. Data clustering with cluster size constraints using a modified k-means algorithm. In 2014 International Conference on Cyber-Enable Distributed Computing and Knowledge Discovery, pp. 158-161. TEFF, 2014.
Aude Genevay, Gabriel Dulac-Aroold, and Yean-Philipps Vert. Differentiable deep clustering with cluster size constraints. arXiv preprint 1910:1111.0000 09000, 2019.
Aric Hagberg, Pieter Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL),, Los Alamos, NM (United States), 2008.
Lars Hagen and Andrew B Kahng. New spectral methods for ratio cut partitioning and clustering. JEEE Iransactions on compuler-aided design of integrated circwits and systems, 11(9))1074 1085, 1992.
Frank L Hitchcock. The distribution of a product from several sources to numerous localitics. Journal of malhematics and plyysccs, 20(1-4):224 230, 1941.
Frank Höppner and Frank Klawonn. Clustering with size constraints. In Computational Intelligence Parudigns, pp. 167-180. Springer, 2008.
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2(1):193-22) 2288 1985.
Arun Jambulapati, Aaron Sidford, and Kevin Tian. direct tilde (1)(s/epsilo)) iteration parallel algorithm for optimal transport. Advances in Neural Information Processing Systems, 32, 2019.
Pan Ji, Tong Zhang, Hongdong Li, Mathieu Salzmann, and Ian Reid. Deep subspace clustering networks. Advances in neural information processing systems, 30, 2017.
IV Kantorovich. On the translocation of masses, dokl. Acad. Sei. URSS, 37:191-22 2011 1942.
Solomon Kullback and Richard Leibler. On information and sufficiency. The annals of mathematical slatistics, 22(1):79 86, 1951.
14

---

Published in Transactions on Machine Learning Research (09/2024)
Charlotte Laclau, levgen Redko, Basarab Matei, Younes Bennani, and Vincent Brault. Co-clustering through optimal transport. In International conference machine learning, pp. 1955-19644 PMLR, 2017.
Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection, 2014.
Huan Li and Zhouchen Lin. Accelerated proximal gradient methods for nonconvex programming. Advances in neural information processing systems, 28, 2015.
Zhihui Li, Feiping Nie, Xiaojun Chang, Zhigang Ma, and Yi Yang. Balanced clustering via exclusive lasso: A pragmatic approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Weibo Lin, Zhu He, and Mingyu Xiao. Balanced clustering: A uniform model and fast algorithm. In IJCAI, pp. 2987-2989 2019.
Chaodie Liu, Feiping Nie, Rong Wang, and Xuelong Li. Graph-based soft-balanced fuzzy clustering. IEEE Transactions on Fuzzy Systems, 31 (1(6):2044 2055, 2022.
Shujun Liu and Huajum Wang. Graph convolutional optimal transport for hyperspectral image spectral clustering. TEEE Transactions on Geoscience and Remole Sensing, 60:1-13, 2022.
Can-Yi Lu, Hai Min, Zhong-Qite Zhao, Lin Zhu, De-Shuang Huang, and Shuicheng Yan. Robust and efficient subspace segmentation via least squares regression. In Computer Vision ECCV 2012: 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 2012, Proceedings, Part VII 12, pp. 347- 360. Springer, 2012.
Peter Bjorn Nemenyi. Distribution-ffee multiple comparisons. Princcton University, 1963.
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14, 2001.
Feiping Nie, Wei Zhu, and Xuclong Li. Unsupervised large graph embedding based on balanced and hicrar- chical k-manns IEEE Transactions on Knowledge and Data Engineering, 34(4):2008-2)) 2019,, 2020.
Feiping Nie, Fangyuan Xie, Weizhong Yu, and Xuelong Li. Parameter-insensitive min cut clustering with flexible size constrains. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
James B Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming, 78(2):109-12) 129, 1997.
Ferran Parés, Dario Garcia Gasulla, Armand Vilalta, Jonatan Moreno, Eduard Ayguadé, Jesús Labarta, Ulises Cortés, and Toyotaro Suzumura. Fluid communities: A competitive, scalable and diverse community detection algorithm. In Complez Networks & Their Applications VI: Proceedings of Complex Networks 2017 (The Sizth International Conference on Complez Networks and Their Applications), pp. 229-240. Springer, 2018.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2882 2011.
Shenfei Pei, Feiping Nic, Rong Wang, and Xuclong Li. Efficient clustering based on unified view of k-means and ratio-cut. Advances in Neural Information Processing Systems, 33:1485; 14866, 2020.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-wasserstein averaging of kernel and distance matrices. In International conference machine learning, pp. 2664-2672. PMLR, 2016.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications data science. Foundalions and Trends in Machine Learning, 11(5-6):355-600 607, 2019.
15

---

Published in Transactions on Machine Learning Research (09/2024)
Kent Quanrud. Approximating Optimal Transport With Linear Programs. In Jeremy T. Fineman and Michael Mitzenmacher (eds.), 2nd Symposium on Simplicity in Algorithms (SOSA 2019), volume 69 of Open Access Series in Informatics (OASIes), pp. 6:1 6:,, Dagstuhl, Germany, 2019. Schloss Dagstuhl -Liibniz-Zentrum für Informatik. ISBN 978-3-95977-00996. doi: (.4230/OASIcs.SOSS.. C.SAA.209... URL htttps:/drrppp http:////rops...suu....... /t/////tiiiiee///ommmm//// 4230/OASIcs. SOSA. 2019.6.
Martin Rosvall, Daniel Axelsson, and Carl T Bergstrom. The map equation. The European Physical Journal Special Topics, 178(1):13 23, 2009.
Meyer Scetbon and marco cuturi. Low-rank optimal transport: Approximation, statisties and debiasing. In
Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advonces in Neural Informa- tion Processing Systems, 2022. URL http://pppeaeeeeeeeeeeeeeetroeap
pet/forrumidd44bNeeee
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888 905, 2000.
Vayer Titouan, levgen Redko, Rémi Flamary, and Nicolas Courty. Co-optimal transport. Advances in newral information processing systems, 05-17559-175700 2020.
René Vidal and Paolo Favaro. Low rank subspace clustering (Irsc). Pullern Recognition Letlers, 43:47 61, 2014.
Clrike Von Luxburg. tutorial on spectral clustering. Statistics and computing, 17(4):395-411 416, 2007.
Rong Wang, Huimin Chen, Yihang Lu, Qianrong Zhang, Feiping Nie, and Xuelong Li. Discrete and balanced spectral clustering with scalability. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
Danyang Wu, Feiping Nie, Jitao Lu, Rong Wang, and Xuelong Li. Balanced graph cut with exponential inter-cluster compactness. IEEE Transactions on Artificial Intelligence, 3(4):498 505, 2021.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07147, 2017.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov-wasserslein learning for graph partitioning and matching. Advances in neural information processing systems, 32, 2019.
Yue Xu, Lu Li, Jiefeng Li, and Cewu Lu. Constructing balance from imbalance for long-tailed image recognition. In European Conference on Computer Vision, pp. 38 36-56..7 Springer, 2022.
Yuguang Yan, Zhihao Xu, Canlin Yang, Jie Zhang, Ruichu Cai, and Michael Kwok Po Ng. An optimal transport view for subspace clustering and spectral clustering. In Proceedings of the AA Conference on Artificial Intelligence, volume 38, pp. 16281-16289, 2024.
Chong You, Chun-Guang Li, Daniel P Robinson, and René Vidal. Oracle based active set algorithm for scalable elastic net subspace clustering. In Proceedings of the IEEE conference computer vision and pollern recognilion, pp. 3928-39299 2016.
Pan Zhou, Yunqing Hou, and Jiashi Feng. Deep adversarial subspace clustering. In Proceedinggs of the IEEE conference on computer vision and pattern recognition, pp. 1596 1596-1604, 2018.
Shunzhi Zhu, Dingding Wang, and Tao Li. Data clustering with size constraints. Krowledge--asse Systems, 2888):883 889888899888 2010.
Xiangxin Zhu, Dragomir Anguelov, and Deva Ramanan. Capturing long- tail distributions of object subcate- gories. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 915-922, 2014.
16

---

Published in Transactions on Machine Learning Research (09/2024)
A List of symbols
A non-cxhaustive list of the symbols used throughout the paper is available in table 6.
Table 6: List of symbols.
Symbol
Description
g
(V,8)
A graph with a set of vertices V and edges &. partition of the nodes of graph g
A
A
The complementary set of A Adjacency matrix of Diagonal matrix of degrees of g Laplacian matrix of A partition matrix Volume of set of nodes Cardinality of a set Trace operalor
L
X
transport plan depending context
vol(.)
II
Tr
<..>>
Frobenius product
I-Il
Frobenius norm
Illlo
Zero norm Tensor-matrix product
II
A transportation polytope
M,M
Similarity matrices
L(M
The tensor of all pairwise divergences between the elements of M and M
G
A partition matrix Transport plans
Y,Z,Y
T n
Probability distributions
Ic
The characteristic function of C Vector of ones Scalars
1
Ct 0,,
17


Reviews:
[{"review_id": "larY3x9UzJ", "reviewer": "Reviewer_wByg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS \n- The experimental results are promising.\n\nIn one set of experiments, the authors compare their methods (OT-rcut, and OT-ncut) to spectral clustering, and current state of the art optimal transport-based methods (S-GWL [5], and SpecGWL [6]). They apply the methods to two classes of data: (1) datasets where graph structure is inherently present (the DBLP citation network, ACM co-author citation network, an emailing network between large European research institutions, and an interaction network between villages in India), and (2) datasets where graph structure must be constructed (MNIST, Fashion-MNIST, KMNIST). For the latter category, the authors apply different subspace clustering techniques to build network representations. The authors report on running time, and ability to recover ground truth clusters as quantified by the Adjusted Rand Index. Across almost all tasks, their methods demonstrate an advantage in terms of running time, and ability to recover ground truth.\n\n\nWEAKNESSES\n- The work lacks some amount of literature review, making it more difficult to understand its novelty. \n\nSection 5 of [7] seems to apply optimal transport to partition graphs in a similar manner. There is also extensive literature related to approximating the Gromov-Wasserstein distance for various choice of cost functionals [8][9]. Additionally, there is extensive literature on using proximal point methods and other numerical methods to solve optimal transport problems when the cost functional is linear [10][11] (and references therein). Though the present submission concerns solving a non-convex optimal transport problem, their method only converges to a critical point. In designing algorithms which converge to a critical point, related algorithms which work for convex settings are typically relevant.\n\n- The writing style can be greatly improved. Technical notation is difficult to parse at times. When the work first defines the Gromov-Wasserstein distance, its use of $\\otimes$ to denote a tensor-matrix product does not make it immediately clear which choice of indices the product is contracting on. \n\nSeemingly important technical details are omitted. An important point is made regarding the use of a concave regularizer to enforce sparsity. What is the matrix norm being used to regularize the Gromov-Wasserstein problem in equation 17? Description of the results are a bit imprecise. What is meant when it is said that the proximal GD algorithm \"has global guarantees\"? Convergence results present in [4] are only to critical points in the objective.\n\nThere are inconsistencies present in how experimental data is reported. What are the units when running time is reported? It is also noted that ARI \"takes values between 1 and -0.5\" (page 9). However, the ARI scores reported for the imbalanced dataset experiments (table 5) range much larger than 1. How are these values scaled?\n\n[4] Li, H. and Lin, Z., 2015. \"Accelerated proximal gradient methods for nonconvex programming.\"\n\n[5] Xu, H., Luo, D. and Carin, L., 2019. \"Scalable Gromov-Wasserstein learning for graph partitioning and matching.\"\n\n[6] Chowdhury, S. and Needham, T., 2021, \"Generalized spectral clustering via Gromov-Wasserstein learning.\"\n\n[7] Abrishami, T., Guillen, N., Rule, P., Schutzman, Z., Solomon, J., Weighill, T. and Wu, S., 2020. \"Geometry of graph partitions via optimal transport.\"\n\n[8] Altschuler, J., Bach, F., Rudi, A. and Weed, J., 2018. \"Approximating the quadratic transportation metric in near-linear time.\"\n\n[9] Quanrud, K., 2018. \"Approximating optimal transport with linear programs.\"\n\n[10] Jambulapati, A., Sidford, A. and Tian, K., 2019. \"A direct $\\tilde{O}(1/\\epsilon)$ iteration parallel algorithm for optimal transport.\"\n\n[11] Altschuler, J., Niles-Weed, J. and Rigollet, P., 2017. \"Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration.\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission studies a method of partitioning graphs via optimal transport. To illustrate their method, consider the following graph clustering problem, sometimes called $k$-balanced partitioning [1]. Given a weighted undirected graph $G = (V, E, w^G)$, and an integer $k > 0$, output a partition of $V$ into $k$ cuts $S\\_1, \\ldots, S\\_k \\subseteq V$ where simultaneously (1) the number of vertices in each partition is identical, and (2) the total capacity of edges across the partitions is minimized.\n\nFinding optimal solutions for minimum $k$-way partitioning is significantly consequential from both a practical and theoretical perspective. Practically, the problem is used to model tasks in image segmentation, VLSI design, parallel computing, and many other domains. Theoretically, the problem is famously intractable; it is known to be NP-hard, and there has been extensive theory developed to understand what algorithmic techniques lead to provably efficient / accurate methods [2][3].\n\nThe authors propose relaxing $k$-balanced partitioning to the following non-convex program. Let $\\mathbf{L} \\in \\mathbb{R}^{n \\times n}$ denote the Laplacian matrix of $G$, where $n$ is the number of vertices, and $\\langle \\cdot, \\cdot \\rangle$ denote the Froebenius inner product. \n$$\n\\begin{aligned}\n& \\min \n& & \\langle \\mathbf{X} \\mathbf{X}^{\\top}, \\mathbf{L} \\rangle \\\\\\\\\n& \\textup{s.t.}\n& & \\mathbf{X} \\mathbf{1} = \\tfrac{1}{n} \\cdot \\mathbf{1} \\\\\\\\\n& & & \\mathbf{X}^{\\top} \\mathbf{1} = \\tfrac{1}{k} \\cdot \\mathbf{1} \\\\\\\\\n& & & \\mathbf{X} \\in \\mathbb{R}\\_{\\geq 0}^{n \\times k}\n\\end{aligned}\n$$\n\nOne can see this is a relaxation by considering an integral solution which assigns $\\mathbf{X}\\_{ij} = \\frac{1}{n}$ if and only if $i \\in S\\_j$. The authors interpret solving this program as solving an optimal transport (Gromov-Wasserstein) problem. Fix an initial distribution $\\mu = \\frac{1}{n} \\cdot \\mathbf{1}\\_{n}$ uniform over the vertices, and terminal distribution $\\nu = \\frac{1}{k} \\cdot \\mathbf{1}\\_{k}$ uniform $k$ disjoint elements, then computing optimal $\\mathbf{X}$ is equivalent to finding the minimum cost transportation plan $\\mathbf{X}$ where $\\mathbf{X}\\_{ij}$ denotes how much mass in $\\nu\\_j$ should comprise of mass in $\\mu\\_i$.\n\nThe core contributions of this work are then the following.\n\n- The authors define the above non-convex relaxation for $k$-balanced partitioning, as well as other balanced partitioning problems. For example, they consider the task of $k$-balanced partitioning where cuts must now have identical volume instead of just the same number of vertices. The non-convex programs differ in how the initial, and terminal distributions $\\mu$ and $\\nu$ are chosen. The authors observe that freedom in choosing $\\mu$ and $\\nu$ allow for tackling a wide variety of graph partitioning tasks.\n\n- The authors then impose a matrix-norm regularizer to the above program, and provide a proximal-point method for solving the resulting regularized problem. Leveraging a framework of [4], the authors prove that their method converges to a critical point given an appropriate choice of step size.\n\n- Finally, the authors provide a promising set of experimental results supporting the viability of their method. \n\n[1] Andreev, K. and Räcke, H., 2004, \"Balanced graph partitioning.\"\n\n[2] Krauthgamer, R., Naor, J. and Schwartz, R., 2009. \"Partitioning graphs into balanced components.\"\n\n[3] Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Seffi, J. and Schwartz, R., 2014. \"Min-max graph partitioning and small set expansion.\"\n\n[4] Li, H. and Lin, Z., 2015. \"Accelerated proximal gradient methods for nonconvex programming.\"", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- [critical] It would be helpful to add some commentary regarding the references listed above, in particular those pertaining to modeling graph partitioning as a Gromov-Wasserstein problem. Alternatively, please explain why the references are not relevant to the current work. \n\n- [critical] It would be helpful to clarify the writing style by addressing the above questions in the body of the paper.\n\n- [non-critical] For the experiments demonstrating that the output cluster size distribution matches the terminal distribution given to the non-convex program, it would be helpful to test the method on a toy dataset generated by a stochastic block model where the block sizes are arbitrarily chosen.\n\n- [nit] There are a couple small typos in the paper.\n  - \"where an self-representation matrix\" -> \"where a...\" (page 1)\n  - \"there some weaknesses\" -> \"there are...\" (page 1)\n  - \"this means that its adjacency matrix is diagonal\" -> \"this means that the adjacency matrix of $\\mathcal{G}_{dc}$ is diagonal\" (page 2)\n  - \"with an weighted\" -> \"with a...\" (page 3)\n  - \"identity matrix$\\mathbf{I}$ -> missing space (page 5)\n  - \"according to Li & Lin...\" -> it is helpful to cite which theorem is being used (page 7)\n  - \"using ground truth...\" -> capitalize \"u\" (page 10)\n  - \"and this for any...\" -> \"and thus (?)\" (page 11)", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JYYwjyletA", "reviewer": "Reviewer_RrfN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The paper presents a novel graph cut algorithm that leverages optimal transport to partition graphs with flexible size constraints. This approach extends the capabilities of popular normalized and ratio cut methods, enabling the incorporation of desired cluster size distributions.\n\n2. The motivation for the proposed method is well-articulated, highlighting the limitations of existing normalized/ratio cut techniques. The paper demonstrates promising results on imbalanced datasets, which are prevalent in real-world scenarios.\n\n3. The theoretical analysis provided in the paper is comprehensive, offering proofs for the sparsity of solutions, algorithm convergence, and computational complexity. Notably, the additional computational cost compared to spectral clustering is limited to an O(log n) factor.\n\n\nWeaknesses\n\n1. Although the paper suggests setting size parameters using domain knowledge, random guesses, or cluster size distributions from other algorithms, further discussion or experiments investigating the sensitivity of results to these size parameters would be valuable. Providing guidance on best practices for determining size parameters in the absence of prior knowledge would enhance the paper's practical utility.\n\n2. The sensitivity of the proposed method to hyperparameters is acknowledged but not extensively investigated. Including a detailed sensitivity analysis that explores the impact of different hyperparameter settings on performance would offer valuable insights to users when selecting appropriate parameters for various datasets.\n\n3. The paper would benefit from ablation studies that elucidate the contribution of different components within the proposed method, such as the concave regularizer. These studies would provide a clearer understanding of the role and importance of each component.\n\n4. The results presented in Table 5 appear to exceed the valid range of the Adjusted Rand Index (ARI), which typically falls between -0.5 and 1. Clarification or correction of these results is necessary to ensure accuracy and consistency.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new graph cut algorithm for partitioning graphs under arbitrary size constraints. The graph cut problem is formulated as a Gromov-Wasserstein optimal transport problem with a concave regularizer. An accelerated proximal gradient descent algorithm is proposed to solve the problem, which has global convergence guarantees. Experiments on real-world graphs and graphs built from image datasets demonstrate the effectiveness of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. To better understand the scalability of the proposed method, it would be informative to include an analysis of how the empirical runtime varies with graph size and the number of clusters. The current runtime plot only compares the method to spectral clustering.\n\n2. While the experiments focus on comparisons with spectral clustering and other OT-based methods, the paper would be strengthened by incorporating comparisons to additional state-of-the-art graph clustering techniques beyond those based on optimal transport. This would provide a more comprehensive evaluation of the proposed method's performance.\n\n3. The notation used throughout the paper is dense, and some terms are introduced without sufficient explanation. Including a table that summarizes the notation and symbols used would greatly assist readers in following the mathematical formulations more easily, enhancing the overall readability of the paper.", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ivtMIIZPPw", "reviewer": "Reviewer_aAB4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Considering the flexibility of cluster sizes in practical applications, the optimal transport theory is applied to spectral clustering, leading to a spectral clustering framework with arbitrary cluster size constraints.\n\n2. In experiments, statistical significance testing is conducted to verify that the proposed approach significantly outperforms comparison methods. The KL divergence between the resulting and desired cluster size distributions is examined to confirm the proposed approach's ability to generate promising cluster size distributions.\n\nWeaknesses:\n1. The proposed model is not entirely accurate. A constraint \\mathbf{X} > \\mathcal{0} should be imposed on the transportation matrix \\mathbf{X}. Without this constraint, the conclusion that \\nabla f is s-Lipschitz cannot be guaranteed, and the partition matrix \\mathbf{G} cannot be obtained by assigning each node i to the (\\arg\\max_i \\mathbf{x}_i)-th partition.\n\n2. The selection of parameters in the proposed model significantly influences its effectiveness. While size parameters can be set using domain knowledge, this requires strong prior knowledge of the dataset's size distribution, which is impractical in real-world unsupervised applications. If these size parameters are determined using other algorithms, the performance of the proposed model will be heavily influenced by those algorithms. Thus, the question arises: how can size parameters be determined in a reasonable manner, and what method was used in this paper? Additionally, the regularization parameter \\lambda significantly affects the sparsity of the transportation matrix \\mathbf{X}. Specifically, a smaller \\lambda results in a sparser \\mathbf{X}. Why is \\lambda set to 1 when \\alpha is set to 1/2? If \\lambda is set to 1, can it be guaranteed that the nonzero entries of the matrix \\mathbf{X} be n + k - 1?\n\n3. The theoretical proofs are neither complete nor entirely correct. In the proof of Proposition 1, the constrained problem (17) is transformed into the regularized problem (18). A key issue is whether this transformation is indeed equivalent. If the constraints in problem (17) are moved to the objective as a regularization, a regularization parameter must be added, which will determine the equivalence relationship between problems (17) and (18). The proof of Proposition 1 seems to suggest that, since problem (17) can be transformed into the form of classical optimal transport, the n + k - 1 nonzero entries of matrix \\mathbf{X} can be guaranteed. This is not entirely accurate. The sparsity of matrix \\mathbf{X} is also influenced by the selection of the parameter \\lambda. Moreover, in Proposition 2, it should be stated that f + g is convex rather than concave, and the proof is notably incomplete. It is not straightforward to conclude that the nonconvex proximal GD algorithm can globally converge in a special case based solely on the literature by Li & Lin (2015). Detailed supplementary proof is necessary.\n\n4. The optimization algorithm is incomplete. The optimization procedure provided in the proof of Proposition 1 lacks sufficient detail for readers to fully understand it. Furthermore, the optimization procedure does not match the steps listed in Algorithm 1. Additionally, there is no explanation on how to initialize the partition matrix \\mathbf{G}.\n\n5. The literature review is incomplete. For balanced clustering, constrained clustering, and Gromov-Wasserstein graph clustering, numerous related and recent approaches exist. For instance, the following literature should be reviewed for balanced clustering:\n[1] Nie, F., Zhu, W. and Li, X., 2020. Unsupervised large graph embedding based on balanced and hierarchical k-means. IEEE Transactions on Knowledge and Data Engineering, 34(4), pp.2008-2019.\n[2] Pei, S., Nie, F., Wang, R. and Li, X., 2020. Efficient clustering based on a unified view of k-means and ratio-cut. Advances in Neural Information Processing Systems, 33, pp.14855-14866.\n[3] Wu, D., Nie, F., Lu, J., Wang, R. and  Li, X., 2021. Balanced graph cut with exponential inter-cluster compactness. IEEE Transactions on Artificial Intelligence, 3(4), pp.498-505.\n[4] Liu, C., Nie, F., Wang, R. and Li, X., 2022. Graph based soft-balanced fuzzy clustering. IEEE Transactions on Fuzzy Systems.\n[5] Wang, R., Chen, H., Lu, Y., Zhang, Q., Nie, F. and  Li, X., 2023. Discrete and Balanced Spectral Clustering With Scalability. IEEE Transactions on Pattern Analysis and Machine Intelligence.\nAdditionally, there are some studies related to this work:\n[6] Nie, F., Xie, F., Yu, W. and  Li, X., 2024. Parameter-insensitive Min Cut Clustering with Flexible Size Constrains. IEEE Transactions on Pattern Analysis and Machine Intelligence.\n[7] Liu, S. and Wang, H., 2022. Graph convolutional optimal transport for hyperspectral image spectral clustering. IEEE Transactions on Geoscience and Remote Sensing, 60, pp.1-13.\n[8] Yan, Y., Xu, Z., Yang, C., Zhang, J., Cai, R. and Ng, M. K. P., 2024, March. An Optimal Transport View for Subspace Clustering and Spectral Clustering. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 15, pp. 16281-16289).\n[9] Chowdhury, S. and Needham, T., 2021, March. Generalized spectral clustering via Gromov-Wasserstein learning. In International Conference on Artificial Intelligence and Statistics (pp. 712-720). PMLR.\n\n6. The experiments are neither complete nor convincing enough. The experimental settings are not described in sufficient detail to reproduce the reported results. It is recommended that the proposed approach be compared with more related works. The clustering performance is evaluated using only a single metric, ARI, and its value range is [-1, 1] rather than [-0.5, 1]. Additionally, the convergence results shown in Figure 1 clearly indicate that the proposed algorithm fails to converge. Why can't the convergence of the proposed algorithm be guaranteed?\n\n7. There are many unclear descriptions in this paper. All abbreviations should be accompanied by their full terms upon first use. Additionally, why is the proximal GD algorithm referred to as the accelerated proximal GD algorithm? What aspect reflects the acceleration? There are many variables that are not mentioned in the notation section. In formula (9), what does “<>” mean? Several relevant references are not cited, such as those for discrete optimal transport, the Kantorovich formulation, and the network simplex algorithm. The statements \"the proposed algorithm has globally convergence guarantees\" in the abstract and conclusion are incorrect, as this is only valid in a special case, and the proof is incomplete.\n\n8. There are numerous typos in this paper. In formula (6), \"W\" should be in bold. Below formula (9), \"c_{ij}\" should be \"m_{ij}\". In formula (12), below the notation \"\\min\", the optimization variable \\mathbf{X} should be indicated. In the proof of Proposition 2, \"coercive\" should be \"concave\".\n\n9. The overall language expression in this article requires further revision. The current version contains some grammar mistakes and expressions that are not natural.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors introduce a novel perspective on graph partitioning, utilizing optimal transport theory within a graph cut framework with arbitrary size constraints. They frame the classic graph cut problem as a Gromov-Wasserstein problem and apply a proximal gradient descent algorithm for its resolution. Experimental results on datasets with diverse balance levels demonstrate the effectiveness of the proposed approach.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the weaknesses mentioned above when revising the article. Please ensure that the revised version effectively resolves all the mentioned issues.", "broader_impact_concerns": "The broader impact section is not included in this article. Based on my assessment, there are no concerns regarding the ethical implications of this work that need to be addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There were significance differences among the reviewers about how new, accurate and convincing this paper is.  I believe that, after the revisions made during rebuttal, the paper can be accepted. I will however ask for a few further revisions:

- There was significant confusion among the reviewers regarding the claims of global convergence. I understand the authors' assigned meaning, but I think it would really clarify the contribution of the paper to include "global convergence to a critical point" or "to a stationary point" wherever this is mentioned.

- The authors should include a section on limitations of their method, which should include a discussion of the need for prior domain knowledge and how this can ameliorated in large applications.
Decision: Accept (poster)