Semi-relaxed Gromov-Wasserstein divergence and applications on graphs
Authors: Cédric Vincent-Cuaz
Rémi Flamary
Marco Corneli
Titouan Vayer
Nicolas Courty
Venue: ICLR 2022 Poster (2022)
Keywords: Optimal Transport
Graph Learning

Abstract: Comparing structured objects such as graphs is a fundamental operation
involved in many learning tasks. To this end, the Gromov-Wasserstein (GW)
distance, based on Optimal Transport (OT), has proven to be successful in
handling the specific nature of the associated objects. More specifically,
through the nodes connectivity relations, GW operates on graphs, seen as
probability measures over specific spaces. At the core of OT is the idea of
conservation of mass, which imposes a coupling between all the nodes from
the two considered graphs. We argue in this paper that this property can be
detrimental for tasks such as graph dictionary or partition learning, and we
relax it by proposing a new semi-relaxed Gromov-Wasserstein divergence.
Aside from immediate computational benefits, we discuss its properties, and
show that it can lead to an efficient graph dictionary learning algorithm.
We empirically demonstrate its relevance for complex tasks on graphs such as
partitioning, clustering and completion.

Published as a conference paper at ICLR 2022
SEMI-RELAXED
DIVERGENCE WITH APPLICATIONS ON GRAPHS
Cédric Vincent-Cuaz ' Rémi Flamary 2, Marroo Corneli 1,3 Titouan Vayer 4, Nicolas Courty Univ. Côte d' Azur, Inria, Maasai, CNRS, LJAD :; IP Paris, CMAP. UMR 7641 2, #SMS Univ. Lyon, Inria, CNRS, ENS de Lyon, LIP UMR 5668 4; Univ. Bretagne-Suf, CNRS, IRISA $ fcedric. vincent-cuaz; marco corneli; titouan. vayerr frr remi, fl fllmaryggolyyecccee
edu; cou.cyliis...ttttriii.......
ABSTRACT
Comparing structured objects such as graphs is fundamental operation involved in many learning tasks. To this end, the Gromov-Wassersten (GW) distance, based on Optimal Transport (OT), has proven be successful in handling the specific nature of the associated objects. More specifically, through the nodes connectivity relations, GW operates on graphs, seen as probability measures over specific spaces. At the core of OT is the idea of conservation of mass, which imposes coupling between all the nodes from the two considered graphs We argue in this paper that this property can be detrimental for tasks such as graph dictionary or partition learning, and we relax it by proposing new semi-relaxed Gromov- Wasserstein divergence. Aside from immediate computational benefits, we discuss its properties, and show that it can lead to an efficient graph dictionary learning algorithm. We empirically demonstrate its relevance for complex tasks on graphs such as partitioning, clustering and completion.
INTRODUCTION
One of the main challenges in machine learning (ML) is to design efficient algorithms that are able learn from structured data (Battaglia et al.] 2018). Learning from datasets containing such non- vectorial objects is difficult task that involves many areas of data analysis such signal processing (Shuman al. 2013), Bayesian and kernel methods on graphs (Ng et al. 2018 Kriege et al. (020) or more recently geometric deep learning (Bronstein et al., 2017 (021)) ) and graph neural networks (Wu ct al. 2020). In terms of applications, building algorithms that go beyond Euclidean data has led to many progresses, e.g. in image analysis (Harchaoui & Bach 2007). brain connectivity (Ktena et al.,
2017), social networks analysis (Yanardag & Vishwanathan 2015) or protein structure prediction (Jumper et al. 2021)
Learning from graph data is ubiquitous a number of ML tasks. A first one is to learn graph representations that can encode the graph structure (a.k.a. graph representation learning). In this domain, advances on graph neural networks led to state-of-the-arr end-to-end embeddings. although requiring a sufficiently large amount of labeled data (Ying al. 2018 Morris et al. 2019 Gao & Jil 2019; Wu et al. (020). Another task is to find meaningful notion of similarity/distaace between graphs. way to address this problem is to leverage geometric or signal properties through the use of graph kernels (Kriege et al. 2020) or other embeddings accounting for graph isomorphisms (Zambon) al. 2020). Finally, it is often of interest either to establish meaningful structural correspondences between the nodes of different graphs, also known graph matching (Zhou & De la Torre 2012
Maron & Lipman 2018 Bernard et al.) 2018 Yan et al. 2016) or to find a representative partition of
the nodes of a graph, which refer graph partitioning (Chen et al.) 2014 Nazi al. 2019
Kawamoto et al. 2018 Bianchi et al.) 2020).
Optimal Transport for structured data. Based on the theory of Optimal Transport (OT, Peyré & Cuturi 2019), novel approach to graph modeling has recently emerged from a series of works. Informally, the goal of OT is to match two probability distributions under the constraint mass conservation and in order minimize given matching cost. OT originally tackles the problem

---

Published as a conference paper at ICLR 2022
GWIC, h. C, h) 0.219
STGW h. C) 0.05
SIGWIC, h. =
Figure I: Comparison of the GW matching (left) and asymmetric srGW matchings (middle and right) between graphs C' and C with uniform distributions. Nodes of the source graph are colored based on their clusters. The OT from the source to the target nodes is represented by ares colored depending on the corresponding source node color. The nodes in the target graph are colored by averaging the (rgb) color of the source nodes, weighted by the entries of the OT plan.
of comparing probability distributions whose supports lie on the same metrie space, by means of the so-called Wasserstein distance. Extensions to graph data analysis were introduced by either embedding the graphs in space endowed with Wasserstein geometry (Nikolentzos et al. 2017
Togninalli et al. 20199] Petric Maretic et al., 2019) or relying on the Gromov- Wassov-asssesttein (GW) distance (Mémoli 2011]] Sturm 2012). The latter approach a variant of the classical OT in which one aims at comparing probability distributions whose supports lic on different metric spaces by finding matching of these distributions being as close as possible to an isometry. By expressing graphs as probability measures over spaces specific to their topology, where the structure of graph is represented through a pairwise distance/similarity matrix between its nodes, the GW distance computes both soft assignment matrix between the nodes of the two graphs and notion of distance between them (see the left part of Figure D] These properties have proven to be useful for wide range of tasks such graph matching and partitioning (Xu al. 2019a Chowdhury & Needham Vayer et al. 2019). estimation of nonparametric graph models (graphons, Diaconis & Janson
2021:
2007
Xu et al. (222)) for graph dictionary learning (Vincent- et al. 2021 Xu 2020). GW
was also extended to directed graphs in Chowdhury & Mémoli 2019) and to labeled graphs via the
Fused
(FGW) distance in Vayer et al. (2020).
Despite those recent successes, applications of GW to graph modeling still have several limitations. First, finding the GW distance remains challenging, as boils down solving difficult non- convex quadratic program (Peyré et al.) 2016 Solomon et al., 2016 Vayer et al. 2019), which, in practice, limits the size of the graphs that can be processed. A second limit naturally emerges when a probability mass function is introduced over the set of the graph nodes. The mass associated with a node refers to its relative importance and, without prior knowledge, each node is either assumed to share the same probability mass or to have one proportional to its degree. In this paper, we somehow argue that these choices can be suboptimal in several cases, and should be relaxed, with the additional benefit of lowering the computational complexity. As an illustration, consider Figure on the left image, the GW matching is given between two graphs, with respectively two and three clusters, associated with uniform weights the nodes. By relaxing the weight constraints over the second (middle image) or first graph (right image) we obtain different matchings, that can better preserve the structure of the source graph by reweighing the target nodes and thus selecting meaningful subgraph.
Contributions. We introduce a new optimal transport based divergence between graphs derived from the GW distance. We call it the semi-relaxed Gromov-Wasserste Wasserstein (srGW) divergence. After discussing properties and motivating its use in MI. applications, we propose an efficient solver for the corresponding optimization problem. Our solver better fits to modern paraliel programming than exact solvers for GW do. We empirically demonstrate the relevance of our divergence for graph partitioning, Dictionary Learning (DL), clustering of graphs and graph completion tasks. With srGW, we recover SOTA performances at a significantly lower computational cost compared to methods based on pure GW.
2 MODELING GRAPHS WITH THE GROMOV- WASSERSTSSS DIVERGENCE
In this section introduce more formally the GW distance and discuss two of its applications graphs, namely graph partitioning and unsupervised graph representation learning. In the following the probability simplex with N-bins is denoted En {h E R Σ, h4 1).
2

---

Published as a conference paper at ICLR 2022
GW graphs similarity. In the OT context, a graph & with n nodes can be modeled couple (C, h) where C' E [ is a matrix encoding the connectivity between nodes and h E Σn is a histogram, referred here distribution, modeling the relative importance of the nodes within the graph. The matrix C' can be arbitrarily chosen as the graph adjacency matrix, or any other matrix describing the relationships between nodes in the topology of the graph (e.g. adjacency, shortest-path Laplacian). The distribution is often considered as uniform (h- = =1,) but can also convey prior knowledge egg. using the normalized degree distribution (Xu et al. 2019a). Consider now two graphs (C,h) and g (C, h), respectively with n and m nodes, potentially different (n f m). The GW distance between and 9 is defined the result of the following optimization problem:
C,,,
= min TI.. T 1 P jjkt
Σ Cy- -kil TuTT with T E FER4 2aXX
(1)
The optimal coupling T acts as probabilistic matching of nodes which tends to associate pairs of nodes that have similar pairwise relations in C' and C' respectively, while preserving masses / and h through its marginals constraints. GW defines a distance on the space of metric measure spaces (mm-spaces) invariant measure preserving isometries (Mémoli, 2011 Sturm 2012). In the case of graphs, which corresponds to discrete mm-spaces, such invariant is a permutation of the nodes that preserves the structures and the weights of the graphs (Vayer al. 2020 First applications of GW to ML on graphics problems (Peyré et al. 2016; Solomon et al. 2016) motivated further connections with graph partitioning. the GW sense, this paradigm is illustrated by finding an ideally partitioned
graph 7 (D, h) of m clustrers whose structure is diagonal matrix D E |R=x representing the cluster's 's connections, and its distribution h estimates the proportion of the nodes in each cluster (Xu et al. 2019a). The OT plan between a graph G = (C, h) represented by its adjacency matrix C' this ideal graph can be used to recover G's clusters, if their number and proportions match the number and the weights of g's nodes. Xu et al. 2019a) suggested to empirically refine both graph distributions, by choosing h based on power-law transformations of the degree distribution of G and to deduce h from h by linear interpolation. Chowdhury & Needham (2021) proposed use heat kernels from the Laplacian of G instead of its adjacency binary representation, and proved that the resulting GW partitioning is closely related to the well-known spectral clustering (Fiedler, 1973).
The GW distance has been extended to graphs with node attributes (typically IRd vectors) thanks to the Fused Gromov-Wasserstein Wasserstein distance (FGW) (Vayer et al. 2019). In this context, an attributed graph G with nodes is a tuple G = (C, F, h) where F E x is its matrix of node features. FGW between two attributed graphs aims at finding an OT by minimizing a weighted sum of a GW cost on structures and Wasserstein cost on features (balanced by parameter E [0, 1].. Most of the applications of GW can be naturally extended with FGW to attributed graphs
GW for Unsupervised Graph Representation Learning. More recently, GW has been used as data fitting term for unsupervised graph representation learning by means of Dictionary Learning (DL) (Mairal et al., 20099, Schmitz et 2018). While DL methods mainly focus on vectorial data (Ng et al. [002] Candès et al. 2011] Bobadilla et al.) 2013), DL applied to graphs datasets consists in factorizing them as composition of graph primitives (or atoms) encoded as {CC,, hE The non-linear DL based on entropic GW barycenters. On the other hand, Vinneet-Cuual et al. (2021) proposed a linear DL method by modeling graphs as a linear combination of graph atoms thus reducing the computational cost. In both cases, the embedding problem that consists in the projection of any graph on the learned graph subspace requires solving a computationally intensive optimization problem.
first approach proposed by (Xul (2200) consists
SEMI-RELAXED SAANOV--ASEESTEEN DIVERGENCE
3.1
DEFINITION AND PROPERTIES
observed graphs G = (C, h) and 7 (C,h) of n and m nodes, we propose to find correspondence between them while relaxing the weights h on the second graph. To this end we introduce the semi-relaxed Gromov- Wasserstein divergence as
Given two
srGW C, C) min CW,,C, TE
3

---

Published as a conference paper at ICLR 2022
This means that we search for reweighing of the nodes of g leading to graph with structure C with minimal GW distance from G. While the optimization problem ( above might seem complex to solve, it is actually equivalent to GW problem where the mass constraints on the second marginal of T are relaxed, reducing the problem to:
srG h C) min Σ CCs Cu with T R tjke
From an optimal coupling T of problem (3), the optimal weights h' expressed in problem can be recovered by computing ' second marginal, i.e h T 1n This reformulation with relaxed marginal has been investigated in the context of the Wasserstein distance (Rabin et al. 2014 Flamary et al. 2016) and for relaxations of the GW problem in (Schmitzer & Schnörr (2013) but was never investigated for the GW distance itself. To the best of our knowledge, the most similar related work
the Unbalanced GW (Séjourné al. (020);; Liu et al. (2020); Chapel al. (2019) where one could recover srGW with different weighting over the marginal relaxations (oo on the first marginal and O on the second) but this specific case was not discussed nor studied in these works.
A first interesting property of srGW is that since h is optimized in the the simplex Em,, its optimal value h can be sparse. As consequence, parts of the graph ς can be omitted in the comparison, similarly to a partial matching. This behavior is illustrated in the Figure [ where two graphs with uniform distributions and structures C' and C forming respectively and 3 clusters are matched. The GW matching (left) between both graphs forces nodes of different clusters from C' to be transported on one of the three clusters of C. leading Whereas srGW can find a reasonable approximation of the structure of the left graph either though transporting only two clusters (middle) or finding structure with clusters in subgraph of the target graph with two clusters (right). A second natural observation resulting from the dependence of srGW, of only one input distributions its asymmetry, i.e. (GWW2(C. h, C) * srGW 2C, h C). Interestingly, srGW2, shares similar properties than GW described in the next proposition:
high GW cost where clusters are not preserved.
Proposition 1 Let C E Raxn and C E R be distance matrices and h E,, with supp(h)
[m]. Then srG (C, h C) iff there exists h Em with card(su))(h)) and bijection
supp(h) + [n] such that:
Vi supp(h), h(i) h(o(i))
(4)
And:
Vk, I supp(h)? Tu Cock)o()-
(5)
In other words srGW2 (C,,,, h. C) vanishes iff there exists a reweighing h. E Em of the nodes of the second graph which cancels the GW distance. When is the case, the induced graphs (C, h) and
(C, h are isomorphic (Mémoli 2011 Sturm 2012). We refer the reader interested in the proofs of the equivalence and the Proposition 1 the annex (section 7.2)
3.2 OPTIMIZATION AND ALGORIHHMM
In this section we discuss the computational aspects of the srGW divergence and propose an algorithm to solve the related optimization problem (3). We also discuss variations resulting from entropic or/and sparse regularization of the initial quadratic problem.
Solving for the semi-relaxed GW. The op- timization problem related to the calculation of srGW3 (C, h C') is non-convex quadratic
Algorithm 1 CG solver for srGW
1: repeat
2: Q + Compute gradient w.r.t T of (p.
program similar the one of GW with the im- portant difference that the linear constraints are independent.
3: ( + minx1 - (X, G(1)
X 20
4: T(++1) + (1-1*) ( (1-1") (0 with y
Consequently, we propose to solve 3 with a Conditional Gradient (CG) algorithm (Jaggi 2013) that can benefit from those independent constraints and is known to converge to local stationary point non-convex problems (Lacoste-Julien) 2016). This algorithm, provided in Alg.
[0, 1] from exact-line search.
5: until convergence.
4

---

Published as a conference paper at ICLR 2022
consists in solving each iteration (t) a linearization (X, G') of the problem where G is the gradient of the objective in (3). The solution of the linearized problem provides a descent direction X T, and linesearch whose optimal step can be found in closed form to update the current solu- tion T (Vayer et al. 2019). While both srGW and GW CG require at each iteration the computation of gradient with complexity On m²n). the main source of efficiency of our algorithm comes from the computation of the descent directions. In the GW case, one needs to solve an exact linear OT problem, while in our case, one just needs to solve several independent linear problems under simplex constraint. This simply amounts to finding the minimum on the rows of G' as discussed in (Flamary al., 2016 Equation (8)), within (mm) operations, with potential parallelization with GPUs. Performance gains are illustrated in the experimental section.
Entropic regularization. Recent OT applications have shown the interest of adding an entropic regularization to the exact problem 3 .e.g. (Cuturi 2013; Peyré et al. (016). Entropic regularization makes the optimization problem smooth and more robust while densifying the optimal transport plan. Similar to (Peyré et al. 2016 Xu et al.] 2019b] Xie et al., (220),,
mirror-descent scheme
w.r. the Kullback-Leible divergence (KL) to solve entropic regularized srGW. The problem boils down to find, at iteration t the coupling ((++1) + arg min.1,.=.:22 (T, G + (L(
where > O, Gtt)) denotes the gradient of the GW loss at iteration and KL(T)T(O) is the KL divergence. These updates can be solved using the following closed-form Bregman Projections
(((+1) arg min e (KL(T)K(4D) T1,, h,720
T(++1) diag
(1)
(6)
K0i
where K(O) exp (G - - (l))(( (exp and log are applied componentwise). Unlike existing solvers for GW based on entropic regularization (Peyré et al.) 2016, [Sooooon et al., 2016) that rely on a Sinkhorn's 's matrix scaling algorithm on k(t) at each iteration, our problem requires only one (left) scaling of (t) per iteration. We denote by srGW, SCG h, C) the result of this procedure.
Sparsity promoting regularization. As illustrated in Figure srGW naturally leads to sparse solutions in h. To compress even more the localization over few nodes of C, we can promote the sparsity of h through a penalization Q(T)) = E, |// which defines a concave function in the positive orthant R.,. We adapt the Majorisation Majorisation-MMniiissttii (MM) of Courrty et al. (2014) that was introduced to solve classical OT with similar regularizer. The resulting algorithm, which relies on local linearization of ((T()), consists in iteratively solving the srGW or srGW. problems,
(T (T )-1/2, Further detailed explanations on these algorithms can be found in section 7.3 of the annex.
regularized at iteration + 1 by a linear OT cost of components (!)) Ag
LEARNING THE TARGET STRUCTURE
dataset of K graphs D ((Cx, hxx) be)]ke[K is now considered, with heterogeneous structures and variable number of nodes, denoted by (n& (m*))e[Ky- In the following. introduce novel graph dictionary learning (DL) whose peculiarity is learn unique dictionary element. Then we discuss how this dictionary can be used to perform graph completion, i.e. reconstruct the full structure of graph from an observed
subgraph. subgraph.
4.1 NEW GRAPH DICTIONARY LEARNING
Semi-relaxed
embedding. We first discuss how an observed graph can be represented in dictionary with unique element (or atom) C E R. assumed to be known or designed through expert knowledge. First, one computes srGW? (Ck, hus C) using the algorithmic solutions and regularization strategies detailed in Section 3.1 From the resulting optimal coupling Th the optimal weights for the target graph C are recovered with h = T 1ng, The graph (C, h can be seen as projection of (Cg, hx))) in the GW sense and the distribution on the nodes h is an embedding of the graph (C₃, h2). Representing graph vector of weights h graph C is new and elegant way to define graph subspace that is orthogonal to other DL methods that either rely on GW barycenters (Xu 2020) or linear representations (Vincent-Cuaz et al. 2021). One particularly
5

---

Published as a conference paper at ICLR 2022
Algorithm/ 2 Stochastic update of the dictionary atom C
1: Sample minibatch of graphs B == {(C(()) he)
2: Get transports {Th Jes from srGW(Ck;; his C) with Alg
3: Compute the gradient c of srGW with fixed JeB and perform projected gradient step symmetric non-negative matrices S:
C t Crorsss v.a
interesting aspect of this modeling is that when hig is sparse, only the subpart (or subgraph) of C corresponding to the nodes with non-zero weights in h is used.
srGW Dictionary Learning and online algorithm. Given dataset of graphs D = {CC,, he)]k]]k; we propose to learn the graph dictionary C E gmxm from the observed data, by optimizing:
K srGW Cz, CR, hu, C)- K
min CER
This problem is denoted as srGW Dictionary Learning. It can be seen as a srGW barycenter problem (Peyré et al., 2016) where we look for graph structure C' for which there exists node weights [k leading to a minimal GW error. Interestingly this DL model requires only to solve the srGW problem compute the embedding hig since can be recovered from the solution T; of the problem.
We solve this non-conver optimization problem above with an online algorithm similar to the one first proposed Mairal al. (2009) for vectorial data and adapted by /Vincent-Cuz et al. (202T) for graph data. The core of the stochastic algorithm is depicted in Alg. 2 The main idea is to use batches of graphs to independently solve the embedding problems (via Al then compute estimates of the gradient V with respect to C on each batch B. Finally a projected gradient on the set S of symmetric non-negative matrices is performed to update C. In practice we use Adam optimizer (Kingma & Bal (2155) in all our experiments. The complexity of this stochastic algorithm is mostly bounded by computing the gradients, which can be done in On m + m²nz) (see Section 3.2p. Hence, in factorization context i.e. max; (mx) >> m, the overall learning procedure has
quadratic complexity w.rl. the maximum graphs size. Since the embedding h is a by-product of computing the different srGW, we do not need iterative solver to estimate it. Consequently, it leads to a speed up on CPU of 2 to 3 orders of magnitude compared to our main competitors (see Section 5.3 whose DL methods, instead, require such iterative scheme.
4.2 DL-BASED MODEL FOR GRAPHS COMPLETION
The structure C' estimated on the dataset D can be used to infer/complete new graph from the dataset that only partially observed. In this setting, we aim at recovering the full structure C' Raxx while only subset of relations between nobs < n nodes is observed. denoted as Coba E 1o This amounts to solving:
STGW? (C.n.)). where E = Cobe
min
(9)
Cimp
Cimp
where only the n 2 coefficients collected into Cimp are optimized (and thus imputed). We solve the optimization problem above by a classical projected gradient descent. At each iteration we find an optimal coupling T of srGW that is used to calculate the gradient of srGW W.E. C imp- The latter is obtained the gradient of the srGW cost function evaluated the fixed optimal coupling T by using the Envelope Theorem (Bonnans & Shapiro 2000). The projection step is here to enforce known properties of C, such as positivity and symmetry. In practice the estimated Cimp will have continuous values, so one has to apply a thresholding (with value 0.5) Cimp to recover binary adjacency matrix. The method can be easily extended to labeled graphs by also optimizing the node features of non-observed nodes.

---

Published as a conference paper at ICLR 2022
GWIC, h. ls. h)= 0.235 (amim0.66)
GWIC, I. -)- 0.244 lami=0.54)
SrGWiC. h. b)= 0.087 (emi=100)
SrGWIC, h. Io) 0.088 (ami=1.0)
Figure 2: GW vs SrGW partitioning of g- (f, with clusters of varying proportions to G (1. h) where h is fixed to uniform for GW (left) and estimated for for srGW (right) for 3 and 4. Nodes of G are colored based on their cluster assignments while those of g are interpolated based on linear interpolation of node colors of linked to them through their OT (colored line between nodes) if these links exist, otherwise default nodes color is black. Node sizes of both graphs G and G depend on their respective masses h and h.
5 NUMERICAL EXPERIMENTS
This section illustrates the behavior of srGW on graph partitioning (a.k.a. nodes clustering), clustering of graphs and graph completion. All the Python implementations in the experiments will be released on Github. For all experiments we provide e.g. validation grids, initializations and complementary metrics in the annex (see sections: partitioning 7.5.1 clustering 7.5.2 completion 7.5.3)
5.1 GRAPH PARTITIONING
As discussed in Section 2 it is possible to achieve graph partitioning via OT by estimating GW matching between the graph to partition g = (C, h) (n nodes) and a smaller graph g (I h), with q < n nodes. The atom Lg is set as the identity matrix to enforce the emergence of densely connected groups (i.e. communities). The distribution h estimates the proportion of nodes in each cluster. We recall that h must be given to compute the GW distance. whereas it is estimated with srGW. All partitioning performances are measured by Adjusted Mutual Information (AMI, Vinh et al. 2010
Simulated data. In Figure 2 we illustrate the behavior of GW and srGW partitioning on toy graph, simulated according to SBM (Holland et al., 1983) with 3 clusters of different proportions. We see that classifiiiccttoonn occurs either when the proportions h do not fit the true ones or when q F 3. On the other hand, clustering from srGW can simultaneously recover any cluster proportions (since it estimates them) and can select the actual number of clusters, using the sparse properties of h.
Real-world datasets. In order to bench- mark the srGW partitioning on real (directed and undirected) graphs, we consider 4 datasets (details provided in Table 4 of the annex); a Wikipedia hyperlink network (Yang & Leskovec 2015); directed graph of email interactions between departments of a Euro- pean research institute (Yin et al. (017); : an
Table 1: Partitioning performances on real datasets measured by AMI. We see in bold (resp. italic) the first (resp. second) best method. NA: applicable.
Wikipedia
EU-email
Village
asym:
sym
a5ym
sym
sym
sym
SPGW (ours)
56.92
56.92
49.94
50.11
48
81.84
StSpee
50.74
50.60
sGW.
$7.13
57.55
54.75
55,05
50.00
83.18
stSpeGW
53.76
61.38
54.27
50.89
85.10
81,31
Amazon product network (Yang & Leskovec) 2015); network of interactions between in- dian villages (Banerjee et al.) 2013). For the directed graphs, we adopt the symmetrization procedure described in Chowdhury & Needham 2021). Our main competitors are the two GW
GWL
38.67
35.77
41.23
46.
38.36
SpecGWL
10.73
48.98
45.89
19:02
65.16
77.85
FastGreedy
NA
55.30
NA
45.89
17.21
93.66
Louvain
NA
56.12
76.30
InfoMap
16.43
46.43
$4.18
49.10
94.33
93.66
based partitioning methods proposed by[Xu al. (2019b) and Chowdhury & Needham (202T). The former (GWI)) relies on adjacency matrices, the latter (SpecGWL) adopts heat kernels on the graph normalized laplacians (SpecGWL). The GW solver of Flamary et al. (02II) was used for these methods. For fairness, we also consider these two representations for srGW partitioning (namely srGW and srSpecGW). Finally, three competing methods specialized in graph partitioning are also considered: FastGreedy (Clauset et al., 2004), Louvain (with validation of its resolution parameter,
code available at https:ttp////..t. httppe///gtibb.ccc//////eeeeeeee
7

---

Published as a conference paper at ICLR 2022
Table 2: Clustering performances on real datasets measured by Rand Index. In bold (resp. italic) we highlight the first (resp. second) best method.
NO ATTRIBUTE
DISCRETE AT TUTIBUUTSS
REAL AI TRIBUTES
MODELS
IMDE-B
IMDB-M
MUTAG
FTC-MR
BZR
COX2
ENZYMES
PROTEIN
SrÜW (ours)
51.39(0100)
54.9400.99)
71.25(0.39)
51,4800.12 12)
62.60N0.96)
60.12(0.27)
59,66/0.10) 71.680.12)
sWGW,
52.44(0.46)
36.70(0.34)
72.31(0.51)
51.76(0.39)
66.75(0,38)
62.15(0.27)
72.51(0.10)
60.6710.29
srGW.
51.75(0..6)
55.36
74.410084)
52.35(0.42)
67.631117)
59.75(0.39)
70.93(0.33)
29.97(0.21)
&eWaery
52.23(0.83)
53,9000.68) 68)
74.6%00.73
52.53(0.47)
67.81(0.94)
60.5310.36)
71.31(0.52)
60.81(0.43)
GDL
51.34(0.27)
55.1400.55)
70.28(0.25)
51.49(0.31)
62.84(1.60)
58.39(0.52)
69.83(0.33)
60. 60.09.0)28
GDLres
51,69(0.56)
25.43(0.22)
70.92(0.11)
51.82(0.47)
1.730
59.61(0.74) (4)
71.03(0.36
60.46(0.66
GWF-r
51,02(0.30
55.09(0.46)
(9.07(1.02)
47.00995
52.45(2.41)
56.9100.44
72.09(0.21 21)
59. 39.97(0.1)
GWF-f
50,43(0.29) 29)
54, 27))
59.13(1887
80.82(0.81)
$1.75(2.84)
$2.84(0.53)
71,58(0.31)
58. 38.92(0.41) 41)
GW-k
50.31(0.03)
53.67(0.07)
47.62(1.45)
30.42(0.33)
56.7700.53)
52.4500. 13)
66.35(1.3)
50.08/0.01)
Blondel et al. 2008 and Infomap (Rosvall & Bergstrom 2008). The graph partitioning results are reported in Table ! Our method srGW always outperforms the GW based approaches and on this application the entropic regularization seems to improve the performance. We want to stress that our general purpose divergence srGW outperforms methods that have been specifically designed for nodes clustering tasks on 3 out of 6 datasets.
5.2 CLUSTERING OF GRAPHS DATASETS
Datasets and methods. We now show how the embeddings (h provided by the srGw Dictionary Learning can be particularly useful for the task of graphs clustering. We considered here three types of datasets (details provided in Ta the annex): i) social networks from IMDB-B B and IMDB-M Yannrddag & Vishwanathan 2015); graphs with discrete features representing chemical compounds from MOTAG (Debnath et al. 1991) and cunciform signs from PTC-MR (Krichene
ct al.
) iii) graphs with continuous features, namely BZR, COX2 (Sutherland et al., 2003) and PROTEINS, ENZYMES (Borgwardt & Kriegel, 2005). Our main competitors are the following OT-based SOTA models: i) GDL Cancent-Cuaz et al. (202I) and its regularized version, namely GDLX; ii) GWF (Xu) 2020), with both fixed (GWF-f) and random (GWF-r, default setting for the method) atom size; ill GW kmeans (GW-k), k-means equipped with GW distances and barycenters
(Peyré et al. 2016).
Experimental settings. For all experiments we follow the benchmark proposed in Vincent- Cuaz al. (202I). The clustering performances are measured by means of Rand Index (RI, Rand 1971). The standard Euclidean distance is used to implement k-means over SrGW and GWFs embeddings, but we use for GDL the dedicated Mahalanobis distance as described in Vincent-Cuad GW-k does not use any embedding since it directly computes (a GW) k-means over the input graphs. For each parameter configuration (number of atoms, number of nodes and regularization parameter, detailed in section 7.5.2) we run each experiment five times, independently. The mean RI over the five runs computed and the dictionary configuration leading to the highest RI for each method is reported.
al. (202
Results and discussion. Clustering performances and running times are reported in Tables 3 respectively. All variants of srGW DL are at least comparable with the SOTA GW based methods. Remarkably, the sparsity promoting variants always outperform other methods. Notably Table 3 shows embedding computation times of the order of the millisecond for srGW, two order of magnitude faster than the competitors.
5.3 GRAPHS COMPLETION
Finally, we present graph completion results on the real world datasets IMDB-B and MUTAG, using the approach proposed in 4.2 Since this completion problem has never been investigated by existing GW graph methods, we adapted the learning procedure used for srGW to GDL. (Vincent-Cuaz et al. 2021
Experimental setting. Since the datasets do not explicitly contain graphs with missing nodes, we proceed follow: first we split the dataset into training dataset (Dtrain) used to learn the dictionary and a test dataset (Drest) reserved for the completion tasks. For each graph of C E Dtests we created incomplete graphs Cots by independently removing 10% and 20% of their nodes, uniformly
8

---

Published as a conference paper at ICLR 2022
Table 3: Embedding computation times (in ms) averaged over whole datasets at a convergence precision of 10 on learned dictionaries. (-) (resp. (+)) denotes the fastest (resp. slowest)
runtimes regarding DL configurations. We report here runtimes using FGWo.s for datasets with nodes attributes. Measures taken on Intel(R) Core(TM) 17-4510U CPU @ 2.00GHz.
ATTRIBUTE
DISCRETE
ATTRIBUTES
ATTRIBUTES
IMDB-8
IMD8-M
MUTAG
PTC-MR
BZR
COX2
ENZYMES
PROTEIN
(-)
(+)
(-)
(+)
(-)
(-]
(+)
(-)
[+)
(-)
(+)
(-)
(+)
(-)
(+)
SIGW (ours)
1.51
2.62
0.83
1.59
0.86
1.83
0.40
1.01
0.43
0.79
0,51
0.90
0.62
0.95
0.46
0.60
sGW,
1.95
5.53
3.68
0.97
4.73
1.57
2.96
GWF-1
219
651
103
373
236
495
191
477
181
916
129
641
93
627
78
322
GDL
108
236
43.8
152
102
514
100
509
73.2
532
48.7
347
301
29
151
IMDB-B 10% imputed nodes
IMDB-8 20% imputed nodes
MUTAG 10% imputed nodes
MUTAG 10% imputed nodes
completion accurscy (96)
95.0
srGW
3rGW
completion accuray
SFGGW
SFGW
97
srSW,
94.5
,
completion MSE
96-
GDI
GDI
GDL GDL
0.02
GDI
GDL,
93.5
GDL
94
GDL
93.0
94
92.5
93
92.0
0.00
10
20
30
40
50
10
20
30
40
50
10
20
30
40
50
10
20
30
40
50
test dataset proportion/%)
proportion(%)
proportion (%6
proportion
Figure 3: Completion performances for IMDB-B (left) and MUTAG (right) datasets, measured by means of accuracy for structures and Mean Squared Error for node features, respectively averaged over all imputed graphs.
at random. The partially observed graphs are then reconstructed using the procedure described in Section 4.2 and the average performance of each method is computed for 5 different dataset splits.
Results. The graph completion results reported in Figure 3
Our srGW dictionary learning outperforms GDL consistently, when enough data is available to learn the atoms. When the proportion that the linear GDL model that maintains the marginal constraints
of train/test data varies, we tends to be less sensitive to the scarcity of data. This can come form the fact that srGW is more flexible thanks to the optimization of h but can slightly overfit when few data is available. Sparsity promoting regularization can clearly compensate this overfitting and systematically leads the best completion performances (high accuracy, low Means Square Error).
CONCLUSION
We introduce new transport based divergence between structured data by relaxing the mass constraint on the second distribution of the Kromov-Wasserse estimate this divergence, called the semi-relaxee Gromov- Wasserstein (srGW), we suggest to learn a unique structure to describe a dataset of graphs in the srGW sense. This novel modeling can be seen as a Dictionary Learning approach where graphs are embedded Numerical experiments highlight the interest of our methods for graph partitioning, and unsupervised representation learning whose evaluation is conducted through clustering and completion of graphs.
problem. After designing efficient solvers to
subgraph of single atom.
We believe that this new divergence will unlock the potential GW for graphs with unbalanced proportions of nodes. The associated fast numerical solvers allow to handle large size graph datasets, which was not possible with current GW solvers. One interesting future research direction includes analysis of srGW perform parameters estimation of stochastic block models. Also, relaxing the second marginal constraint in the original optimization problem gives more degrees freedom the underlying problem, one can expect dedicated regularization schemes, over e.g. the level of sparsity of h, to address a variety of application needs. Finally, method can be seen special relaxation the subgraph isomorphism problem. remains to be understood theoretically which sense this relaxation holds.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work is partially funded through the projects OATMIL ANR-17-CE23-0012 OTTOPIA ANR- 20-CHIA-0030 and 31A Côte d' Azur Investments ANR-19 19--199--3--022 of the French National Research Agency (ANR). This research was produced within the framework of Energy4Climate Interdisciplinary Center (B4C) of IP Paris and Ecole des Ponts ParisTech. This research was supported by 3rd Programme d' Investissements d' Avenir the support of the Chair "Challenging Technology for Responsible Energy" led by 1'X Ecole polytechnique and the Fondation de E'Ecole polytechnique, sponsored by TOTAL. This work is supported by the ACADEMICS grant of the IDEXLYON, project of the Universit de Lyon, PIA The authors are grateful to the OPAL infrastructure from Université
100-188-UR-00066
This action benefited from
operated by Côte d' Azur for providing resources and support.
REFERENCES
Abhijit Banerjee, Arun Chandrasekhar, Esther Duflo, and Matthew O Jackson. The diffusion of microfinance. Science, 341(6144), 2013.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston. Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, 2018.
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Iterative Bregman Projections for Regularized Transportation Problems. SIAM Journal on Scientific Computing, 37(2):A111-AA113 January 2015. ISSN 1064-8275, 1095-7197. doi: 10.1137/ 141000439.
Florian Bernard, Christian Theobalt, and Michael Moeller. Ds*; Tighter lifting-free convex relaxations for quadratic matching problems. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4310 2018.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pp. 874-883.
PMLR, 2020.
Vincent D 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): 2008.
Jesús Bobadilla, Fernando Ortega, Antonio Hernando, and Abraham Gutiérrez. Recommender systems survey. Knowledge-based systems, 46:109-132, 2013.
J. Bonnans and Alexander Shapiro. Perturbation Analysis of Optimization Problems. 01 2000. ISBN 978-1-4612-7119-1. doi: 1-0077998-114612--11
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. Fifth IEEE international conference data mining (ICDM 05), pp. 8-pp. IEEE, 2005.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEFE Signal Processing Magazine, 34(4):18 42, 2017.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Velivckovié. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. ArXiv, abs/2104. 13478, 2021.
Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37, 2011.
Lactitia Chapel, Mokhtar Z Alaya, and Gilles Gasso. Partial woasorvwasserstein with applications positive-unlabeled learning. arXiv preprint arXiv:2002.08276, 2019.
10

---

Published as a conference paper at ICLR 2022
Yudong Chen, Sujay Sanghavi, and Huan Xu. Improved graph clustering. IEEE Transactions Information Theory, 60(10);6440-6) 6455, 2014.
Samir Chowdhury and Facundo Mémoli. The gromov-wasserster distance between networks and stable network invariants. Information and Inference: Journal the IMA, 8(4):757-777, 2019, 2019.
Samir Chowdhury and Tom Needham. Generalized spectral clustering via gromov-wasserstem learning. In International Conference on Artificial Intelligence and Statistics, pp. 712-720. PMLR, 2021.
Aaron Clauset, Mark Newman, and Cristopher Moore. Finding community structure very large networks. Physical review E, 70(6):0661 11, 2004.
Nicolas Courty, Rémi Flamary, and Devis Tuia. Domain adaptation with regularized optimal transport. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp- 274-289, Springer, 2014.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in neural information processing systems, pp. 2292-2300, 2013.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 (2):786-797, 1991.
Persi Diaconis and Svante Janson. Graph limits and exchangeable random graphs. arXiv preprint arXiv:0712.27499, 2007.
Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2): 298-305, 1973.
Rémi Flamary, Cédric Févotte, Nicolas Courty, and Valentin Emiya. Optimal spectral transportation with application to music transcription. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, pp. 703711, 1. Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819,
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Zahdi Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenñlos, Kilian Fatras, Nemo Fournier, et al. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021.
Hongyang Gao and Shuiwang Ji. Graph u-nets. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings the 36th International Conference Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 1083-20092 PMLR, 09-15 Jun 2019.
Zaïd Harchaoui and Francis Bach, Image classification with segmentation graph kernels. In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8. IEEE, 2007.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First
steps. Social networks, 502):199-33,, 1983.
David R Hunter and Kenneth Lange. A tutorial on mm algorithms. The American Statistician, 58(1): 30-37, 2004.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International Conference Machine Learning, pp. 427-435. PMLR, 2013.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Židek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-55)
2021.
Tatsuro Kawamoto, Masashi Tsubaki, and Tomoyuki Obuchi. Mean-field theory graph neural networks in graph partitioning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 43664376, Red Hook, NY, USA, 2018. Curran Associates Inc.
11

---

Published as a conference paper at ICLR 2022
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Walid Krichene, Syrine Krichene, and Alexandre Bayen. Efficient bregman projections onto the simplex. In 2015 54th IEEE Conference on Decision and Control (CDC), pp. 3291-3298, IEEE, 2015.
Nils M Kriege, Fredrik Johansson, and Christopher Morris. A survey on graph kemnels. Applied Network Science, ((1):1-42, 2020.
Sofia Ira Ktena, Sarah Parisot, Enzo Ferrante, Martin Rajchl, Matthew Lee, Ben Glocker, and Daniel Rueckert. Distance metric learning using graph convolutional networks: Application functional brain networks. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 469-477. Springer, 2017.
Simon Lacoste-Julien. Convergence rate of frank-wolfe for non-convex objectives. arXiv preprint arXiv:16677000345, 2016.
Weijie Liu, Chao Zhang, Jiahao Xie, Zebang Shen, Hui Qian, and Nenggan Zheng. Partial gromov- wasserstein learning for partial graph matching, arXiv preprint arXiv:20/2.01252, 2020.
Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online dictionary learning for sparse coding. Proceedings of the 26th annual international conference on muchine learning, pp- 689-696, 2009.
Haggai Maron and Yaron Lipman. (probably) concave graph matching. In Advances in Neural Information Processing Systems, pp. 408-418, 2018.
Facundo Mémoli. Gromov-wasserstein distances and the metric approach to object matching. Foundations of computational mathematics, 11(4)417-447, 2011.
Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Azade Nazi, Will Hang, Anna Goldic, Sujith Ravi, and Azalia Mirhoseini. Gap: Generalizable approximate graph partitioning framework. arXiv preprint arXiv:1903.00614 2019.
Andrew Y Ng. Michael Jordan, Yair Weiss, et al. On spectral clustering: Analysis and algorithm.
Advances in neural information processing systems, 2:849-856, 2002.
Yin Cheng Ng, Nicolò Colombo, and Ricardo Silva. Bayesian semi-supervised learning with graph
gaussian processes. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Basa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. Matching node embeddings for graph similarity. In Proceedings of the Thirty- AAAI Conference Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pp. 1429-2433 2017.
Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. Got: An optimal transport framework for graph comparison. Advances in Neural Information Processing Systems, 32: 12:13876-1388 2019.
Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends in Machine Learning. 11:355-607) 2019.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-wwaserstein averaging of kernel and distance matrices. In International Conference on Machine Learning, pp. 2664-2672, 2016.
Julien Rabin, Sira Ferradans. and Nicolas Papadakis. Adaptive color transfer with relaxed optimal transport. In 2014 IEEE International Conference on Image Processing (ICIP), pp. (852-4856, 2014. doi: 10. 10.1100 109//CIP220144400559585
12

---

Published as a conference paper at ICLR 2022
William M Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, 66(336):846- -000,006--00-00 1971.
Simone Romano, Nguyen Xuan Vinh, James Bailey, and Karin Verspoor. Adjusting for chance clustering comparison measures. The Journal of Machine Learning Research, 17(1):4635-466 2016.
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):1118-11233 2008
Morgan
Schmitz, Matthieu Heitz,, Nicolas Bonneel, Fred Ngole, David Coeurjolly, Marco Cuturi, Gabriel Peyré, and Jean-Luc Starck. Wasserstein dictionary learning: Optimal transport-based unsupervised nonlinear dictionary learning, SIAM Journal on Imaging Sciences, 11()):6436678 2018.
Bernhard Schmitzer and Christoph Schnörr. Modelling convex shape priors and matching based on the gromov- woasev-waserrttin distance. J. Math. Imaging Vis., 46(1):143159, may 2013. ISSN 0924-9907. doi: 10.10077s10881--12--3333
Thibault Séjourné, François-Xavier Vialard, and Gabriel Peyré. The unbalanced gromov wasserstein distance: Conic formulation and relaxation. arXiv preprini urXiv:2009.04220 2020.
David Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEFE Signal Processing Magazine, 30:83-98, 2013.
Justin Solomon, Gabriel Peyré, Vladimir G Kim, and Suvrit Sra. Entropic metric alignment for correspondence problems. ACM Transactions on Graphics (TOG), 35(4):1-13, 2016.
Karl-Theodor Sturm. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. arXiv preprint arXiv: /200//08.000 0434, 2012.
Jeffrey Sutherland, Lee A O'brien, and Donald F Weaver. spline-fitting with genetic algorithm: A method for developing classification structure- activity relationships. Journal of chemical information and computer sciences, 43(6): 2003.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-lehman graph kernels. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alcéé-Bur E. Fox, and Garnett (eds.), Advances in Neural Information Processing Systems 32 (NeurIPS), pp. 6436-6446. Curran Associates, Inc., 2019.
Titouan Vayer, Nicolas Courty, Romain Tavenard, and Rémi Flamary. Optimal transport for structured data with application graphs. In International Conference Machine Learning, pp. 6275-6284. PMLR, 2019.
Titouan Vayer, Laetitia Chapel. Remi Flamary, Romain Tavenard, and Nicolas Courty. Fused gromov- wasserstein distance for structured objects. Algorithms, 13(9), 2020. ISSN 1999-4893. doi: 0..3390/a13000220
Cédric Vincent-Cuaz, Titouan Vayer, Rémi Flamary, Marco Comeli, and Nicolas Courty. Online graph dictionary learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 10564-10574. PMLR, 18-24 Jul 2021.
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, 1:2887-2854, 2010.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
13

---

Published as a conference paper at ICLR 2022
Yujia Xie, Xiangfeng Wang, Ruijia Wang, and Hongyuan Zha. A fast proximal point method for computing exact wasserstein distance. In Ryan Adams and Vibhav Gogate (eds.), Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pp. 433-453. PMIR, 22-25 Jul 2020.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov-wassersten learning for graph partitioning and matching, Advances in neural information processing systems, 32:3052-3062, 2019a.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov-wassersten learning for graph matching and node embedding. International conference on machine learning, pp. 6932-6941. PMLR, 2019b.
Hongteng Xu, Dixin Luo, Lawrence Carin, and Hongyuan Zha. Learning graphons via structured gromov-wasserstiin barycenters. Proceedings of the AAAI Conference Artificial Intelligence, 35(12):10505-10513, May 2021.
Hongtengl Xu. Gromov-wasserstr factorization models for graph clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp.
2020.
Junchi Yan, Xu- Xu-Cheng Yin, Weiyao Lin, Cheng Deng, Hongyuan Zha, and Xiaokang Yang. A short survey of recent advances in graph matching. In Proceedings of the 2016 ACM on International Conference on Multimedia Retrieval, pp. 167-174, 2016.
Pinar Yanardag and SVN Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 42(1):181-22 2015.
Hao Yin, Austin R Benson, Jure Leskovec, and David F Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 555-564, 2017.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. Proceedings of the 32nd International Conference Neural Information Processing Systems, NIPS' 18, pp. 48054815, Red Hook, NY, USA, 2018. Curran Associates Inc.
Daniele Zambon, C. Alippi, and Lorenzo Livi. Graph random neural features for distance-preserving graph representations. In JCML, 2020.
Feng Zhou and Fernando De la Torre. Factorized graph matching. In 2012 IEEE Conference Computer Vision and Pattern Recognition, pp. 127-134. IEFF, 2012.
7 APPENDIX
7.1 NOTATIONS & DEFINITIONS
In this section recall the notations used in the rest of the appendix.
Notations.
For a vector h E R we define its support as supp(h) = fi E [m]
h; + 0}. Note that
if h Σm have supp(h) {i [m]][;; 0). The cardinal of discrete set A is denoted |A].
For a 4-D tensor L= (Lozkt)ijи we denote 2 the censor-matrix multiplication such that for a given matrix M. L 88 M is the matrix with entries (Eu Tagga Maa
14

---

Published as a conference paper at ICLR 2022
Constraints on couplings. and h, i.c the set
We introduce U(h, h) the set of all admissible couplings between h
u(h, h) = (T ma Tim = h h, =h)
We also introduce for any 2n and m N Uhh, m) the set of all admissible couplings between h and any histogram of 2m i.e the set
u(h,m) == (T E Raxm [1m = =h),
such that vT E (1h,, m), the second marginal h = T 1n) belongs to Σm
Gromov- Maanov-Wasssrstein distance. For any q 2 1, the Gromov- Wasse--tnnnrtniinn distance of order between (C, h) and (C, h) is defined by:
GWa(C,h,C,h)
min C, TEU(h.))
where
(,C,,,,T)= E E 1Cy- - TT....
[JE[m]RR RJE[I]]
This definition can be equivalently expressed with tensor-matrix multiplication
h.h.)
min TEU(h,
(Lg(C,C) & T.T)
(10)
where (C, is the 4-D tensor such that (C ((Ci) Cxt)9) 19kl"
Semi-relaxed Maanoo-Wasssestein divergence. gence of order satisfies the following equation:
The semi-relaxed Wasserseen diver-
CG, min TEU(H.))
C,,
or equivalently
C,, min Tel(h.))
(,C,CC)TTT 0
(11)
Fused Gromoy-Wassersser distance. For attributed graphs i.e graphs with nodes features, use the Fused Wassersttnn distance (Vayer et al. 2019). Consider two attributed graphs = CCCCE h) and 9 = (C,F.)) h) where = (Fi)ie]n E IR nxd and F = (F))) E Rxx are their respective matrix of features whose rows are denoted by (Fitie[n) and (Fe)imm)) Given trade-off parameter between structures and features denoted E [0:1], the FGW a. distance is defined as the result of the following optimization problem
min (1 - a) ΣIE; TEU(h,)
|FF FilliT +
(12)
ijkl
which is equivalent
min (1- (F) (CL Teu(h.
(13)
where M2(F F,F. F) is matrix with entries M2 (F, F)
F;
Fjl
Semi-relaxed Frommo--Waserstein distance. Then in a similar way than for the Gromov- of order q is defined for any
Wasserstein distance, the semi-relaxed Fused trade-off parameter a E [0; 1] as the result of the following optimization problem
ST FGW2 9.0 (C,WW,,CCCCC F.C.F.h..FF.
min ((1 (C. T
(14)
One can see these problems as regularized versions of the quadratic problem of GW/srGW where a linear term in T takes into account similarity measure between features of attributed graphs.
15

---

Published as a conference paper at ICLR 2022
7.2
SEMI-RELAXED (FUSED) WASSERSSSSSR PROPERTIES
7.2.
EQUIVALENCE OF THE OPTIMIZATION PROBLEMS
Let us begin with the proof of the equivalence between both optimization problems used to define semi-relaxed Gromov-Wassersee divergence. Consider two observed graph (C, and (C, h) of and m nodes. Our first optimization problem reads as
h arg min GW,(C,h,C.h) KEE.
(15)
The second optimization problem coming from the relaxation of the second marginal constraints (T 1n = h) of admissible couplings T reads as
min ΣlG,, - Cal CkIlTTTT TTaTat- (E) GjkI
(16)
Note that in the following proofs we always assume that graphs correspond to finite discrete measures and that their geometry is well-defined in the that entries of C and C are always finite. This implies that graphs define compact spaces ensuring existence of optimal solutions for both problems.
Lemma Problems 15 and 16 are equivalent.
Proof. Consider solution of problem 15 denoted (fz Ti) note that the definition implies that Ti E u(h, K.). Another observation is that given hy the transport plan T₁ also belongs to arg min CC, C,T) hence is an optimal solution of GW, (C,(C, h, C,h,).
Now consider solution of problem 16 denoted T2 with second marginal h By definition the couple (h2 T2) is suboptimal for problem (15 i.e
C,C,,,,T) S C,C,C,
(17)
And the symmetric also holds as T3 a suboptimal admissible coupling for problem 16
CC, < CC,,C,T..
(18)
These inequalities imply that CC CC, Therefore we necessarily have Tj arg migg (C,C,T) and (h,, TT) arg equality, GW (C, = GW (C, h. C, h2 holds true. Therefore by double inclusion we have
CC, C,T). Hence the
arg min (C,C,.) hEEm.TEU(hh)) r))(h,m
arg min C,C,,C,T)
(19)
Which is enough to prove that both problems are equivalent.
The equivalence between analog problems for the semi-relaxed Fused Gromov-Wassersein diver- gence can be proved in the exact same way.
7.2.2 ZERO CONDITIONS OF (FUSED) SRGW
We prove the following result:
Proposition 1 Let C E Raxn and C' E mm be distance matrices and E En, with shpp(h) = WC,,,CC (C, C, C)=
[n]. Then srGW,
= iff there exists h E Em with card(supp(h)) n and a bijection
sh) + [n]] such that:
Vi (h),(h),Ttt hii) h(a(i))
(20)
and:
Ak, I supp(h)² Cu Co(k)o())
(21)
16

---

Published as a conference paper at ICLR 2022
Algorithm 3 CG solver for srGW, optionally with linear regularization term D m Note that
D = 0 for unregularized version of srGW of equation 25
1: repeat
2: G Compute gradient w.r.t T of 24 satisfying equation 2p in T(t)
3: Get direction X problem: Solve independent subproblems rows of G thanks to the
equivalence stated here
X
arg mrg (X, G( +D)
XEl(hh.))
(22)
(h,a)") senn f arg (an G. + D,).
m, m,
4: Get optimal step size 7 for the descent direction X T for any y [0, 1] let us denote
(n) (7) (T() (xx
(x (t) T ) then y is defined
arg min (L(C, C) & Z (0 (7). z' (n)) + (D, (D, (7)) >E(o.1]
(23)
factored as a second-order polynomial function of the form ary by + c, by using linearity of the conso--multplliaaiion @ and of the scalar product. Then the closed form obtained by simple analysis of coefficients and as in (Vayer et al. 2019).
5:
((++)) + ( (r*) = (1 --"""" >*(((() + 7 x*)
6: until convergence decided based relative variation of the loss between step and t 1.
Proof. The reasoning involved in this proof mostly relates on the definition of srGW as kEE. GW;(C, C.).
(+) Assume that srG 0. Then we have GW, C,,, 0 for some h. By virtue to Kromov-Wassersee
properties (Sturm) 2012, Lemma 1.10) there exists a bijection o between the support of the distributions which is distance preserving. In other words, there exists shpp(h) - supp(h) = [n] such that h(j) h(((j)) for all j shpp(h) and Cki (o(k)o(1) for all k, supp(h)?
(+) Consider T U(,, h) and the induced bijection a satisfying equations 20 and Is trivial verify that L(C, C, T) implying that GC, h, C, h) 0. Moreover T E U(h, m) since uh, h) c (h, m) and the same cost is involved in both transport problems, we have:
h, 0 < h, GW GW, C. =0
=
7.3 ALGORITHMIC DETAILS
We provide in this section the algorithmic details completing our explanations given in the main paper (see subsection 3.2). Note that for all numerical experiments we considered 2, so the following algorithms are specific to this scenario.
7.3. CONDITIONAL GRADIENT SOLVER FOR SRGW AND SRFGW
The optimization problem related to computing sr GW C, h, C) can be reformulated as
vec(T)) (c" 8K 1 2C 00 c) vec(T).
min Tlmsh 720
(24)
where Ø denotes the Kronecker product of two matrices, vec the column-stacking operator and the power operation on C is applied element-win For simplicity let use the other equivalent formulation using the 4-D tensor notation i.e
min Teu(h,F)
C)C,C) & TTT)
(25)
17

---

Published as a conference paper at ICLR 2022
where C) ((C,) - xx izk!" This is non-convex optimization problem with the same objective and gradient G than GW which can be expressed in the general case as
G L 8 L(C,, , c
(26)
Note that if and are symmetric matrices the gradient can be factored to
G = =) &T.
(27)
We propose to use Conditional Gradient (CG) algorithm Jaggi 2013 to solve this problem, provided in Alg. 3
For the sake of conciseness, we also introduce here a linear regularization term of the form (D, T which will be used while enforcing sparsity promoting regularization on srGW or for adapting this algorithm to srFGW where D results from distances between features (up to proper scaling with the trade-off parameter a).
Then in this general case, our CG algorithm consists in solving at each iteration t the following linearization of the problem (24)
min (x, G(9 + D)
(28)
Xim=h X
where ((t) is the gradient (*) of (24). The optimization problem above can be very efficiently
solved as discussed in (Flamary et al. 2016, Equation (8)). Indeed the problem above can clearly
be reformulated as independent linear problems under simplex constraints (each row of X can be
solved independently) of the form
min
x
(29)
where 9r is the row r of G. Optimizing a linear function over the simplex of dimensionality n can be done in ((m) because it consists in finding the smallest component i arg min g. in the linear cost, the solution being scaled dirac vector d, where all the mass is positioned on component i*. The solution the linearized problem provides a descent direction (() ( and a line-search is performed get the optimal step size as described in equation 23 Note that the gradients at time step
T( and (+++) have simple linear relation, which used in our implementation for conciseness but it is rather equivalent to the more classical implementation literally expressing terms involved in the line-search part.
Extension to srFGW. For two attributed graphs (C, h) and FC, of n and nodes respectively, the semi-relaxed Fused Gromov- Wasserstein divergence of order 2 from onto y is defined for any E [0, 1] as the result of the following optimization problem
STFGW2 (C.F,H.CFFF
min ((L MF F) aL(C, Tel((h.)
(30)
where M(F F) denotes the matrix of euclidean distances between features of and F, i.e. M, = |. - ,12 As a side note, one efficient way to compute this matrix in practice is by using the following factorization M (F, F) = (F 1, + 1,,17 (Fo O F) - F where c denotes the Hadamard product. The problem in equation 14 is nonconvex quadratic problem which gradient w.E.t T reads as
oG + (1--a) (1-a)
(31)
where G corresponds to the gradient of the GW cost satisfying equation 26 Therefore propose
tackle this problem by straight-forward adaptation of the CG algorithm detailed above by adding
the multiplier a to the GW cost and setting D = (1 ( F).
7.3.2 ALGORITHMIC DETAILS AND GUARANTIES ON ENTROPIC SRGW.
Recent OT applications have shown the interest of adding an entropic regularization to the exact problem (44 Cuturi (013); Peyré al. (2016). We detail here how to design a misror-descent scheme w.r.f. the Kullback- Leibler divergence (KL) to solve (24). in the same vein than Peyré et al.
(2016); Xu al. (209h)) Xie et al. (2020).
18

---

Published as a conference paper at ICLR 2022
Algorithm 4 MD solver for entropic srGW. optionally with linear regularization D R=xx
Note that D = 0 for unregularized version of srGW of equation 25
1: repeat
2: G Compute gradient w.r. T of 24 satisfying equation 26
applied in T())
3: Compute the matrix K (e) following equations (36) and (38
4: Get T(++1) with the scaling of (e) following equation 37
5: until convergence decided based on relative variation of the loss between step and t 1.
mirror- descent scheme w.rl the KL geometry. At iteration i, the update of the current transport plan T()) E l(h,, m) results from the following optimization problem
Algorithmic details. Indeed in order to solve the srGW problem stated in 16
((++1) &
arg min (G(T T) + (L((T)(() TEU(h.))
(32)
where G' satisfies and (L(TTT(()) = Eig Túp log( T!.) Tú, T Let us denote the entropy
of any T R4 2 by H(T) =is (log Taj 1), then the following relation can be proven
M
(M, T) H KT exp(- + (L
(-elog M, M) H(T)
(33)
and leads to this equivalent formulation of 32
( < arg min (G)) log ( (1),, T) H(T). Tel(h.m)
(34)
Denoting ()) G(T()) log (t), overall we end up with the following iterations
((+1)) arg min (M (c), - H(T). Tel(h,m)
(35)
Which is equivalent thanks to the relation stated above
((+1) arg min TEU(h.m)
(KT((K(((()))) where (1) -x)
(36)
Following the seminal work of (Bnnamou al. 2015), the optimal ((++)) given by a simple scaling of the matrix K(t) (e) reading
h ( diag (c)mm)
K (E).
(37)
Note that an analog scheme is achievable while penalizing the srGW problem with a linear term of the form (D, T). Which would simply result modification the matrix (*) such that
( G(T())) D e log (t))
(38)
This more general setting is summarized in algorithm 4
Similarly than for the CG algorithm 3 it is straight-forward to adapt the MD algorithm 4 to the semi-relaxed Fused Wasserttsss using FGW cost expressed in 31
7.3.3 SPARSITY PROMOTING REGULARIZATION OF SRGW
In order to promote sparsity of the estimated target distribution while matching (C, h) to the structure T using SrGW, we suggest to use Q(T) Σ, 1/2 which defines concave function in the positive orthant R,, This results in the following optimization problem:
min (h)
(L(C, & T.T) + (T)
(39)
with X, E R, an hyperparameter. As mentioned in the main paper, equation 39 can tackled with a Majorisation-MMnniiisttoon (MM) algorithm. MM consists in iteratively minimising upper bound
19

---

Published as a conference paper at ICLR 2022
Algorithm 5 MM solver for srGW, and srGWe+g
1: Set R = O.
2: repeat
3: Get optimal transport (()) with second marginal h (1) from CG solver (srGW,) or MD
solver (srGW (4g) with D (())
4: Compute R((+1))
Aa 2 h kjj
(t) -1/2
the new local linearization of ((T()).
5: until convergence.
Algorithm Stochastic update of the atom C
Sample a minibatch of graphs B == {(C(()) , 3e.
2: Get transports hee from srGW(Ck: h&s C) with Alg
3: Compute the gradient V of srGW with fixed (Te)keB and perform projected gradient step on symmetric non-negative matrices S:
C C-orjs - +
(41)
of the objective function which is tight the current iterate (Hunter & Lange 2004). With this procedure, the objective function is guaranteed to decrease at every iteration. In our case, we only need to majorize the penalty term (T(T)) to obtain a tractable function. Denoting h² T I,. the estimate at iteration f, one can simply apply the tangent inequality
ΣV S Σ
(h h T
(40)
h
Using this inequality is equivalent to linearize the regularization term at h whose contribution
can be absorbed into the inner product as (L(C,T) 3 T + R( (T) where R( (h) (1)
1
The overall optimization procedure is summarized in 5 Note that the same procedure is used for
promoting sparsity of srFGW using the adaptation of our CG solver 3 and MD solver 4 to this scenario.
7.4
LEARNING THE TARGET STRUCTURE
We detail in the following the algorithms for the srGW Dictionary Learning and its application to graphs completion.
7.4.1
SRGW DICTIONARY LEARNING.
We propose learn the graph atom C puxm from the observed data D {(C), hu ke) by optimizing
K
min DERmXm
SrGW? hu, C),
(42)
K
This is a nonconvex problem that we propose to tackle thanks to a stochastic gradient algorithm summarized in 6 At each iteration it consists in sampling a batch of graphs B ((C,, h2) hejp
from the dataset and to embed each graph where F = T 1, by solving independent srGW problems for the current state of the dictionary. Then we compute the estimate the gradient over reading
VC())
Σ kE|B]
(Cohuhe - T C.T...
(43)
B
Note that only the entries (i,j) of C such that and j belongs to U₁ (fp can have non-null gradient. Finally, depending on the input structures we consider, we apply a projection on an adequate set S, for instance if input structures adjacency matrices consider S the set of non-negative
20

---

Published as a conference paper at ICLR 2022
Algorithm 7 Algorithms for graph completion using DL from srGW or GDL
1: Initialize randomly the entries Cimp by iid sampling from (0.5, 0.01) (In symmetric manner
if Cots is symmetric).
2: repeat
3: Compute the optimal representations ( of the (C(9, h) onto the dictionary and optimal transport ( between (C((1) h) and G(t);
(srGW): (( (C, h 1,) where T(( +- srGW h, C)
(GDL): : ((0) = 2 mg C,, where (w T(t) + min GW(C h, Σ sE]+]
Wc C. h)
weBs
+E[e]
(46)
4: Get C(++1) from projected gradient step w.r.t. the GW distance between (C h) and ((t)) with the optimal coupling (())
5: until convergence.
symmetric matrices (iterates can preserve symmetry but not necessarily non-negativity depending on the chosen learning rate).
Extension to attributed graphs. The stochastic algorithm described above can be adapted to dataset of attributed graph {(Ck, Fx) hx]] with nodes features in Rd by learning an attributed graph atom (C, F). The optimization problem would now read as
min CERMXm FERmx
Σ
srFGW? 2,0 (CR, FE, hg, C,F)
(44)
K
KEIK]
for any [0, 1]. The stochastic algorithm i then adapted by first computing embeddings based on srFGW instead of srGW. Then simultaneously updating C following (44) up to the factor a and F thanks the following equation
2
Σ KE[B]
(diag(h))) T3 FE).
(45)
7.4.2 DL-BASED MODEL FOR GRAPHS COMPLETION
The estimated structure C, learned on the dataset can be used to infer/complete a new graph form the dataset being only partially observed. Let say that want to recover the structure C Rax but we only observed the relations between noss < n nodes denoted as Coha E Roba Roba, We propose solve the following optimization problems recover the full matrix C' while modeling graphs with our srGW Dictionary Learning
min
srGW3 (č,,,C), where Ö
Coba
(47)
Camp
Cimp
Graph completion with GDL For the linear dictionary GDL (Vincent -uaz et al., 2021 with several atoms denoted (Cx)se[s] sharing the same weights h we adapted our formulation their model:
min min GW? Comp WeE,
C.h. Σ W.C. SE[S]
(48)
The matrix C has only the n obs coefficients collected into Cimp are optimized (and thus imputed). This way Camp expresses connections between the imputed nodes, and between these nodes and the observed ones in Cobs- We tackle the non-convex problems above following the procedure described Algorithm
It consists in an alternating scheme where at each iteration we embed the current estimated graph (t)) the dictionary depending the chosen model (see (6)). Let us denote (1)) (C (1)
21

---

Published as a conference paper at ICLR 2022
this representation which respectively reads for srGW as T = (c,h²) and for GDL as G EEEes] w. w.'C C, h)). Note that from this embedding step also get the optimal transport T(t) from the GW distance between (C h) and ( Then we can update the imputed part Cmp of C while keeping fixed Cots thanks to a projected gradient step with gradient w.z. C' reading as
(c Oh T -(00011
(49)
7.5
DETAILS ON THE NUMERICAL. EXPERIMENTS.
7.5. GRAPH PARTITIONING
Table 4: Partitioning benchmark: Datasets statistics.
Datasets
nodes
# communities
connectivity rate (%)
Wikipedia
1998
15
0.09
EU-emai
T00S
42
3.25
Amazon
1501
12
0.41
Village
1991
12
0.42
Table Partitioning performances on real datasets measured by AMI. Comparison between srGW and Kmeans whose hard assignments are used to initialize srGW.
Wikipedia
EU
Amazzn sym
Village
ssym
sym
asym
sym
sym
sGG (ours)
36.92
56.92
49.34
30.11
48.28
81.84
xGW
57.13
57.55
54.75
53.05
50.00
83.18
Kmmans (ad))
29.40
29.40
36.59
34.36
60.83
Detailed partitioning benchmark. We detail here the benchmark between srGW and state-of- the-art methods for graph partitioning on real (directed and undirected) graphs. We replicated the benchmark from (Chowdhury& Needham) 202T) using the 4 datasets whose preprocessing is detailed in their paper and resulting statistics are provided in Table 4 We considered the two GW based partitioning methods proposed by (Xu et al. 2019a) (GWL) and (Chowdhury & Needham 202I) (SpecGWL). We benchmarked our methods denoted srGW and srSpecGW using respectively the adjacency and heat kernel on normalized Laplacian matrices as inputs. All these OT based methods depend on hyperparameters which can be tuned in unsupervised way (i.e. without knowing the ground truth partition) based on modularity maximization (Chowdhury & Needham 202T). Following their numerical experiments, we considered input distribution h for the observed graph the parameterized power-law transformations of the form h2 = 2i where p. = (deg(i)
a),, with deg(i) the i-th node degree and real parameters E R and b E [0. 1]. If the graph has isolated nodes we chose
and 1 otherwise. b is validated within these 10 values {0, 0.0001, 0.005.... .... 0.1, 0.5, 1} which progressively transform the input distribution from the uniform the normalized degree ones. An ablation study this parameter reported in Table 6 The heat parameter for SpecGWL and srSpecGW is tuned for each dataset within the range [1, 100] by recursively splitting this range into 5 values, find the parameter leading to maximum modularity. and repeat the same process on the induced new interval with this best parameter as center. This process is stopped based on the relative variation of maximum modularity between two successive iterates of precision 10-3 A similar scheme can be used to fine-tune the entropic parameter.
On our algorithm initialization. (Chowdhury & Needham 2021 1 also discussed the sensitivity of GW solvers to the initialization and showed that GW matchings with heat kernels have considerably less spurious local minimum than GW applied adjacency matrices. This way it is arguable to
compare both methods by using the product hh as default initialization. We observed for srGW that using an initialization based on the hard assignments of a kmeans on the rows of the input representations (up to the left scaling diag(h)) was better trade-off for both kinds of representation. Hence we applied this scheme for our method in this benchmark. We illustrate in Table how srGW refines these hard assignments by soft ones through OT.
Note that for these partitioning tasks we should/can not initialize the transport plan of our srGW solver using the product of h. E En with uniform target distribution h (0)
2 lg. leading to
22

---

Published as a conference paper at ICLR 2022
Table 6: Partitioning performances on real datasets measured by AMI: Ablation study of the param- eter involved in the power-law transformations parameterized by b E [0, 1] of normalized degree distributions for srGW and GW based methods. We denote different modes of transformation by "unif" (b- 0), 'deg' (b = 1) and 'inter' (0 < b < 1). We see in bold (resp. italic) the first (resp. second) best model. We also highlight distribution modes leading to first (bold) and second (italic)
times to highest scores across all methods.
Wikppedi
EU emaal
Village
syym Dkg
sym
35ym
sym
sym
sym
MAy
inter
deg
inter
Day
deg
Inter
deg
Inter
degg
inter
undl
dog
W (ORns)
27.
50.9
$2.7
27.4
36.9
42.7
2...5
25.9
20.3
15.3
S111
4013
-2.7
38.1
74.0
6:.0
X1.8
stSpeeGW
48.9
44.8
50.7
58.2
55.4
63.0
47.8
44.3
19.1
46.8
43.6
50.6
15.7
69.5
76.3
$7.5
78.1
86.7
aGW,
54.9
48.5
$7.1
54.3
47.8
57.6
53.9
48.6
54.8
53.5
42.1
55.1
48.2
42.9
50.0
83.2
69.1
82.7
SS
53.8
39,0
54.9
61.4
47.9
76.9
85.1
84.3
77.6
83.9
GWL
33.15
27.5
SpectiWL
29.5
48.9
40.7
48.8
47.1
64.5
64.8
05.1
77.3
64.9
77.8
T g Indeed, for any symmetric input representation C of the graph, the partial derivative of our objective w.r. the (p,4)= [N] x [Q] entries of T, satisfies
Oc (C, Iq, (( = - Cipp 5zg) (T1
2
E(
Cg + 8āg - 20
8Tpp
Q
(50)
2 Q Σ Q
C +1 2
This expression is independent of q E [Q]. taking the minimum value over each row in the direction finding step of our CG algorithm (see algo
3 will lead to X T Then the line-search
step involving, for any Y E [0, 1]. Z (7) ( + T will be independent of as Z ( (7) = (D) This would imply that the algorithm will terminate with optimal solution T == T) being a non-informative coupling.
Parameterized input distributions: Ablation study. We report in Table 6 an ablation study of the parameter 5 E [o, 1] introduced on the input graph distributions, first suggested by (Xu al. 2019a). In most scenario and every OT based methods, a parameter =j0, 1[ leads to best AMI performances (except for the dataset Village), while the common assumption of uniform distribution remains competitive. The use of raw normalized degree distributions consequently reduces partitioning performances of all methods. Hence these results first indicated that further research on the input distributions could be beneficial. They also suggest that the commonly used uniform input distributions provide a good compromise in terms of performances while being parameter-free.
Additional clustering metric. In order com- plete our partitioning benchmark on real datasets, report in the Adjusted Rand Index (ART). The comparison between ARI and AMI has been thor- oughly investigated in (Romano al. 2016) and led to the following conclusion: ARI should be used when the reference clustering has large equal sized clusters; AMI should be used when the reference clustering is unbalanced and there exist small clus- ters. Our method srGW always outperforms the GW based approaches for a given type of input structure representations (adjacency vs heat kernels) and on this application the entropic regularization seems to improve the performance. Note that this metric also leads to slight variations of rankings, which seem to occur more often for methods explicitly based on modularity maximization. We want stress that for this metric our general purpose divergence STGW outperforms methods that have been specifically designed for nodes clustering tasks on 4 out of 6 datasets (instead of 3 using the AMI).
Table 7: Partitioning performances real datasets measured by Adjusted Rand Index (ARI) corresponding to best configurations reported in Table T We see in bold (resp. italic) the first (resp. second) best method. NA: non applicable.
Wisipedha
EU email
Amazzn
Village
asym
sym
asym
sym
19m
sym
art (ours)
33.36
33.56
31.9
30.05
67.01
scSpecGW
32.85
58.91
32.76
31.28
51,94
80.16
36.27
35.91
srspestWW
57.24
38.22
30.74
74.71
GWL
5:70
13.35
19.35
25.81
25.96
48.35
SpertPW1.
25.23
30.94
26
33
30.17
46.66
67.7
Fantireedy
NA
35.61
NA
17
45.30
93.97
Lauvain
NA
52.16
NA
32.79
42.64
93.97
InfoMaa
93.97
23

---

2000 2500 3000 Published as a conference paper at ICLR 2022
Table 9: Clustering and Completion benchmark: Datasets descriptions
datnsets
Teatures
#graphs
#olasses
mean #nndes
min #hodles
max #nodes
median #hodes
mean connectivity rate
IMDB-B
None
1000
19.77
12
136
17
35.53
IMDB-M
None
1500
3
13.00
89
10
86.44
MUTAG
[0.2]
14.79
PTR.MR
00...
344
2
14.29
04
13
25.7
BZR
R
405
35.75
13
57
35
6.70
COX2
R
41.23
32
41
PROTEIN
12
1113
2
29.06
620
26
23.58
ENZYMES
12.8
600
32.63
126
32
17.14
srGW runtimes: CPU vs GPU for large graphs. Par- titioning experiments with our methods were run on a GPU Tesla K80 it brought considerable speed up in
runtimes per iter (ms)
cpu
50
gpu
terms of computation time compared to using CPUs as large graphs had be processed. To illustrate this mat- ter, we generated 10 graphs following Stochastic Block Models with 10 clusters, a varying number of nodes in {100, 200, ..... 2900, 3000) and the same connectivity ma- trix. We report Table the averaged runtimes of one CG iteration depending small graphs with a few hundreds nodes, performances on CPUs single GPU are comparable. However, op- erating on GPU becomes very beneficial once graphs of few thousand of nodes processed.
30
20
the size of the input graphs. For
500
1000
1500
number of nodes
Figure 4: Runtimes of srGW's CG algo- rithm over increasing graph sizes.
Runtimes comparison real datasets. We report in Table g the runtimes CPUs for the partitioning benchmark on real datasets. For the sake of comparison, we ran the srGW partitioning experiments using CPUs instead of GPU. We can observe that GW partitioning of raw adjacency matrices (GWL) is the most competitive in terms of computation time (while being the last in terms of clustering performances), on par with InfoMap. Our srGW partitioning methods lack behind the GW based ones in terms of speed. Note that we remain in the same order of complexity. We want to stress that as illustrated in the previous paragraph, the use of CPUs for srGW multiplied by 10 20 times the computation times observed on a GPU. First the linear OT problems involved in each CG iteration of GW based methods are solved thanks to C solver (POT's implementation (Flamary et al. 2021)), whereas our srGW CG solver is fully imple- mented in Python. This can compensate the computa- tional benefits of srGW solver regarding GW solver (see details in section 3.2 of the main paper). So the computation time became mostly affected by the number of computed gradients. We observed in these experiments that for the same precision level, srGW needed considerably more iterations converge than GW. Let us recall that our srGW partitioning method consists matching an observed graph to the identity matrix C I, whereas GW based partitioning methods use target structure C diag(h) as h is fixed beforehand. Our lack of heterogeneity in the chosen target structure could be the reason of these slow convergence patterns. hence advocates for further studies regarding srGW based graph partitioning using more informative structures.
Table 8: Runtimes (seconds) on real datasets measured on CPU for all partitioning methods and corresponding best configurations.
Wikipolia
Amszznn
Village
4.18
4.22
4.31
scSpectiW
sGW.
2,81
2.53
xSpecGWW
2.35
196
2.15
2.00
2.16
2.58
GWL
0.17
0.17
0.13
6.12
0.13
0.16
SpeetiWL
0.77
1225
1.35
0.77
1.01
0.88
FasiCreedy
0.56
NA
2311
0.37
1.26
Lauvain
IntoMap
0.12
0.34
7.5.2 DICTIONARY LEARNING: CLUSTERING EXPERIMENTS
We report in table the statistics of the datasets used for our benchmark on clustering of many graphs.
Detailed settings for the clustering benchmark. We detail now the experimental setting used in the clustering benchmark derived from the benchmark conducted by Viincent-Cuus et al. (202T). For datasets with attributes involving FGW, validated 15 values of the trade-off parameter
24

---

Published as a conference paper at ICLR 2022
Table 10: Clustering performances on real datasets measured by Adjusted Rand Index(ARI. In bold (resp. italic) we highlight the first (resp. second) best method.
NO ATTIIBTT
DISCRETE ATTRIBUTES
REAL ATTRIBUTES
MODELS
IMDB-B
IMDB-M
MUTAG
PIC-MR
BZR
COX2
ENZYMES
PROTEIN
SGGW (ours)
3,14(0.99)
2.2610.08)
41.12(0.33)
16
6.24(1.49
2.98(1.26)
16.670019) 3.74(0.22)
sGW,
5.03(0.90)
3.09/..11)
43.27(1.20)
3.28(0.76)
16.50(2.06)
7.78(1.46)
1.)
(8.52(0.28)
srGW
3.51(1.10)
2,18(0.05)
45.12(1.65)
4.6000.91)
15.44(2.46)
5.71(0.93)
3.36(0.39)
16.81(0.17)
srGW
4.56(1.62)
2.71(0.24)
48.77(1.47)
4.97(0.83)
16.3812.15)
6.15(1.24)
3.98(0.62)
18.03(0.32)
GDL
2.670.522)
1.2610.13)
39.62(.499
4.72
4,43(142)
3.12(1.37)
3.39(0.31)
27.08(0.21)
GDI
3,44(1.09)
1.1710.19)
40.75(0.23)
3.59/0.71)
14.83 (8))
6, 6.27)
3.57(0.44)
FR. (8.25)))37))
GWF-r
2,09(0.61)
2.03(0.15)
37.09(1.13)
2.92(0.92)
2.89(2.66)
5.18(1.17)
17.34(0.14) 4.27(0.31)
GWI-I
0.85(0.57)
1.74(0.13)
18.14(3.09)
1.54(1.24)
2.78(2.41)
4.03((0.9)
3.69(0.28)
15.89(0.20)
GW.k
0.66(0.07)
1,23(0004)
15.09(2.48)
0.66(0.43)
4.56(0.83)
4.19(0.58)
2.34(0.96)
0.43(0.06)
Table 11: Clustering performances on real datasets measured by Adjusted Mutual Information(AM)) In bold (resp. italic) we highlight the first (resp. second) best method.
ATRIAUTE
DISCRETE
ATTRIBUTES
REAL ATTRIBUTES
MODELS
IMD8-8
IMDB-M
MUTAG
PTC-MR
BZR
COX2
ENZYMES
PROTEIN
SGGW (ours)
3.31(0.25)
2.63(0.33)
32.97(0.57)
3,21(0.23)
8.20(0.75)
2.64(0.40)
6.99(0.18)
12.69(0.32)
sGW,
4.65(0.33)
2.95(0.24)
33,82(1.58)
5.47(0.55)
()6()
3.08(0.61)
7,48(0224)
13.75(0.
SWGW,
3.58(0.25)
2.57)0.26)
35.01(0.96)
2.53(0.56)
10.28(1.03)
3.0100.78)
7.71(0.29)
12.31(0.35)
stG c+v
4.2010.77)
2.4910.61)
35.13(2.10)
2.8000.64)
10.0911.79)
3.76(0.63)
8.7(0..3)
14.11(0.30)
GDL
2.78(0.20)
3.57
32.25(0.95)
3.81(0.46)
8.14(0.84)
2.02(0.89)
6.86(0.32)
12.06(0.31)
GDL
3,42(0.41)
2.52:0.27)
32.73(0.98)
4.93/0.49)
8.76(1.25)
2.56(0.95)
7.39(0.40)
13.7710.49)
GWI-1
2.11(0.34)
2.41(0.46)
32.94(1.96)
2.39(0.79)
(.65(1.8)
3.28/0.71)
8.31(0.29)
12. 12.82().28)
GWF
1,05(0.5))
(.8510.28)
15.03(.771)
1.27(0.96)
3.8911.62)
(.53(0.58)
7.56(0.21)
11 11.03(0.33)
GW-k
0.68(0.08)
1.3910.19)
9 .044
0.80C0. 18)
6.91(0.48)
(.51(0.17)
4.9 4.99().63)
3.94(0.09)
via a logspace search in (0, and symmetrically (0.5, 1). For DL based approaches, first step consists into learning the atoms. srGW dictionary sizes are tested in M E {10, 30, 40, 50), the atom is initialized by randomly sampling its entries from (0.55, 0.01) and made symmetric. The extension of srGW to attributed graphs, namely srFGW, is referred as srGW for conciseness in 2 of the main paper. One efficient way to initialize atoms features for minimizing our resulting reconstruction reconstruction errors is to use a Kmeans algorithm seeking for M clusters on the nodes features observed in the dataset. For GDL and GWF, a variable number of $ = ,kk atoms is validated, where denotes the number of classes and B E 6,8. The size of the atoms M is set to the median of observed graph sizes within the dataset for GDL and GWF-f. These methods initialize their atoms by sampling observed graphs within the dataset, with adequate sizes for GDL and GWF-f, while sizes of GWF-r are just determined by this random sampling procedure independently of the number of nodes distribution. For For srGW, g, SrGW c+g and GDL,, the coefficient of our respective sparsity promoting regularizers validated within {0.001, 0.01, 0.1, 1.0.. Then for srGW srGW etg. GWF-f and GWF-r, the entropic regularization coefficient is validated also within (0.001, 0.1, 1.0].
Finally, we considered the same settings for the stochastic algorithm hyperparameters across all methods: learning rates are validated within {0.01, 0.001} while the batch size is validated within {16, 32}; We learn all models fixing a maximum number of epochs of 100 (over convergence requirements) and implemented an (umsupervised) early-stopping strategy which consists in computing the respective unmixings every 5 epochs and stop the learning process if the cumulated reconstruction error (Err)) does not improve anymore over 2 consecutive evaluations (i.e. Err,- < Err,+1 and Err, < ETT(+2). For the sake of consistency, we report in Table 7 the Averaged Mutual Information (AMI) performances on this benchmark, as we reported the RI in the main paper to be consistent with our main competitors.
Visualizations of srGW embeddings. We provide in Figure some examples of graphs embed- dings from the dataset IMDB-B learned srGW dictionary C of 10 nodes. We assigned different colors to each nodes of the graph atom (forth column) in order to visualize the correspondences recovered by the OT plan T* resulting from the projection of the respective sample (C, h) onto C in the srGW sense (third column). As the atom has continuous values we set the edges intensity of grey proportionally to the entries of C. By coloring nodes of the observed graphs based on the OT to its respective embedding (second column) we clearly observe that key subgraphs information, such as clusters and hubs are captured within the embedding.
25

---

Published as a conference paper at ICLR 2022
Data sample C.
Data sample (colored by T)
Projected ć. h
Dictionary C
Data sample C, h;
Data sample (colored by T)
Projected C. h
Dictionary C
Data sample C, h,
Data sample (colored by T)
Projected Ć, h
Dictionary č
Data sample C,
Data sample (colared by T)
Projected h
Dictionary C
Figure 5: Illustaatoon the embedding of different graphs from the IMDB dataset on the estimated dictionary C. Each row corresponds to one observed graph and we show its graph (left), graph with nodes colored corresponding to the OT plan (center left), the projected graph on the dictionary with optimal weight h and the full dictionary with uniform mass (right).
IMDB unmixings on srGW dic lictinnaries
Impact of the graph atom size. Morcover if we increase the size the dictionary, our embeddings refined and can bring complementary structural information at a higher resolution egg. finding sub- structures or variable connectivity between nodes in the same cluster. We illustrate these resolution patterns in Table 66] for embeddings learned on the IMDB-B dataset. We represent the embedded graph size distributions depending on the sizes of the graph atom learned thanks to sr srGW and its sparse variant srGW, g. For any graph atom size, the mean each embedded graph size distribution represented with a white dot is below the atom size, hence embed- dings are sparse and subparts of the atom indeed selected. Moreover, promoting sparsity of the embed- dings (srGW, 3) lead more concentrated embedded
method
srGW
s/GW,
umbedded graph
15
10
20 30 40
50
graph
Figure Evolution of the embedded graph sizes over the graph atom size validated in {10, 20, 30, 40, 50) for dictionaries learned with srGW and srGW, (with À 0.01).
26

---

Published as a conference paper at ICLR 2022
graph size distributions with lower averaged sizes than its unregularized counterpart (srGW), as expected. Finally, these distributions seem to reach a stable configuration when the graph atom size is large enough. This argues in favor of the existence of a (rather small) threshold on the atom size where the heterogeneity of all the graphs contained in the dataset is well summarized in the dictionaries.
7.5.3 DICTIONARY LEARNING: COMPLETION EXPERIMENTS
Experiment details graphs completion. For these completion experiments the exact same scheme, than in our clustering benchmark, is applied for learning srGW and GDL dictionaries on formed datasets Dtrain- On interesting specificity used on dataset IMDB-B was for the initialization. Indeed instead of initializing the structure atom iid from (0.5, 0.01), we initialized the entries of Cimp denoting connections only between the new imputed nodes randomly. Then initialized entries representating connections of these nodes to the ones of Cohe seeing the degree (scaled by maximum observed degrees) of each observed node as initial probability for new node to be connected to this observed node. Then for each entries (i,j) where z; belongs to Cobs and I, to
Cimp. Cij is initialized N max.ca. deg(a:)' 0.01). This initialization led to better performances for both model so might be first good practice to tackle completion of clustered graph using OT. For MUTAG we sticked with the initialization used for our and initialized imputed features randomly in the range of locally observed features.
deg(#:)
Additional experiments on graphs completion. We complete the experiments on com- pletion tasks of datasets IMDB-B and MUTAG reported in the subsection 5.3 of the main paper. Let us recall that for these experiments we fixed a percentage of im- puted nodes (10 % and 20%) and looked the evolution of completion performances over the proportion of train/test datasets. Here instead, we fix the proportion of the test dataset 10% and make percentage of imputed nodes vary in {10, 15, 20, 25, 30). A similar benchmark procedure than for experiments of the main paper is conducted. These graph completion results are reported in Figure for IMDB-B dataset and in Figure MUTAG dataset. Our srGW dictionary learn- ing and its regularized variants outperform GDL and GDL, consistently when the percentage of imputed nodes is not too high (< 20%), whereas this trend is reversed for high percentage of im- puted nodes. Indeed, srGW dictionaries cap- ture subgraph patterns of variable resolutions from the input graphs, the scarcity of prior in- formation in an observed graph leads to a too
IMDB-B test dataset proportion 10.0%
srGW
97
srGW,
completion accuracy (%)
96
srGW,
srGW,
GDL
94
GDLA
93
92
high number of valid possibilities to complete it. Whereas GDL dictionaries based on GW
lead to more steady performances they keep their focus on global stteructures. Interestingly, the sparsity promoting regularization can clearly compensate this kind of overfitting over sub- graphs for higher levels of imputed nodes and systematically leads to better completion per- formances (high accuracy, low Means Square Emror). Moreover, the entropic regularization of srGW (srGW, and srGWett) can be favorably used to compensate this overfitting pattern for high percentages of imputed nodes (> 20%) and also pairs well with the sparse regularization (srGW (Wetg).
30
imputed nodes (%)
Figure 7: Completion performances for IMDB-B dataset, measured by means of accuracy for struc- tures averaged over all imputed graphs.
27

---

Published as a conference paper at ICLR 2022
MUTAG test dataset proportion 10.0%
MUTAG test dataset proportion 10.0%
95.5
0.035
SIFGW
SIFGW
srFGW,
srFGW,
95.0
SIFGW ent
0.030
SIFGW ent
completion accuracy
srFGW,
ent
sFFGW, ent
GDL
completion MSE
0.025
GDL
GDL
GDL,
94.0
93.5
0.015
93.0
92.5
0.005
10
15
20
25
30
10
15
20
25
30
imputed nodes (%)
imputed nodes (%)
Figure Completion performances for MUTAG dataset, measured by means of accuracy for structures and Mean Squared Error for node features, respectively averaged over all imputed graphs.
28


Reviews:
[{"review_id": "fgTrKdbtjHo", "reviewer": "Reviewer_ioNk", "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": "**Strengths:**\n\n- The simple formulation of the srGW problem means that it fits nicely with prior GW literature, and can be implemented in existing codebases with minimal refactoring.\n\n- The authors provide formulations of the standard srGW as well as entropy regularized and sparsity promoting variants, following the relevant literature. These formulations are not superfluous, as the authors demonstrate their use cases in the experiments (entropy regularization benefits graph partitioning, sparsity-promotion benefits clustering of graph datasets). I particularly liked Figure 2, as it helped me understand the strong performance of srGW in graph partitioning.\n\n- srGW being a (possibly asymmetric) divergence is really quite interesting. Following up on Sturm's work, it seems then that the space of graphs equipped with srGW is a quasimetric space, which in turn leads to various questions about its metric structure. These theoretical questions are out of the scope of the current paper, but I would be curious to know if the authors had some potential use cases of this asymmetry in mind. E.g. with KL divergence, one often interprets KL(P||Q) to be the information loss in assuming a model Q of the data P. Can there be a similar interpretation of srGW in light of the single-atom dictionary learning method in Section 4?\n\n\n**Neutral about:**\n\n- On the note of the single-atom dictionary learning, it seems that this is a renaming of the Fréchet mean//GW barycenter problem. To their credit, the authors do not hide this fact, although it could be argued that casting this problem with a new name is a bit unnecessary. However, Sections 4.2 (graph completion theory) and 5.3 (empirical graph completion) do a good job of alleviating my concerns here, as they showcase a novel application of this technique.\n\n**Weaknesses/points to clarify:**\n\n- for Equation (3), could the authors clarify if there is any relation to the \"Flexible Y-Marginals\" formulation of ref. [A] below?\n\n- In Section 3.1, I think it would help the reader if the authors clearly delineated between the metric measure space case and the graph case. Mémoli and Sturm proved their results for the mm space setting, and the theoretical results for the graph setting came a few years later. Alternatively, the authors could state up front that all their graphs are connected, which would mean that graph distances would always be well-defined.  \n\n- In Section 3.2, I think the explanation of the CG method could be improved. $X$ in $\\langle X,G\\rangle$ seems to appear without introduction - it would be better to explain how we would like to project G onto the transport polytope, and that this corresponds to an OT problem with solution given by $X^*$. Also, I see that in the srGW setting, this problem becomes easier because one need not solve a full linear program, but the explanation here could be improved. Exactly what are the independent subproblems? Also, in \"finding the minimum on the lines of G\", I would replace \"lines\" by \"rows\" (as in Algo 1).\n\n- Section 4.2, please add a few more lines about the use of the envelope theorem.\n\nRefs:\n\n[A] Schmitzer, Schnorr - Modelling Convex Shape Priors and Matching Based on the Gromov-Wasserstein Distance. JMIV 2013.", "summary_of_the_paper": "This paper proposes a semi-relaxed Gromov-Wasserstein (GW) dissimilarity for learning tasks on graphs. Here the \"semi-relaxed\" refers to removing one of the marginal constraints, with the practical effect that during GW graph matching, one is able to ignore some of the nodes in the source or target and thus obtain matchings that better respect the structure of the problem. What is quite interesting is that this simple relaxation immediately yields benefits in fundamental tasks such as graph partitioning, and the authors validate this observation with extensive experiments on graph datasets. The empirical results are strong, and show state-of-the-art performance compared to several recent baselines.", "summary_of_the_review": "The authors take the well-studied GW problem--which involves optimization over probability matrices satisfying row and column constraints--and consider a simple relaxation wherein the column constraints are removed. They also propose variations of the underlying optimization with respect to various regularizers. The usefulness of the core method and its variations are demonstrated on benchmark datasets and compared to relevant baselines, where the authors obtain SOTA performance. Additionally, the authors propose a novel application to graph completion and provide experiments in this regard. While it could be argued that the novelty scores should be between 2 and 3, I would lean toward 3 because I believe the authors have done their due diligence for each of their claims in the paper. Overall, I think this is a good paper, and I would favor acceptance.  ", "strength_and_weaknesses": "", "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": "ZQCQUAUKB4", "reviewer": "Reviewer_4kuX", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The idea of relaxing the histogram of one distribution in GW distance looks intriguing. Relaxed GW divergence leads to less constrained optimization problems which help to improve the computational challenges of the original GW distance. The existing problems of learning with graphs such as graph clustering (partitioning), graph dictionary learning can be interestingly reformulated using the newly proposed divergence. However, the contribution of the paper can be improved in several aspects:\n - Is the proposed 'divergence' truly a divergence, i.e. srG(p,q)=0 iff p=q?\n\n - What is the difference between the GW barycenter with one measure and the srGW? As if we consider the GW barycenter of measure p with fixed supports, we will solve the same problem with computing srGW. One is to estimate the minimizer while the other compute the distance.\n\n - On page 4 (third paragraph), the paper states that \"A first interesting property of srGW is that since h is optimized ..., its optimal value h* can be sparse\". What is the insight for the statement that its optimal value h* can be sparse? Is this property is proved theoretically or experimentally besides the experiments with the sparse regularization? If it is not proved yet, what is the intuition that leads to the property?\n\n - Will algorithm 2 for graph dictionary learning converge to a local solution?\n\n -Regarding computational complexity in Table 3, what are the settings (e.g. GPU or CPU implementations) for proposed and baseline methods? The details should be clarified to make sure that comparable settings are used.\n \n", "summary_of_the_paper": "The paper proposed a relaxed version of the Gromov-Wasserstein (GW) distance between two probability distributions on (graph) structured data. The main idea of new divergence is to relax the target distribution via an optimization setting. Based on the proposed divergence, the paper also introduced new formulations for existing problems of learning with graphs such as graph clustering (partitioning), graph dictionary learning, clustering of the graph, and graph completion. The experimental results for those applications on graph data have shown the efficiency of the proposed divergence.", "summary_of_the_review": "In short, the proposed GW-based divergence looks interesting in terms of computational and applicable aspects. However, srGW may be considered as a special case of GW barycenter (for one measure) except that the authors provide further insights.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XDxFHLRrWnt", "reviewer": "Reviewer_jEHW", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper is well written in general, although there are some typos, missing words, or inconsistencies in the citation format, especially from Section 4 onwards. \nAlso, the descriptions of the objectives in each part of Section 4 for instance, or the datasets and specific tasks in Section 5, are not complete.\n\nI liked the proposed formulation, and especially the equivalent problem (3).\n\nRegarding the Dictionary Learning section in page 6.\n - How do you select m? (or for a particular application)\n - The resulting matrix $\\bar{C}$ is not binary, right? \n - in particular for the graph completion, but also valid in general: when learning the structure $\\bar{C}$, you are assuming that the graphs follow a certain distribution, right? Even if this is more general (and not particular for the paper), this should be clearly stated.\n\nRegarding the results in Table 1. It seems like for the symmetric datasets, the specialized graph partitioning methods perform much better. Are there similar methods that take into account the directive graphs as well?\n\nI think that the paper would have been much better if the space used for some applications in Section 5, was used to better explain the rest of the paper, or show some other images/interpretations.\n\nMinor comments:\n - in Proposition 1, there is a $srGW_2(h,C,\\bar{C})$, which has the arguments in a different order than the others.\n - In the third paragraph of page 3, please add the dimension of matrix $\\bar{D}$ (m by m), because at first I thought that it was a block diagonal, similar to an SBM probability matrix let's say. It's clear afterward from Fig 2 in any case.\nSummary of the Review\n - please check the consistency in the references. Michael Bronstein is written in two different ways for instance.\n", "summary_of_the_paper": "In this paper the authors propose a modification of the Gromov-Wasserstein problem for matching given matrices $C$ and $\\bar{C}$ with its respective histograms $h$ and $\\bar{h}$, relaxing the restriction on $\\bar{h}$. The problem is then given in an equivalent formulation, which is solved via Conditional Gradient. \nThe authors propose applications with graphs, such as graph partitioning, clustering, and completion via Graph Dictionary Learning.\n", "summary_of_the_review": "The paper presents a good idea, in the form of a relaxation of GW, and its equivalent formulation, and promising results in real datasets. The presentation of the paper can be improved.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QXBtLCmCOcE", "reviewer": "Reviewer_vbhF", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The GW distance between two graphs is based on two quantities: the distance of the inner structure of graph and the weight of graph. This work proposes to relax the weight on one graph and keep the matrix  distance of that graph, and then try to find the GW-distance between two graphs when the constraint on weight of one side disappears. In fact, it try to match the structure of two graphs by ignoring the weights of one graph. \n\nThe first question, that is easily to have, is that what is the role and the effect of the weight of the first graph in the srGW? Does it affect the final result or not? In all three proposed applications, at the end, they are only concerned about  the inner structure of a graph and do not bother the weight? \n\nAnother concern is that by relaxing the condition on the weight, we are not very sure what we obtain when minimizing the srGW function. It could be a hybrid structure of two graphs or something else. In the  third picture of Figure 1, in my opinion,  the orange points of graph on  the left should be matched to some more dimmed points which are close to the orange points of the graph on the right, rather than a few orange points. The same could be said for the green points. It is quite opposite in the middle illustration of Figure 1, when the graph on the left tries to match its clusters to  clusters of the right.  Do the authors have an explanation about that rather than the asymmetric property.  In the paper, they stated that the interesting property of weight is the sparsity, but they should have a better theoretical result than Proposition 1, since it only deals with the case of zero  srGW. \n\nThe author(s) apply the srGW to do graph partitioning and clustering. The reviewer finds that two tasks are similar. It is not clear for the reviewer how the author(s) choose the number of clusters, which is often important step in clustering method. For example, in the synthetic data, when we increase the value of $q$, we could obtain very different set of clusters, rather than small $q=3$ or $4$. In both graph partitioning and graph clustering, they use different measures to compare the performances between methods. Could we have both Adjusted Rand Index and AMI reported for both graph clustering and partitioning?\n\nIn the graph partition, could the authors compare the running time between methods? \nThe reviewer believes that the complexity for srGW is of order $m^2n + n^2m$ and that of  Spectral GWL is only  $n^2\\ln(n)$. Could author explain the better performance of the InforMap, FastGreedy and Louvain method over their method in the Amazon and Village datasets? \n\nIn the graph completion, Figure 3, the reviewer did not find  the performance of all methods on MUTAG with $20\\%$ imputed nodes?", "summary_of_the_paper": " The paper proposes to apply a version of Gromov-Wasserstein divergence to graphs. In particular, they relax the weight constraint of the second graph  and try to find a minimizer of the Gromov-Wasserstein distance. They named it Semi-relaxed Gromov Wasserstein distance (srGW) and apply it to solve some problems in graphs, namely, graph partition, graph clustering and graph completion. The experiments were carried out on synthetic data and real dataset such as: Wikipedia hyper link network, Amazon product network etc. The results show comparable and better performance over other methods such as  GW and spectral GW.", "summary_of_the_review": "Positive: I find that the idea of applying the srGW divergence to the graph clustering is interesting.\n\nNegative: There is a little understanding of the method (srGW),  other parts of the paper are entirely based on utilising  other existing works. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper takes advantage of a well known fact in the OT literature: that relaxing either of the marginals of OT problems results in nearest neighbor assignments (as e.g. in k-means) or soft-assignments when using an entropic regularizer. The authors take advantage of this simple property (used e.g. in the first iterations of the word mover's distance) to speed up the inner iterations of the GW problem. As a result, theirs is a very simplified divergence that drops an important piece of info (the weights of the second measure) but which is illustrated on a few tasks dealing with graphs. Overall the paper has been appreciated by most reviewers, some criticizing the paper for its incremental nature but being overall pleased with the experimental validation.
Decision: Accept (Poster)