PAC Learnability under Explanation-Preserving Graph Perturbations

• URL: http://arxiv.org/abs/2402.05039v1
• Date: Wed, 7 Feb 2024 17:23:15 GMT
• Title: PAC Learnability under Explanation-Preserving Graph Perturbations
• Authors: Xu Zheng, Farhad Shirani, Tianchun Wang, Shouwei Gao, Wenqian Dong, Wei Cheng, Dongsheng Luo
• Abstract summary: Graph neural networks (GNNs) 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. This work considers two methods for leveraging such perturbation invariances in the design and training of GNNs.
• Score: 15.83659369727204
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Imbalanced Graph Classification with Multi-scale Oversampling Graph Neural Networks [25.12261412297796]
  We introduce a novel multi-scale oversampling graph neural network (MOSGNN) that learns expressive minority graph representations. It achieves this by jointly optimizing subgraph-level, graph-level, and pairwise-graph learning tasks. Experiments on 16 imbalanced graph datasets show that MOSGNN i) significantly outperforms five state-of-the-art models.
  arXiv  Detail & Related papers  (2024-05-08T09:16:54Z)
• Generating In-Distribution Proxy Graphs for Explaining Graph Neural Networks [17.71313964436965]
  A popular paradigm for the explainability of GNNs is to identify explainable subgraphs by comparing their labels with the ones of original graphs. This task is challenging due to the substantial distributional shift from the original graphs in the training set to the set of explainable subgraphs. We propose a novel method that generates proxy graphs for explainable subgraphs that are in the distribution of training data.
  arXiv  Detail & Related papers  (2024-02-03T05:19:02Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. Due to the selection bias of training and testing data, distribution deviation is widespread. We propose OOD calibration to measure the distribution deviation of virtual samples.
  arXiv  Detail & Related papers  (2023-08-16T13:10:27Z)
• Diving into Unified Data-Model Sparsity for Class-Imbalanced Graph Representation Learning [30.23894624193583]
  Graph Neural Networks (GNNs) training upon non-Euclidean graph data often encounters relatively higher time costs. We develop a unified data-model dynamic sparsity framework named Graph Decantation (GraphDec) to address challenges brought by training upon a massive class-imbalanced graph data.
  arXiv  Detail & Related papers  (2022-10-01T01:47:00Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  We propose a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN) GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive.
  arXiv  Detail & Related papers  (2022-05-19T14:08:15Z)
• Graph-in-Graph (GiG): Learning interpretable latent graphs in non-Euclidean domain for biological and healthcare applications [52.65389473899139]
  Graphs are a powerful tool for representing and analyzing unstructured, non-Euclidean data ubiquitous in the healthcare domain. Recent works have shown that considering relationships between input data samples have a positive regularizing effect for the downstream task. We propose Graph-in-Graph (GiG), a neural network architecture for protein classification and brain imaging applications.
  arXiv  Detail & Related papers  (2022-04-01T10:01:37Z)
• Discovering Invariant Rationales for Graph Neural Networks [104.61908788639052]
  Intrinsic interpretability of graph neural networks (GNNs) is to find a small subset of the input graph's features. We propose a new strategy of discovering invariant rationale (DIR) to construct intrinsically interpretable GNNs.
  arXiv  Detail & Related papers  (2022-01-30T16:43:40Z)
• OOD-GNN: Out-of-Distribution Generalized Graph Neural Network [73.67049248445277]
  Graph neural networks (GNNs) have achieved impressive performance when testing and training graph data come from identical distribution. Existing GNNs lack out-of-distribution generalization abilities so that their performance substantially degrades when there exist distribution shifts between testing and training graph data. We propose an out-of-distribution generalized graph neural network (OOD-GNN) for achieving satisfactory performance on unseen testing graphs that have different distributions with training graphs.
  arXiv  Detail & Related papers  (2021-12-07T16:29:10Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  Semi-supervised learning (SSL) over graph-structured data emerges in many network science applications. To efficiently manage learning over graphs, variants of graph neural networks (GNNs) have been developed recently. Despite their success in practice, most of existing methods are unable to handle graphs with uncertain nodal attributes. Challenges also arise due to distributional uncertainties associated with data acquired by noisy measurements. A distributionally robust learning framework is developed, where the objective is to train models that exhibit quantifiable robustness against perturbations.
  arXiv  Detail & Related papers  (2021-10-20T14:23:54Z)
• Hyperbolic Graph Embedding with Enhanced Semi-Implicit Variational Inference [48.63194907060615]
  We build off of semi-implicit graph variational auto-encoders to capture higher-order statistics in a low-dimensional graph latent representation. We incorporate hyperbolic geometry in the latent space through a Poincare embedding to efficiently represent graphs exhibiting hierarchical structure.
  arXiv  Detail & Related papers  (2020-10-31T05:48:34Z)
• Contrastive Graph Neural Network Explanation [13.234975857626749]
  Graph Neural Networks achieve remarkable results on problems with structured data but come as black-box predictors. We argue that explicability must use graphs compliant with the distribution underlying the training data. We present a novel Contrastive GNN Explanation technique following this paradigm.
  arXiv  Detail & Related papers  (2020-10-26T15:32:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.