Robust Learning on Graphs

Despite the recent success of graph neural networks (GNNs) in modeling graph-structured data, its vulnerability to adversarial attacks has been revealed, and attacks on both node features and graph structure have been designed. Direct extension of defense algorithms based on adversarial samples meets with the immediate challenge because computing the adversarial network costs substantially. Taking Graph Convolutional Networks (GCN) as a base model, we first present the work of adversarial training via latent perturbation which not only dispenses with generating adversarial networks, but also attains improved robustness and accuracy by respecting the latent manifold of the data. Next, given a threat model based on GCN, we investigate the certificate of robustness for the task of graph classification. Specifically, we develop a method based on Lagrangian dualization to provide a lower bound of classification margin. As a byproduct, we also come up with an efficient attack algorithm to serve an upper bound, measuring the tightness of certificates. Furthermore, to tackle the nonconvexity of activation functions, we propose another method based on the convex envelope, resulting in tight approximation bounds. Lastly, due to the intrinsic properties of graphs, we consider providing the certificate of robustness under permutation invariance. To address it, we first develop a new metric for graphs, named Orthogonal Gromov-Wasserstein (OGW) distance, which formulates a coupling between the structured data based on optimal transportation and optimizes over the orthogonal domain with tractable lower and upper bound. In addition, we build its Fenchel biconjugate to facilitate convex optimization in the certificate problem. By wrapping up with the classification margin criteria and deriving a tight convex envelope formulation, our methods construct the first robustness certificate for graph classification subject to structural permutation invariant constraint.