Timezone: »
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.
Author Information
Qingru Zhang (Georgia Institute of Technology)
David Wipf (Microsoft Research)
Quan Gan (New York University)
Le Song (Georgia Institute of Technology)
More from the Same Authors
-
2021 Spotlight: On the Value of Infinite Gradients in Variational Autoencoder Models »
Bin Dai · Li Wenliang · David Wipf -
2021 : Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning »
Jiani Huang · Ziyang Li · Binghong Chen · Karan Samel · Mayur Naik · Le Song · Xujie Si -
2021 : Large Scale Coordination Transfer for Cooperative Multi-Agent Reinforcement Learning »
Ethan Wang · Binghong Chen · Le Song -
2022 Poster: Learning Enhanced Representation for Tabular Data via Neighborhood Propagation »
Kounianhua Du · Weinan Zhang · Ruiwen Zhou · Yangkun Wang · Xilong Zhao · Jiarui Jin · Quan Gan · Zheng Zhang · David P Wipf -
2023 Poster: xTrimoGene: An Efficient and Scalable Representation Learner for Single-Cell RNA-Seq Data »
Jing Gong · Minsheng Hao · Xin Zeng · Chiming Liu · Jianzhu Ma · Xingyi Cheng · Taifeng Wang · Xuegong Zhang · Le Song -
2023 Poster: Injecting Multimodal Information into Rigid Protein Docking via Bi-level Optimization »
Ruijia Wang · YiWu Sun · Yujie Luo · Cheng Yang · Shaochuan Li · Xingyi Cheng · Hui Li · Chuan Shi · Le Song -
2023 Poster: Robust Multi-Agent Reinforcement Learning via Adversarial Regularization: Theoretical Foundation and Stable Algorithms »
Alexander Bukharin · Yan Li · Yue Yu · Qingru Zhang · Zhehui Chen · Simiao Zuo · Chao Zhang · Songan Zhang · Tuo Zhao -
2022 Poster: Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks »
Hongjoon Ahn · Yongyi Yang · Quan Gan · Taesup Moon · David P Wipf -
2022 Poster: Uncovering the Structural Fairness in Graph Contrastive Learning »
Ruijia Wang · Xiao Wang · Chuan Shi · Le Song -
2021 Poster: Locality Sensitive Teaching »
Zhaozhuo Xu · Beidi Chen · Chaojian Li · Weiyang Liu · Le Song · Yingyan Lin · Anshumali Shrivastava -
2021 Poster: GRIN: Generative Relation and Intention Network for Multi-agent Trajectory Prediction »
Longyuan Li · Jian Yao · Li Wenliang · Tong He · Tianjun Xiao · Junchi Yan · David Wipf · Zheng Zhang -
2021 Poster: From Canonical Correlation Analysis to Self-supervised Graph Neural Networks »
Hengrui Zhang · Qitian Wu · Junchi Yan · David Wipf · Philip S Yu -
2021 Poster: Multi-task Learning of Order-Consistent Causal Graphs »
Xinshi Chen · Haoran Sun · Caleb Ellington · Eric Xing · Le Song -
2021 Poster: RoMA: Robust Model Adaptation for Offline Model-based Optimization »
Sihyun Yu · Sungsoo Ahn · Le Song · Jinwoo Shin -
2021 Poster: On the Value of Infinite Gradients in Variational Autoencoder Models »
Bin Dai · Li Wenliang · David Wipf -
2021 Poster: Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning »
Jiani Huang · Ziyang Li · Binghong Chen · Karan Samel · Mayur Naik · Le Song · Xujie Si -
2020 Poster: Understanding Deep Architecture with Reasoning Layer »
Xinshi Chen · Yufei Zhang · Christoph Reisinger · Le Song -
2020 Poster: The Devil is in the Detail: A Framework for Macroscopic Prediction via Microscopic Models »
Yingxiang Yang · Negar Kiyavash · Le Song · Niao He -
2020 Spotlight: The Devil is in the Detail: A Framework for Macroscopic Prediction via Microscopic Models »
Yingxiang Yang · Negar Kiyavash · Le Song · Niao He -
2019 Workshop: Learning with Temporal Point Processes »
Manuel Rodriguez · Le Song · Isabel Valera · Yan Liu · Abir De · Hongyuan Zha -
2019 Poster: Neural Similarity Learning »
Weiyang Liu · Zhen Liu · James Rehg · Le Song -
2019 Poster: Meta Architecture Search »
Albert Shaw · Wei Wei · Weiyang Liu · Le Song · Bo Dai -
2019 Poster: Exponential Family Estimation via Adversarial Dynamics Embedding »
Bo Dai · Zhen Liu · Hanjun Dai · Niao He · Arthur Gretton · Le Song · Dale Schuurmans -
2019 Poster: Retrosynthesis Prediction with Conditional Graph Logic Network »
Hanjun Dai · Chengtao Li · Connor Coley · Bo Dai · Le Song -
2018 Poster: Learning Loop Invariants for Program Verification »
Xujie Si · Hanjun Dai · Mukund Raghothaman · Mayur Naik · Le Song -
2018 Spotlight: Learning Loop Invariants for Program Verification »
Xujie Si · Hanjun Dai · Mukund Raghothaman · Mayur Naik · Le Song -
2018 Poster: Coupled Variational Bayes via Optimization Embedding »
Bo Dai · Hanjun Dai · Niao He · Weiyang Liu · Zhen Liu · Jianshu Chen · Lin Xiao · Le Song -
2018 Poster: Learning Temporal Point Processes via Reinforcement Learning »
Shuang Li · Shuai Xiao · Shixiang Zhu · Nan Du · Yao Xie · Le Song -
2018 Spotlight: Learning Temporal Point Processes via Reinforcement Learning »
Shuang Li · Shuai Xiao · Shixiang Zhu · Nan Du · Yao Xie · Le Song -
2018 Poster: Learning towards Minimum Hyperspherical Energy »
Weiyang Liu · Rongmei Lin · Zhen Liu · Lixin Liu · Zhiding Yu · Bo Dai · Le Song -
2017 : Learning from Conditional Distributions via Dual Embeddings (poster). »
Le Song -
2017 Oral: From Bayesian Sparsity to Gated Recurrent Nets »
Hao He · Bo Xin · Satoshi Ikehata · David Wipf -
2017 Poster: Predicting User Activity Level In Point Processes With Mass Transport Equation »
Yichen Wang · Xiaojing Ye · Hongyuan Zha · Le Song -
2017 Poster: From Bayesian Sparsity to Gated Recurrent Nets »
Hao He · Bo Xin · Satoshi Ikehata · David Wipf -
2017 Poster: Learning Combinatorial Optimization Algorithms over Graphs »
Elias Khalil · Hanjun Dai · Yuyu Zhang · Bistra Dilkina · Le Song -
2017 Spotlight: Learning Combinatorial Optimization Algorithms over Graphs »
Elias Khalil · Hanjun Dai · Yuyu Zhang · Bistra Dilkina · Le Song -
2017 Poster: Deep Hyperspherical Learning »
Weiyang Liu · Yan-Ming Zhang · Xingguo Li · Zhiding Yu · Bo Dai · Tuo Zhao · Le Song -
2017 Poster: On the Complexity of Learning Neural Networks »
Le Song · Santosh Vempala · John Wilmes · Bo Xie -
2017 Spotlight: Deep Hyperspherical Learning »
Weiyang Liu · Yan-Ming Zhang · Xingguo Li · Zhiding Yu · Bo Dai · Tuo Zhao · Le Song -
2017 Spotlight: On the Complexity of Learning Neural Networks »
Le Song · Santosh Vempala · John Wilmes · Bo Xie -
2017 Poster: Wasserstein Learning of Deep Generative Point Process Models »
Shuai Xiao · Mehrdad Farajtabar · Xiaojing Ye · Junchi Yan · Xiaokang Yang · Le Song · Hongyuan Zha -
2016 Poster: A Pseudo-Bayesian Algorithm for Robust PCA »
Tae-Hyun Oh · Yasuyuki Matsushita · In So Kweon · David Wipf -
2016 Poster: Multistage Campaigning in Social Networks »
Mehrdad Farajtabar · Xiaojing Ye · Sahar Harati · Le Song · Hongyuan Zha -
2016 Poster: Coevolutionary Latent Feature Processes for Continuous-Time User-Item Interactions »
Yichen Wang · Nan Du · Rakshit Trivedi · Le Song -
2016 Poster: Maximal Sparsity with Deep Networks? »
Bo Xin · Yizhou Wang · Wen Gao · David Wipf · Baoyuan Wang -
2015 Poster: Time-Sensitive Recommendation From Recurrent User Activities »
Nan Du · Yichen Wang · Niao He · Jimeng Sun · Le Song -
2015 Poster: Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients »
Bo Xie · Yingyu Liang · Le Song -
2015 Poster: Efficient Learning of Continuous-Time Hidden Markov Models for Disease Progression »
Yu-Ying Liu · Shuang Li · Fuxin Li · Le Song · James Rehg -
2015 Poster: COEVOLVE: A Joint Point Process Model for Information Diffusion and Network Co-evolution »
Mehrdad Farajtabar · Yichen Wang · Manuel Rodriguez · Shuang Li · Hongyuan Zha · Le Song -
2015 Oral: COEVOLVE: A Joint Point Process Model for Information Diffusion and Network Co-evolution »
Mehrdad Farajtabar · Yichen Wang · Manuel Rodriguez · Shuang Li · Hongyuan Zha · Le Song -
2015 Poster: M-Statistic for Kernel Change-Point Detection »
Shuang Li · Yao Xie · Hanjun Dai · Le Song -
2014 Poster: Active Learning and Best-Response Dynamics »
Maria-Florina F Balcan · Christopher Berlind · Avrim Blum · Emma Cohen · Kaushik Patnaik · Le Song -
2014 Poster: Learning Time-Varying Coverage Functions »
Nan Du · Yingyu Liang · Maria-Florina F Balcan · Le Song -
2014 Poster: Shaping Social Activity by Incentivizing Users »
Mehrdad Farajtabar · Nan Du · Manuel Gomez Rodriguez · Isabel Valera · Hongyuan Zha · Le Song -
2014 Poster: Scalable Kernel Methods via Doubly Stochastic Gradients »
Bo Dai · Bo Xie · Niao He · Yingyu Liang · Anant Raj · Maria-Florina F Balcan · Le Song -
2013 Poster: Robust Low Rank Kernel Embeddings of Multivariate Distributions »
Le Song · Bo Dai -
2013 Poster: Non-Uniform Camera Shake Removal Using a Spatially-Adaptive Sparse Penalty »
Haichao Zhang · David Wipf -
2013 Poster: Scalable Influence Estimation in Continuous-Time Diffusion Networks »
Nan Du · Le Song · Manuel Gomez Rodriguez · Hongyuan Zha -
2013 Oral: Non-Uniform Camera Shake Removal Using a Spatially-Adaptive Sparse Penalty »
Haichao Zhang · David Wipf -
2013 Oral: Scalable Influence Estimation in Continuous-Time Diffusion Networks »
Nan Du · Le Song · Manuel Gomez Rodriguez · Hongyuan Zha -
2012 Workshop: Confluence between Kernel Methods and Graphical Models »
Le Song · Arthur Gretton · Alexander Smola -
2012 Workshop: Spectral Algorithms for Latent Variable Models »
Ankur P Parikh · Le Song · Eric Xing -
2012 Poster: Learning Networks of Heterogeneous Influence »
Nan Du · Le Song · Alexander Smola · Ming Yuan -
2012 Spotlight: Learning Networks of Heterogeneous Influence »
Nan Du · Le Song · Alexander Smola · Ming Yuan