A Biased Graph Neural Network Sampler with Near-Optimal Regret
被引:0
|
作者:
Zhang, Qingru
论文数: 0引用数: 0
h-index: 0
机构:
Georgia Inst Technol, Atlanta, GA 30332 USAGeorgia Inst Technol, Atlanta, GA 30332 USA
Zhang, Qingru
[1
]
Wipf, David
论文数: 0引用数: 0
h-index: 0
机构:
Amazon Shanghai AI Lab, Shanghai, Peoples R ChinaGeorgia Inst Technol, Atlanta, GA 30332 USA
Wipf, David
[2
]
Gan, Quan
论文数: 0引用数: 0
h-index: 0
机构:
Amazon Shanghai AI Lab, Shanghai, Peoples R ChinaGeorgia Inst Technol, Atlanta, GA 30332 USA
Gan, Quan
[2
]
Song, Le
论文数: 0引用数: 0
h-index: 0
机构:
Georgia Inst Technol, Atlanta, GA 30332 USA
Mohamed Bin Zayed Univ Artificial Intelligence, Abu Dhabi, U Arab EmiratesGeorgia Inst Technol, Atlanta, GA 30332 USA
Song, Le
[1
,3
]
机构:
[1] Georgia Inst Technol, Atlanta, GA 30332 USA
[2] Amazon Shanghai AI Lab, Shanghai, Peoples R China
[3] Mohamed Bin Zayed Univ Artificial Intelligence, Abu Dhabi, U Arab Emirates
来源:
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 34 (NEURIPS 2021)
|
2021年
/
34卷
关键词:
D O I:
暂无
中图分类号:
TP18 [人工智能理论];
学科分类号:
081104 ;
0812 ;
0835 ;
1405 ;
摘要:
Graph neural networks (GNN) have recently emerged as a vehicle for applying deep network architectures to graph and relational data. However, given the increasing size of industrial datasets, in many practical situations the message passing computations required for sharing information across GNN layers are no longer scalable. Although various sampling methods have been introduced to approximate full-graph training within a tractable budget, there remain unresolved complications such as high variances and limited theoretical guarantees. To address these issues, we build upon existing work and treat GNN neighbor sampling as a multi-armed bandit problem but with a newly-designed reward function that introduces some degree of bias designed to reduce variance and avoid unstable, possibly-unbounded pay outs. And unlike prior bandit-GNN use cases, the resulting policy leads to near-optimal regret while accounting for the GNN training dynamics introduced by SGD. From a practical standpoint, this translates into lower variance estimates and competitive or superior test accuracy across several benchmarks.