Robust Graph Dictionary Learning
Authors: Weijie Liu
Jiahao Xie
Chao Zhang
Makoto Yamada
Nenggan Zheng
Hui Qian
Venue: ICLR 2023 poster (2023)
Keywords: Graph Learning
Optimal Transport

Abstract: Traditional Dictionary Learning (DL) aims to approximate data vectors as sparse linear combinations of basis elements (atoms) and is widely used in machine learning, computer vision, and signal processing. To extend DL to graphs, Vincent-Cuaz et al. 2021 propose a method, called GDL, which describes the topology of each graph with a pairwise relation matrix (PRM) and compares PRMs via the Gromov-Wasserstein Discrepancy (GWD). However, the lack of robustness often excludes GDL from a variety of real-world applications since GWD is sensitive to the structural noise in graphs. This paper proposes an improved graph dictionary learning algorithm based on a robust Gromov-Wasserstein discrepancy (RGWD) which has theoretically sound properties and an efficient numerical scheme. Based on such a discrepancy, our dictionary learning algorithm can learn atoms from noisy graph data. Experimental results demonstrate that our algorithm achieves good performance on both simulated and real-world datasets.

Published as a conference paper at ICLR 2023
ROBUST GRAPH DICTIONARY LEARNING
Weijie Liu,12 1. Jiahao Xie,² Chao Zhang, 2.8.9 Makoto Yamada, 3.45 Nenggan Zheng, Qiushi Academy for Advanced Studies, Zhejiang University
3.4.5
1.2668 Hui Qian 2.7,8
2 College of Computer Science and Technology, Zhejiang University
3 Okinawa Institute of Science and Technology
4 Kyoto University
5 RIKEN AIP
Zhejiang Lab
7 State Key Lab of CAD&CG, Zhejiang University
8 Alibaba-Zhes Bababa-Zhejiang University Joint Research Institute of Frontier Technologies
9 Advanced Technology Institute, Zhejiang University
(we Inesttnhunter, xiejh, zezju, zng, qianhui 2
j ju. edu. cn, makoto. yamada@oist.
ABSTRACT
Traditional Dictionary Learning (DL) aims to approximate data vectors sparse linear combinations of basis elements (atoms) and widely used in machine learning, computer vision, and signal processing. To extend DL to graphs, Vincent-Cuaz et al. 2021 proposed a method, called GDL, which describes the topology of each graph with pairwise relation matrix (PRM) and compares PRMs via the Gromov- Wasserstsnnn Discrepancy (GWD). However, the lack of ro- bustness often excludes GDL from variety of real-world applications since GWD is sensitive to the structural noise in graphs. This paper proposes an improved graph dictionary learning algorithm based robust Gromov-Wassertten dis- crepancy (RGWD) which has theoretically sound properties and an efficient nu- merical scheme. Based on such a discrepancy, our dictionary learning algorithm can learn atoms from noisy graph data. Experimental results demonstrate that our algorithm achieves good performance on both simulated and real-world datasets.
INTRODUCTION
Dictionary learning (DL) seeks to learn a set of basis elements (atoms) from data and approximates data samples by sparse linear combinations of these basis elements (Mallat 1999; Mairal et al.
2009 Tošié and Frossard 2011). which has numerous machine learning applications including di-
mensionality reduction (Feng al. 2013 Wei et al. 2018). classification (Raina et al. 2007 Mairal
ct al. 2008), and clustering (Ramirez et al. 2010 Sprechmann and Sapiro 2010). to name few.
Although DL has received significant attention, it mostly focuses vectorized data of the same dimension and is not amenable to graph data (Xul 2020 Vincent-Cuaz et al. 2021 2022). Many exciting machine learning tasks use graphs to capture complex structures (Backstrom and Leskoved 2011 Sadreazami et al. 2017 Naderializadeh et al. 2020 Jin et al. 2017 Agrawal et al.) 2018)
DL for graphs is more challenging due the lack effective means to compare graphs. Specifi- cally, evaluating the similarity between one observed graph and its approximation is difficult, since they are often with different numbers of nodes and the node correspondence across graphs is often
unknown (Xu 2020 Vincent-Cuaz et al. 2021).
The seminal work of Vincent-Cuaz et al. (202T) proposed a DI. method for graphs based on the Gromov-Wassersten Discrepancy (GWD) that is variant of the Gromov-Wasserster dis- tance. Gromoy-Wasserstcnn distance compares probability distributions supported on different met- ric spaces using pairwise distances (Mémoli 2011). By expressing each graph as probability measure and capturing the graph topology with a pairwise relation matrix (PRM), comparing graphs be naturally formulated as computing the GWD, since both the node correspondence and the discrepancy of the compared graphs are calculated (Peyré et al. 2016 Xu et al.] 2019b). However,
"Corresponding author.

---

Published as a conference paper at ICLR 2023
observed graphs often contain structural noise including spurious missing edges, which leads to the differences between the obtained PRMs and the true ones (Donnat et al. 2018 Xu et al. (019b).
Since GWD lacks robustness (Séjouréé et al. 2021 Vincent-Cuaz al. 2022 Tran et al. 2022
the inaccuracies PRMs may severely affect GWD and the effectiveness of DL in real-world ap- plications.
Contributions. To handle the inaccuracies of PRMs, this paper first proposes novel robust Wasseeseesse discrepancy (RGWD) which adopts a minimax formulation. We prove that the inner maximization problem has closed-form solution and derive efficient numerical scheme to approximate RGWD. Under suitable assumptions, such a numerical scheme guaranteed to find d-stationary solution within O( (22) iterations. We further prove that RGWD is lower bounded and the lower bound is achieved if and only if two graphs are isomorphic. Therefore, RGWD can be employed compare graphs. RGWD also satisfies the triangle inequality which is of its own interest and allows numerous potential applications. A robust graph dictionary learning (RGDL) algorithm is thereby developed learn atoms from noisy graph data, which assesses the quality of approximated graphs via RGWD. Numerical experiments on both synthetic and real-world datasets demonstrate that RGDI, achieves good performance.
The rest of the paper is organized as follows. In Sec. 2 comprehensive review of the background given. Sec. presents RGWD and the numerical approximation scheme for RGWD. RGDL is delineated in Sec. Empirical results are demonstrated in Sec. 5 We finally discuss related work
Sec. 6
2
PRELIMINARY
2.1 OPTIMAL TRANSPORT
We first present the notation used throughout this paper and then review the definition of the distance that originates from the optimal transport theory (Villani 2008 Peyre and Cuturi 2018).
Notation. We use bold lowercase symbols (e.g- x), bold uppercase letters (e.g. A), uppercase calligraphic fonts (e.g. X), and Greek letters (e.g. a) to denote vectors, matrices, spaces (sets), and measures, respectively. 1d E Rdd is a d-dimensional all-ones vector. A is the probability simplex with d bins, namely the set of probability vectors A = (a E R Ei= a; 1]. Ali, and [ j] are the Th row and the jth column of matrix A respectively. Given a matrix A, ||A]| and ||A denote its Frobenius norm and element-wise lo -nom (i.e., || = max,,, (Ari). respectively. The cardinality of set A is denoted by IA). The bracketed notation [n] is the shorthand for integer sets {1, 2, .,,,,....77) n2). A discrete measure a is denoted by a = Σm" a,,x.. where 8x is the Dirac measure at position i.e., a unit of mass infinitely concentrated at
Soommo-Wasserstein distance. Optimal Transport addresses the problem of transporting one probability measure towards another probability measure with the minimum cost (Villani 2008 Peyre and Cuturi, 2018). The induced cost defines a distance between the two probability measures. Cromov-Wasserster (GW) distance extends classic optimal transport to compare probability mea- sures supported on different spaces (Mémoli) 201 Let (X,dx) and (V,dy) be two metric spaces.
Given two probability measures a = =>in Piox; and B >'= gr where X1, X2, Xm E X and y1, 32,..... Yn E V, the r-GW distance between and 3 defined as
GW, = min TEIl(..))
Σ i,5= f11'=1
Σ
where the feasible domain of the transport plan T [Tw]] is given by the set
T q) = (T E R T1" p. TT T = =q}
and Dwas calculates the difference between pairwise distances, ie., Diis = [dx(xxxx,)
dy dy (yv,,y)) Y-
2

---

Published as a conference paper at ICLR 2023
2.2 GRAPH REPRESENTATION AND COMPARISON
In this subsection, we formalize the idea of comparing graphs with GWD, which addresses the challenges that graphs are often with different numbers of nodes and the node correspondence unknown (Xu et al. 2019b Xu 2020 Vincent-Cuaa et al. (021).
Pairwise relation and graph representation. Given graph with n nodes, assigning each node an index E [[x]]] 9 can be expressed as a tuple (C, p), where C E R a matrix encoding the pairwise relations (c.g. adjacency, shortest-path, Laplacian, or heat kernel) and p A is probability vector modeling the relative importance of nodes within the graph (Peyré et al. 2016 Xu et
2019b Titouan al. 2019 Vincent- Sincent-Cuaz et al. 2022).
Discrepancy. GWD can be derived from the 2-GW distance by replacing the metries with pairwise relations (Xu et al. 2019b Vincent-Cuaz et al.) 2022). More specifically, given an observed source graph G and a target graph 9 that can be expressed as (C*, pp) and (C", p²) respectively, GWD is defined as
n Σ Σ 5
C2p) (T, $
GWD ((C ('),
min TTll(pp pp")
(Ci
where n²" and n' are the numbers of nodes g" and G' respectively. GWD computes both a soft assignment matrix between the nodes of the two graphs and notion of discrepancy between them. For conciseness, we abbreviate GWD ((Cr, p²), (C*, p')) to GWD(C", C*) in the sequel.
2.3 DICTIONARY LEARNING
Traditional DL approximates data vectors sparse linear combinations of basis elements (atoms)
(Mallat 1999
Mairal et al., 2009 Tošič and Frossard. 2011 Jiang et al. 2015). and is usually
formulated
||
min DEC,
X kJ
Σ
w
D[s ml
+ Al(w*),
where X E IRdxK the data matrix whose columns represent samples, the matrix |g contains M atoms to learn and is constrained to the following set
C D E dx [Vm E [[M]] [D[: mill2 S 1}.
W E M is the new representation of data whose th col-um w [wm]me[M] stores the embedding of the 1tth sample, and Al(w*)) promotes the sparsity of w Such formulation only applies to vectorized data.
Recently, Xu 2020 ically, given dataset K graphs which has PRMs {C* } such that C e IB" xx. the basis elements (C"") } [M] are learned by solving
propposs proposes approximate graphs via the highly non-linear GW barycenter. Specif-
K Σ GWD? (ct (C,.B(",
(Ct, wt (C IC"TMm)))))
min MEERI
where w E AM is referred to as the emhedding of the 1th graph gk, and the GW barycenter B(w* (Cm")m[[M) gives the approximation of Gk and is defined
B w (Cm) "me[mm)
argmin B
w GWD? CT)).
Therefore, a complex livel optimization problem is involved, which is computationally inefficient VVincentCuaz et al. 2021).

---

Published as a conference paper at ICLR 2023
DL for graphs. To overcome the above computational issues, Vincent-Cuaz al. 2021 proposed GDL which approximates each graph as a weighted sum of PRMs and is formulated as
K
Ms
min
GWD* (c+, Σ
Σ cTh mal1
w
+ ASZ(w"),
where each atom C is a n² matrix. In contrast to the lg loss in Eq. [1. GWD is used assess the quality the linear representation Σ w C. for & [K]. However, the observed graphs often contain noisy edges or miss some edges in real-world applications (Clauset et al. 2008 Xu al., 2019b Shi et al., 2019 Piccioli al. 2022), which leads to the inaccuracies of the PRMs that the deviation between C and the true PRM CK* Since GWD lacks robustness (Séjouréé
et al. 2021; Vincent- et al. 2022 Tran et al. 2022 the quality of the learned dictionary may
be severely affected.
ROBUST GROMOV-WaR WASSERSTEIN DISCREPANCY
To deal with the inaccuracies of PRMs, this section defines robust variant of GWD, referred to as RGWD. The properties of RGWD are rigorously analyzed. We then derive a theoretically guaran- teed numerical scheme for calculating RGWD approximately, Due to the limit of space, all proofs can be found in the appendix.
Definition 1 Given observed source graph G and target graph go that be expressed as (C*, p²) and (C", .p') respectively, RGWD is defined by the solution to the following problem
RGWD ((C5, p'), (p),,,))) Tell(pp .p) EEUL
min max ET,,E
where the objective S()) is given by
n²
((T,E,CTC))
Σ
Σ 6-=1"8ド==
(C
Cj3' Egyi ) TT
and the perturbation E the bounded set U E E
E and S c)-
RGWD requires the sought transport plan to have low transportation costs for all perturbation E in set Ue For succinctness, we omit C and C in f(T, E; C", C*) in the following.
3.1 PROPERTIES OF RGWD
The properties of RGWD are presented follows. Firstly, although RGWD involves non-convex non-concave minimax optimization problem, the inner maximization problem has a closed-form solution, which allows efficient numerical scheme for RGWD. Secondly, RGWD has lower bound that is achieved if and only if the expressions of compared graphs are identical up to per- mutation, which implies RGWD can be employed to evaluate the similarity between one observed graph and its approximation in DL. Thirdly, RGWD satisfies the triangle inequality, which allows numerous potential applications including clustering (Elkan 2003 [HajKacem et al.] 2019), metric learning (Pitis et al., 2019), and Bayesian learning (Moore) 2000 Xiao et al., 2019). Finally, arbi- trarily changing the node orders does not affect the value of RGWD. More formally, we state the properties in the following theorem.
Theorem Given an observed source graph G and a target graph G that can be expressed as (C p²) and (C', p') respectively, RGWD satisfies
1. for all T TT(pp" .²)., E(T) [F (T)) where
if E Tw - Cbp) 50,
Egy E; -c, otherwise.
solves the inner maximization problem
max f(T, EEU,
4

---

Published as a conference paper at ICLR 2023
2. RGWD is lower bounded, that is, RGWD ((C), (C,, 2e,
where the equality holds if and only if there exists bijective x² [ne] - [n'] such that p Ps for all i [n²]] and C3j ())) for all i,j [n']]
3. The triangle inequality holds for RGWD. ie..
RGWD ((C), ""C),,'),CC (C),, ,p'),
<RGWD ((C), ,p'), p²),e) + RGWD (CC",p") (C'.)))))
4. RGWD is invariant to the permutation of node orders, i.e., for all permutation matrices Q" and Q', RGWD (C")
RGWD ((Q (QT (") p')),))
As is implied by Theorem [ RGWD does not define a distance between metric-measure spaces. Firstly, the identity axiom is not satisfied. Secondly, the symmetry generally does not hold either, which we exemplify below.
Example (Asymmetry of RGWD) Consider the case Pd p'
0. C
01 C
[- Then RGWD ((Cs, ((C,,pt) p'), (C*, 1)), 11.5 with the solution given by T
0.25
and E" - - In contrast, RGWD ((C,p')) (C,. (C*.p").1) 10.5 with T 10.25
0.25
and
0.25
Ex = --
One has RGWD ((C p¹), (C', (C"'.''),)) RGWD ((Cr, p'), (C*, 1p),
Example showcases that RGWD is asymmetric even if n² n².
3.2 NUMERICAL SCHEME OF RGWD
We derive gradient based numerical scheme solve RGWD by exploiting the property that the inner maximization problem has closed-form solution, which is summarized in Algorithm [ In each iteration, E,, that solves the inner problem for current T, is calculated. Then, the transport plan is updated using the projected gradient descent.
Algorithm Projected Gradient Descent for RGWD
Input: Initialization To, step-size 17, number of iterations N.
2: Output: Estimated optimal transport plan T and its corresponding perturbation É.
3: for 7 7=0 0. 1......, N - do
4: Find E, that maximizes S(T,, E).
5: Update the transport plan via
(T.-NV/((T...,, Ex).
T Proin pa)
where the partial gradient takes the form
(T, =2 o T,),1" I" 21 1nn T, T=((C'+ ((C+EE,) E,) T(C'
(C' + (C++E))
(C" E.),
with @ denoting the element-wiss multiplication.
6: end for
7: Pick uniformly at random from {1,2....,7] T).
8: Set T k- T,.
9: Find E that maximizes f(T, E).
To present the convergence guarantee of Algorithm [ we introduce the notion of the Moreau en- velope. The stationarity of any function h(x) be quantified by the norm of the gradient of its Moreau envelope (x) ming h(x') + 2x | x The following theorem gives the conver- gence rate of Algorithm T and the proof deferred to the appendix.
5

---

Published as a conference paper at ICLR 2023
Theorem 2 Define o()) maxgeu, f(,, E). The output T of Algorithm 7 with step-size VN+I
satisfies
- 11 91/2((TT) min p') (TT +
E V (1)22
VVN +1
where 1 = 22 max 10m
+ 6n 6n 1nU1122 + e
e2.6n'nn 6n U1U2 + 2U2 + U2E and L = ||
22 max [ + U2 2(201 + U with max(n", n²), U1 = and U2 max p2212, max [T r]
When U1 and are of the order O(+)), both and L are of the order ((1) and Theorem 2 states that an d-stationary solution can be obtained within ( iterations. Note that we can multiply C C², and by the same number without affecting the resulted transport plan.
ROBUST GRAPH DICTIONARY LEARNING
The problem learning a robust dictionary for graph data is now formulated as follows. Given dataset of K graphs expressed by {(C*, pp) {=)] estimating the optimal dictionary is formalized by
RGWD2 (C A C. ())
min
A//w^113
(2)
(C Tmmaar-(ww JRELK]
m=1
where {CTM) Ime]M] and [w* ]REAA] are the dictionary and graph embeddings respectively, and p obtained by sorting and averaging {p* kKejK] following Xu et al. (2019a). To resolve (2),
propose a nested iterative optimization algorithm that is summarized in Algorithm 2 The mam idea
that the dictionary and embeddings updated alternatingly. We discuss some crucial details
below.
Algorithm 2 Robust Graph Dictionary Learning (RGDL)
Input: The dataset { (C*s ppp ]ε[K]] the initial dictionary (Č" Ime[M] the number of iterations
T. mini-batch size b.
2: Output: The learned dictionary (Cm) me{Md]
3: for t = 0, 1, ..... T 1 do
4: Sample a mini- batch graphs whose indices are denoted by B such that [ =
5: for B do
6: Initialize w
M 1 and T =pp"
7: repeat
8:
Calculate (T* E² via Algorithm I with fixed w
9:
Compute w solving (4) for the fixed T and E* with conditional gradient.
until Convergence
11: end for
Update the atom CM for E [M] with stochastic gradient V C... which has the form
M
2
Σ
W
Σ
with
① pp
T (C + =E"IT²
(3)
5
KEB
m
13: end for
Solving w. We now formulate the problem of obtaining the embedding of the th graph S when the dictionary is fixed and the PRM is inaccurate. Given dictionary {Crm) [C"]em[ Rn"xx" xx" the embedding of S expressed by (C*, p*)) is calculated by solving
Ime[ar] where each C
R (( W
(C
M
k C p). (C* ,p),)) 112
min
(4)

---

Published as a conference paper at ICLR 2023
where A > 0 induces negative quadratic regularization promoting sparsity on the simplex
Li
et al. 2020 Vincent-Cuaz et al. 2021). When w is fixed, updating T and E can be solved by Algorithm whose convergence is guaranteed by Theorem 2 For fixed T and EL, the problem of updating w is a non-convex problem that can be tackled by a conditional gradient algorithm. Note that for non-convex problems, the conditional gradient algorithm is proved to converge stationary point (Lacoste-Julien) 2016). Such a procedure is described from Line 5 to Line [ in Algorithm which observe converges within tens of iterations empirically.
local
Stochastic updates. To enhance computational efficiency, each atom is updated with stochastic estimates of the gradient. At each stochastic update, b embedding learning problems are solved independently for the current dictionary using the procedure stated above, where 6 is the size of the sampled mini-batch. Each atom is then updated using the stochastic gradient given in Eq. ( Note that the symmetry of each atom is preserved as long the initialized atom is symmetrie, since the stochastic gradients are symmetric.
5 EXPERIMENTS
This section provides empirical evidence that RGDL performs well in the unsupervised graph clus- tering task on both synthetic and real-world dataset:] The heat kernel matrix is employed for the PRM since it captures both global and local topology and achieves good performance in many tasks (Donnat et al. 2018 Tsitsulin et al. 2018 Chowdhury and Needham (02T).
5.1 SIMULATED DATASETS
We first test RGDL in the graph clustering task on datasets simulated according to the well-studies
Stochastic Block Model (SBM) (Holland et al. 1983; Wang and Wong 1987). RGDL is compared against the following state-of-the-an graph clustering methods: (i) GDL V'nccet-Cuua
al.) 2021)
learns graph dictionaries via GWD; (ii) approximates graphs via GW barycenters; (ii) Spectral Clustering (SC) of Shi and Malik (2000);
Factorization (GWF) (Xul (020) that
Stella and Shi (203) applied to the matrix with each entry storing the GWD between two graphs.
Table 1: Average (stdev) ARI scores for the first scenario of synthetic datasets.
balanced
unbalanced
0.05
0.10
0.15
0.05
0.10
0.15
GDL
0.119(0.017)
(.031(0.012)
0.016(0.006)
0.049(0.019)
0.018(0.004)
0.018(0.001)
GWF
0.071(0.007)
0.034(0.003)
0.008(0.001)
0.052(0.020)
0.015(0.001) 0.014(0.001)
SC
0.057(0.002)
0.033(0.002)
0.010(0.001)
0.054(0.024)
0.015(0.004)
0.010(0.001)
RGDL(c=0001)
0.316(0.005)
0.161(0.005)
0.052(0.002)
0.246(0.013)
0.039(0.009)
0.024 (0.001)
(GDL((=0.1)
0.853(0.003)
0.756(0.018)
0.439(0.015)
0.765(0.022)
0.694(0.046)
0.499(0.016)
RGDL(==0.2)
0.975(0.025)
0.879(0.023)
0.736(0.020)
0.866(0.023)
0.815(0.028)
0.770(0.016)
RGDL(==03)
0.879(0.023) 0.975(0.025)
0.869(0.013)
0.916(0.027) 0.943(0.001)
0.848(0.061)
RGDL(c=10)
(.975(0.025)
0.950(0.000
0.950(0.000)
0.943(0.001)
0.943(0.001)
(.943(0.001)
RGDL(c=30)
0.781(0.046)
0.779(0.070)
0.728(0.085)
0.723(0.067)
0.698(0.057)
0.666(0.040)
Dataset generation. We consider two scenarios of inaccuracies. In the first scenario (S1), Gaussian noise is added into the heat kernel matrix of each graph. More specifically, denoting the heat kernel matrix of the 4h graph C for k [K] the PRM available to DL methods is C* C + Z + Z where each entry Zij of Z is sampled from the Gaussian distribution (0, In the second scenario (S2),
randomly add p| edges into the graph and then randomly remove 3|E edges while keeping the graph connected, where E is the edge set of the graph. The heat kernel matrix is then constructed for the modified graph. Such two scenarios allow RGDL against different scales of inaccuracies. In both SI and S2 we generate two datasets, both of which involve three generative structures (also used label graphs): dense (only one community), two communities, and three communities. We fix p 0.1 as the probability of inter-community connectivity and - p as the probability of intra intra-community connectivity. The first dataset includes 20 graphs for each generative structure and thus is referred to as the balanced dataset. The second
study the performance of
Cooe available httpttttt//// peattpa://giiie com/ wttp://wwwccccccccceee

---

Published as a conference paper at ICLR 2023
Table 2: Average (stdev) ARI scores for the second scenario of synthetic datasets.
balanced
unbalanced
p
0.00
0.05
0.10
0.00
0.05
0.1
GDL
0.260(0.020)
0.187(0.013)
0.024(0.004)
0.152(0..08)
0.018(0.001)
0.005(0.001)
GWF
0.182(0.006)
0.086(0.004)
0.027(0.005)
0.020(0.005)
0.016(0.002)
0.010(0.002)
SC
0.204(0.002)
0.129(0.017)
0.016(0.005)
0.129(0.008)
0.013(0.001)
0.011(0.005)
RGDL(c=0.01)
0.451(0.014)
0.449(0.016)
0.449(0.016)
(.401(0.002)
0.399(0.000) 0.401(0.000)
(GD1((=0.1)
1.000(0.000)
1.000(0.000)
0.975(0.025)
1.000(0.000)
1.000(0.000)
1.000(0.000)
RGDL(c=0.2)
1.000(0.000)
1.000(0,000)
0.975(0.025)
1.000(0.000)
1.000(0.000)
1.000(0.000)
RGDL((=0.3)
1.000(0.000)
1.000(0.000)
1.000(0.000)
1.000(0.000)
1.000(0.000)
1.000(0.000)
RGDL(c=10)
1.000(0.000)
1.000
1.000(0.000)
1.000(0.000)
1.000(0.000)
1.000(0.000)
RGDL(c=30)
0.896(0.070)
0.888(0.080)
0.857(0.044)
0.864(0.057)
0.827(0.043)
0.816(0.074)
dataset consists of 12, 18, and 30 graphs for the three generative structures respectively, and is hence named as the unbalanced dataset. The number of graph nodes is uniformly sampled from [30, 50).
The magnitude of the observed PRM C² satisfies ||C* llce S 15.
Evaluating the performance. The learned embeddings of the graphs are used as input for a k- means algorithm to cluster graphs. We use the well-known Adjusted Rand Index (ARI) (Hubert and Arabie 1985 Steinley 2004), to evaluate the quality of clustering by comparing it with the graph labels. RGDL with varied c compared against GDL, GWF, and SC. RGDL, GDL and GWF use three atoms which are 6x6 matrices. We run each method for 5 times and report the averaged ARI scores the standard deviations. Experimental results reported in Table Table demonsttate RGDL outperforms baselines significantly.
Influence of e, RGDL with moderate e values outperforms baseline methods by a large margin and is more robust to the noise. Even when is relatively small (e=0.01), RGDL achieves better performance than baselines. Increasing within a suitable range can boost ARI and RGDL is not sensitive to the choice of If becomes too large, the performance of RGDL slowly decreases. In practice when a small quantity of data labels are available, can be chosen according to the performance on this small subset of data.
GOL
RGDLEE 01
RGDLL 10 PU)
SC
RGBLIe- -0)
RGDLC-
0.12
0.10
0.00
680
0.04
0.1
0.02
0.0
0.00
0.00
50
100
150
200
250
300
350
100
200
300
400
500
20
60
80
100
120
timatsec)
amelsecl
timelsec)
Figure 1: ARI scores vs. time on MUTAG (left), BZR(middle), and Peking-1(right datasets.
5.2 REAL-WORLDD DATASETS
We further use RGDL to cluster real-world graphs. We consider widely utilized benchmark datasets including MUTAG (Debnath et al., 1991). BZR (Sutherland et al., 2003), and Peking (Pan et al.) 2016). The labels of the graphs are employed as the ground truth to evaluate the estimated clustering results. For each dataset, the size of the atoms is set as the median of the numbers of graph nodes following Vincent- Cuatt al. (2021). The number of atoms M is set M B classes) where is chosen from {2, 3, 4, 5). RGDL run with different values of e. Specifically, e chosen from (U, 100100 10-2U, 10 10) where U max || llcc
8

---

Published as a conference paper at ICLR 2023
Results. The experimental results real-world graphs reported in Figure I RGDL with 10 10 or = 10 P outperforms baselines on all datasets, which implies that the observed graphs contain structural noise and [10 2U, 10] is often suitable range for e. The time required for RGDL to converge is comparable to that of state-of-the-art of methods.
RELATED WORK
Unbalanced OT.
Enhancing the robustness of the optimal transport plan has received wide atten-
tion recently (Balaji et al., 2020 Mukherjee et al., 2021 Le et al. 2021 Nietert al., 2022 Chapel
et al. 2020 Séjourné et al. [021] Vincent-Cuaz et al. (022). Originally, robust variants of classical
OT were proposed compare distributions supported on the same metric space (Balaji et al. 2020
Mukherjee et al. 2021 Le et al. 2021 Nietert al. 2022 which model the noise outlier supports and reduce the influence of outlier supports by allowing mass destruction and creation. Following the same spirit, variants of the GW distance that also relax the marginal constraints were proposed (Chapel et al., 2020; Séjourné et al., 2021; VVincent- Cuaz et al. 2022). However, these methods do not take the inaccuracies of the pairwise distances/simillriiiss into account. The proposed RGWD aims to handle such cases.
Graph representation learning and graph comparison. Comparing graphs often requires learn- ing meaningful graph representations. Some methods manually design representations that are variant under graph isomorphism (Bagrow and Bollt 2019; Tam and Dunson] 2022). Such rep- resentations are often sophisticated and require domain knowledge. Graph neural network- methods learn the representations of graphs in an end-to-end manner (Scarselli et al. 2008 Zhang
ct al. 2018 Lee et al.] 2018 Errica et al. 2019), which however requires a large amount of labeled data. Another family of methods that graph representations implicitly is referred to graph kernels (Shervashidze et al.) 2009 Vishwanathan et al.) 2010)) GWD and its variants based methods estimate the node correspondence and provide interpretable discrepancy between compared graphs (Xu et al. 2019b Titouan et al. 2019) Barbe et al. 2020: Chapel et al. 2020). In this paper, we propose a novel graph dictionary learning method based on robust variant of GWD learn representations of graphs which are useful in downstream tasks.
Non-linear combination of atoms. Classic DL. methods linear in the sense that they attempt to approximate each vectorized datum by a linear combination of a few basis elements. Recently, non-linear operations were also considered. In order exploit the non-linear nature of data, butoencoder-based methods encode them to Now-dimensional vectors using neural networks, and decode data with another neural network (Hinton and Salakhutdinov 2006; Hu and Tan 2018). An- other family of methods replace the linear combinations by geodesic interpolations (Boissard et al., 2011 Bigot et al.] 20133 Seguy and Cuturi, 2015] |Shhmitz et al.] 2018). More closely related to our work, Xu 2020 proposed to approximate graphs via the GW barycenter of graph atoms, which however involves complicated and computational demanding optimization problem.
Projection robust OT. To improve the convergence of empirical Wasserstein distances Rüschendorf 1985) population ones, group of methods project the distributions to informa- live low-dimensional subspaces (Paty and Cuturi, 2019: Lin et al.] 2020 [02T]) which involves solving min-max or max-min problems. This paper considers distributions supported on different metric spaces and does not project distributions.
7 CONCLUSION
In this paper, we propose novel graph dictionary learning algorithm that is robust to the structural noise graphs. We first propose robust variant GWD, referred as RGWD, which involves minimax optimization problem. Exploiting the fact that the inner maximization problem has closed-form solution, an efficient numerical scheme is derived. Based on RGWD, a robust dictio- nary learning algorithm for graphs called RGDL is derived to leamn atoms from noisy graph data. Numerical results on both simulated and weal-world datasets demonstrate that RGDL achieves good performance in the presence of structural noise.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work is supported by the National Key R&D Program of China (2020YFB131350)) 2020AAA0107400), National Natural Science Foundation of China (T2293723, 61972347, 61672376, 61751209, 61472347, 62206248), Zhejiang Provincial Natural Science Foundation (LR19F020005, LZIIFF20002), the Key Research and Development Project Zhejiang Province (2022C01022, 2022C011 19, 202IC03003), the Fundamental Research Funds for the Central Uni- versities (22--2022-00051) Alibaba-Zhejjang University Joint Research Institute of Frontier Tech- nologies, China Scholarship Council (202206320311), and MEXT KAKENHI (20H04243).
REFERENCES
Monica Agrawal, Marinka Zitnik, and Jure Leskovec. Large-scale analysis of disease pathways in the human interactome. In PACIFIC SYMPOSIUM ON BIOCOMPUTING 2018: Proceedings of the Pacific Symposium, pages 111-122. World Scientific, 2018.
Lars Backstrom and Jure Leskovec. Supervised random walks: predicting and recommending links in social networks. Proceedings of the fourth ACM international conference on Web search and data mining, pages 635-644, 2011.
James Bagrow and Erik M Bollt. An cooommttionthhoretti all-scales approach to comparing networks. Applied Network Science, 4(1):1-15,
Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. Advances in Neural Information Processing Systems, 13:12934-12244, 2020.
Amélie Barbe, Marc Sebban, Paulo Gonçalves, Pierre Borgnat, and Rémi Gribonval. Graph diffu- sion wasserstein distances. ECML PKDD, 2020.
Jérémie Bigot, Raúl Gouet, Thierry Klein, and Alfredo López. Geodesic pea in the wasserstein space. arXiv preprint arXiv:1307.770 130.7771,. 2013.
Emmanuel Boissard, Thibaut Le Gouic, and Jean-Michel Loubes. Distribution's 's template estimate with wasserstein metrics. arXiv preprint arXiv:1111.590 2011.
Sébastien Bubeck al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-337, 2015.
Laetitia Chapel, Gilles Gasso, et al. Partial optimal tranport with applications positive-unlabeled learning. NeurIPS, 2020.
Samir Chowdhury and Tom Needham. Generalized spectral clustering via gromov-wassersein learning. International Conference on Artificial Intelligence and Statistics, pages 712-720. PMLR, 2021.
Aaron Clauset, Cristopher Moore, and M Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 45317191):98-101, 2008.
Asim Kumar Debnath, Rosa Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Cor- win Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-797, 1991.
Claire Donnat, Marinka Zitmik, David Hallac, and Jure Leskovee. Learning structural node embed- dings via diffusion wavelets. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1320-1329, 2018.
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kerne:: Fusing graph neural networks with graph kernels, Advances in neural information processing systems, 32, 2019.
10

---

Published as a conference paper at ICLR 2023
Charles Elkan. Using the triangle inequality to accelerate k-means. In Proceedings of the 20th international conference on Machine Learning (ICML-03), pages 147-153, 2003.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neu- ral networks for graph classification. In International Conference on Learning Representations, 2019.
Zhizhao Feng, Meng Yang, Lei Zhang, Yan Liu, and David Zhang. Joint discriminative dimensional- ity reduction and dictionary learning for face recognition. Pattern Recognition, 46(8):2134-2143, 2013.
Mohamed Aymen Ben HajKacem, Chiheb-Eddine Ben N'Cir, and Nadia Essoussi. Overview of scalable partitional methods for big data clustering. In Clustering Methods for Big Data Analytics, pages 1-23. Springer, 2019.
Geoffrey E Hinton and Ruslan Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-5077 2006.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2): 109-137,, 1983.
Junlin Hu and Yap-Peng Tan. Nonlinear dictionary learning with application to image classification. Pattern Recognition, 75:282-291, 2018.
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2(1):193-218 1985.
Wenhao Jiang, Feiping Nie, and Heng Huang. Robust dictionary learning with capped 11-norm. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015. 2015.
Wengong Jin, Connor Coley, Regina Barzilay, and Tommi Jaakkola. Predicting organic reaction
outcomes with weisfeiler-lehman network. Advances neural information processing systems, 30, 2017.
Simon Lacoste-Julien Convergence rate of wolfe for non-convex objectives. arXiv preprint arXiv:1607.00344 2016.
Khang Le, Huy Nguyen, Quang M Nguyen, Tung Pham, Hung Bui, and Nhat Ho. On robust optimal transport: Computational complexity and barycenter computation. Advances in Neural Information Processing Systems, 34:21947-21959, 2021.
John Boaz Lee, Ryan Rossi, and Xiangnan Kong. Graph classification using structural attention. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1666-1674, 2018.
Ping Li, Syama Sundar Rangapuram, and Martin Slawski. Methods for sparse and low-rank recovery under simplex constraints. Statistica Sinica, 30(2):557-577, 2020.
Tianyi Lin, Chenyou Fan, Nhat Ho, Marco Cuturi, and Michael Jordan. Projection robust wasser- stein distance and riemannian optimization. Advances in neural information processing systems, 33:9383-9399 2020.
Tianyi Lin, Zeyu Zheng, Elynn Chen, Marco Cuturi, and Michael Jordan. On projection robust optimal transport: Sample complexity and model misspecification. In International Conference on Artificial Intelligence and Statistics, pages 262- 270. PMLR, 2021.
Julien Mairal, Jean Ponce, Guillermo Sapiro, Andrew Zisserman, and Francis Bach. Supervised dictionary learning. Advances in neural information processing systems, 21, 2008.
Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online dictionary learning for sparse coding. In Proceedings of the 26th annual international conference on machine learning, pages 689-696, 2009.
Stéphane Mallat. A wavelet tour of signal processing. Elsevier, 1999.
11

---

Published as a conference paper at ICLR 2023
Facundo Mémoli. Ktomov-wassersee distances and the metric approach to object matching. Foun- dations of computational mathematics, 11(4):417-477 2011.
Andrew W Moore. The anchors hierarchy: using the triangle inequality to survive high dimensional data. In Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence, pages 397-405, 2000.
Debarghya Mukherjee, Aritra Guha, Justin M Solomon, Yuekai Sun, and Mikhail Yurochkin. Outlier-robust optimal transport. International Conference on Machine Learning, pages 7850- 7860. PMLR. 2021.
Navid Naderializadeh, Mark Eisen, and Alejandro Ribeiro. Wireless power control via counterfac- tual optimization of graph neural networks. In 2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pages 1-5. IEEE, 2020.
Sloan Nietert, Ziv Goldfeld, and Rachel Cummings. Outlier-robust optimal transport: Duality, struc- ture, and statistical analysis. International Conference on Artificial Intelligence and Statistics, pages 1691-11719, PMLR, 2022.
Shirui Pan, Jia Wu, Xingquan Zhu, Guodong Long, and Chengqi Zhang. Task sensitive feature exploration and learning for multitask graph classification. IEEE transactions cybernetics, 47 (3):744-758, 2016.
François-Pierre Paty and Marco Cuturi. Subspace robust wasserstein distances. In International conference on machine learning, pages 5072-5081. PMLR, 2019.
Gabriel Peyre and Marco Cuturi. Computational optimal transport. arXiv: Machine Learning, 2018.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromovv-wsssestein averaging of kernel and distance matrices. In ICML, 2016.
Giovanni Piccioli, Guilhem Semerjian, Gabriele Sicuro, and Lenka Zdeborová. Aligning random graphs with a sub-tree similarity peessage-psssnng algorithm. Journal of Statistical Mechanics: Theory and Experiment, 2022(6):063401, 2022.
Silviu Pitis, Harris Chan, Kiarash Jamali, and Jimmy Ba. An inductive bias for distances: Neural nets that respect the triangle incquality. International Conference on Learning Representations, 2019.
Rajat Raina, Alexis Battle, Honglak Lee, Benjamin Packer, and Andrew Y Ng. Self-taught learning: transfer learning from unlabeled data. In Proceedings of the 24th international conference on Machine learning, pages 759-766, 2007.
Ignacio Ramirez, Pablo Sprechmann, and Guillermo Sapiro. Classification and clustering via dictio- nary learning with structured incoherence and shared features. In 2010 IEEE Computer Society Conference on Computer Vision and Puttern Recognition, pages 3501-3508 IEEE, 2010.
Ludger Rüschendorf. The wasserstein distance and approximation theorems. Probability Theory and Related Fields, 70(1):117-129, 1985.
Hamidreza Sadreazami, Arash Mohammadi, Amir Asif, and Konstantinos N Plataniotis. statistical approach for intrusion detection in syberr-hysite systems. IEEE Transactions on Signal and Information Processing over Networks, 4(1):137-147, 2017.
Distributed-graph
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
Morgan A Schmitz, Matthieu Heitz, Nicolas Bonneel, Fred Ngole, David Coeurjolly, Marco Cuturi, Gabriel Peyré, and Jean-Lue Starck. Wasserstein dictionary learning: Optimal transport-based unsupervised nonlinear dictionary learning. SIAM Journal Imaging Sciences. 11(1):643-678, 2018.
Vivien Seguy and Marco Cuturi. Principal geodesic analysis for probability measures under the optimal transport metric. Advances in Neural Information Processing Systems, 28, 2015.
12

---

Published as a conference paper at ICLR 2023
Thibault Séjoumé, François François-Xavier Xavier Vialard, and Gabriel Peyré. The unbalanced gromnv wasserstein distance: Conic formulation and relaxation, Advances in Neural Information Processing Systems, 34:8766-8779. 2021.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In Artificial intelligence and stafistics, pages 488-495. PMLR, 2009.
Chuan Shi, Binbin Hu, Wayne Xin Zhao, and Philip S Yu. Heterogeneous information network embedding for recommendation. IEEE Transactions on Knowledge and Data Engineering, 31 (2):357-370, 2019.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-99) 905, 2000.
Pablo Sprechmann and Guillermo Sapiro. Dictionary learning and sparse coding for unsupervised clustering. In 2010 IEEE international conference on acoustics, speech and signal processing, pages 2042-2045. IEEE, 2010.
Douglas Steinley. Properties of the hubert-arable adjusted rand index. Psychological methods, 9()): 386, 2004.
Yu Stella and Jianbo Shi. Multiclass spectral clustering. In Computer Vision, IEEE International Conference on, volume 2, pages 313-313, IEEE Computer Society, 2003.
Jeffrey Sutherland, Lee A O'brien, and Donald F Weaver. spline-fittingg with a genetic algorithm: A method for developing classification structure- activity relationships. Journal of chemical in- formation and computer sciences, 43(6):1906-1115, 2003.
Edric Tam and David Dunson. Multiscale graph comparison via the embedded laplacian distance.
arXiv preprint arXiv:2201. 2022.
Vayer Titouan, Nicolas Courty, Romain Tavenard, Chapel Laetitia, and Rémi Flamary. Optimal transport for structured data with application on graphs. In JCML, 2019.
Ivana Tošié and Pascal Frossard. Dictionary learning. IEEE Signal Processing Magazine, 28(2): 27-38, 2011.
Quang Huy Tran, Hicham Janati, Nicolas Courty, Rémi Flamary, Ievgen Redko, Pinar Demetei, and Ritambhara Singh. Unbalanced co-optimal transport. arXiv preprint arXiv:2205. 149223 2022.
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alexander Bronstein, and Emmanuel Müller. Netlsd: hearing the shape of a graph. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 2347-2356, 2018
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Cédric Vincent-Cuaz, Titouan Vayer, Rémi Flamary, Marco Corelli, and Nicolas Courty. Online graph dictionary learning. In International Conference on Machine Learning, pages 10564- 10574. PMLR, 2021.
Cédric Vincent-Cuaz, Rémi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty. Semi- relaxed grssesewas divergence and applications on graphs. In International Confer- ence on Learning Representations, 2022. URL https:://ppezeeieew net/ ffr.mmidrmi RShaMexjo-x
Vishwanathan, N Schraudolph, R Kondor, and KM Borgwardt. Graph kernels. the journal ofma- chine learning research. 2010.
Yuchung Wang and George Y Wong. Stochastic blockmodels for directed graphs. Journal of the American Statistical Association, 82(397):8-19, 1987.
13

---

Published as a conference paper at ICLR 2023
Xian Wei, Hao Shen, Yuanxiang Li, Xuan Tang, Fengxiang Wang, Martin Kleinsteuber, and Yi Lu Murphey. Reconstructible nonlinear dimensionality reduction via joint dictionary learning. IEEE transactions on neural networks and learning systems, 30(1):175-189) 2018.
Teng Xiao, Jiaxin Ren, Zaiqiao Meng, Huan Sun, and Shangsong Liang. Dynamic bayesian metric learning for personalized product search. In Proceedings of the 28th ACM International Confer- ence on Information and Knowledge Management, pages 1693-1702, 2019.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov- learning for graph partitioning and matching. In NeurIPS, 2019a.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov-waaserstein learning for graph matching and node embedding. In ICML, 2019b.
Hongtengl Xu. wassereease factorization models for graph clustering. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 6478-6485, 2020.
Yangyang Xu. Iteration complexity of inexact augmented lagrangian methods for constrained con- vex programming. Mathematical Programming, 1991)):9,,244, 2021.
Pinar Yanardag and S Vishwanathan. Deep graph kernels in: Proceedings of the 21th aem sigkdd international conference on knowledge discovery and data mining, 1365-1374. ACM, New York, 2015.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference on artificial intelli- gence, volume 32, 2018
Tong Zhang, Yun Wang, Zhen Cui, Chuanwei Zhou, Baoliang Cui, Haikuan Huang, and Jian Yang. Deep wasserstein graph discriminant learning for graph classification. In AAAI, pages 10914- 10922, 2021.
14

---

Published as a conference paper at ICLR 2023
Appendix
The appendix is organized as follows. We first provide omitted proofs in the main paper in Sec. Then, algorithmic details are presented in Sec. B Finally, Sec. Civves additional experimental results.
A OMITTED PROOFS
Theorem Given an observed source graph 9 and target graph G that can be expressed as (C", p²) and (C¹, p') respectively, RGWD satisfies
1. for all T E 11(p", p'), E(T) = [Eer (T) where
Eii= Tw TuTT5(C3 C2p) S0,
E 6, -c,
otherwise.
solves the inner maximization problem
max f(T, E).
EEN,
2. RGWD is lower bounded, that is,
RGWD (CC", (C',),
where the equality holds if and only if there exists bijective n² [n*] - [n'] such that
D = p' (o) for all i [n*]] and Ci₃y C() for all i, [n*].
3. The triangle inequality holds for RGWD, ie.,
RGWD ((C², "C',,')), p'',, pp),,)
<RGWD ((C', pp'). p²),c) + RGWD (C),
4. RGWD is invariant the permutation of node orders, iee, for all permutation matrices Q and Q'
RGWD (C', RGWD " (") Q'T e').
Proof: (i) The objective be rewritten follows.
(G - C2-- Eay) To
n
n²
(Cg - Cg,y) TT +
Σ
Σ
To Eg, -2 Σ
TwT (C, CCty)
i,==1
i,j=1
12"
Σ J=
Σ
(C - -
+
Ei
Σ
Tw Tari (C
City) (
(5)
which by the property of quadratic functions yields the closed-form solution E(T) [F (T)) where
if Σ I Tw (C7, Cbp.) S 0.
E, -E, otherwise.
Egy (T)
is easy to verify that the such a choice guarantees the symmetry of E(T).
(ii) We now prove the lower boundedness. By Eq. 5). we have
min
Σ
(C C2.y E Th: Tyx 2 min
Σ Σ
Tar Tay =2.
TEll(p' p BEU.
Tell(p..p))
w=1l-==1
15

---

Published as a conference paper at ICLR 2023
Note that when there exists bijective x²
[n*]] [n']] such that p; p)- for all i E [n*]] and
Cj C (0)x))))))))) for all i,j E [n*]]. choosing the transport plan T = [Tee] where
Th pr: 10
if -
otherwise,
have for all V' [n'].
Σ To (y - Obp)) T sw 1600 (C--1090-110) - - 0,
1-=1
which implies that Eey (T) = for all '',5" E [n']. We then have
[C Cjyy Esy TT 33' Σ
(C) C (( (1) =
ij=1
Therefore, in such case, RGWD ((C*, p*), (C', (C', = On the other hand, when such bijective does not exist,
RGWD ((C* (C', V
2
min TEllppp. .p')
Σ
Σ
(C
c,
W==1"''==
where the strict inequality is due to the fact that Eij=1 (iii) Thirdly, prove the triangle inequality. Given tuples (C), p'), (C², p²), and (C3 p²) which have the node numbers n', n², and n² respectively, let (T E (T E and
E Ei' f'=l CC - P
0.
(T* E.13) be the solutions of RGWD ((C), (C*,
RGWD ((C p²), (C)))
and RGWD ((C', p²), (C3, ()), Define T [T13 where fiig
22 ip23.
1 814g
Pr
1=
Then we have RGWD
(C*, ,P)),))
Σ 3
(C) h1
C3 isis - E113
2T13
Jids
$1:11 =1 Aa.Ja=1
n1
n
12a
Th n²
Σ
(Cl in
C3 Jajn - E.131
i12o i21g
jaha
Pi
2
p
=1
Ka
12=1
12=1
n Σ Σ
n1
n3
12
T -212
(C) - C22 + +022jn
13
2
1210
jzha
ig78
p]
3
12227=23 T212
ΣΣ
(C),, - C2
2
1112
12ts
jaJa jido
p
ΣΣ 3
22
23 Jaja
1232 - -C3 - E
Σ
CCl
tn - C2
2T:127=122 +
Σ
n²
3
(C2 12222
-C3 - -E+13) ( 2T=23T=22
J132
1228 1233
12:00=1 ka:7a =1
< RGWD ((C), p²) (C² "C','p''). p2). + RGWD (C* c)).c).
16

---

Published as a conference paper at ICLR 2023
(iv) Finally, prove the invariance the node order permutation. Denote the solution to the objective of RGWD by T [T and E [Egy, which implies
if Ei Tw (C - otherwise,
Cby) S0
Bgy =
and
Σ Σ w=lF-yy=
(Cjj
Cz3y b T
max Beul ij j/=
Σ
Σ
CC - -Gyy
E Tww Thx'
for T E 1p(p, p¹). nt and n². Denote
The two permutation operations can be equivalently denoted as two bijectives
Č [Cry] where Öt. = C (()-(()---11)))
Č [r where C/ C 7- (()=(())*"
E [E2yr yl where Egy E E - -1)-
T [T where Th = T 1(0) ((1)'
We first prove E' solves the inner maximization problem for T For all d',j' E [n']. when Eig Th Ty (Oz Cgy) S 0, we have Ei, The -i T (g)) (Ciz C -)-1)))))- S o, which is consistent with = e. The case when Eij T
33 (Ci (gy) > similar. Since
n2
n
n²
Σ
(C - C3y - E TT
CC C,ty - Egy) TTx TV
35'
Fd
P'd==l
and
n²a
n
Σ
max BEUle (C, J33 Esy) T3y'
(C Ez.y Euy
max BEll,
==='"''==1
i.j=1
where
Tw RGWD ((Q
T 70- (2) T and E solve the optimization problem of Q p*) T' cP).c).
To prove Theorem 2 we require the following lemma.
Lemma f(-) is I-smooth and T--Lipschitz. where I = v2 max + 6n + 4nU, + 4n Un²U,Up U2 + 2U3 + U22 and L = /2 max{ 2e)U3n3, 2(2U + e)2 with max n², n²), U1 max[]|C[] bo |C and U2 max 112, ma [
Proof: (i) We first prove that f(-) is L-Lipschitz For all T' II(p", p²) and E, E' u.
(( E) f(T', E')l
Σ (Cg - -Cpy
TTw Σ ECG C2py Egy' 2 Tix
Σ (C, -byy -E TTs
Σ (Ctz
C2py Egy TTt 13
Σ (Cr C2yy ) TT
Σ (C
C2py Egy TT T
17

---

Published as a conference paper at ICLR 2023
For the first term,
Σ CC Ciyy - Eey ) Tw: 1 Cipy - )
Te T38
Σ(CH (Cg -Cyy Eay + Cig -C2y - E,y.) E TTi
Σ City - C23 - Pay + Cij - G3y - F - Eey | T3
S(UU - 26) U3
El BBay Earl.
8'
For the second term,
Σ (C -gpy ) Thi T3 - (C -Cty "
W/'''
$
Σ Joj C23- -, 2 T(sse |Tgs - -T/rl
1j0'''
<(201 + -2²²U Σ [8hJ Ti
"/''3'
+ u2) +(2U1+c)
Tzp' T
For the third term,
Σ (Ci Ciyy F/yyy The
[C;
Cipy
Te Tj3
<(201 - <) U2n Tii TTyb
Combining the three relations above, we have
|T E) f(T', F(T
<max { {(1U + n2)),n", + U22?
Fbg - Egg' +
Σ
Tas Tyst)
33'
<> <LVIE |E- + T T T.
(ii) Now we prove that f(-) is I-smooth, which requires finding a constant satisfying
vec (Vrf(T, E)] vve (Tr ED) vec (VE/(T,E)) E))
vec (TES(T', E
< /
vec vee E))
T
vvee T vec E')
where vec(X) means the vectorization of matrix X and [6] denotes the concatenation of vectors and b. Since the left hand side satisfies
vec VTf(T, B)] vec (ET((T
vec (Tr((T. (")))))))))))) E`)
vvec (Vr.(T', E')
/T VTS(TT, E' ( E) VES(TT, E < (T, E) - VTr((T', VT/ (e)(TT,E')lll
and the right hand side satisfies
vec T)) (E)
[Ve)(T)
vec T vec E')
=ly E
E' + T - T 1|
E
E -2
T - T
18

---

Published as a conference paper at ICLR 2023
it suffices to find constant I satisfying
1
1
(TT (erLEE))-V/((BBB E')le s - E--E
T T-
V2
V2
We bound Vr. as follows,
[VT (T))
22n 3 C F T - || +E) - T'(C" + EE)l
+2n
T((* + +C*+E)
+ T' + E') о (C' + E'Illr
For the first term,
2n C + - s 2m
S U T
For the second term,
||CCC + - CC + E'Ilee
-||C"I|TTTTTI ( - + [B|r) r)) + || -
S4 + Un T| 4nU E'Ie.
For the third term,
2n + E) O +C*+ - E'Ilss
<2n
+ E) -CC
E)
+2m (C*=+=)(('+
(C* +)]+
+2m
(C' +E'll
<
[E] E
( 4n Un E'Ile
Since VEf(T,E) = 2 E C -T - E'Ill can be bounded
as follows,
|VEf(T. E) VES(T' E')l
2 - E')ll=lle> T|| [ <2U - E')ll 4nU T
Combining the above four relations, we have
[[Vrf(T, Vrf(T', + T <max(10n uU? + un 4nU,U + 3 6n Un?US + 2U3 + 4n Un?] [EE E'Ile + || - -T'Il)).
VE,((T','')l
which yields the desired result.
Theorem Define <()) maxgeu, f(, E). The output T Algorithmm step-szzen VN+1 satisfies
E V (T) < 11/2:(To) minTenlp D²) (T) + 1T.272 TVN +1 2.
where = /2 max 110 max(10n + 6n Un 4nU,U, + 2n 2, 6n unn + 2U3 + Unc] and L
m2 + U3 2,22), +e) with n = max(n" n }. Un = max | C |C']
and U2 m maxp'ellpppp' []]
19

---

Published as a conference paper at ICLR 2023
Proof:
By the smoothness of f()), for any T II(p", and T, from Algorithm | we have
1 I
Φ T ((. 2 (T E,) (Vrf(T E,), T T-) 2 T
(6)
[T, + VT E,), T - b 1
Let T, = argminrel(pppp (T) + T T- ll We have
$1/21 (T++1) ((T,) + T++ - T/
$ <T,) + - E,) T/
< (T,,) + +I[,, - T-11 2/1 VT TT/ /TTT/(TTTFrr E,), T, - T²) (T,, E,)
s 11/22( + VT/ E7); T, TT, + + V (T E.)
$ / (T+) 2npl (TT,) 2 T
+ 1
where the second line uses Lemma 3.1 of Bubeck et al. (2013) and the last line follows from (6) Taking a telescopic sum over т, we obtain
11/2(TT) S (To) 2np
Σ
(0(T,) - (TT,) _ -T,11)) 1112
7=0
Rearranging this, we obtain
1
01/2 - minte Epp .pt) (TT) ny2
(TT (T TT, -T,11
2 (7)
N+1
2
T=0
Since (TT) + I 11 is 1-strongly convex, we have
( | -
Tr - T, |/ (T,)+1111 + +IIT, T min (T)) + + T.1..)
2
T/ -
47 1 ?
Plugging this 7 and combining Lemma proves the result.
B ALGORITHMIC DETAILS
The Projected Gradient Descent (PGD) consists of the following three steps in each iteration
Find E, that maximizes f(T,, E). By Theorem 1, we need to calculate an auxiliary matrix
G G T,T,CT, - - o T,
where @ denotes the element-wise multiplication. And we have
(T,) 6, Gey $ 0, Such step involves computational cost O(n3) where max(n",n'),
-c, otherwise.
Gradient descent. Calculate H, = T TT/ E,) where
VTf(T,.E.) 2 1"' 1n + 21 1n"""1n1 T ((C' (C'+EE, O (C'+E.)) -4CTT,(C* +E.),
which also involves computational cost O(n3).
20

---

Published as a conference paper at ICLR 2023
PCA-based visualization of embeddings produced by GDL (left), GWF (middle), and RGDL (right) respectively for the graphs in MUTAG dataset. The color of each point indicate the type of the corresponding graph. RGDL achieves the best clustering results.
Figure 2:
Projection into the feasible domain.
This requires solving the following problem
min T20
T 1 s.t. T1 p. T 1 q.
This optimization problem has strongly convex objective and linear constraints, and hence can be solved efficiently via Augmented Lagrangian Method with computational complexity n² nollog (Xu 2021 where measures the optimality, that is, the violation of the two linear constraints. When P= this step also has cubic costs if ignore the log term.
Therefore, the overall complexity of PGD obtaining d-stationary solution O na + p17282
loc
C ADDITIONAL EXPERIMENTS
C.I ADDITIONAL EXPERIMENTAL RESULTS OF GRAPH CLUSTERING
Visualization of graph embeddings. Since GDL, GWF, and RGDL can output graph embed- dings, we further illustrate the embeddings generated by them respectively based on PCA. As is shown in Figure 2 the embeddings the two types of the graphs are less likely be mixed gether, which explains why RGDL achieves higher ARI values.
Sensitivity analysis of X. As is discussed in Li al. (2020); Vincent-Cuaa al. 2021). J. the neg- ative quadratic term can promote the sparsity of graph embeddings. We further conduct sensitivity analysis of by varying the value {0, 10 10 10-3 10 10-1). J. As is shown Table [10 101 often yields good performance. The experiments in the main paper are run with
10-3 3
Table 3: ARI scores RGDL with varied X's.
Datasets
0
10-5
10-1
10-3
10-2
10-1
MUTAG
0.4389
0.4561
0.4636
0.458
0.4661
0.4412
BZR 0.2515
0.2515
0.2707
0.2707
0.2707
Peking
0.1195
0.1195
0.1195
0.1195
0.1195
0.1079
C.2 GRAPH CLASSIFICATION
The learned embeddings of graphs can also be used in the graph classification task. RGDL is thus compared against GDL /Vincent-Cuaz et al. 202T), GWF [Xu 2020). and other state-of-the-ar
graph classification methods including WGDL (Zhang al. 2021 and GNTK (Du al. 2019) on the benchmark datasets MUTAG (Debnath et al. 1191). IMDB-B, and IMDB-M (Yanardag and Vishwanathan 2015). RGDL, GDL, and GWF
3-NN as the classifier due its simplicity. We perform 10-fold nested cross validation (using 9 folds for training, for testing, and reporting the average accuracy of this experiment repeated 10 times) by keeping same folds across methods.
21

---

Published as a conference paper at ICLR 2023
Table 4: Graph classification results.
Datasets
RGDL
GDL
GWF
WGDL
GNTK
IMDB-B
77.7(1.5)
59.0(2.6)
53.0(6.2)
79.7(3.6)
76.9(3.6
IMDB-M
52.9(2.5)
44.2(2.3)
42.0(3.7)
53.5(5.0)
52.8(4.6)
MUTAG
98.2(3.0)
89.5(5.3)
86.0(3.0
94.7(2.6)
90.0(8.5)
The results reported in Table 4 and RGDL outperforms matches state-of-the-ar methods. RGDL outperforms GDL and GWF significantly, which indicates the necessity of taking into ac- count the structural noise of observed graphs. Although WGDL and GNTK have similar perfor- mance, they are more computation and memory demanding due to the usage of graph neural net- works.
22


Reviews:
[{"review_id": "yKkvTC-zCS", "reviewer": "Reviewer_Lcq7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the problem of dictionary learning for graphs. It proposed an improved graph dictionary learning algorithm based on a robust Gromov-Wasserstein discrepancy (RGWD). It also provided some theoretical results and numerical results. ", "summary_of_the_review": "Overall, the idea of robust dictionary learning is interesting though robust dictionary learning has been widely studied in many previous work of vector data. The novelty is fine and the experiments should be improved.", "strength_and_weaknesses": "Strengths:\n1. Graph-level dictionary learning is a challenging problem and hasn't been well studied. The paper proposed an effective method called RGWD though heavily relying on previous work.\n\n2. The authors provide some theoretical analysis including some properties of the proposed metric and the convergence of the optimization algorithm.\n\n3. The numerical results especially those of the synthetic data showed the effectiveness of the proposed method in comparison to GDL.\n\nWeaknesses:\n1. In terms of the model, the contribution is not significant because compared with previous work of GWD, the proposed method only added an error term E. Thus RGWD can be regarded as a natural relaxation of GWD. The connection and difference should be highlighted. In the numerical results, what caused the improvement of RGDL over GDL? Is it the noise term E or optimization algorithm?\n\n2. It seems that the time complexity is $O(n^4)$ and the authors did not discuss the time cost in the experiments.\n\n3. The role and effectiveness of E are not clearly explained. Could one use other constraint on E instead of the infinity norm?\n\n4. In Theorem 1, it is not clear why RGWD cannot reach zero.\n\n5. Is RGWD symmetric?\n\n6. In the experiments, are C_i similarity matrices? If yes, setting $\\epsilon$ to large values such as 10 and 30 in Table 1 looks a little weird.\n\n7. In Table 4, it seems that all methods failed in clustering IMDB-B and IMDB-M because the ARIs are less than 0.1, which makes the experimental results useless. The authors should consider more real datasets on which the proposed method can work well. One MUTAG dataset is not enough.\n\n8. It is not clear why the authors did not show the influence of $\\epsilon$ on the clustering performance of the real datasets.", "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": "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": {}}, {"review_id": "sN3i37hTC_", "reviewer": "Reviewer_ia1M", "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": "", "summary_of_the_paper": "This paper proposes a robust graph dictionary learning algorithm based on a metric named robust Gromov-Wasserstein discrepancy (RGWD).  With the proposed method,  a set of atoms can be learned from noisy graph data. Experiments are conducted on synthetic datasets as well as public real-world datasets to evaluate the proposed method.", "summary_of_the_review": "The motivation of the way for optimizing the transport plan should be made clear, and more experimental results should be provided with a comprehensive comparison.", "strength_and_weaknesses": "Strengths\nTheoretical analysis about the properties of the proposed RGWD is provided.\n\nWeakness\n1. Lacking the motivation of using the projected gradient to update the transport plan.\n2. Insufficient experimental evaluation.\n\nDetailed comments:\n1. What’s the advantage of using the projected gradient to update the transport plan.? Can it be solved by employing the Sinkhorn algorithm? More theoretical or experimental evidence needs to be provided to compare their efficiency/convergence and results.\n2. Three datasets named MUTAG, IMDB-B, and IMDB-M are used to evaluate the proposed method with the metric of ARI score. However, as these datasets are usually used for graph classification, it’s suggested to provide the classification performance on these datasets as well.\n3. More graph learning methods could also be compared, e.g. graph kernel-based methods, other than only graph dictionary learning. Specifically, a deep graph dictionary learning method is proposed in [a] recently. It is suggested to compare this work by discussing the advantages and disadvantages, as well as comparing the performance.\n[a] T. Zhang, et al. Deep Wasserstein Graph Discriminant Learning for Graph Classification. AAAI 2021. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HChirKWLHN", "reviewer": "Reviewer_2db5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an improved graph learning algorithm based on a robust Gromov-Wasserstein discrepancy (RGWD). Following the previous GDL by Vincent-Cuaz et al. 2021, the new method replaces GWD by a new RGWD which uses a minimax formulation. Moreover, robust graph dictionary learning algorithm is also proposed based on stochastic gradient descent. Overall, the paper has a certain novelty on designing a discrepancy form with theories, and the numerical experiements on synthetic and real-world data sets have shown the performance of the proposed algorithm. ", "summary_of_the_review": "The paper is interesting, reads well and has clear motivation and contributions. ", "strength_and_weaknesses": "Strengths:\n1. A new robust variant of GWD is proposed with discussions on its properties such as asymmetry. \n2. A projected gradient descent algorithm for RGWD is provided with convergence guarantees. \n3. Performance of the proposed method on synthetic and real-world datasets is outstanding. \n\nWeaknesses:\n1. In Sec 3.2, the Moreau envelope of the maximum function turns out to be a minimax problem, and the corresponding proximal operator is not straightforward. Some remarks about the role of this in Theorem 1 could be made. \n2. It's not clear why a negative quadratic term is necessary in eqn.(4), which also makes the objective nonconvex and may cause convergence issues. In addition, guidance on choosing the parameter $\\lambda$ for some datasets could be given.\n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "G1sHrxz1fOE", "reviewer": "Reviewer_q8cY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a robust approach for dictionary learning on graphs. The method is based on a robust version of the Gromov-Wasserstein discrepancy, which involves a minimax optimization problem that is neither convex/concave. The authors proved several properties of the RGWD. The authors demonstrate the efficacy of their approach via experiments and simulations. ", "summary_of_the_review": "I think overall the paper is well written, the approach is natural, and the contributions are sufficiently novel/original. However, there remains some areas for improvement that I think if addressed, would make the paper much stronger. In particular, if they could compare against more alternatives in their simulations, add the very related references that are suggested, and comment on whether their method satisfies the permutation invariance property which is very important and natural. ", "strength_and_weaknesses": "- Strengths: \n\n- The approach is well motivated and natural. The drawbacks (lack for robustness under noise) of the current GWD approach is stated, and then a solution that address the robustness drawback is proposed. \n\n- The paper is well-written. The background material on optimal transport and graph dictionary learning is presented clearly. \n\n- The proposed method is a very natural extension of GWD. \n\n- Some nice (although pretty basic) properties of the RGWD, such as triangle inequality is posed. \n\n- In experiments and simulations, RGWD appears to perform quite substantially better than competitors. \n\n- Weaknesses: \n\n- The comparison in the simulations is limited. In the simulations, the authors used RGWD with a wide variety of epsilon parameters and compare all of them against only GDL. While the performance of RGWD is good/better than GWD across a variety of epsilon choices, comparison against only one alternative (on a simulated graph clustering task, of which many alternatives should be available) does not convince the reader strongly enough that the RGWD is truly superior to a broad set of competitors. I highly suggest that the authors compare the performance of RGWD against a few other graph clustering methods to make their simulations more convincing. \n\n- With any distance/divergence or other tool for graph comparison, certain specific basic properties should be shown. Of particular importance is whether the divergence/distance etc is invariant to the representation of the graph. For example, If I am comparing graph G_s and G_t, would the resulting number/distance be invariant to vertex label permutations? I.e. distance(G_s, G_t) = distance(permutation1(G_s), permutation2(G_t))? I think this property is very important since it makes sures that the distance is comparing graph structure, not some arbitrary label/representation. As of now it is not clear whether the RGWD satisfies this property. If the property is satisfied, then it would be great to state it explicitly. If it is not satisfied, then at least the authors could mention/discuss it. \n\nMinor Points: \n\nThere are some related work/references on comparing graphs of different sizes/number of nodes with no alignments that I think the authors could cite: \n\nNetwork Portrait Divergence: \nAn information-theoretic, all-scales approach to comparing networks. James Bagrow and Erik Bollt\n\nEmbedded Laplacian Distance: \nMultiscale Graph Comparison via the Embedded Laplacian Distance. Edric Tam, David Dunson\n\nGraph Diffusion Wasserstein Distance: \nBarbe et. al. Graph Diffusion Wasserstein Distances. ECML-PKDD 2020", "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": {}}]

Author rebuttal:

Decision: Accept: poster