GNNCert: Deterministic Certification of Graph Neural Networks against Adversarial Perturbations

We thank the reviewers for appreciating paper writing and the constructive comments

Question-1: Vary $N$ depending on the graph size.

Thanks for pointing this out. We use a fixed number of sub-graphs on 8 datasets to be consistent. Our robustness guarantee against graph structure and node feature perturbation still holds when varying $N$ based on the number of nodes in a graph. For instance, we could set T_s=0.3 * \\#nodes\ in\ a\ graph. On MUTAG dataset, the certified accuracies are 90% and 54% when an attacker could arbitrarily add/delete 1 and 5 edges. We will add the discussion to our paper.

Question-2: No restrictions on the hash function (i.e., independent of edge structure and node features).

We don’t place restrictions on the hash function because we aim to resist arbitrary adversarial attacks (with bounded edge/node feature perturbations). If the hash function depends on the input’s edge structure and node features, then it could potentially be influenced by the attacker, making it more challenging to derive formal robustness guarantees against arbitrary attacks. We will add the discussion. Note that our GraphGuard is compatible with any hash function. Figure 6 shows our GraphGuard achieves similar performance with different hash functions.

Question-3: Certify robustness against node insertion/deletion.

Thanks for pointing it out. Our GraphGuard could be further extended to certify node insertion/deletion. In particular, we could divide nodes into different sub-graphs (using a hash function to calculate a group ID for each node), where each node only belongs to one group. Thus, inserting/deleting one node would influence at most one sub-graph, enabling us to derive the robustness guarantees. We added an experiment to validate this. On MUTAG dataset, our GraphGuard could achieve a 59% certified accuracy when an attacker could arbitrarily add/delete one node (note that the attacker could arbitrarily add/delete edges for that node).

Question-4: Local structure.

We note that our GraphGuard with structure (or feature) division could utilize all node features (or entire graph structure). For structure-feature division, our method could utilize local structure with a moderate number of sub-graphs. We agree with the reviewer that each sub-graph may lose local structure information when the number of sub-graphs is large, i.e., there is a tradeoff between accuracy and robustness.

We thank the reviewers for appreciating the novelty, significance, solid theory, and constructive comments!

Comment-1: The notation at the end of the line 4 on Page 4.

Thanks for pointing it out. It is indeed $H(\cdot)\\%T_s+1$. We will fix the typo.

Comment-2: The hash value depends on which node is visited first.

Sorry for the confusion. We note that each node has a node ID. We always put the node with a smaller ID first. We also add an experiment to put the node with a larger ID first on MUTAG dataset. The certified accuracy is 92% (smaller ID first) and 92% (larger ID first) when an attacker arbitrarily adds/deletes one edge, respectively. The results demonstrate that our method is insensitive to the orders of nodes. We will clarify and add results to our paper.

Comment-3: How node features are transformed into string representations.

Node features could be represented as a feature vector, where each feature value is a real number. We transform each feature value into a string. For instance, if the feature value is 0.12, we can transform it into the string “0.12”. Then, we concatenate the strings for different feature values. We will clarify as suggested.

Comment-4: Preference of hash-based sub-sampling over $\tau$ fraction-based sampling.

Our hash-based sub-sampling has the following advantages. First, our hash-based sub-sampling enables our defense to certify feature perturbation as well as both feature and structure perturbations for graph classification. By contrast, existing sub-sampling methods cannot. Second, hash-based sub-sampling divides a graph into sub-graphs deterministically while $\tau$ fraction-based sampling generates sub-graphs probabilistically. As a result, our method could provide deterministic robustness guarantees while existing methods cannot due to the randomness in their sub-sampling. Third, our hash-based division makes our defense very efficient (as shown in Table 1). The reason is that our hash-based sub-sampling divides a graph into a moderate number of (e.g., 30) sub-graphs. By contrast, existing $\tau$ fraction-based sampling requires sampling hundreds of sub-sampled graphs to estimate the robustness guarantees (as they utilize Monte-Carlo to estimate them). Our experimental results in Figure 8 (in Appendix) show the certified accuracy of existing methods is much worse when reducing the number of sub-sampled graphs for them.

In general, there is a tradeoff between utility (measured by the accuracy without attacks) and robustness. One limitation of our defense is that it also has such a tradeoff. For instance, when the number of groups is very large, the accuracy without attacks of our defense slightly drops. The experimental results show our defense achieves a better tradeoff than existing methods.

Comment-5: How to determine the values of $T_s$ and $T_f$.

In our experiment, we use a fixed $T_s=30$ and $T_f=30$ for all 8 datasets to be consistent. Additionally, we show the impact of $T_s$ and $T_f$ in Figures 4 and 5. Our results show GraphGuard could achieve better robustness guarantees when $T_s$ and $T_f$ are larger. We could set $T_s$ and $T_f$ based on the number of edges and nodes, respectively. In particular, we could set a larger $T_s$ and $T_f$ when the number of edges and nodes in a graph is larger to ensure better robustness.

We thank the reviewer for appreciating the solid theoretical contributions and constructive comments!

Question-1: Was the perturbation uniform noise?

Sorry for the confusion. The graph classifier built by our defense could resist arbitrary perturbations (e.g., uniform noise perturbation, carefully crafted perturbation by a malicious agent using a black or white-box attack) to a graph, once the total number of perturbed edges or number of nodes with perturbed features are bounded. For instance, with structure division, we derive a lower bound of the accuracy (i.e., certified accuracy) that our graph classifier could achieve on a testing dataset when an attacker could arbitrarily add/delete at most a number of edges (called perturbation size) to each testing graph. Take Figure 2 as an example. Our results show the accuracy drop of our graph classifier is within 3% when an attacker arbitrarily adds/deletes one connection to each testing graph. We will clarify.

Question-2: Add datasets for a realistic malicious agent scenario.

We test a real-world Twitter dataset [1] as suggested, where the task is to classify whether a user is fake or benign based on its ego network. We use the white-box attack in [2] to craft a small perturbation such that a graph classifier makes incorrect predictions. For a standard graph classifier (GIN), the accuracy drops from 76% to 2% when adding/deleting at most 5 edges to each testing graph. Under the same perturbation, the accuracy of our GraphGuard is 68% for perturbed testing graphs. The results demonstrate that our GraphGuard is robust against carefully crafted perturbations. We will incorporate the results and corresponding discussion into our paper.

[1] Zhang et al. “Backdoor Attacks to Graph Neural Networks”, 2022.

[2] Wan et al. "Adversarial attacks on graph classification via bayesian optimisation", 2021.