A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data 
Authors: Jiajin Li
Jianheng Tang
Lemin Kong
Huikang Liu
Jia Li
Anthony Man-Cho So
Jose Blanchet
Venue: ICLR 2023 poster (2023)
Keywords: Gromov-Wasserstein
Graph Learning
Optimization

Abstract: In this work, we present the Bregman Alternating Projected Gradient (BAPG) method, a single-loop algorithm that offers an approximate solution to the Gromov-Wasserstein (GW) distance. 
We introduce a novel relaxation technique that balances accuracy and computational efficiency, albeit with some compromises in the feasibility of the coupling map.  Our analysis is based on the observation that the GW problem satisfies the Luo-Tseng error bound condition, which relates to estimating the distance of a point to the critical point set of the GW problem based on the optimality residual.
This observation allows us to provide an approximation bound for the distance between the fixed-point set of BAPG and the critical point set of GW. Moreover, under a mild  technical assumption, we can  show that BAPG converges to its fixed point set.
The effectiveness of BAPG has been validated through comprehensive numerical experiments in graph alignment and partition tasks, where it outperforms existing methods in terms of both solution quality and wall-clock time.

Published as a conference paper at ICLR 2023
A CONVERGENT SINGLE-LOOP ALGORITHM FOR RE- LAXATION OF GROMOV- WASSERSTENN IN GRAPH DATA
Jiajin Li
Jianheng Tang
Stanford University
HKUST (GZ)
jlajinli@stanford...
jtanghffcconeect.. ust
Lemin Kong
Huikang Liu SUFE
Jía Li
CUHK 1kongêse. cuhk. edu, hk
HKUST (GZ)
Lishutkangesufe.ddu cn
jialeelust. hk
Anthony Man-Cho So CUHK cuc.sssseecckeeeeee manchoso@se. cuhk cuhk.edu.hi. edu.hk
Jose Blanchet
Stanford University jose. www.b.ncnettstanffrrrettte
ABSTRACT
In this work, present the Bregman Alternating Projected Gradient (BAPG) method, a single-loop algorithm that offers an approximate solution to the Gromov- Wasserstein (GW) distance. We introduce novel relaxation technique that balances accuracy and computational efficiency, albeit with some compromises in the feasi- bility of the coupling map. Our analysis is based on the observation that the GW problem satisfies the Luo-Tseng error bound condition, which relates to estimating the distance of a point to the critical point set of the GW problem based on the optimality residual. This observation allows us to provide an approximation bound for the distance between the fixed-point set of BAPG and the critical point set of GW. Moreover, under mild technical assumption, we can show that BAPG converges to its fixed point set. The effectiveness of BAPG has been validated through comprehensive numerical experiments in graph alignment and partition tasks, where outperforms existing methods in terms of both solution quality and wall-clock time.
INTRODUCTION
The GW distance provides a flexible way to compare and couple probability distributions supported on different metric spaces. This has led surge in literature that applies the GW distance to various structural data analysis tasks, including 2D/3D shape matching (Peyré et al., 2016; Mémoli Sapiro, 2004; Mémoli, 2009), molecule analysis (Vayer al., 2018; 2019a), graph alignment and partition (Chowdhury & Mémoli, 2019; Xu et al., 2019h;a; Chowdhury & Needham, 2021; Gao et al., 2021), graph embedding and classification (Vincent-Cuun et al., 2021b; Xu al., 2022), generative modeling (Bunne et al., 2019; Xu et al., 2021).
Although the GW distance has gained lot of attention in the machine learning and data science communities, most existing algorithms for computing the GW distance are double-loop algorithms that require another iterative algorithm a subroutine, making them not ideal for practical use. Recently, an retropy-regularized iterative sinkhorn projection algorithm called eBPG was proposed by Solomon et al. (2016), which has been proven to converge under the Kurdykk--tojasiewiie. framework. However, eBPG has several limitations. Firstly, it addresses an entropic-reguularizee GW objective, whose regularization parameter has a major impact on the model's performance. Secondly, it requires solving entropic optimal transport problem at each iteration, which is both computationally expensive and not practical. In an effort to solve the GW problem directly, Xu et al. (2019b) proposed the Bregman projected gradient (BPG), which is still double-loop algorithm that relies on another iterative algorithm as a subroutine. Additionally, it suffers from numerical instability due to the lack of an entropic regularizer. While Vayer et al. (2019a) 9a); Mémoli (201 1) introduced the

---

Published as a conference paper at ICLR 2023
Frank- Wolfe method to solve the GW problem, they still relied on linear programming solvers and line-search schemes, making it unsuitable for even medium-sized tasks. Recently, Xu et al. (2019b) developed simple heuristic, single-lopp method called BPG-S based on BPG that showed good empirical performance on node correspondence tasks. However, its performance in the presence of noise is unknown due the lack of theoretical support.
The main challenge lies in efficiently tackling the Birkhoff polytope constraints (i.e., the polytope of doubly stochastic matrices) for the coupling matrix. The key issue is that there no closed update for its Bregman projection, which forces current algorithms to rely on computationally expensive or byperparamettr--eesstty sensitive iterative methods. To address this difficulty. we propose a single-loop algorithm (BAPG) that solves the GW distance approximately. Our solution incorporates novel relaxation technique that sacrifices some feasibility of the coupling map to achieve computational efficiency. This violation is acceptable for certain learning tasks, such as graph alignment and partition, where the quality of the coupling is not the primary concern. We find that BAPG can obtain desirable performance on some graph learning tasks as the performance measure for those tasks is the matching accuracy instead of the sharpness of the probabilistic correspondence. In conclusion, BAPG offers way sacrifice the feasibility for both computational efficiency and matching accuracy.
In our approach, we decouple the Birkhoff polytope constraint into separate simplex constraints for the rows and columns. The projected gradient descent is then performed on constructed penalty function using an alternating fashion. By utilizing the closed-form Bregman projection of the simplex constraint with relative entropy the base function, BAPG only requires satrrix-vector/matii--mme multipiications and element-wise matrix operations at each iteration, making it computationally efficient algorithm. Thus, BAPG has several convenient properties such as compatibility with GPU implementation, robustness with regards to the step size (the only hyperparameter), and low memory requirements.
Next, we investigate the approximation bound and convergence behavior of BAPG. We surprisingly discover that the GW problem satisfies the Luo-Tseng error bound condition (Luo & Tseng, 1992). This fact allows us to bound the distance between the exed-point set of BAPG and the critical point set of the GW problem, which is a notable departure from the usual approach of utilizing the Luo-Tseng error bound condition in establishing the linear convergence rate for structured convex problems (Zhou & So, 2017). With this finding, we are able to quantify the approximation bound for the fixed-point set of BAPG explicitly. Moreover, establish the subsequence convergence result when the accumulative asymmetric error of the Bregman distance is bounded.
Lastly, we present extensive experimental results to validate the effectiveness of BAPG for graph alignment and graph partition. Our results demonstrate that BAPG outperforms other heuristic single-loop and theoretically sound double-loop methods in terms of both computational efficiency and matching accuracy. We also conduct a sensitivity analysis of BAPG and demonstrate the benefits of its GPU acceleration through experiments on both synthetic and real-world datasets. All theoretical insights and results have been well-corroborated in the experiments.
2 PROPOSED ALGORITHM
In this section, we begin by presenting the GW distance as nonconvex quadratic problem with Birkhoff polytope constraints. We then delve into the theoretical insights and computational charac- teristics of our proposed algorithm, BAPG.
The Gromov-Wasserster Wasserstein distance was first introduced in (Mémoli, 2011; 2014; Peyré et al., 2019) as a way to quantify the distance between two probability measures supported on different metric spaces. More precisely:
Definition 2.1 (GW distance). Suppose that we are given two unregistered compact metric spaces dx), (), dy)) accompanied with Borel probability measures p,, v respectively. The GW distance
between μ and v is defined as
Sf [f dy. (tm. v/), rell(u.e)
inf
where v) is the set of all probability measures on X x y with p and as marginals.
2

---

Published as a conference paper at ICLR 2023
Intuitively, the GW distance aims to preserve the isometric structure between two probability measures through optimal transport. there is a map that pairs x - y and + y/ then the distance between at and z' should be similar to the distance between y and y'. Due these desirable properties, the GW distance is a powerful tool in structural data analysis, particularly in graph learning. Some examples of its applications include (Vayer al., 2019b; Xu et al., 2019b;a; Solomon et al., 2016; Peyré et al., 2016) and related references.
To start with our algorithmic developments, we consider the discrete case for simplicity and practi- cality, where μ and y are two empirical distributions, i.e., μ Ei=1 M40a, and v= 2 1j0gg As result, the GW distance can be reformulated as follows:
min mxmm
-T((DxTDyT')
(1)
S.L. TIm ,4 11, U1 20,
where Dx and Dy are two symmetric distance matrices.
2.1 RELAXATION OF GW DISTANCE
Now, we will introduce our relaxation of GW distance. The nonconvex quadratic program (1) with polytope constraints is typically addressed by (Bregman) projected gradient descent type algorithms. However, existing algorithms require an inner iterative algorithm, such as Sinkhorn (Cuturi, 2013) or the semi-smooth Newton method (Cuturi, 2013), solve the regularized optimal transport problem at each iteration. This can lead to a computationally intensive double-loop scheme, which is not ideal for GPU-friendly computation. To overcome this issue, we aim handle the row and column constraints separately using an operator splitting-basee -ased relaxation technique.
For simplicity, we consider the compact form for better exploiting the problem specific structures:
min f(T) + gi (T) + g2(m).
Here, f(T) =TT((xDDD== nonconvex quadratic function; 91 (अ) [mect)) and g2((T)
((TeC)) indicator functions closed convex polyhedral sets. Here, C₁ (x 2 0: I 11) and C2 = { 2 >-,,, v). decouple the Birkhoff polytope constraint, we adopt the operator splitting strategy to reformulate (2) as
min f(T, w) 91 (T) 92(w)
(3)
where f(x, w) -Tr(Dxe IT(DxDDy"") Then, penalize the equality constraint and process the alternating minimization scheme on the constructed penalized function, i.c..
PA( w) f(T, w) (TT 92(w) +
Here, Dn((s-) )) is the so-called Bregman divergence, i.e., Dx == -()))(())>-)--)))) -(y)) - v). where in(-) is the Legendre function, e.g., |||=|| relative entropy x log x. etc.
2.2 BREGMAN ALTERNATING PROJECTED GRADIENT (BAPG)
Next, we present the proposed single-loop Bregman alternating projected gradient (BAPG) method. The crux of BPAG is to take the alternating projected gradient descent step between C₁ and Cz. For the k-tth iteration, the BAPG update takes the form
arg min [S( wx*) ) pD (T,
xcC;
k+ arg min ( {f(x ((x""l,,)) (w) pDn n b1
weC,
The choice of relative entropy as h also brings the advantage of efficient computation of Bregman projection for simplex constraints, such as C1 and Cz, discussed in (Krichene et al., 2015). These observations result closed-form updates in each iteration of BAPG (4). We refer to this specific case as KI--BAG..
3

---

Published as a conference paper at ICLR 2023
KL-BAPG
π o exp(xxxpDxxxppppp + diag(u1/TTlm)
o exppxxxxpxxxxXpp + #diigg (esiag((.//)) (v./T" In),
where p the step size and denotes element-wise (Hadamard) matrix multiplication. KL-BAPG has several advantageous properties that make it ideal for medium to large-scale graph learning tasks. Firstly, is a single-loop algorithm that only requires matrix- wwwtor//aatiii-mmmaaiieaae matrix multiplications and element- weine matrix operations, which are highly optimized on GPUs. Secondly, unlike the entropic regularization parameter eBPG, KL-BAPG is less sensitive to the choice of the step size p. Thirdly, KL-BAPG only requires one memory operation for a matrix of size nm, which is the main bottleneck in large-scale optimal transport problems rather than Hoating-poin computations. (Mai et al., 2021).
Similar to the quadratic penalty method (Nocedal & Wright, 2006), BAPG an infeasible method that only converges to a critical point of (1) in asymptotic sense, meaning there will always be an infcasibility gap if o is chosen as a constant. Despite this, BAPG is a suitable option for learning tasks that prioritize efficiency and matching accuracy, such graph alignment and partition. This idea of sacrificing some feasibility for other benefits is further supported by recent studies such as the relaxed version of GW distance proposed in (Vincent- Cuaz et al., 202 for graph partitioning. Additionally, Séjourné et al. (2021) introduced a closely related marginal relaxation, but they did not develop an efficient algorithm with a convergence guarantee. That is, we make w and (T T) is the objective introduced in (Séjouréé et al., 2021). Our experiments in Sec 4.2 and 4.3 demonstrate that KL-BAPG outperforms existing baselines in graph alignment and partitioning tasks.
THEORETICAL RESULTS
In this section, we present the theoretical results that have been carried out in this paper. This
includes the approximation bound of the fixed-point set of BAPG and its convergence analysis. The
comerstone of our analysis is the following regularity condition for the GW problem in equation (1)
Proposition 3.1 (Luo-Tseng Error Bound Condition for (1)). There exist scalars e > 0 and such that
dist (T,, X) < | proic,nc, (T DxTDy)ll whenever | projcincs Dx s where X is the critical point set of (2) defined by (= n C2 0 ( + NN,, ( (T) NN)
(6)
and (T) denotes the normal cone to at n.
As the GW problem is nonconvex quadratic program with polytope constraint, we can invoke Theorem 2.3 in (Luo & Tseng, 1992) to conclude that the error bound condition (6) holds on the whole feasible set C1 n C2. Proposition 3.1 extends (6) to the whole space RR=. This regularity condition is trying to bound the distance of any coupling matrix to the critical point set of the GW problem by its optimality residual, which is characterized by the difference for one step projected gradient descent. turns out that this error bound condition plays an important role in quantifying the approximation bound for the fixed points set of BAPG explicitly.
3.1 APPROXIMATION BOUND FOR THE FIXED-POINT SET OF BAPG
To start, we present one key lemma that shall be used in studying the approximation bound of BAPG. Lemma 3.2. Let C1 and C2 be convex polyhedral sets. There exists constant M > 0 such that
[ < |[proic, (z) projc, Vz C1,ye Cg.
||
projc, (x) + proje, (1) projc,nc.
2
The proof idea follows essentially from the observation that the inequality can be regarded as the stability of the optimal solution for a sinear-quadrate problem, i.c.,
argmin min
arg
P.0 2 |x pl 2 ql2
(p(r),
s.t. p-q-r,pe P C₁ Oz.
4

---

Published as a conference paper at ICLR 2023
The parameter is indeed the perturbation quantity. I 0, we have p(0) (()) projo by choosing r prolc, (z)-proojj (v), it is easy to see that (p(r),g(r) = (proic, (1)), projc, (y)) Together with Theorem 4.1 in (Zhang Luo, 2022), the desired result is obtained. All the proof details are given in Appendix.
Equipped with Lemma 3.2 and Proposition 3.1, it is not hard to obtain the approximation result.
Proposition 3.3 (Approximation Bound of the Fixed-point Set of BAPG). The point (л', w²) belongs to the fixed-poine set XEAGG of BAPG if it satisfies
vf(w")) + p(Vh(=") (h(w"))+pp" VS( ((VV((")-VV(C""" + ==
where p e NN, (x') and q No, (w)). Then, the infeasibility error satisfies 1T w01 + and the gap between XEAPG and satisfies
dist
π + w
72 S p
where and are two constants.
Remark 3.4. If = w", then XBAGG ((8) is identical to X and BAPG can reach a critical point of the GW problem (1). Proposition 3.3 indicates that as p +00, the infeasibility error term | w" shrinks to zero and thus BAPG converges to a critical point of (1) in an asymptotic way. Furthermore. explicitly quantifies the approximation gap when we select the parameter p as constant. The proof can be found in Appendix. The explicit form of Tı and T2 only depend on the problem itself. including max xx mas (Dy). the constant for the Luo-Tseng error bound condition Proposition 3.1 and so
3.2 CONVERGENCE ANALYSIS OF BAPG
A natural follow-up question is whether BAPG converges. We answer affirmatively. Under several standard assumptions, we demonstrate that any limit point of BAPG is element of XBAPG. With this goal in mind, we first establish the sufficient decrease property of the potential function Fp(.).
Proposition 3.5. Let {(T wh ) be the sequence generated by BAPG. Suppose that Ee=D (Dt(a wh) DD, (n ; m xtt))) is bounded. Then, we have
F ( ktl) - Fo(T", w² ~T= (T pW wtt)
(9)
As F.).) is coercive, we have Ex Da (x*,, + + w +o0. Both (Dx("*, n k++ ( h)20 and (Dx (w", wkk+)) k20 k20 converge to zero. Thus, the following convergence result holds.
Theorem 3.6 (Subsequence Convergence of BAPG). Any limit point of the sequence {(**, w w }
generated by BAPG belongs to XEAPG-
Remark 3.7. Verifying the boundedness of the accumulative asymmetric error is challenging task, address this we perform empirical verification on a 2D except in the case where h is quadratic. toy example, as described in Sec 4.1. The results of this verification for various step sizes, can be seen in Fig. in Appendix C.I. Additionally, when is quadratic, we can employ the Hurdyka-Lojasieww analysis framework, which was developed in (Attouch et al., 2010; 2013) to prove global convergence.
To the best of our knowledge, the convergence analysis of alternating projected gradient descent methods has only been given under the convex setting, (Wang & Bertsekas, 2016; Nedić, 2011 1) for details. In this paper, by heavily exploiting the error bound condition of the GW problem, we take the first step and provide new path conduct the analysis of alternating projected descent method for nonconvex problems, which could be of independent interest.
4 EXPERIMENT RESULTS
In this section, we provide extensive experiment results validate the effectiveness of the proposed KL-BAPG on various representative graph learning tasks, including graph alignment (Tang et al., 2023) and graph partition (Li al., 2021). All simulations implemented using Python 3.9
5

---

Published as a conference paper at ICLR 2023
Shape Geometry
(b) eBPG map
BPG map
Source Target
0.5
100
100
12
-0.5
300
300
-1
400
400
-0.5
0.5
100
200
300
100
200
300
(d) BPGGS map
(c) map
(1) KLL-BAPG map
10
200
200
200
300
300
300
400
100
200
300
100
200
300
100
200
300
Figure 1: (a): 2D shape geometry of the source and target; (b)-(f): visualization of coupling matrix.
high-perfie pegerrerform computing server running Ubuntu 20.04 with Intel(R) Xcon(R) Gold 6226R CPU and an NVIDIA GeForce RTX 3090 GPU. For all methods conducted the experiment part, the relative error | x |2/
|| 12 1e-6 and the maximum iteration the stopping criterion, i.e., min(k Z [ T 1 > 1e- and k 2000]. Our code is available at Wrassersteinnfor-Grae
4.1 ToY 2D MATCHING PROBLEM
In this subsection, we study toy matching problem in 2D confirm our theoretical insights and results in See 2 and 3. Fig. (a) illustrates an example of mapping a two-dimensional shape without any symmetries
rotated version of the same shape. Here, we sample 300 points from the source shape and 400 points from the target shape, and use the Euclidean distance to construct the distance matrices Dx and Dy
1 (b)-(f) provide all color maps of coupling matrices to visualize the matching results. Here, sparser coupling matrices indicate sharper mapping. All experiment results are consistent with those in Table 4. We observe that both BPG and FW give satisfactory solution performance as they aim at solving the GW problem exactly. However, FW and BPG will suffer from a significant computation burden which will be further justified in Sec 4.2 and 4.3. On the other hand, the performance of BPG-S and eBPG is obviously harmed by the inexacness issue. The sharpness of KL-BAPG's coupling matrix relatively unaffected by its infeasibility issue much, although its coupling matrix is denser than BPG and FW ones. As we shall see later, the effect of the infeasibility issue is minor when the penalty parameter p is not small and will even result in any real cost for graph alignment and partition tasks, which only care about the matching accuracy instead of the sharpness of the coupling.
4.2 GRAPH ALIGNMENT
Graph alignment aims to identify the node correspondence between two graphs possibly with different topology structures (Zhang et al., 2021; Chen et al., 2020). Instead of solving the restricted quadratic assignment problem (Lawler, 1963; Lacoste-Julics et al., 2006), the GW distance provides optimal probabilistic correspondence relationship via preservation of the isometric property. Here, we compare the proposed KL-BAPG with all existing baselines: FW (Vayer et al., 2019a), BPG (Xu et al., 2019b), BPG-S (Xu et al., 2019b) (i.e., the only difference between BPG and BPG-S is that the number of inner iterations for BPG-S is just one), ScalaGW (Xu al., 2019a), SpecGW (Chowdhury Needham, 2021), and eBPG (Solomon et al., 2016). Except for BPG and eBPG, others are pure heuristic methods without any theoretical guarantee. Besides the GW-based methods, also

---

Published as a conference paper at ICLR 2023
Table I: Comparison of the matching accuracy (%) and wall-clock time (seconds) on graph alignment. For KL-BAPG, we also report the time of GPU implementation.
Synthetic
Proteins Noisy
Enzymes Noisy
Reddit Noisy
Method
Ace
Time
Raw
Time
Raw
Time
Raw
Time
IPFP RRWM
43.84
29.89
87.0
40.37
27.39
23.7
71.79
33.92
239.3
60.56
30.51
114.1
SpecMethod
72.40
22.92
40.5
71.43
21.39
9.6
FW
24.50
8182
29.96
20.24
54.2
32.17
22.80
10.8
21.51
17.17
1121
ScalaGW
17.93
12002
16.37
16.05
372.2
12.72
11.46
213.0
0.54
0.70
1109
SpecGW
13.27
1462
78.11
19.31
30.7
79.07
21.14
6.7
50.71
19.66
1074
cBPG
34.33
9502
67.48
45.85
208.2
78.25
60.46
499.7
3.76
3,34
1234
BPG
57.56
22600
71.99
52.46
130.4
79.19
62.32
73.1
39.04
36.68
1907
BPG-S
61.48
18587
71.74
52.74
40.4
79.25
62.21
13.4
39.04
36.68
1431
KI-BAPG
99.79
9024
78.18
57.16
59.1 1
79.66
62.85
6.9
50.93
49.45
780
KL-BAPG-GPU
1253
75.4
21.8
115
consider three widely used non-GW graph alignment baselines, including IPFP (Leordeanu et al., 2009), RRWM (Cho et al., 2010), and SpecMethod (Leordeanu & Hebert, 2005).
Parameters Setup We utilize the unweighted symmetric adjacency matrices matrices, i.e., Dx and Dy. Alternatively, SpecGW uses the heat kernel cxp(-L) where L is the normalized graph Laplacian matrix. We set both μ and to be the uniform distribution. For three heuristic methods - BPG-S, ScalaGW, and SpecGW, we follow the same setup reported in their papers. As mentioned, eBPG very sensitive to the entropic regularization parameter. To get comparable results, we report the best result among the set {0.1, 0.01, 0.001} of the regularization parameter. For BPG and KL-BAPG, we use the constant step size 5 and p 0.1 respectively. For FW, we use the default implementation in the PythonOT package (see Appendix 4). All the experiment results reported here were the average of independent trials over different random seeds and the standard deviation is collected in Appendix 4.
input distance
Database Statisties We test all methods both synthetic and real-world databases. Our setup for the synthetic database is the same as in (Xu et al., 2019b). The source graph G. (V., E. is generated by two ideal random models, Gaussian random partition and Aarabasi-Albert models, with different scales, i.e., [V_| (500, 1000, 1500, 2000, 2500). Then, we generate the target graph g. = (V., & by first adding 4% noisy nodes to the source graph, and then generating 9% noisy edges between the nodes in Vr, i.e., |
(1+ (1)EEE..,. where g e (0, 10, 20, 30, 40, 50). For each setup, we generate five synthetic graph pairs over different random seeds. To sum up, the synthetic database contains 300 different graph pairs. We also validate our proposed methods on three other real-world databases from (Chowdhury & Needham, 2021), including two biological graph databases Proteins and Engymes, and social network database Reddit. Furthermore, to demonstrate the robustness of our method regarding the noise level, we follow the noise- generating process (i.e., q = 10%) conducted for the synthesis case create new databases on top of the three real-world databases. Toward that end, the statistics of all databases used for the graph alignment task have been summarized in Appendix 4. We match each node in G. with the most likely node in G. according to the optimized T." Given the predicted correspondence set Spred and the ground-truth correspondence set Sgt, we calculate the matching accuracy by Ace Sgg n Spewl//Sg 100%.
Results of Our Methods Table 1 shows the comparison of matching accuracy and wall-clock time on four databases. We observe that KL-BAPG works exceptionally well both in terms of computational time and accuracy, especially for two large-scale noisy graph databases Synthetic and Reddit. Notably, KL-BAPG is robust enough so that it is not necessary to perform parameter tuning. As we mentioned in See 2, the effectiveness of GPU acceleration for KL-BAPG is also well corroborated on Synthetic and Reddit. GPU cannot further speed up the training time of Proteins and Reddit as graphs in these two databases are scall-scale. Additional experiment results to demonstrate the robustness of KL-BAPG and its GPU acceleration will be given in Sec 4.4.
Comparison with Other Methods Traditional non-GW graph alignment methods (IPFP, RRWM, and SpecMethod) have the oft-oo--mmory issue on graphs with more than 500 nodes (e.g.. Synthetic and Reddit) and are sensitive noise. The performance of eBPG and ScalaGW is influenced by the
7

---

Published as a conference paper at ICLR 2023
Table 2: Comparison of AMI scores on graph partition datasets using the adjaceney matrices and the heat kernel matrices.
Wikipedia Noisy
EU-email
Amazon
Village
Category
Method
Raw
Raw
Noisy
Raw
Noisy
Raw
Noisy
FastGreedy
0.382
0.341
0.312
0.251
0.637
0.573
0.881
0.778
Non-GW
Louvain
0.377
0.329
0.447
0.382
0.622
0.584
0.881
0.827
Infomap
0.332
0.329
0.374
0.379
0.940
0.463
0.881
0.190
FW
0.341
0.323
0.440
0.409
0.374
0.338
0.684
0.539
eBPG
0.461
0.413
0,517
0.422
0.429
0.387
0.703
0.658
Adjacency
BPG
0.367
0.333
0.478
0.414
0.412
0.368
0.642
0.575
BPG-S
0.357
0.285
0.451
0.404
0.443
0.352
0.606
0.560
KL-BAPG
0.469
0.396
0.508
0.428
0.457
0.362
0.736
0.681
SpecGiW
0.442
0.395
0.487
0.425
0.565
0.487
0.758
0.707
eBPG
0.100
0.082
0.011
0.188
0.604
0.031
0.002
0.003
Heat Kernel
BPG
0.418
0.373
0.473
0.253
0.492
0.436
0.705
0.619
BPG-S
0.411
0.373
0.475
0.253
0.483
0.425
0.642
0.619
KL-BAPG
0.533
0.365
0.533
0.436
0.630
0.502
0.797
0.711
entropic regularization parameter and approximation error respectively, which accounts for their poor performance. Moreover, it is easy to observe that SpecGW works pretty well on the small dataset but the performance degrades dramatically on the large one, e.g., synthetic. The reason is that SpecGW relies linear programming solver its subroutine, which is not well-suited for large-scale settings. Besides, although ScalaGW has the lowest per-iteration computational complexity, the recursive K -prrtiiion mechanism developed in (Xu et al., 2019a) is not friendly parallel computing. Therefore, ScalaGW does not demonstrate attractive performance on multi-core processors.
4.3 GRAPH PARTITION
The GW distance can also be potentially applied to the graph partition task. That is, we are trying to match the source graph with a disconnected target graph having K isolated and self-connected super nodes, where K' is the number of clusters (Abrishami et al., 2020; Li et al., 2020). Similarly, we compare the proposed KL-BAPG with the other baselines described in Sec 4.2 on four real-world graph partitioning datasets. Following (Chowdhury & Needham, 2021), we also add three non- GW methods specialized in graph aligmment, including FastGreedy (Clauset et al., 2004), Louvain (Blondel et al., 2008), and Infomap (Rosvall & Bergstrom, 2008).
Parameters Setup For the input distance matrices Dx and Dy, we test our methods on both the adjacency matrices and the heat kernel matrices proposed in (Chowdhury & Needham, 2021). For KL-BAPG, we pick the lowest converged function value among p e {0.1, 0.05, 0.01) for adjacency matrices and p {0.001, 0.0005, 0.0001} for heat kernel matrices. The quality of graph partition results is quantified by computing the adjusted mutual information (AMI) score (Vinh et al., 2010) against the ground-truth partition.
Results of All Methods Table 2 shows the comparison of AMI scores among all methods for graph partition. KL-BAPG outperforms other GW-based methods in most cases and is more robust under noisy conditions. Specifically, KL-BAPG consistently better than both FW and SpecGW, which rely on the Frank-Wolfe method to solve the problem. eBPG has comparable results when using the adjacency matrices. but is sensitive to process the spectral matrices. The possible reason is that the adjacency matrix and the heat kernel matrix have quite different structures, e.g., the former is sparse while the latter is dense. BPG and BPG-S enjoy similar performances in most cases, but they are not as good as our proposed KL-BAPG on all datasets. KL-BAPG also shows competitive performance compared to specialized non-GW graph partition methods. For example, KL-BAPG outperforms Infomap and Louvain in 6 and 4 datasets out of 8, respectively
4.4 THE EFFECTIVENESS AND ROBUSTNESS OF KL-BAPG
At first, we target at demonstrating the robustness of KL-BAPG on graph alignment, as it is more reasonable to test the robustness of a method on a database (c.g., graph alignment) rather than a single point (e.g., graph partition).
8

---

Published as a conference paper at ICLR 2023
Table 3: GPU CPU wall-clock time comparison of KL-BAPG, BPG, and eBPG on graph alignment.
Reddit Datasct BPG
Synthetic Dataset
KL-BAPG
eBPG
KL-BAPG
BPG
eBPG
CPU Time(s)
780
1907
1234
9024
22600
9502
GPU Time(s)
115
1013
2274
1253
4458
2709
Accelcration Ratio
6.78
1.88
0.54
7.20
5.07
3.51
SpecGW
BPG-S
BPG
Efficiency (2000s-700g)
ScalaGW
eBPG
KL-BAPG
KL-BAPG
100
100
4BPG
Accuracy (%)
80
BPG
Accuracy
60
40
40
20
20
Feasibility 1e-6-1e-12)
Accuracy (0%- 50%)
01
1000 1500 2000 2500 Nodes Num
Noise Level (%)
(b)
Figure 2: (a) Sensitivity of the noise level and graph scale on the synthetic graph alignment database. (b) Visualization of trade-off among efficiency, accuracy and feasibility on the Reddit database. The infeasibility error is computed by 1 wil || slll- "Closer to the boundary of the outer cycle generally indicates higher accuracy, faster speed, and lower infeasibility error.
Noise Level and Graph Scale At the beginning, we present the sensitivity analysis of KL-BAPG with respect the noise level 9% and the graph scale [V. in Fig. 2 using the Synthetic Database. Surprisingly, the solution performance of KL-BAPG is robust to both the noise level and graph scale. contrast, the accuracy of other methods degrades dramatically as the noise level or the graph scale increases.
Trade-off among Efficiency, Accuracy and Feasibility We present unified perspective on the trade-off between efficiency, accuracy, and feasibility for all GW-based algorithms on the Reddit database in Fig. (b). As shown, our proposed KL-BAPG is able to achieve a desirable balance between these three factors. Table provides detailed comparison of the four databases, while Table 8 demonstrates the robustness of KL-BAPG with respect to the step size p. This experiment supports the validity of Proposition 3.3 and provides practical guidance on choosing the optimal step size. Note that larger p leads lower infeasibility error but slower convergence rate.
GPU Acceleration of KL-BAPG. We conduct experiment results to further justify that KL-BAPG GPU-friendly. In Table 3, We compare the acceleration ratio (i.e., CPU wall-clock time divided by GPU wall-clock time) of KL-BAPG, eBPG, and BPG on two large-scale graph alignment datasets using the same computing server. For eBPG, package, which supports running on GPU. For BPG, we implement the GPU version by ourselves using Pytorch. We can find that KL-BAPG has much higher acceleration ratio on the GPÜ compared to BPG and eBPG.
use the official implementation in the PythonOT
CLOSING REMARK
In this study, we have explored the development of a single-loop algorithm for the relaxation of GW distance computation. By utilizing an eтror bound condition that was not previously investigated in the GW literature, we have successfully conducted the convergence analysis of BAPG. However, the proposed algorithm still faces the challenge of cubic per-iteration computational complexity, which limits its applicability to large-scale real-world problems. potential future direction is to incorporate sparse and low-rank structures in the matching matrix to reduce the per-iteration cost and improve the performance of the algorithm. Additionally, our method can also be applied to -ymmmmmmtii distance matrices, the Luo-tseng error bound condition remains valid. On another note, our work also provides a new perspective for the study of the alternating projected descent method for general non-convex problems, which is an open area of research in the optimization community.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
Material this paper is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-20-1-0397 Additional support is gratefully acknowledged from NSF grants 1915967 and 21 18199. Jianheng Tang and Jia are supported by NSFC Grant 62206067 and Guangzhou-Hae HOaDa--KUUSSGGAA Joint Funding Scheme. Anthony Man-Cho So is supported by in part by the Hong Kong RGC GRF project CUHK 14203920.
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 Computing, 4255):3330-A3366 2020.
Hédy Attouch, Jérôme Bolte, Patrick Redont, and Antoine Soubeyran. Proximal alternating mini- mization and projection methods for nonconvex problems: An approach based on the kurdyka- tojasiewicz inequality. Mathematics of operations research, 35(2):438 457,84457510 2010.
Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi- algebraic and tame problems: proximal algorithms,, forward-backwart splitting, and regularized geuse- methods. Mathematical Programming. 137(1):91-129, 2013.
Heinz H. Bauschke. Projection Algorithms and Monotone Operators. PhD thesis, Simon Fraser University, 1996.
Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008
(10):P10008, 2008
Charlotte Bunne, David Alvarez-Melis, Andreas Krause, and Stefanie Jegelka. Learning generative models across incomparable spaces. In International Conference on Machine Learning. pp. 851-861. PMLR, 2019.
Kai Cao, Xiangqi Bai, Yiguang Hong, and Lin Wan. Unsupervised topological alignment for single-cell multi-omics integration. Bioinformatics, (atpappplemeen__)ii---iiiei 2020.
Kai Cao, Yiguang Hong, and Lin Wan. Manifold alignment for heterogeneous single-cell multi-omics data integration using pamona. Bioinformatiis, 38(1):211 2022.
Xiyuan Chen, Mark Heimann, Fatemeh Vahedian, and Danai Koutra. Consistent network alignment via ppoximity-preserrvnn node embedding. arXiv preprint arXiv:2005.0 04725, 2020.
Minsu Cho, Jungmin Lee, and Kyoung Mu Lee. Reweighted random walks for graph matching. In European conference on Computer vision, pp. 492-505. Springer, 2010.
Samir Chowdhury and Facundo Mémoli. The grosov-wasserstinn distance between networks and stable network invariants. Information and Inference: Journal of the IMA. 8(4):757-787, 2019.
Samir Chowdhury and Tom Needham. Generalized spectral clustering via gromov-wasserstei learning. In International Conference on Artificial Intelligence and Statistics, pp. 712-720. PMLR, 2021.
Aaron Clauset, Mark EJ Newman, and Cristopher Moore. Finding community structure in very large networks. Physical review E, 70(6):0661 1, 2004.
Marco Cuturi. Sinkhor distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2300, 2013.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia 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 J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021. URL http: / //mml r. www.or//paae... wttggpapers//eee /22pe 2.0 451 html.
10

---

Published as a conference paper at ICLR 2023
Ji Gao, Xiao Huang, and Jundong Li. Unsupervised graph alignment with wasserstein distance discriminator. In Proceedings of the 27th ACM SICKDD Conference on Knowledge Discovery & Data Mining, pp. 426-435, 2021.
Walid Krichene, Syrine Krichene, and Alexandre Bayen. Efficient bregman projections onto the simplex. In 2015 54th IEEE Conference Decision and Control (CDC), pp. 3291-3298. IEEE, 2015.
Simon Lacoste-Julient Ben Taskar, Dan Klein, and Michael Jordan. Word alignment via quadratic assignment. 2006.
Eugene L Lawler. The quadratic assignment problem. Management science, 9(4):586-599 1963.
Marius Leordeanu and Martial Hebert. A spectral technique for correspondence problems using pairwise constraints. In International Conference on Computer Vision, pp. 1482-1489. IEEE, 2005.
Marius Leordeanu, Martial Hebert, and Rahul Sukthankar. An integer projected fixed point method for graph matching and map inference. Advances in neural information processing systems, 22, 2009.
Jia Li, Jianwei Yu, Jiajin Li, Honglei Zhang, Kangfei Zhao, Yu Rong, Hong Cheng, and Junzhou Huang. Dirichlet graph variational autoencoder. Advances in Neural Information Processing Systems, 33:5274-5283, 2020.
Jia Li, Mengzhou Liu, Honglei Zhang, Pengyun Wang, Yong Wen, Lujia Pan, and Hong Cheng. Mask-gvae: Blind denoising graphs via partition. In Proceedings of the Web Conference 2021, pp. 3688 3698,,69,.40 2021.
Zhi- Quii Luo and Paul Tseng. Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem. SIAM Journal on Optimization, 2(1):43-544 1992.
Vien V Mai, Jacob Lindbäck, and Mikael Johansson. A fast and accurate splitting method for optimal transport: Analysis and implementation. arXiv preprint arXiv:2110. 1738, 2021.
Facundo Mémoli. Spectral gromov-waseerstin distances for shape matching. In 2009 IEEE 12th International Conference Computer Vision Workshops, ICCV Workshops, pp. 256-263. IEEE, 2009.
Facundo Mémoli.
distances and the metric approach to object matching. Foundations of computational mathematics, 1 114):417-487, 2011.
Facundo Mémoli. The gromov-wasserstein distance: A brief overview. Axioms, 3(3):335-341 2014.
Facundo Mémoli and Guillermo Sapiro. Comparing point clouds. In Proceedings of the 2004 Eurographics/ACM SIGGRAPHI symposium Geometry processing, pp. 32-40, 2004.
Angelia Nedié. Random algorithms for convex minimization problems. Mathematical programming. 129(2):225-255 201
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-wasserstein averaging of kernel and distance matrices. International Conference on Machine Learning, pp. 2664-2672. PMLR, 2016.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning, 11(5-6):355-677, 2019.
Martin Rosvall and Carl T Bergstrom. Maps of random walks on complex networks reveal community structure. Proceedings of the national academy of sciences, 105(4):1188-1123 2008
11

---

Published as a conference paper at ICLR 2023
Thibault Séjoumé, François- François-Xavier Xavier Vialard, and Gabriel Peyré. The unbalanced gromov wasserstein distance: Conic formulation and relaxation, Advances in Neural Information Processing Systems, 34:8766-8779, 2021.
Justin Solomon, Gabriel Peyré, Vladimir G Kim, and Suvrit Sra. Entropic metric alignment for
correspondence problems. problems.. ACM Transactions on Graphics (TOG), 35(4):1-133 2016.
Jianheng Tang, Weiqi Zhang, Jiajin Li, Kangfei Zhao, Fugee Tsung, and Jia Li. Robust attributed graph alignment via joint structure learning and optimal transport. ICDE, 2023.
Sarah Teichmann and Mirjana Efremova. Method of the year 2019: single-cell multimodal omics.
Nature Methods, 17(1)20020, 2020.
Titouan Vayer, Laetita Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Fused gromov- wasserstein distance for structured objects: theoretical foundations and mathematical properties. arXiv preprint arviv: /8/ I. L02834, 2018.
Titouan Vayer, Nicolas Courty, Romain Tavenard, and Rémi Flamary. Optimal transport for structured data with application on graphs In International Conference on Machine Learning, pp. 6275-6284. PMLR, 2019a.
Titouan Vayer, Rémi Flamary, Romain Tavenard, Laetitia Chapel, and Nicolas Courty. Sliced gromov- wasserstein. In NeurlPS thir Conference on Neural Information Processing Systems, volume 32, 2019b.
Cédric Vincent-Cuaz, Rémi Flamary, Marco Corell,, Titouan Vayer, and Nicolas Courty. Semi-relaxed gromov wasserstein divergence with applications on graphs. arXiv preprint arXiv:2110.02753, 2021a.
Cédric Vincent-Cuaz, Titouan Vayer, Rémi Flamary, Marco Corneli, and Nicolas Courty, Online graph dictionary learning. arXiv preprint arXiv:2102.06555 2021b.
Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. The Journal of Machine Learning Research, 11:2837-2854- 2010.
Mengdi Wang and Dimitri P Bertsekas. Stochastic first-order methods with random constraint projection. SIAM Journal on Optimization, 26(1):681-717, 2016.
Hongzhi Wen, Jiayuan Ding, Wei Jin, Yiqi Wang, Yuying Xie, and Jiliang Tang. Graph neural networks for multimodal single-cell data integration. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4153-4163, 2022.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov iasserseann learning for graph partitioning and matching. Advances neural information processing systems, 32:3052-3062, 2019a.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. Gromov-wassersten learning for graph matching and node embedding. In International conference machine learning, pp. 6932-6941. PMLR, 2019b.
Hongteng Xu, Dixin Luo, Lawrence Carin, and Hongyuan Zha. Learning graphons via structured gromov-wasserstiin barycenters. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10505-10513 2021.
Hongteng Xu, Jiachang Liu, Dixin Luo, and Lawrence Carin. Representing graphs via gromov- wasserstein factorization. IEEE Transactions Pattern Analysis and Machine Intelligence, 2022.
Jiawei Zhang and Zhi-Quan Luo. A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization. SIAM Journal on Optimization, 32(3):2319-255 9344,, 2022.
12

---

Published as a conference paper at ICLR 2023
Si Zhang, Hanghang Tong, Long Jin, Yinglong Xia, and Yunsong Guo. Balancing consistency and disparity in network alignment. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp.
2021.
Zirui Zhou and Anthony Man-Cho So. A unified approach error bounds for structured convex optimization problems, Mathematical Programming, 165(():689-728, 2017.
13


Reviews:
[{"review_id": "qTOj5JIybWs", "reviewer": "Reviewer_sorA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes an (approximation) algorithm to compute Gromov-Wasserstein (GW) distance, and called it Bregman Alternating Projected Gradient (BAPG) method. The author(s) claim that this is the first single-loop algorithm that has provable convergence guarantees. In particular, they provide an approximation bound for the distance between the fixed-point set of BAPG method and the critical point set of GW. Their analysis is based on the observation that the GW problem satisfies a so-called Luo-Tseng error bound condition, and the authors claim that they are the first to incorporate this idea in the GW literature. The paper complements their theoretical analysis with a few experiments comparing the performance of BAPG and other algorithms on graph alignment and partition tasks. They claim that BAPG achieves state-of-the-art results in terms of both wall-clock time and quality of solutions.\n\n", "summary_of_the_review": "The algorithm proposed connects existing optimization ideas in a novel way, and the analysis seems technically sound. It is also expected to run faster than competing GW algorithms in practice. The author(s) claim that this the first single-loop GW algorithm that has provable convergence guarantees, though being single-loop was not a standard performance measure in the literature nor well explained in the paper. Finally, it wasn’t clear that the experiments chosen are suitable for the purpose of comparing the relative strength of GW algorithms.\n\nScore increased after review.", "strength_and_weaknesses": "Strengths:\n-Technical details are easy to follow and verify\n-BAPG involves only the matrix-vector or matrix-matrix operations at each iteration. Consequently, it has good properties such as being GPU implementation-friendly, robustness with respect to the step size, and low memory cost.\n-The paper seems to be the first to incorporate the idea of Luo-Tseng error bound condition in the GW literature.\n-While the idea of the algorithm is based on applying various known existing tricks and methods, the innovation lies in connecting them in novel ways. In particular, the authors decouple the Birkhoff polytope as simplex constraints for rows and columns separately, which is the key to enabling the projected gradient descent in an alternating fashion.\n\nWeaknesses:\n-One of the main claims of the paper is that their algorithm is provably single-loop, as compared to all-but-one algorithms in Table 1 which are classified as double-loop. However, we believe this single-loop vs double-loop terminology is neither standard in the literature nor explicitly defined in the paper. In particular, it wasn’t immediately clear why\n --being single-loop is an important performance measure (either in theory or in practice) that makes it preferable to double-loop; \n --each algorithm in Table 1 is classified as double-loop or single-loop\n\n-Author(s) claim that the infeasibility of the solution provided by their algorithm (BAPG) “does not matter at all” for graph alignment/partitioning, but provide little theoretical justification besides the indifference of these problems to the sharpness of the coupling. Moreover, there does not seem to be sufficient empirical evidence to support their claim. If the infeasibility does not matter at all, does that mean the graph tasks can be potentially solved using an easier formulation (i.e., one that does not require solving an GW problem)? This seems to suggest that the experiments chosen are unsuitable for the purpose of comparing the relative strength of GW algorithms. Also, the authors compared their graph alignment/partitioning performance with other GW-based algorithms. It will be much more meaningful to include comparisons with other non GW-based methods, especially those methods specialized in graph alignment/partitioning (e.g., Infomap for graph-partitioning), especially if the authors claim their method achieves state-of-the-art result\n- Because the author(s) assume only that Dx and Dy are symmetric distance matrices, their algorithm could potentially be extended to a wider class of data/tasks, but they make little mention of this. Maybe include this in future work.\n-Author(s) claim that their method is stable compared to existing methods, but provide no such notion of stability\n-The accuracy of their algorithm in figure 2a seems a little suspicious\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "eUNK2hsnG0P", "reviewer": "Reviewer_h6Kq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This article proposes a new algorithm (BAPG) to estimate the GW distance between two discrete measured metric spaces $(X,d_X,\\mu)$ and $(Y, d_Y, \\nu)$. That is, it consider the following optimization problem  :\n$$\\min_{\\pi} -Tr(D_X \\pi D_Y \\pi^T)$$\nwhere $D_X = (d_X(x_i,x_j))_{ij}$ (and similarly for $D_Y$) and $\\pi$ is constraint to have $\\mu,\\nu$ as marginals. \n\nThe main idea is to consider a relaxation of the bilinear problem that naturally arise from this _quadratic_ optimization problem by minimizing instead \n\n$$F_\\rho (\\pi,w) = - Tr(D_X \\pi D_Y w^T) + \\rho D_h(\\pi, w)$$\n\nwhere $\\pi$ is constrained to have $\\mu$ as first marginal, $w$ is constrained to have $\\nu$ as second marginal, $\\rho$ is a regularization parameter and $D_h$ is the Bregman divergence associated to the convex map $h$ (in practice, the entropy, so that $D_h$ is the KL divergence, or the quadratic loss so that $D_h$ is the Euclidean distance). \n\nAkin to the usual derivations of the Sinkhorn algorithm as Iterative Bregman Projections [Benamou et al., 2015], authors propose an iterative algorithm (BAPG) to obtained minimizers of the proposed functional. \n\nOf crucial importance, authors show that : \n- [Theorem 3.6] Any accumulation point of the sequence $(\\pi^k,w^k)_k$ must belong to a set of fixed-points for BAPG. \n- [Proposition 3.3] Any such fixed-point must satisfy $|\\pi^\\star - w^\\star| = O(1/\\rho)$, so that in particular in the regime $\\rho \\to \\infty$, one expect to have $\\pi^\\star = w^\\star$, and the middle-point $(\\pi^\\star + w^\\star) / 2$ is close (as a $O(1/\\rho)$) to an optimal solution of the original GW problem. \n\nEventually, authors showcase their approach on a variety of numerical experiments, achieving good performances in terms of computational efficiency (running times) and utility (matching accuracy). ", "summary_of_the_review": "I think this is a good paper that introduce an interesting approach to address a difficult and important problem. It is supported by both theoretical and numerical claims. ", "strength_and_weaknesses": "## Strength\n\n- Introduces an interesting algorithm to tackle an important problem in Computational OT and related fields. \n- Address both theoretical and numerical aspects of the problem. \n- Well-written paper. \n\n## Weaknesses \n\n- There are still few theoretical points that remain to be investigated/detailed. For instance: \n   - does Eq. (9) enables to get a convergence rate toward the fixed-point $(\\pi^\\star, w^\\star)$? (if so, and provided a rounding scheme is valid there (see below), I think this would yield an overall approximation-rate for GW which may be of interest and could be compared with other benchmarks).\n    - Why is it clear that a limit point $(\\pi^\\infty, w^\\infty)$ exists? I guess this follow from some compactness arguments (i.e. the sequence shall be bounded thanks to $f$ being coercive), but this is not striking in the proof as far as I can tell.  \n- [More a suggestion than a weakness] Experimental evaluation could be slightly extended as they suggest some interesting behavior. In particular, in the light of Fig 2. (b), it seems there is a (natural) tradeoff between convergence speed and the infeasibility error wrt the parameter $\\rho$, so a possibly useful idea would be to start with a fairly high $\\rho$ and progressively reduce it (as a sort of warm start). \n- I think some references are missing, in particular the work of _The unbalanced Gromov Wasserstein distance: Conic formulation and relaxation_ by Séjourné et al., 2021, which introduces a similar relaxation of the GW problem, and proves under specific condition that minimizers of $(\\pi, w) \\mapsto F(\\pi,w)$ are the same as those of $\\pi \\mapsto F(\\pi,\\pi)$. \n\n## Other remarks/questions/suggestion\n- If my understanding is correct, the output of BAPG is (approximately) a plan of the form $(\\pi^\\star + w^\\star)/2$, which, if I am correct, does not exactly have the expected marginals $(\\mu,\\nu)$. Assuming this would be critical, could someone apply a `rounding` scheme in the vein of [Altschuler et al., 2018] ? \n- [suggestion for clarity] I think that in propositions statements, it may serve clarity to add quantifers \"$\\forall x,y$\", or \"$\\forall \\pi \\in \\mathbb{R}^{n \\times m}$, and so on, to make clear on which parameter does the constant $M,\\tau_1,\\tau_2$ depend (or not). \n- [typo] In Remark 3.7, the ref to prop 3.4 should be 3.5 I think. \n- [typo] In proof of prop 3.1, $D_x$ should be $D_X$. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RegRyI7uiic", "reviewer": "Reviewer_huho", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new method for computation of the Gromov-Wasserstein distance over graphs.  The GW distance is a measure distance between two distributions defined over different metric spaces. The authors give a list of existing algorithms for this problem which are either expensive computationally or do not have theoretical justification.  The present contribution is stated to be both, thus a breakthrough.  Computational results are provided for a set of different graph problems (alignment, partitioning, etc) which show the proposed scheme is indeed more efficient than existing methods.  The key idea is a surprising application of anold result (error bound condition of Luo & Tseng, 1992).", "summary_of_the_review": "This is a very technical paper dealing with computation of the GW distance for graph data.  There is a strong theory component to the approach proposed and considerable computational work.  I did not see how the main theorem applied to the algorithm to be single loop but this could be due to my lack of expertise in this area.", "strength_and_weaknesses": "\nStrength\n\no The paper is narrowly focused and laser sharp on what it aims to show\n\no GW distance on graphs is indeed a useful tool for analysis of large data\n\no There is a reasonable description of a highly specialized field for a non-expert to follow the main logic of the submission\n\nWeakness\n\no The paper is highly specialized\n\no I'm not aware that anyone had previously complained that GW distance computation is a bottleneck is some key data science field", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "2LbbrWSP8e", "reviewer": "Reviewer_Jipi", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "In this work, the authors propose an efficient single-loop iterative procedure to compute the Gromov Wasserstein (GW) distance between two sets. The GW distance can be formulated as a quadratic programming with a doubly-stochastic constraint. Many of the existing approaches for solving this optimization are double loop in nature, which involve solving another expensive sub-problem iteratively within a single iteration. In the proposed algorithm BAPG, a Bregman alternating projection step is performed with respect to the row and column stochastic constraints in each iteration. By alternatively projecting to polytopes with only row or column constraints, the projection attains a closed form update, thus attaining computational efficiency compared with other algorithms. For a theoretical understanding of the proposed algorithm BAPG, it has been shown that (1) BAPG converges to a fixed point asymptotically and (2) the distance between a fixed point of BAPG and the set of critical points of the original GW problem can be bounded, which is inversely proportional to the penalty parameter. The authors evaluate the algorithm on both synthetic and real datasets related to graph alignment and partition, and demonstrate the solution quality as well as the time efficiency.", "summary_of_the_review": "This work improves the state-of-the-art for computing the GW distance by obtaining the first provable and efficient single loop algorithm. The analysis of the algorithm is based on the splitting strategy and the Luo-Tseng error bound. With the extensive experiments on both synthetic and real datasets, some of the theoretical claims are verified. It is seen that the proposed method attains good accuracy within less time for graph alignment and partition. ", "strength_and_weaknesses": "The main strength of this work is the splitting strategy for designing the algorithm and the analysis of the algorithm. The Luo-Tseng error bound is utilized to establish the distance between the fixed point of the algorithm and the critical set of the original GW problem. A few minor things in terms of technicality: (1) the algorithm itself is not stated with splitting, e.g., a single variable $\\pi$ for the update; but the analysis uses two variables. Can the connection be explicitly stated in the main text? (2) Since the BAPG only returns a solution that is close to the critical set of the GW. Could it happen that some critical point has much worse value than the global min of the GW problem? (3) BAPG returns an infeasible solution in many cases. What if we want to return a feasible solution? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster