Timezone: »
Sampling-based methods promise scalability improvements when paired with stochastic gradient descent in training Graph Convolutional Networks (GCNs). While effective in alleviating the neighborhood explosion, due to bandwidth and memory bottlenecks, these methods lead to computational overheads in preprocessing and loading new samples in heterogeneous systems, which significantly deteriorate the sampling performance. By decoupling the frequency of sampling from the sampling strategy, we propose LazyGCN, a general yet effective framework that can be integrated with any sampling strategy to substantially improve the training time. The basic idea behind LazyGCN is to perform sampling periodically and effectively recycle the sampled nodes to mitigate data preparation overhead. We theoretically analyze the proposed algorithm and show that under a mild condition on the recycling size, by reducing the variance of inner layers, we are able to obtain the same convergence rate as the underlying sampling method. We also give corroborating empirical evidence on large real-world graphs, demonstrating that the proposed schema can significantly reduce the number of sampling steps and yield superior speedup without compromising the accuracy.
Author Information
Morteza Ramezani (Pennsylvania State University)
Weilin Cong (Pennsylvania State University)
Mehrdad Mahdavi (Pennsylvania State University)
Mehrdad Mahdavi is an Assistant Professor of Computer Science & Engineering at Pennsylvania State University. He runs the Machine Learning and Optimization Lab, where they work on fundamental problems in computational and theoretical machine learning.
Anand Sivasubramaniam (Penn State)
Mahmut Kandemir (Pennsylvania State University)
More from the Same Authors
-
2023 Poster: Understanding Deep Gradient Leakage via Inversion Influence Functions »
Haobo Zhang · Junyuan Hong · Yuyang Deng · Mehrdad Mahdavi · Jiayu Zhou -
2023 Poster: Mixture Weight Estimation and Model Prediction in Multi-source Multi-target Domain Adaptation »
Yuyang Deng · Ilja Kuzborskij · Mehrdad Mahdavi -
2023 Poster: Distributed Personalized Empirical Risk Minimization »
Yuyang Deng · Mohammad Mahdi Kamani · Pouria Mahdavinia · Mehrdad Mahdavi -
2022 Poster: Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems »
Pouria Mahdavinia · Yuyang Deng · Haochuan Li · Mehrdad Mahdavi -
2021 Poster: Structured in Space, Randomized in Time: Leveraging Dropout in RNNs for Efficient Training »
Anup Sarma · Sonali Singh · Huaipan Jiang · Rui Zhang · Mahmut Kandemir · Chita Das -
2021 Poster: On Provable Benefits of Depth in Training Graph Convolutional Networks »
Weilin Cong · Morteza Ramezani · Mehrdad Mahdavi -
2020 Poster: Online Structured Meta-learning »
Huaxiu Yao · Yingbo Zhou · Mehrdad Mahdavi · Zhenhui (Jessie) Li · Richard Socher · Caiming Xiong -
2020 Poster: Distributionally Robust Federated Averaging »
Yuyang Deng · Mohammad Mahdi Kamani · Mehrdad Mahdavi -
2019 Poster: Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization »
Farzin Haddadpour · Mohammad Mahdi Kamani · Mehrdad Mahdavi · Viveck Cadambe