A common issue in graph learning under the semi-supervised setting is referred to as gradient scarcity. That is, learning graphs by minimizing a loss on a subset of nodes causes edges between unlabelled nodes that are far from labelled ones to receive zero gradients. The phenomenon was first described when optimizing the graph and the weights of a Graph Neural Network (GCN) with a joint optimization algorithm. In this work, we give a precise mathematical characterization of this phenomenon, and prove that it also emerges in bilevel optimization, where additional dependency exists between the parameters of the problem. While for GCNs gradient scarcity occurs due to their finite receptive field, we show that it also occurs with the Laplacian regularization model, in the sense that gradients amplitude decreases exponentially with distance to labelled nodes. To alleviate this issue, we study several solutions: we propose to resort to latent graph learning using a Graph-to-Graph model (G2G), graph regularization to impose a prior structure on the graph, or optimizing on a larger graph than the original one with a reduced diameter. Our experiments on synthetic and real datasets validate our analysis and prove the efficiency of the proposed solutions.


翻译:在半监督设置下,图学习中的一个常见问题是梯度稀缺现象。也就是说,通过对部分节点上的损失进行最小化来学习图会导致标记之间相距较远且没有标记的节点之间的边缘接收到零梯度。当优化图和图神经网络(Graph Neural Network,GCN)的权重时,这种现象被称为梯度稀缺现象。在这项工作中,我们对此现象进行了精确定义,并证明了它在双层优化中也会出现,其中问题的参数之间存在其他依赖关系。虽然对于GCNs,梯度稀缺现象是由于其有限的感受野而导致的,但我们表明这种现象也会在拉普拉斯正则化模型中出现,其梯度幅度随着到标记节点的距离指数级下降。为了缓解这个问题,我们研究了一些解决方案:我们建议使用Graph-to-Graph(G2G)模型进行潜在图学习,使用图正则化对图进行先验结构约束,或使用具有更小直径的较大图进行优化。我们在合成和真实数据集上进行的实验验证了我们的分析,并证明了所提出解决方案的有效性。

0
下载
关闭预览

相关内容

梯度的本意是一个向量(矢量),表示某一函数在该点处的方向导数沿着该方向取得最大值,即函数在该点处沿着该方向(此梯度的方向)变化最快,变化率最大(为该梯度的模)。
【Google AI】鲁棒图神经网络,Robust Graph Neural Networks
专知会员服务
37+阅读 · 2022年3月9日
专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
52+阅读 · 2020年11月3日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
浅聊对比学习(Contrastive Learning)
极市平台
2+阅读 · 2022年7月26日
浅聊对比学习(Contrastive Learning)第一弹
PaperWeekly
0+阅读 · 2022年6月10日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
2+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
20+阅读 · 2021年9月22日
Arxiv
13+阅读 · 2021年6月14日
Attentive Graph Neural Networks for Few-Shot Learning
Arxiv
40+阅读 · 2020年7月14日
Arxiv
19+阅读 · 2020年7月13日
Arxiv
17+阅读 · 2019年3月28日
Arxiv
24+阅读 · 2018年10月24日
Arxiv
23+阅读 · 2018年10月1日
VIP会员
相关VIP内容
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
浅聊对比学习(Contrastive Learning)
极市平台
2+阅读 · 2022年7月26日
浅聊对比学习(Contrastive Learning)第一弹
PaperWeekly
0+阅读 · 2022年6月10日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
相关论文
Arxiv
20+阅读 · 2021年9月22日
Arxiv
13+阅读 · 2021年6月14日
Attentive Graph Neural Networks for Few-Shot Learning
Arxiv
40+阅读 · 2020年7月14日
Arxiv
19+阅读 · 2020年7月13日
Arxiv
17+阅读 · 2019年3月28日
Arxiv
24+阅读 · 2018年10月24日
Arxiv
23+阅读 · 2018年10月1日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
2+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员