About the senario of ''Certifiable Robustness'' on graph.

[guyguygang]

Hi, Really nice work! When I read the paper, the senario of ''Certifiable Robustness'' on graph really confused me. Could we assume that we have the clean (unperturbed) graph data in this senario? If we have access to the clean graph, it seems that there could be some simple tricks to make the model "certifiable robustness". For example, we could force the model to allign its predictions with the unperturbed one. Please correct me if I made it wrong. Looking forward to your reply. Thanks a lot!

[abojchevski]

This is a good question. There are different potential answers.

First, recall that the guarantee which we get from the certificate is that given an observed graph G, the prediction will stay the same for some percentage of nodes for all graph G' that differ in some number of edges. Note, here I say observed and not clean since this guarantee holds regardless. How to interpret this guarantee in practice depends on additional assumptions you make.

If you assume that the observed graph at training time is clean, and that at test time the graph has not changed, then you are right, we trivially have provable robustness since it directly follows from the assumptions.

Another scenario is that the observed graph at training time is clean, but at test time the graph could have been perturbed. This is the evasion setting. Then a certificate like the one we propose is useful. You might ask now, why can't we simple use the clean train-time graph and ignore the potentially perturbed test-time graph. Well, you can imagine that the test-time graph has some useful information that we want to utilize (e.g. new clean edges) in addition to having some potentially perturbed edges. Or, it could be that we are in the inductive setting and we have new nodes at test time that have not been seen before. In both these cases a certificate like the one we propose is useful.

A different assumption is that the observed graph is already perturbed and that it differs from the clean graph (which we cannot see) in at most X edges. Now, if the certificate tells you that the observed graph has the same prediction when any X edges are perturbed, that implies that the observed graph has the same prediction as the clean graph (which we don't see). In other words, the certificate says that in the "ball" around the observed graph G all predictions are the same, and the clean graph is somewhere in that ball.

A different perspective is that the certificate is just something that gives you information about the stability of your model. If I have two models with same accuracy, but one is much more stable to small edge perturbations as measure by the certificate, I would pick the more stable one to put in production.

Hope this helps.

[guyguygang]

Hi Bochenski,

Thanks for your comprehensive reply and discussion on Github about the definition of certifiable robustness on graph data.

Under the inductive setting, I think the definition of certifiable robustness is clear and meaningful. As you point out, we can think of it as the stability of the model under potential perturbations.

My main concern is that under transductive settings, in which we can access all the label&unlabel data. The definition of certifiable robustness becomes unclear for me. Especially when I read one paper(Adversarial Immunization for Certifiable Robustness on Graphs) published in the WSDM21. According to my understanding of their method, they use too much information(labels of all nodes) to achieve its 'certifiable robustness', making me confused about the definition of certifiable robustness under the transductive setting. If labels of all nodes are accessible (no matter from ground truth or predictions on the clean graph), we could simply use a lookup table to make predictions, which is 'robust; since the predictions will not change in all cases.

I hope I make my concern clear. Thanks for your patience in answering my questions.

Best regards.