PAC Learnability under Explanation-Preserving Graph Perturbations
This work addresses sample efficiency in graph neural networks for applications like social networks and biology, but it is incremental as it builds on existing explanation and perturbation concepts.
The paper tackles the problem of improving graph neural network (GNN) learning by leveraging explanation-preserving graph perturbations, showing that explanation-assisted learning can reduce sample complexity arbitrarily compared to explanation-agnostic methods, and that data augmentation based on these perturbations can improve performance if in-distribution but harm it if out-of-distribution.
Graphical models capture relations between entities in a wide range of applications including social networks, biology, and natural language processing, among others. Graph neural networks (GNN) are neural models that operate over graphs, enabling the model to leverage the complex relationships and dependencies in graph-structured data. A graph explanation is a subgraph which is an `almost sufficient' statistic of the input graph with respect to its classification label. Consequently, the classification label is invariant, with high probability, to perturbations of graph edges not belonging to its explanation subgraph. This work considers two methods for leveraging such perturbation invariances in the design and training of GNNs. First, explanation-assisted learning rules are considered. It is shown that the sample complexity of explanation-assisted learning can be arbitrarily smaller than explanation-agnostic learning. Next, explanation-assisted data augmentation is considered, where the training set is enlarged by artificially producing new training samples via perturbation of the non-explanation edges in the original training set. It is shown that such data augmentation methods may improve performance if the augmented data is in-distribution, however, it may also lead to worse sample complexity compared to explanation-agnostic learning rules if the augmented data is out-of-distribution. Extensive empirical evaluations are provided to verify the theoretical analysis.