Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors consider the certification and attack of graph convolution network-based classifier.
In this work, the authors proposed an orthogonal Gromov-Wasserstein (OGW )discrepancy to quantify the strength of the attack on graph topology.
The OGW achieves a convex approximation of the original GW distance, which can be computed efficiently.
Moreover, OGW yields a tight outer convex approximation for resistance distance on graph nodes.
Experimental 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. 
Additionally, the authors also verified the rationality of using OGW-based threats to attack and certification of GCN classifiers.
strengths_and_weaknesses: Weaknesses:

(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. 

(2) There are many notations used without definitions, which makes the paper hard to follow. (See the questions below)
questions: (1) Line 109, Eq.(7), what is the difference between E and \hat{E}?

(2) Line 134, Eq.(14), why do we need the notation "f^{**}"?

(3) Line 142, what is the difference between D and \mathcal{D}?

(4) Line 221, what is the definition of Omega^{*}? What is the difference between M^* and M^**?

---- after rebuttal ----
The authors explained the logic behind their writing and revised the submission based on some of my comments.
Although I am not an expert in this field, I am willing to change my score to 5.


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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
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.

In 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.  

The 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? 

have some other minor comments.
- Might help to point out that the coupling is the set of doubly stochastic matrices (line 104).
- 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.
- Might be useful to clarify what “Vec. Attr.” and “Disc. Attr.” mean in table 2.

In 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) 

questions: I have a few small questions:

- “bona fide distance”, do the authors just mean metric?
- “but the Kantorovich dual no longer exists” (line 36), does this line mean it exists for the Gromov Wasserstein distance but not the discrepancy?
- Why setting Z is equivalent to (20)?
- Why does Z1 = -1?
- 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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).

The 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).

While 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).

The 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.
questions: 1.  Can the certificate be applied to multi-layer GCNs, and if yes, how do the results change? 
2.  How do the plots in Fig. 3 change for larger values of local budget?
3.  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. 
4. Same as above, but now also enforcing the local and global budgets.
5. What is the accuracy of the certified model in section 5.3. and how does it compare to SOTA (non-certifiable) models?
6. 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.
review_title: null

Meta-review: metareview: This paper proposes a robustness certificate for graph classifiers under orthogonal Gromov-Wasserstein (OGW) threat models. OGW considers symmetries/isometries and does not rely on a fixed node ordering. The computation of the certificate is based on convex relations. The certificate is demonstrated on a single-layer GCN graph classifier. The paper addresses the interesting and important problem of certifying a graph classifier. The reviewers found the paper original and of high quality. During the rebuttal period, the authors provided an insightful discussion on their work and addressed most of the questions and concerns raised by the reviewers.
confidence: Certain
Decision: Accept