Subgroup Generalization and Fairness of Graph Neural Networks

Abstract

Despite enormous successful applications of graph neural networks (GNNs), theoretical understanding of their generalization ability, especially for node-level tasks where data are not independent and identically-distributed (IID), has been sparse. The theoretical investigation of the generalization performance is beneficial for understanding fundamental issues (such as fairness) of GNN models and designing better learning methods. In this paper, we present a novel PAC-Bayesian analysis for GNNs under a non-IID semi-supervised learning setup. Moreover, we analyze the generalization performances on different subgroups of unlabeled nodes, which allows us to further study an accuracy-(dis)parity-style (un)fairness of GNNs from a theoretical perspective. Under reasonable assumptions, we demonstrate that the distance between a test subgroup and the training set can be a key factor affecting the GNN performance on that subgroup, which calls special attention to the training node selection for fair learning. Experiments across multiple GNN models and datasets support our theoretical results.

arXiv commentNeurIPS 2021 Spotlight

References in corpus (18)

• Semi-Supervised Classification with Graph Convolutional Networks
• Simplifying Graph Convolutional Networks
• Junction Tree Variational Autoencoder for Molecular Graph Generation
• Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
• Pitfalls of Graph Neural Network Evaluation
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Revisiting Graph Neural Networks: All We Have is Low-Pass Filters
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• Compositional Fairness Constraints for Graph Embeddings
• Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm
• A Survey on The Expressive Power of Graph Neural Networks
• Measuring and Improving the Use of Graph Information in Graph Neural Networks
• Is Homophily a Necessity for Graph Neural Networks?
• A Primer on PAC-Bayesian Learning
• Contextual Stochastic Block Models
• Towards a Unified Framework for Fair and Stable Graph Representation Learning
• Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization

Cited by in corpus (6)

• A Comprehensive Survey on Deep Graph Representation Learning
• Alleviating Structural Distribution Shift in Graph Anomaly Detection
• Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Tools
• GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks
• FairSample: Training Fair and Accurate Graph Convolutional Neural Networks Efficiently
• Generalizability Analysis of Graph-based Trajectory Predictor with Vectorized Representation