Explaining and Adapting Graph Conditional Shift

• URL: http://arxiv.org/abs/2306.03256v1
• Date: Mon, 5 Jun 2023 21:17:48 GMT
• Title: Explaining and Adapting Graph Conditional Shift
• Authors: Qi Zhu, Yizhu Jiao, Natalia Ponomareva, Jiawei Han, Bryan Perozzi
• Abstract summary: Graph Neural Networks (GNNs) have shown remarkable performance on graph-structured data. Recent empirical studies suggest that GNNs are very susceptible to distribution shift.
• Score: 28.532526595793364
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) have shown remarkable performance on graph-structured data. However, recent empirical studies suggest that GNNs are very susceptible to distribution shift. There is still significant ambiguity about why graph-based models seem more vulnerable to these shifts. In this work we provide a thorough theoretical analysis on it by quantifying the magnitude of conditional shift between the input features and the output label. Our findings show that both graph heterophily and model architecture exacerbate conditional shifts, leading to performance degradation. To address this, we propose an approach that involves estimating and minimizing the conditional shift for unsupervised domain adaptation on graphs. In our controlled synthetic experiments, our algorithm demonstrates robustness towards distribution shift, resulting in up to 10% absolute ROC AUC improvement versus the second-best algorithm. Furthermore, comprehensive experiments on both node classification and graph classification show its robust performance under various distribution shifts.

Related papers

• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• Graph Out-of-Distribution Generalization via Causal Intervention [69.70137479660113]
  We introduce a conceptually simple yet principled approach for training robust graph neural networks (GNNs) under node-level distribution shifts. Our method resorts to a new learning objective derived from causal inference that coordinates an environment estimator and a mixture-of-expert GNN predictor. Our model can effectively enhance generalization with various types of distribution shifts and yield up to 27.4% accuracy improvement over state-of-the-arts on graph OOD generalization benchmarks.
  arXiv  Detail & Related papers  (2024-02-18T07:49:22Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  Graph Neural Networks (GNNs) show promising results for graph tasks. Existing GNNs' generalization ability will degrade when there exist distribution shifts between testing and training graph data. We propose a novel nonlinear graph decorrelation method, which can substantially improve the out-of-distribution generalization ability.
  arXiv  Detail & Related papers  (2023-12-19T12:25:10Z)
• Global Minima, Recoverability Thresholds, and Higher-Order Structure in GNNS [0.0]
  We analyze the performance of graph neural network (GNN) architectures from the perspective of random graph theory. We show how both specific higher-order structures in synthetic data and the mix of empirical structures in real data have dramatic effects on GNN performance.
  arXiv  Detail & Related papers  (2023-10-11T17:16:33Z)
• Structural Re-weighting Improves Graph Domain Adaptation [13.019371337183202]
  This work examines different impacts of distribution shifts caused by either graph structure or node attributes. A novel approach, called structural reweighting (StruRW), is proposed to address this issue and is tested on synthetic graphs, four benchmark datasets, and a new application in high energy physics.
  arXiv  Detail & Related papers  (2023-06-05T20:11:30Z)
• Evaluating Robustness and Uncertainty of Graph Models Under Structural Distributional Shifts [43.40315460712298]
  In node-level problems of graph learning, distributional shifts can be especially complex. We propose a general approach for inducing diverse distributional shifts based on graph structure. We show that simple models often outperform more sophisticated methods on the considered structural shifts.
  arXiv  Detail & Related papers  (2023-02-27T15:25:21Z)
• A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks [33.35609077417775]
  We characterize the mechanism behind the phenomenon via a non-asymptotic analysis. We show that oversmoothing happens once the mixing effect starts to dominate the denoising effect. Our results suggest that while PPR mitigates oversmoothing at deeper layers, PPR-based architectures still achieve their best performance at a shallow depth.
  arXiv  Detail & Related papers  (2022-12-21T00:33:59Z)
• Stable and Transferable Hyper-Graph Neural Networks [95.07035704188984]
  We introduce an architecture for processing signals supported on hypergraphs via graph neural networks (GNNs) We provide a framework for bounding the stability and transferability error of GNNs across arbitrary graphs via spectral similarity.
  arXiv  Detail & Related papers  (2022-11-11T23:44:20Z)
• From Spectral Graph Convolutions to Large Scale Graph Convolutional Networks [0.0]
  Graph Convolutional Networks (GCNs) have been shown to be a powerful concept that has been successfully applied to a large variety of tasks. We study the theory that paved the way to the definition of GCN, including related parts of classical graph theory.
  arXiv  Detail & Related papers  (2022-07-12T16:57:08Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• 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)

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.