Certifying Robust Graph Classification under Orthogonal Gromov-Wasserstein Threats
Authors: Hongwei Jin
Zishun Yu
Xinhua Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: certification of robustness
Gromov-Wasserstein distance
convex relaxation

Abstract: Graph classifiers are vulnerable to topological attacks. Although certificates of robustness have been recently developed, their threat model only counts local and global edge perturbations, which effectively ignores important graph structures such as isomorphism. To address this issue, we propose measuring the perturbation with the orthogonal Gromov-Wasserstein discrepancy, and building its Fenchel biconjugate to facilitate convex optimization. Our key insight is drawn from the matching loss whose root connects two variables via a monotone operator, and it yields a tight outer convex approximation for resistance distance on graph nodes. When applied to graph classification by graph convolutional networks, both our certificate and attack algorithm are demonstrated effective.

Certifying Robust Graph Classification under Orthogonal Cromov-Wassersee Threats
Hongwei Jin"
Xinhua Zhang Department of Computer Science University of Illinois Chicago
Zishun Yu,
Mathematics and Computer Science Division Argonne National Laboratory
Lemont, IL 60439
Chicago, IL 60607 {zyu32, zhangx)@uicc edu
iin@@al.gor
Abstract
Graph classifiers are vulnerable to topological attacks. Although certificates of robustness have been recently developed, their threat model only counts local and global edge perturbations, which effectively ignores important graph structures such as isomorphism. To address this issue, we propose measuring the perturbation with the orthogonal Gromov- Wasserstein discrepancy, and building its Fenchel biconjugate facilitate convex optimization. Our key insight drawn from the matching loss whose root connects two variables via monotone operator, and it yields tight outer convex approximation for resistance distance on graph nodes. When applied to graph classification by graph convolutional networks, both our certificate and attack algorithm are demonstrated effective.
Introduction
satte-of-thh-att graph classifiers such graph convolutional networks (GCNs) have been recently revealed vulnerable to adversarial structural attacks, namely adding and removing edges [1. 2]. Due to the hardness of finding the strongest attack, alternative strategy aims certify robustness, Le., proving that no perturbation in the threat model can successfully attack the classifier. To this end, [3, 4] extended randomized smoothing to discrete noises with applications in, e.g., community detection. Although our focus is on graph classification, certificates have been studied for node classification using, e.g, convex outer adversarial polytope 6]. Most relevant to our method is [7], which constructed the tightest lower bound of the margin via Fenchel biconjugation.
However, all existing threat models only count the total edges removed added (global budget) the change each node's 's degree (local budget), while overlooking the important notion of isomorphism. In contrast, there has been wealth of more refined discrepancy measures between graphs, including kernels [8, 9] and GCNs [10, 11]. Recently, the Gromov- Wasserstein discrepancy [GW, 12]. which extends the Wasserstten distance [13], has emerged
effective transportation distance between structured data, alleviating the incomparability issue between different structures by aligning the intra-relational geometries. Thanks to its favorable properties such efficiency and awareness of isomorphism, GW has been extensively applied to domain adaptation [14], word embedding [15], graph classification [16], metric alignment [17], generative modeling [18], and graph matching and node embedding [19, 20]. Therefore, it is clearly natural to adopt such a measure in the certification of graph robustness. Analogously. Wasserstein distance has already been employed in distributional robustness [21] and in attacking images [22], where perturbations can be found that better reflect the image content compared with the standard t, attacks.
Unfortunately. GW is not tractable to evaluate, differing from the standard Wasserstein distance which is linear program. So all existing optimization techniques settle for local solutions, lacking
Work done when the author was at the University of Illinois Chicago
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

an analyzable guarantee. To develop certificates. tractable lower bounds of GW would be essential, but the Kantorovich dual no longer exists and the existing lower bounds [13, 23] are not tight [24]. Further, underlying the standard probability coupling is the metrics within each graph, e.g., shortest- path distance [13, SP distance], which requires nontrivial discrete optimization. This significantly complicates the entire certificate as the subject of perturbation is exactly the topological structure. In addition, certificates based on randomized smoothing [4, 25]. which adds noise to the input, are also hindered by the significant challenge in designing the noise distribution that aligns with GW.
The goal of this work, therefore, is to construct the first robustness certificate for GW-style threat models, with applications in graph classification. This is achieved by casting the entire computation procedure of GW as a two-layer model, each of which is subsequently relaxed tractable fashion:
graph structure
resistance distance
distance btw nodes
orthugonal GW
discrepancy btw graphs.
matching loss
envelop
Firstly, we circumvent the discrete optimization in SP distance by resorting to the resistance distance [26]. which, along with its scaled version known as commute time, is one of the most commonly used distances in computer science, machine learning, and beyond [27]. Compared with SP distance, it admits a closed-form based on matrix inversion, which monotone operator on the positive semi-definite cone. This enables our first contribution, where a convex relaxation is designed for resistance distance in Section 3 based on the matching loss [28].
Our second contribution achieves convex relaxation of the GW-style discrepancy measure. Our seed inspiration is drawn from the latest orthogonal GW discrepancy (OGW) [24] reviewed in Section 2.2 preserves most of the desirable properties of GW while admitting a tight and efficient lower bound. We next make the key observation in Section 2.3 that the lower bound, despite not convex, admits a closed-form Fenchel dual, which in turn facilitates an efficient evaluation of the Fenchel biconjugate. Such a convex lower bound applied to graph convolution networks in Section 4, where both attacking algorithm and robustness certificates are developed.
Our experiments in Section 5 verify the effectiveness of our attacker and certificate, in that large proportion of the graphs can be proved either vulnerable or robust.
Related Work Certification or verification has been longstanding pursuit in machine learning and systems. Formally, it inquires if f() can be driven down to negative over x E X, where both f and X' can be too complicated for global optimization. So lower bound of the optimal objective is sought, which provides incomplete verification (some true properties are confirmed true). A lower bound can also be useful in branch-and- bound algorithms [6]. A natural approach is the Lagrange dual [29, 30], which minorizes the primal by the weak duality. However, it can be loose, and a provably tighter lower bound is the convex envelope or Fenchel biconjugate [7]. But they themselves are efficiently computable only under limited scenarios.
In general, the objective f is composed of several "layers", i.e., ʃ fo where fa is simpler but no longer scalar-valued (i 2 1). So is natural to relax their graphs. For example, min [o (x)) is equivalent to ming,y fo(y) s.t. is simpler than f) and employ the convex hull of {xx y) : y = f1:).. The latter is represented by the convex envelope relaxation of the ReLU activation [31-35]. which has also found applications in graph neural networks [6. 36]. However, they have been so far limited to R- + E nonlinear functions while a multivariate extension is not available yet, as the convex hull is much harder compute.
(x)). So we can possibly use the convex envelop of So (which
Another commonly used approach randomized smoothing, which adds noise to the input [25, 37- 391. Although it has also been shown effective in graph robustness [3, 4], the design of discrete noise can be quite intricate and so far no such methods exist for GW-style threat models. Other methods include semi-definite relaxation [40, 41] which is often loose, Lipschitz continuity analysis [42-44] where the local and global estimation of curvature difficult in the discrete domain, and reformulation lincarization technique [45] used by [5] for directed but not undirected graphs.
2 Moamoy-Wasserstein Threats for Attacking Graph Classifiers
We consider attacking a graph classifier where the edge connectivity is perturbed. Here both the original graph D and the resulting graph C are assumed undirected, unweighted, and connected. Let the adjacency matrix of be A E (0, 1|mxx, where A, = 0, and A.j E (0, 1) (i () indicating whether an edge exists between nodes i and j. Here is the order of the graph, i.e., number of nodes.
2

---

Now suppose the graph's 's edge connectivity is perturbed, leading to new adjacency matrix A == A + X (corresponding to C). Obviously. X needs to be symmetric, zero diagonal, and X;, E (-Aij, 1 A. If we relax it to the continuous domain such as convex relaxation, Xij is naturally relaxed to [-A 1 Atj]. The threat model governs additional budgets on X besides the above admissible conditions. Global change budget can be written as 1 o S) - 6g. where S = 1 2A and stands for the Hadamard product. Local budget is (X a S)1 S 6;1 (elementwise). If we only allow adding edges, then Xij 2 0. All these basic constraints are linear in X, and we will collectively refer to them as X E X, convex set.
Suppose we have trained graph classifier G (e.g.. graph convolution network, GCN) which maps an adjacency matrix A to K -d-dienniooal logit vector (AA) corresponding to K classes. Assume the true class is y and 9 predicts correctly, i.e., y = arg max, Go(A). Then the margin of classification is
M(A) == minezt -
(1)
The attacker seeks a feasible perturbation X E that drives the classification margin to negative, i.e. a misclassification. G is called robust on this graph if minxex M(A+ + X) is positive, and is called vulnerable if the minimal value is negative. It is noteworthy that we employ graph classification and GCN only as example context of applying our proposed relaxation technique. Other tasks such as node classification are readily applicable too - simply replace the M function.
Although the global and local budgets are natural and reasonable characterizations of the perturbation, they ignore an important notion on graphs: isomorphism. Exact isomorphism can be relaxed by defining a distance between two graphs, which quantify their difference under the most favorable permutation of nodes. One of the most commonly used distance is the Gromov- Wasserstein distance [13], which has been extended to Gromov- Wasserstein discrepancy [GW, 12]. So in addition to the standard local and global budgets specified by X, it is natural to further constrain the perturbation in terms of the GW distance. To conclude, the attack and certification tasks can be formalized as minxex M(A + X) s.t. GW(new graph A + X, old graph A) S da for some budget oG > O.
2.1 Definition of
distance
Since our threat model will only add or remove edges while the nodes remain intact, we only need to compare two graphs C and 'D with the same order. Although GW takes a prior distribution nodes that represents their importance, it is often observed that a simple uniform distribution performs equally well better [12. 16, 46], and many applications do not have such an external prior. So we can restrict GW to uniform distributions, leading to the following expression under Ez distance:
min GW(C, PERRX":PI=PTTI 1=n-11
Σ L.j.p. (Cas - Dpg) 2Pp P39-
(2)
Here 1 is an all-one vector, and Cij is a distance measure between nodes i and j in C, egg. SP distance. We will denote the n matrices C (for C) and D (for D). We also follow the idea of [12], where Cty does not have to be metric and f2 can be extended to asymmetric losses. They call it GW discrepancy, and we do not take the square root of the right-hand side of (2) when defining GW. In the sequel, we will also write GW D) instead of GW(C, D) whenever it causes no confusion.
2.2 Orthogonal GW and its upper and lower bounds
Unfortunately, GW relies on a nonconvex optimization, and the optimal P in (2) is intractable to find. Although polytime lower bounds have been proposed by [13], they are shown quite loose [24]. Since aim is to certify robustness under such a measure, tight and efficient lower bound is in demand (see below). To this end, we resort to the recently proposed orthogonal GW JOGW, 24], which does offer such lower bound. OGW first rewrites the GW in the Koopmans- Koopmans--Bekkman Beckmann form [47]:
GW(C, = ( + ||D|
max tr(CPDPT) PEErN
(3)
where E:= (P E Rx ; P1 = 11,1, :=
IIC =
Σ
C2 'y'
(4)
Let TI be the set of n. x permutation matrices. The Birkhoff-von Neumann theorem asserts that the domain of coupling (É N)) is the convex hull of 11. In addition, 1I can be characterized by
= where O, = (P E R PT = PPT = 1).
(5)
3

---

Since both On and & are spectral constraints, [24] proposed using these two domains only:
OGW(C, D) + [ -2 max PEENO..
tr(CPDTT))
(6)
To summarize, the attacker tries minimize the margin by solving the discrete problem:
minx M(A+ + X), s.t., X X1 E (-A,,, A.j.. OGW(CA+X, CA) S on,
(7)
where CA+X and CA D are the base distance matrices for A + X and A. respectively. Since OGW is still intractable to compute, we will next review how [24] proposed to approximate it.
Lower bound of OGW for certificates To certify the robustness, one only needs optimize (7) with the discrete constraint relaxed into X; [-A Aiz]. If the optimal objective value remains above O, then robustness certified. To tackle the intractability of OGW, a conservative approach (no false positive) is to relax the feasible domain by replacing OGW with an efficient lower bound.
Although the optimal P in (2) still intractable solve, OGW admits an efficient lower bound that is inspired by the quadratic assignment literature [48]. To begin with, [48] noted that O n = 11 + VQVT : : ), where is any n (n 1) matrix satisfying V
and
VTV = 1. So denoting X := VTVVVVVVV XV and sx == 1 Xx for any compatible matrix X, we obtain
PEO,nE tr(CPDPT) sCSD + @C,
max
(8)
where Q(C, == max (tr(CQδQT) + tr(ETT)) E ===²cı QEO.-1
So a lower bound of OGW (named OGW1s) can be naturally derived by decoupling the two occur- rences of Q in Q(C, D):
OGW D) + +001+11011 SGSD 2Q,
(10)
where Quo(C, == max Q E0.-1
tr(CQ,DQ)) + max tr(ET Q2).
(11)
QrEO.-1
One can derive that Q2 is optimized V where UVAVVE is the singular value decomposition (SVD) of f.. This results in tr [T (TT(22== = || F. ||.. the trace norm, which the sum of its singular values. An optimal Q1 is P2P if C and D respectively admit eigen-decompositions Ô = P1 diag(Ap PTT and = Ps diag( P2) [49, 50J. This yields an optimal value of tr(C',,, (QT as A Ag. The overall computation costs On²)) and the gap arising from decoupling Q1 and Q2 small because in general, the matrix É is much smaller than Ô and D in magnitude, as noted by both [48] and [24].
Upper bound of OGW for the attacker A conservative estimate of whether the attack can be successful is obtainable by further restraining the feasible domain. This can be served by replacing OGW with its upper bound, which can be trivially achieved by locally optimizing Q in (9). We denote it as OGW ub- Locally optimizing over O, (a.k.a. Stiefel manifold) has been very well studied (51 [51-53), and we adopt straightforward approach of projected quasi-Newton, noting that the projection of any matrix Q on O, is simply UQV where the SVD of Q is AQV
As is shown by [24], both OGW and OGW are nonnegative, symmetric, and evaluates zero when C and D are isomorphic. Their square root also satisfies the triangle inequality. Experiments on graph classification and barycenter show that they well capture the structural dissimilarities between graphs. Similarly GW, we compute OGW in practice via OGW....
2.3 Convex lower bound of OGW
Although OGW,, minorizes OGW, is still not convex in its input C, falling short of the requirement of certification. We next derive a convex lower bound via Fenchel biconjugation. In general, case admits efficient recipes.
biconjugation can be computationally expensive, but interestingly,
Recall that in the context perturbation, we assume C and D correspond the new and original graphs, respectively, and our goal is to find a convex lower bound for the part of OGW(C, D) that

---

depends on C.i.e f(C):=||C13 - maxPEenO, )CCDP)) We first compute its Fenchel dual:
(R) = max c
() -)-((()} = max
+ max PEENO,
(CCPDPT))(12)
C
max max (I((R
+R+ PRP [| (13)
= PEEPO,
max
PEENOn C
à | + || pp + max
lr(RPDPT)
(14)
PEÊNO,
$ 1 || + | pp + n7 SRSD - Quo(R,
(15)
As f (= (f , the biconjugation), OGW(C, as a function of can be lower bounded by
OGW(C, 2 # [DII + f = 2/2 (IDII max(tr(R C) (R)))
(16)
R
(r( |||]|p n= SRSD z n² R
max
2ub (R, (D)
(17)
=: RCC)
(18)
The evaluation of (C())) requires solving a convex optimization, utilizing the closed form for Oub in (11). In the optimization for the certificate below, we will avoid such an optimization over R by considering the dual of (2C)), which can be easily read off from the objective of R in (17).
3 Convex Outer Approximation for Resistance Distance
So far, we have taken the distance matrix C as the source of variation. In the certification problem, however, variations originate from the perturbation X on the graph structure. So we will next relate X to Ca+x, and formulate a conver domain in X. Unfortunately, this is difficult, we resort to the convex outer approximation of the graph of X + CA4x. Such an approach has been commonly used in approximating the ReLU activation [31], and extend it multivariate setting via new approach of matching loss [28].
3.1 Using resistance distance as the base measure
Although the SP distance has enjoyed significant popularity, its computation requires a nontrivial discrete optimization, obstructing convex relaxation. As such, we propose using resistance distance as the base distance because it bona fide metric [26], admits a closed form, and costs (n²) to compute all-pair distance (same as SP distance). In Section 5.1 and 5.2, we will show that it not only eases computation, but also performs competitively on machine learning tasks. Let the Laplacian of the perturbed graph be L := diag(Ab (A1) Á. Then the resistance distance between node and j is
Cy= L/ + Ll, -2i1/-
(19)
where īt is the pscudo-inverse of L. Since we only consider connected undirected graphs, it follows _11 A closely related distance measure the commute time, which multiply the resistance distance by the volume of the graph (1 Ā1). Since the volume a scalar and relates closely with the global budget, it can be incorporated with ease discussed in Appendix A.
Íi (L +1++111 -11
In summary, letting Z = -(L+ 111 C' determined through X + - Āt C. As both the first two steps and the last two steps are affine, we will denote them as 7.x and Cz respectively. Only the step of L. Z nonlinear, posing the major challenge we will address next.
3.2 Convex outer approximation of matrix inversion
Let S4 and S++ be respectively the positive semi-definite and positive definite matrix cones sized n-by-n. We consider the set
F == (i. 2), ES ES ((-S++) 2 -f (1 i 0. Vi vi
5

---

The conditions on are naturally motivated from graph Laplacian, and it follows implicitly that L + 1111 E S++. A trivial choice of B:y is O. If we only allow adding edges, then Biy can be AAj.
Given strictly convex function F, the associated matching loss is defined [28]
(Z, (2)+ + F(Ø) tr(Z +))
(20)
and it is well known that the minimum value of & is 0, attained if, and only if, 2 = VF(().
Now consider F()) log dct( ( over & E S++. It is easy to show that F strictly convex,
V VF()) - Φ and |- (Z) = -n log det(- over Z E -S4+. VF - 7
Therefore, setting Z -0L (L 11 is equivalent to enforcing
=
- tr(z (L 1
11 )) 00
(21)
This has significantly reduced the difficulty of relaxation because almost all the nonlinearities have been subsumed by the convex functions 1 and F. The only remaining challenge is the bilinear term in trace, but it is much easier to relax than a general nonlinear function. In particular, by the property
of Laplacian, Z1 = -1 and Z E -S++. Let Ta = - -i and Tip = 2Zzj Zii Zjz for + j. Then T 2 elementwise. So it follows that
- (T(zT)) = (T - Tú - Tig) + Σ Ti:Li
(22)
it3
= 2 ΣTTLi + > Tas Eis Enj
(by L1=0)
ETyLLs 2 - Σ
BijTay. (23)
itj
it)
Let B be symmetric matrix such that tr(BZ) = 2 Eizj Bu = 1 E B:y - Zi. 2zz)
Then the constraint set F is enclosed by conver outer approximation as
Fout= {(L, Z) S+ x (-S++): L+ 111 S i1=
- 0, Lú SB3 Vi
(24)
Z1 - Fz) F " +
s 0}.
(25)
Overall, we relax the budget OGW as follows:
{X perturbation X satisfies OGW(C, CA) S dn)
(26)
= (X: OGW(C, Ca) S dn, (I, E F, C = Oz, i. -= Lx}
(27)
(by (17)) C (X: ((C2) & da, (Lx, E F]
(28)
(by F (X: : ((C2) & 8a, (Lx, 2) E Fouth.
(29)
Finally, we attain convex domain. The last two subsumptions summarize our key contributions of convex relaxation in Section 2.2 and 3, and we will experimentally demonstrate that they are tight.
4 Optimization of Attacks and Robustness Certificates with Relaxed OGW
Attacker algorithm As discussed in Section 2.2, an attacker solves (7) by resorting to an upper bound of OGW, requiring OGW... S &g. Here OGW ... only needs an efficient local optimization. To deal with the constraint, we resort to the Lagrange dual:
min X20 -Ex
M(A + X) + B.OGW..(CA-H. Ca) -n))
(30)
Given A, X can be optimized greedily as shown in Algorithm 2. To ease notation, denote WWWasCCA+x...
OGWas (CA+x, CA) as T(A + X). So the problem becomes a simple search for the smallest such that T(A + X) S ōg. and it can be solved by binary search as in Algorithm 1. Due to the lack of strong duality, the success of the attack is checked by the sign of M(A + X) at the X found by Algorithm 1, not by the sign of the final objective value in (30).
4.1 Certificate algorithm
When the GCN has a single hidden layer, [7] showed that (A) can be computed in a closed form over the domain of A., that is relaxed to [0, 1] (i * j), intersected with local and global budgets.

---

Algorithm 1: Attacking with binary search
Algorithm 2: Compute Xx for given À
Input: global budget 6, and OGW budget on
Ag A
< 1, and compute Xx via Algorithm 2.
for = 0, 1,,...,6---
do
T + Xx) 2 8n then
C. <- cost matrix for A,.
Double À until T(4 + Xx) S de
Q: f locally optimal Q in Q(Cr, CA)
< A (upper est.), < (lower est.)
for E all pairs of nodes do
If flipping edge e on A, violates any local budget then Ve + oo and continue A' f- adjacency matrix flipping on A,
else
Halve A until T(A + X 2 6n
I + A, u 2(
while u - 1> 0.01 (or any threshold) do
Update C for A'
A < (u I)/2
Ve (A') + (A')., where the Q in Q(C, CA) is initialized by Q:
T Xx) 2 óg then f- À else +
Return Xx
Ac+1 +- flip on A, the edge arg mine V.
Return Xx == As,
As a result, MM* can also be computed efficiently through a convex optimization. Since M minorizes M, we can confirm the robustness (i.e., (7) cannot be reduced to negative) if the lowest possible value of M is nonnegative over an even larger domain of X than that in (7). This is sufficient but not necessary condition, and the tightness of the relaxation can be verified via the percentage of graphs that can neither be certified as robust, nor successfully attacked by Algorithm 1.
Formalizing this idea, the certification algorithm needs to solve the following problem based on (29),
minx,2 2 M* (A XX, s.t., Xe X, 2(C2) 82, (Éx, Z) E Fout-
(31)
Plugging in the definition of Fout and noting that the conditions on É are automatically satisfied by a graph Laplacian, we explicitize the final convex optimization problem
min XEX,Z
M M (A+
(32)
s.t.
((Oz) S on, ZE = (Z E -S++ : 21 = = (Z) + F(Lx + !111 )) + - tr((tr(B) 0.
(33)
(34)
Optimization algorithm Solving this optimization efficiently requires appropriately leveraging the structure in the problem. Since both M and Ω involve an inner optimization, it will be very inefficient if we nest their evaluation inside the overall procedure. Noting that both M and Ω have a closed form, we will dualize these terms and introduce two Lagrange multipliers to enforce the inequalities (2(z)) S dg and (34):
min max max X ZEZ a20,720 U.S
-ar -z)-s00(SS)) (S)
(35)
ada +++ -x(() +
(36)
min max
max
MM + tr C2) -00C))a)(((00))
(37)
X XEX,ZEZ 020.200 U.V
-aón + + (2) + + + - -t +
(38)
The introduction of V makes the resulting objective concave in all the max variables (a, U, V). noting that as?" V /a) is the perspective function of Ω², hence convex. This is not the case in (35) because a222 is not jointly convex. Finally, swapping the min and max in (37), we obtain the dual objective. Fixing the max variables, we can 1) minimize over X by projected quasi-Newton because the objective is smooth and strongly convex, and the domain X' is simple (Appendix A.2); 2) minimize over Z, which admits closed-form solution. We defer the details to Appendix A.3. Finally, we maximize over (a, y, U, V by L-BFGS-B [54], terminating once the dual objective gets positive.
Remark on connected graph. As we set up above, the graphs under consideration are always connected. This is the case for all the (original) graphs in our datasets. a perturbation makes graph disconnected, then both Q and OGW will be infinity. Therefore the attacker in Algorithm I will automatically avoid dropping an edge e that disconnects graph, because the corresponding V. in Algorithm 2 will be infinity. As for the certificate, since F()) log det the term F(Lx 111 ) in (34) creates barrier to ensure Lx + 111 is positive definite, hence connected.
7

---

Table Statistics the datasets
dataset
graphs
# class
# features
avc.
edge
min odge
max edge
avg. node
min node
max node
MUTAG
188
38
20
66
17.5
10
28
PTC-MR
25.0
142
13.0
COX2
86.0
118
41.0
74.0
120
35.0
Table 2: Graph classification accuracy
Graph Kernels
GW based SVM
OGW based SVM
Dataset
GK (k=3)
WL
SP
RD
SP
RD
Vec.
BZR
78.8 + 0.5
78.5 0.6
78.7 + 0.4
79.0 = 3,0
78.7 + 0.4
78.7 + 0,4
Attr.
COX2
78.2 0.4
78.2 0.4
78.2 + 0.4
78.2 = 0.4
78.2 + 0.4
78.2 + 0.4
Disc.
MUTAG
66.5 0.9
78.8
4.8
67.5
76.
+ 4.8
79.8 + 5.6
Attr.
PTC-MR
61.3 + 2.8
61.3 2.8
56.1 + 0.6
56.4 1.3
57.9
5.4
59.0 1.00:000
Experimental Results
The goal of our experiments lies in two folds: i) verify that resistance distance (RD) well characterizes graph structures and performs better than or as well as SP distance in classification and barycenter problems, when applied under OGW and GW; ii) demonstrate the effectiveness of our attack and certificate algorithms on real datasets, thereby confirming the tightness our relaxations. The code is available at [55].
Datasets. We experimented on four graph datasets whose statistics are given in Table [56]. They contain collection of molecules where the vertices represent atoms and edges are chemical bonds. The class label represents certain property of the molecules, e.g., mutagenic effect on specific bacterium (MUTAG) and carcinogenicity of compounds for male rats (PTC-MR), BZR and COX2 consist of ligands for the benzodiazepine receptor and cyclooxygenase-2 inhibitors, respectively.
5.1 Effectiveness of resistance distance in classification
To verify the effectiveness of resistance distance, first followed [16] study the graph classifica- tion accuracy of an SVM, whose kernel (C, D) is defined as exp (-y. OGW(C, D)) and the base measure for OGW is RD SP distance. We split the dataset into 75% / 25% for training / testing, and tuned the and regularizer weight in SVM by 5-fold cross validation on the training set.
The accuracy achieved by SVM based on GW and OGW is presented in Table 2. In addition, we also present graph kernels including graphlet sampling [57] and Weisfeiler-Lehman method [9] as the baselines. Clearly, taking resistance distance as the base measure produces similar better performance than SP distance under both GW and OGW.
5.2 Effectiveness of resistance distance barycenter
Furthermore, we also validated the resistance distance the barycenter problem. Given a set of structured data represented as graphs (D; 1,,,,..,, S). finds the Fréchet mean defined as arg ming Σ Ad,(C, D:), where d can GW and OGW, and uniform weights X are endowed on all the examples in [12]. We generated 8 cycle-like graphs with structured noises from order 15 to 25 (Figure 1), and constructed the barycenters of 20 nodes with respect to GW and OGW discrepancies under the base measure of SP and RD. Following Section 3 of [24], took block coordinate update between C' and P. in (6), where the former has a closed form and the latter is locally optimized inside GW and OGW.
Figure shows the results of constructed barycenter with different discrepancies and base measures. Clearly, both SP and RD capture the key structure property (cycle graph) with some additional structural noise under GW and OGW. hard to differentiate which structure is better in the context of noised samples.

---

(a) GW + SP (b) GW+RD RD
(c) OGW + SP (d) OGW RD Figure Barycenters
Figure 1: Synthetic graph samples
DGV
100
100
15
80
Graphss
of Graphs
1.0
60
60
Certifially Rebust
Certifiably Robust
20
Carti cortifiably Mulnerablle
20
Cartifiably Vulrerable
0.0
10
10.0)
Figure 3: Gap between and
(a) Robust training and dn
(b) Robust training and ón 10
OGW
100
6g
5.
Graphs
90
Graphs
0.1
10-
0.0
0.4
0.2
0.0
10
10
6g
(c) Certificate
(d) Attack
Figure 4: F and Ω attack on
graph No. 125 of MUTAG
Figure 5: Fraction of robust and vulnerable graphs on MUTAG
5.3 Performance of certificates and attacks
We next measure the effectiveness of our robustness certificate and attack algorithm jointly, and the criterion is the fraction of graphs that are neither certified as robust nor vulnerable (i.., successfully attacked). Due to space limitation, we only report the result of MUTAG in the main paper, and defer the result of the other three datasets to Appendix B. To the best of our knowledge, there no existing certification algorithm that addresses GW OGW budgets, except generic global optimization techniques which do not scale well when nested inside the overall problem (7).
Settings. Following [7], we split each dataset into 30%, 20%, and 50% for training, validation, and testing, respectively. A GCN model was then learned using single linear convolutional layer with 64 hidden nodes, followed by average pooling. [7] also constructed M with ReLU activation, but showed larger gap than linear activation. Since our focus here is on the tightness of certificate and attack under OGW, we would like to insulate the complication from ReLU and hence focused on linear activation. Following [5, 36), the GCN is trained with a hinge loss that promotes large margin from (1) for robustness: Eesy max (0, + max (A) (A))), where A is optimized under the budget of 8 1 and d, = 10.

---

Results. To start with, we empirically checked the tightness of convexified OGW. We took the first graph in the MUTAG dataset, and randomly perturbed its structure (adding or deleting edges) for 20 times with the global budget 6g varied from to 10. Figure 3 shows the average values of OGW and Q with resistance distance used as the base measure. As 0g increases, both OGW and S2 grow, but not monotonically. This is consistent with the fact that perturbing multiple edges may just lead to small changes GW and OGW due to isomorphism. Moreover, the gap between OGW and 12 gets wider with higher og. but their relative difference remains almost intact.
Figure shows the fraction of certifiably robust graphs in the lower green area, and 100 minus the fraction of certified vulnerable graphs in the upper red area. This leaves the white area showing the gap of undetermined graphs, and a narrow white area indicates the effectiveness of both the certificate and the attacker. Here, we fixed 6/ = 1, which is sufficient for the global budget óg on MUTAG.
Sub-plots (a) and (b) present the result for óg and 10, respectively. The gap grows with 6g and stays below 20% of the graphs. Sub-plots (c) and (d) provide a clearer comparison, between different values of og. over the performance of certificate and attack. Increasing the value of óα enlarges the feasible domain in (33), allowing more (less) graphs to be certified vulnerable (robust).
Figure 4 shows, for graph No. 125 in MUTAG, the value of OGW and M as 6, is increased and ón = 1. Interestingly, the increase of 6g does not monotonically consume more budget in Q2 which is consistent with the property of $2.
We additionally compared the performance of our vanilla and robust one-layer GCN model with an MLP model with node feature only, and two other state-of-the-art models, namely MemGNN [58] and FactorGCN [59]. The results are deferred to Appendix E.
Conclusion
We designed new convex lower bound for the orthogonal Gromov-Wasserster Wasserstein distance based on Fenchel biconjugation. Combined with a convex relaxation of the resistance distance using matching loss, it provides tight certificate of robustness for graph classification with GCNs.
Future work can extend the approach to certifying distributional robustness, and further leverage the closed form of resistance distance for provable optimization graphs. It is noteworthy that relaxation of OGW with resistance distance orthogonal to the graph classifier itself. When the classifier is changed, one will only need to re-derive the expression of M** for the risk margin. The constraints in (30) and (32), however, remain intact, and that part is our contribution. will also be interesting extend GCN to multiple layers GCN, by, e.g., leveraging the convex envelop discussed in Appendix D of [7].
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the National Science Foundation under Grant No. 1910146.
References
[1] D. Zügner, A. Akbarnejad, and S. Günnemann. Adversarial attacks neural networks for graph data. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pp. 2847-2856. ACM, 2018
[2] K. Xu, H. Chen, S. Liu, P.-Y. Chen, T.-W. Weng, M. Hong, and X. Lin. Topology attack and defense for graph neural networks: An optimization perspective. In International Joint Conference Artificial Intelligence (IICAI). 2019.
[3] J. Jia, B. Wang, X. Cao, and N. Z. Gong. Certified robustness of community detection against adversarial structural perturbation via randomized smoothing. International Conference on the World Wide Web (WWW). 2020.
[4] A. Bojchevski, J. Klicpera, and S. Günnemann. Efficient robustness certificates for discrete data: Sparsity- aware randomized smoothing for graphs, images and more. In International Conference Machine Learning (ICML). 2020.
10

---

[5] A. Bojchevski and S. Günnemann. Certifiable robustness to graph perturbations. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
[6] D. Zügner and S. Günnemann. Certifiable robustness of graph convolutional networks under structure perturbations. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD). 2020.
[7] H. Jin, Z. Shi, A. Peruri, and X. Zhang, Certified robustness of graph convolution networks for graph classification under topological attacks. Neural Information Processing Systems (NeurIPS). 2020.
[8] S. V. N. Vishwanathan, N. N. Schraudolph, I. R. Kondor, and K. M. Borgwardt. Graph kernels. Journal of Machine Learning Research, 140);:
2010.
[9] N. Shervashidze, P. Schweitzer, E. J. van Leeuwen, K. Mehlhorn, and K. M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Reseurch, 12:2539-2561, 201 1.
[10] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 14(4):18-42 2017.
[11] M. Defferrard, X. Bresson, and Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems (NeurIPS). 2016.
[12] G. Peyre, M. Cuturi, and J. Solomon. Gromov- Wasserstein averaging of kernel and distance matrices. In International Conference on Machine Learning (ICML). 2016.
[13] Memoli. Gromov- Wasserstein distances and the metric approach object matching. Foun- dutions of Computational Mathematics, 1 11:41 17-77777 2011.
[14] Y. Yan, W. Li, H. Wu, H. Min, M. Tan, and Q. Wu. Semi-supervised optimal transport for heterogeneous domain adaptation. In International Joint Conference on Artificial Intelligence (IJCAT). 2018.
[15] D. Alvarez-Melis and T. Jaakkola. In Conference on Empirical Methods in Natural Language Processing (EMNLP). 2018.
alignment of word embedding spaces.
[16] T. Vayer, L. Chapel, R. Flamary, R. Tavenard, and N. Courty. Optimal transport for structured data with application on graphs. In International Conference on Machine Learning (ICML). 2019.
[17] D. Ezuz, Solomon, G. Kim, and M. Ben-Chen. GWCNN: A metric alignment layer for deep shape analysis. Comput. Gruph. Forum, 36(5):49-57, 2017.
[18] S. Cohen and D. Sejdinovic. On the Gromov-Wasserster distance and coupled deep generative models. In NeurIPS 2019 Workshop on Optimal Transport & Machine Learning. 2019.
[19] H. Xu, D. Luo, H. Zha, and L. Carin. Beaamov-Wasserstchi learning for graph matching and node embedding. In International Conference on Machine Learning (ICML). 2019.
[20] H. Xu, D. Luo, and L. Carin. Scalable Wassersenn learning for graph partitioning and matching. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
[21] A. Sinha, Namkoong, and Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations (ICLR). 2018.
[22] E. Wong, F. Schmidt, and Z. Kolter. Wasserstein adversarial examples via projected sinkhorn iterations. In International Conference on Machine Learning (ICML). 2019.
[23] S. Chowdhury and F. Mémoli. The Haaomoy-Wassesseenn distance between networks and stable network invariants. Information and Inference: A Journal of the IMA, 8(4):757-787, 2019.
[24] H. Jin, Z. Yu, and X. Zhang. Orthogonal Gromov- Wasserstein discrepancy with efficient lower 2022.
bound, arXiv:2205.0080
[25] G.-H. Lee, Y. Yuan, S. Chang, and T. Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Newral Information Processing Systems (NeurIPS). 2019.
[26] D. J. Klein and M. Randie. Resistance distance. Journal of Mathematical Chemistry, 12(81- 95):1-31, 1993.
[27] U. von Luxburg, A. Radl, and M. Hein. Hitting and commute times large random neighbor- hood graphs. Journal of Machine Learning Research, 15551)117, 2014.
11

---

[28] P. Auer, M. Herbster, and M. K. Warmuth. Exponentially many local minima for single neurons. In Advances in Neural Information Processing Systems 9, 1996.
[29] R. Bunel, A. De Palma, A. Desmaison, K. Dvijotham, P. Kohli, P. H. S. Torr, and M. Kumar. Lagrangian decomposition for neural network verification. In Conference on Uncertainty in Artificial Intelligence (UAI). 2020.
[30] S. Singla and S. Feizi. Second-order provable defenses against adversarial attacks. In Interna- tional Conference on Machine Learning (ICML). 2020.
[31] E. Wong and J. Z. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning (ICML). 2018.
[32] H. Zhang, T.-W. Weng, P.-Y. Chen, C.-J. Hsieh, and L. Daniel. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems (NeurIPS). 2018.
[33] T.-W. Weng, H. Zhang, H. Chen, Z. Song, C.-J. Hsich, D. Boning, I. S. Dhillon, and L. Daniel. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning (ICML). 2018.
[34] K. (DioDvij,hham, R. Stanforth, S. Gowal, T. Mann, and P. Kohli. A dual approach to scalable verification of deep networks. In Conference on Uncertainty in Artificial Intelligence (UAI). 2018.
[35] G. Katz, C. Barrett, D. Dill, K. Julian, and M. Kochenderfer. Reluplex: An efficient smtsolver for verifying deep neural networks. In International Conference on Computer Aided Verification (CAV). 2017.
[36] D. Zügner and Günnemann. Certifiable robustness and robust training for graph convolutional networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pp. 246-256, ACM, 2019.
[37] J. M. Cohen, E. Rosenfeld, and J. Z. Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning (ICML). 2019.
[38] B. Li, C. Chen, W. Wang, and L. Carin. Certified adversarial robustnesswith additive noise. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
[39] M. Lécuyer, V. Atlidakis, R. Geambasu, D. Hsu, and S. Jana. Certified robustness to adversarial examples with differential privacy. IEEE Symposium on Security and Privacy (S&P). 2019.
[40] A. Raghunathan, J. Steinhardt, and P. Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations (ICLR). 2018.
[41] A. Raghunathan, J. Steinhardt, and P. Liang. Semidefnnite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems (NeurIPS). 2018.
[42] S. Singla and S. Feizi. Robustness certificates against adversarial examples for ReLU networks. 1rXiv:1902.01233. 2019.
[43] M. Cisse, P. Bojanowski. Grave, Y. Dauphin, and N. Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning (ICML). 2017.
[44] C. Anil, J. Lucas, and R. Grosse. Sorting out Lipschitz function approximation. In International Conference Machine Learning (ICML). 2019.
[45] H. D. Sherali and C. H. Tuncbilek. A coformulatonn-conveiffiee nonconvex quadratic programming problems. Journal of Global Optimization, 7(1):1-31, 1995.
approach for solving
[46] T. Vayer, R. Flamary, R. Tavenard, L. Chapel, and N. Courty. Sliced Gromov-Wassersein. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
[47] T. C. Koopmans and M. Beckmann. Assignment problems and the location of economic activities. In Econometrica. Journal of the Econometric Society. 1957.
[48] W. Hadley, F. Rendl, and H. Wolkowiez. new lower bound via projection for the quadratic assignment problem. Mathematics of Operations Research, 17(3):727-73, 1992.
12

---

[49] F. Rendl and H. Wolkowicz. Applications of parametric programming and eigenvalue maxi- mization to the quadratic assignment problem. Mathematical Programming: Series and B, 53(1-3):63-78, 1992.
[50] S. Umeyama. An eigendecomposition approach to weighted graph matching problems. IEEE Transactions Patlern Analysis and Machine Intelligence, 10(5):695-703, 1988.
[51] P.-.. Absil, R. Mahony, and R. Sepulchre. Oplimization Algorithms on Matrix Manifolds. Princeton University Press, 2009,
[52] Z. Wen and W. Yin. A feasible method for optimization with orthogonality constraints. Mathe- matical Programming. 142:397-434, 2013.
[53] K. T. Arasu and M. T. Mohan. Optimization problems with orthogonal matrix constraints.
Numerical Algebra. Control & Optimization, 8(4):413 440, 2018.
[54] R. Byrd, P. Lu, J. Nocedal, and C. Zhu. A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific Computing. (6(5):1190-1)) 1208, 1995.
[55] Online Supplementary. Supplementary material including code. httpa:///gituub.oom/coeo cert_ogu.
[56] TUDataset. Tudataset. https://chrsmrr ceneerssggitt github. io/astasett/bbos/hoon///
[57] N. Przulj. Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2)xe177-<183, Jan 2007.
[58] A. H. Khasahmadi, K. Hassani, Moradi, L. Lee, and Q. Morris. Memory-based graph networks. In International Conference Learning Representations. 2020.
[59] Y. Yang, Z. Feng, M. Song, and X. Wang. Factorizable graph convolutional networks. Advances in Neural Information Processing Systems, 33:20286-20296 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
13

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "sw5zDWZ7D3", "reviewer": "Reviewer_cA6U", "summary": "In this paper, the authors consider the certification and attack of graph convolution network-based classifier.\nIn this work, the authors proposed an orthogonal Gromov-Wasserstein (OGW )discrepancy to quantify the strength of the attack on graph topology.\nThe OGW achieves a convex approximation of the original GW distance, which can be computed efficiently.\nMoreover, OGW yields a tight outer convex approximation for resistance distance on graph nodes.\nExperimental results demonstrate that the OGW-based resistance distance can be used to achieve kernel-based graph classification and works better than the shortest path-based method. \nAdditionally, the authors also verified the rationality of using OGW-based threats to attack and certification of GCN classifiers.", "questions": "(1) Line 109, Eq.(7), what is the difference between E and \\hat{E}?\n\n(2) Line 134, Eq.(14), why do we need the notation \"f^{**}\"?\n\n(3) Line 142, what is the difference between D and \\mathcal{D}?\n\n(4) Line 221, what is the definition of Omega^{*}? What is the difference between M^* and M^**?\n\n---- after rebuttal ----\nThe authors explained the logic behind their writing and revised the submission based on some of my comments.\nAlthough I am not an expert in this field, I am willing to change my score to 5.\n\n", "limitations": "Although I am not an expert in this field, I believe that this paper should be rewritten completely. Its current status is not reading-friendly.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weaknesses:\n\n(1) I am not an expert on model certification and attack, but I think the organization of the paper is questionable. I don't think introducing OGW in section 2 is a good idea. The authors should introduce the target problem or the task before introducing the technique part, such that the readers can obtain a big picture about what the authors did and what key challenges they solved. \n\n(2) There are many notations used without definitions, which makes the paper hard to follow. (See the questions below)", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nnpOKy2muQx", "reviewer": "Reviewer_hBdY", "summary": "The authors propose a robustness certificate for graph classifiers under orthogonal Gromov-Wasserstein threats which are sensitive to whether two graphs are isomorphic. They use a (convex relaxation) of the resistance distance as the underlying metric, and derive a convex lower bound of OGW via Fenchel biconjugation. This gives them a sound but incomplete certificate. They also propose a complementary attack to show non-robustness. They evaluate their certificate on graph classification tasks using a single layer linear GCN.", "questions": "1.  Can the certificate be applied to multi-layer GCNs, and if yes, how do the results change? \n2.  How do the plots in Fig. 3 change for larger values of local budget?\n3.  Given very large (practically infinite) values of local and global budget and some seed original graph, what are all the reachable graphs that satisfy the OGW constraint? It would be helpful to provide a few examples, starting with small values of $\\delta_\\Omega$ and gradually increasing it. \n4. Same as above, but now also enforcing the local and global budgets.\n5. What is the accuracy of the certified model in section 5.3. and how does it compare to SOTA (non-certifiable) models?\n6. How do vanilla-trained models perform and does robust training decrease the clean accuracy?", "limitations": "The authors do not explicitly discuss the limitations of the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written and easy to follow. The problem that they tackle is very important since it is moving us beyond simple threat models such as global and local edge perturbations that effectively ignore the graph structure. The motivation to use the Gromov-Wasserstein discrepancy is sound, and the chosen relaxations (resistance distance instead of shortest path, orthogonal GW) are necessary to make the certificate tractable. The technical contributions are significant. Since the authors also propose a complementary attack it is possible to experimentally evaluate the tightness of the proposed certificate by looking at the fraction of non-verifiable graphs (neither robust nor non-robust).\n\nThe main weakness of the paper is the experimental evaluation. The certificates and attacks are evaluated only fora a GCN model using a single linear convolutional layer followed by average pooling (see Q1). Moreover, most of the experiments are performed with a fixed local budget which might be over-constraining the set of solutions leading to false sense of security w.r.t. tightness (see Q2).\n\nWhile the final threat model is definitely a move in the right direction it is not as interpretable as simple edge perturbations. It would be helpful if the authors can provide more intuition (see Q3 and Q4).\n\nThe authors do not discuss whether there is an accuracy vs. robustness tradeoff (see Q5 and Q6). While they do show the graph classification performance in section 5.1. these are for different models, and not the one they are certifying. Relatedly, I think that sections 5.1. and 5.2 distract the reader from the main message. While they provide interesting insights that should perhaps be relegated to the appendix. The additional space can be used to address some of the questions below.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FOTQ5pYZ-PV", "reviewer": "Reviewer_yoMg", "summary": "The papers consider certifiable certificates under the Orthogonal Gromov Wasserstein discrepancy (OGW). This contrasts with other graphs “distances” used in the literature, such as L1 distance between the adjacency matrices. The advantage of OGW is that it considers symmetries/isometries and does not rely on a fixed node ordering. To compute the certificate, the authors use convex relation. More specifically, they propose using the resistance distance as the metric space on the graph (as opposed to the more commonly used shortest path metric) and design a convex relaxation of this computation. Secondly, they give a convex relation of the OGW discrepancy measure. The authors demonstrate the certificate on a single-layer GCN graph classifier. ", "questions": "I have a few small questions:\n\n- “bona fide distance”, do the authors just mean metric?\n- “but the Kantorovich dual no longer exists” (line 36), does this line mean it exists for the Gromov Wasserstein distance but not the discrepancy?\n- Why setting Z is equivalent to (20)?\n- Why does Z1 = -1?\n- Line 105, what is the spectral constraint of \\mathcal{E}? Can the authors comment on why them being a spectral constraint is a reason to use just them?", "limitations": "The main limitations of the proposed method are that is does not scale that well, and it is not clear how it would perform with models beyond the very simple model they consider.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper addresses an interesting and important problem of certifying a graph classifier. The problem is extended beyond the usual global and local budget to consider a budget under the Gromov Wasserstein discrepancy (OGW). To the best of the authors knowledge, as well as my knowledge, they are the first to consider an extension to a budget that considers isometry. I do wonder however, if when combined with local and global budgets, if this can be taken advantage of. For example, if many edges are flipped to give an isometric graph, the OGW will be zero, but the local and global budgets will still be violated.\n\nIn general I think the experimental section is well written. The authors do a good job of motivating the use of effective distance, and give a convincing argument for its use by through SVM classifiers and barycenter visualisation. Unfortunately, the authors only experimented with a very simple model. As I understand it the model is a GCN convolutional layer with 64 hidden units, followed by an averaging pooling and presumably a linear layer afterwards, with no activation functions. This can be written as 1/n \\mathbf{1} A X W_1 W_2 where  1/n \\mathbf{1}  gives the pooling, A X W_1 is the GCN layer and W_2 is the final layer. Since there are no non-linearities, we can tie the weights W_1 W_2 to get an equivalent model and see its equivalent to a GCN with a single hidden unit followed by an averaging of the node outputs. It's not actually clear to me if this certificate could be used on more complex models without further modification and, if so if it would become too loose to be a useful certificate. It would be appreciated if the authors could comment on this or even better demonstrate their method on a slightly more complex model.  \n\nThe other weakness is the scalability of the certificate. The authors are upfront in the paper that the certificate is O(n^3). As shown in figure 9, the certificate takes a few minutes to compute, even for very small graphs. I wonder if it's feasible to run a certificate like this on something like COLLAB graphs? Would the authors consider extending figure 9 or commenting on the sorts of time required for graphs of sizes 50, 100 or 200 nodes? \n\nhave some other minor comments.\n- Might help to point out that the coupling is the set of doubly stochastic matrices (line 104).\n- Expanding on some of the derivations in an appendix would be useful. For example, I could not follow lines (11) and (12). There was also some parts in Section 3.2 I did not follow, for example why setting Z is equivalent to (20). And why Z1 = -1.\n- Might be useful to clarify what “Vec. Attr.” and “Disc. Attr.” mean in table 2.\n\nIn general, I think the paper is original and of high quality. Despite the weaknesses I've mentioned, I think it is a good paper demonstrating how to use OGW in a certificate. I think this paper can inspire future research into certificates that consider graph distances/discrepancies beyond those that assume fixed node orderings and that this is important as most GNNs are invariant to node reorderings (i.e. node permutation) \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept