  Representation learning of graph-structured data is challenging because both
graph structure and node features carry important information. Graph Neural
Networks (GNNs) provide an expressive way to fuse information from network
structure and node features. However, GNNs are prone to adversarial attacks.
Here we introduce Graph Information Bottleneck (GIB), an information-theoretic
principle that optimally balances expressiveness and robustness of the learned
representation of graph-structured data. Inheriting from the general
Information Bottleneck (IB), GIB aims to learn the minimal sufficient
representation for a given task by maximizing the mutual information between
the representation and the target, and simultaneously constraining the mutual
information between the representation and the input data. Different from the
general IB, GIB regularizes the structural as well as the feature information.
We design two sampling algorithms for structural regularization and instantiate
the GIB principle with two new models: GIB-Cat and GIB-Bern, and demonstrate
the benefits by evaluating the resilience to adversarial attacks. We show that
our proposed models are more robust than state-of-the-art graph defense models.
GIB-based models empirically achieve up to 31% improvement with adversarial
perturbation of the graph structure as well as node features.
