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.


翻译:尽管图形神经网络应用非常成功,但对其一般化能力的理论理解,特别是数据不独立和分布相同的节点任务(IID),却很少见。对一般化表现的理论调查有助于理解GNN模型的基本问题(如公平性)和设计更好的学习方法。在本文中,我们在非IID半监督的学习设置下,为GNN提供了一个新的PAC-Bayesian分析。此外,我们分析了未加标记节点不同分组的概括化表现,这使我们能够从理论角度进一步研究GNN的准确性(差异性)类型(不公平性)(不公平性)。在合理的假设下,我们证明试验分组与培训组合之间的距离可能是影响该分组GNN业绩的一个关键因素,这要求特别关注公平学习的培训节点选择。多个GNN模型和数据集的实验支持我们的理论结果。

0
下载
关闭预览

相关内容

【图神经网络导论】Intro to Graph Neural Networks,176页ppt
专知会员服务
125+阅读 · 2021年6月4日
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Linguistically Regularized LSTMs for Sentiment Classification
黑龙江大学自然语言处理实验室
8+阅读 · 2018年5月4日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
FORML: Learning to Reweight Data for Fairness
Arxiv
0+阅读 · 2022年2月3日
Arxiv
38+阅读 · 2020年12月2日
Arxiv
4+阅读 · 2020年10月18日
Arxiv
27+阅读 · 2020年6月19日
Arxiv
23+阅读 · 2018年10月1日
VIP会员
相关VIP内容
【图神经网络导论】Intro to Graph Neural Networks,176页ppt
专知会员服务
125+阅读 · 2021年6月4日
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Linguistically Regularized LSTMs for Sentiment Classification
黑龙江大学自然语言处理实验室
8+阅读 · 2018年5月4日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员