Timezone: »
Most state-of-the-art Graph Neural Networks (GNNs) can be defined as a form of graph convolution which can be realized by message passing between direct neighbors or beyond. To scale such GNNs to large graphs, various neighbor-, layer-, or subgraph-sampling techniques are proposed to alleviate the "neighbor explosion" problem by considering only a small subset of messages passed to the nodes in a mini-batch. However, sampling-based methods are difficult to apply to GNNs that utilize many-hops-away or global context each layer, show unstable performance for different tasks and datasets, and do not speed up model inference. We propose a principled and fundamentally different approach, VQ-GNN, a universal framework to scale up any convolution-based GNNs using Vector Quantization (VQ) without compromising the performance. In contrast to sampling-based techniques, our approach can effectively preserve all the messages passed to a mini-batch of nodes by learning and updating a small number of quantized reference vectors of global node representations, using VQ within each GNN layer. Our framework avoids the "neighbor explosion" problem of GNNs using quantized representations combined with a low-rank version of the graph convolution matrix. We show that such a compact low-rank version of the gigantic convolution matrix is sufficient both theoretically and experimentally. In company with VQ, we design a novel approximated message passing algorithm and a nontrivial back-propagation rule for our framework. Experiments on various types of GNN backbones demonstrate the scalability and competitive performance of our framework on large-graph node classification and link prediction benchmarks.
Author Information
Mucong Ding (Department of Computer Science, University of Maryland, College Park)
Kezhi Kong (University of Maryland, College Park)
Jingling Li (University of Maryland, College Park)
Chen Zhu (University of Maryland, College Park)
John Dickerson (University of Maryland)
Furong Huang (University of Maryland)
Furong Huang is an assistant professor of computer science. Huang’s research focuses on machine learning, high-dimensional statistics and distributed algorithms—both the theoretical analysis and practical implementation of parallel spectral methods for latent variable graphical models. Some applications of her research include developing fast detection algorithms to discover hidden and overlapping user communities in social networks, learning convolutional sparse coding models for understanding semantic meanings of sentences and object recognition in images, healthcare analytics by learning a hierarchy on human diseases for guiding doctors to identify potential diseases afflicting patients, and more. Huang recently completed a postdoctoral position at Microsoft Research in New York.
Tom Goldstein (Rice University)
More from the Same Authors
-
2021 : A Closer Look at Distribution Shifts and Out-of-Distribution Generalization on Graphs »
Mucong Ding · Kezhi Kong · Jiuhai Chen · John Kirchenbauer · Micah Goldblum · David P Wipf · Furong Huang · Tom Goldstein -
2021 : Diurnal or Nocturnal? Federated Learning from Periodically Shifting Distributions »
Chen Zhu · Zheng Xu · Mingqing Chen · Jakub Konečný · Andrew S Hard · Tom Goldstein -
2021 : Transfer RL across Observation Feature Spaces via Model-Based Regularization »
Yanchao Sun · Ruijie Zheng · Xiyao Wang · Andrew Cohen · Furong Huang -
2021 : Who Is the Strongest Enemy? Towards Optimal and Efficient Evasion Attacks in Deep RL »
Yanchao Sun · Ruijie Zheng · Yongyuan Liang · Furong Huang -
2021 : Learning Revenue-Maximizing Auctions With Differentiable Matching »
Michael Curry · Uro Lyi · Tom Goldstein · John P Dickerson -
2021 : Learning Revenue-Maximizing Auctions With Differentiable Matching »
Michael Curry · Uro Lyi · Tom Goldstein · John P Dickerson -
2021 : An mHealth Intervention for African American and Hispanic Adults: Preliminary Results from a One-Year Field Test »
Christine Herlihy · John Dickerson -
2021 : An mHealth Intervention for African American and Hispanic Adults: Preliminary Results from a One-Year Field Test »
Christine Herlihy · John Dickerson -
2022 : A Deep Dive into Dataset Imbalance and Bias in Face Identification »
Valeriia Cherepanova · Steven Reich · Samuel Dooley · Hossein Souri · John Dickerson · Micah Goldblum · Tom Goldstein -
2022 : Tensions Between the Proxies of Human Values in AI »
Daniel Nissani · Teresa Datta · John Dickerson · Max Cembalest · Akash Khanna · Haley Massa -
2022 : Characterizing Anomalies with Explainable Classifiers »
Naveen Durvasula · Valentine d Hauteville · Keegan Hines · John Dickerson -
2022 : A Deep Dive into Dataset Imbalance and Bias in Face Identification »
Valeriia Cherepanova · Steven Reich · Samuel Dooley · Hossein Souri · John Dickerson · Micah Goldblum · Tom Goldstein -
2022 : On the Importance of Architectures and Hyperparameters for Fairness in Face Recognition »
Samuel Dooley · Rhea Sukthanker · John Dickerson · Colin White · Frank Hutter · Micah Goldblum -
2022 : Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity »
Mucong Ding · Tahseen Rabbani · Bang An · Evan Wang · Furong Huang -
2022 : Faster Hyperparameter Search on Graphs via Calibrated Dataset Condensation »
Mucong Ding · Xiaoyu Liu · Tahseen Rabbani · Furong Huang -
2022 : On the Importance of Architectures and Hyperparameters for Fairness in Face Recognition »
Samuel Dooley · Rhea Sukthanker · John Dickerson · Colin White · Frank Hutter · Micah Goldblum -
2022 : A Deep Dive into Dataset Imbalance and Bias in Face Identification »
Valeriia Cherepanova · Steven Reich · Samuel Dooley · Hossein Souri · John Dickerson · Micah Goldblum · Tom Goldstein -
2022 Workshop: Graph Learning for Industrial Applications: Finance, Crime Detection, Medicine and Social Media »
Manuela Veloso · John Dickerson · Senthil Kumar · Eren K. · Jian Tang · Jie Chen · Peter Henstock · Susan Tibbs · Ani Calinescu · Naftali Cohen · C. Bayan Bruss · Armineh Nourbakhsh -
2022 Social: Open Mic Night »
John Dickerson -
2022 Poster: Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity »
Mucong Ding · Tahseen Rabbani · Bang An · Evan Wang · Furong Huang -
2022 Poster: Robustness Disparities in Face Detection »
Samuel Dooley · George Z Wei · Tom Goldstein · John Dickerson -
2022 Poster: Pre-Train Your Loss: Easy Bayesian Transfer Learning with Informative Priors »
Ravid Shwartz-Ziv · Micah Goldblum · Hossein Souri · Sanyam Kapoor · Chen Zhu · Yann LeCun · Andrew Wilson -
2022 Poster: On the Generalizability and Predictability of Recommender Systems »
Duncan McElfresh · Sujay Khandagale · Jonathan Valverde · John Dickerson · Colin White -
2022 Poster: Transferring Fairness under Distribution Shifts via Fair Consistency Regularization »
Bang An · Zora Che · Mucong Ding · Furong Huang -
2021 : A Closer Look at Distribution Shifts and Out-of-Distribution Generalization on Graphs »
Mucong Ding · Kezhi Kong · Jiuhai Chen · John Kirchenbauer · Micah Goldblum · David P Wipf · Furong Huang · Tom Goldstein -
2021 Poster: Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks »
Avi Schwarzschild · Eitan Borgnia · Arjun Gupta · Furong Huang · Uzi Vishkin · Micah Goldblum · Tom Goldstein -
2021 Poster: Fair Clustering Under a Bounded Cost »
Seyed Esmaeili · Brian Brubach · Aravind Srinivasan · John Dickerson -
2021 Poster: PreferenceNet: Encoding Human Preferences in Auction Design with Deep Learning »
Neehar Peri · Michael Curry · Samuel Dooley · John Dickerson -
2021 Poster: How does a Neural Network's Architecture Impact its Robustness to Noisy Labels? »
Jingling Li · Mozhi Zhang · Keyulu Xu · John Dickerson · Jimmy Ba -
2021 Poster: GradInit: Learning to Initialize Neural Networks for Stable and Efficient Training »
Chen Zhu · Renkun Ni · Zheng Xu · Kezhi Kong · W. Ronny Huang · Tom Goldstein -
2021 Poster: Understanding the Generalization Benefit of Model Invariance from a Data Perspective »
Sicheng Zhu · Bang An · Furong Huang -
2021 Poster: Gradient-Free Adversarial Training Against Image Corruption for Learning-based Steering »
Yu Shen · Laura Zheng · Manli Shu · Weizi Li · Tom Goldstein · Ming Lin -
2021 Poster: Adversarial Examples Make Strong Poisons »
Liam Fowl · Micah Goldblum · Ping-yeh Chiang · Jonas Geiping · Wojciech Czaja · Tom Goldstein -
2021 Poster: Center Smoothing: Certified Robustness for Networks with Structured Outputs »
Aounon Kumar · Tom Goldstein -
2021 Poster: Encoding Robustness to Image Style via Adversarial Feature Perturbations »
Manli Shu · Zuxuan Wu · Micah Goldblum · Tom Goldstein -
2021 Poster: Long-Short Transformer: Efficient Transformers for Language and Vision »
Chen Zhu · Wei Ping · Chaowei Xiao · Mohammad Shoeybi · Tom Goldstein · Anima Anandkumar · Bryan Catanzaro -
2020 : The Intrinsic Dimension of Images and Its Impact on Learning »
Chen Zhu · Micah Goldblum · Ahmed Abdelkader · Tom Goldstein · Phillip Pope -
2020 Workshop: Workshop on Dataset Curation and Security »
Nathalie Baracaldo · Yonatan Bisk · Avrim Blum · Michael Curry · John Dickerson · Micah Goldblum · Tom Goldstein · Bo Li · Avi Schwarzschild -
2020 Poster: Detection as Regression: Certified Object Detection with Median Smoothing »
Ping-yeh Chiang · Michael Curry · Ahmed Abdelkader · Aounon Kumar · John Dickerson · Tom Goldstein -
2020 Poster: Large-Scale Adversarial Training for Vision-and-Language Representation Learning »
Zhe Gan · Yen-Chun Chen · Linjie Li · Chen Zhu · Yu Cheng · Jingjing Liu -
2020 Spotlight: Large-Scale Adversarial Training for Vision-and-Language Representation Learning »
Zhe Gan · Yen-Chun Chen · Linjie Li · Chen Zhu · Yu Cheng · Jingjing Liu -
2020 Poster: Certifying Strategyproof Auction Networks »
Michael Curry · Ping-yeh Chiang · Tom Goldstein · John Dickerson -
2020 Poster: Convolutional Tensor-Train LSTM for Spatio-Temporal Learning »
Jiahao Su · Wonmin Byeon · Jean Kossaifi · Furong Huang · Jan Kautz · Anima Anandkumar -
2020 Poster: ARMA Nets: Expanding Receptive Field for Dense Prediction »
Jiahao Su · Shiqi Wang · Furong Huang -
2020 Poster: Improving Policy-Constrained Kidney Exchange via Pre-Screening »
Duncan McElfresh · Michael Curry · Tuomas Sandholm · John Dickerson -
2020 Poster: Probabilistic Fair Clustering »
Seyed Esmaeili · Brian Brubach · Leonidas Tsepenekas · John Dickerson -
2019 : Break / Poster Session 1 »
Antonia Marcu · Yao-Yuan Yang · Pascale Gourdeau · Chen Zhu · Thodoris Lykouris · Jianfeng Chi · Mark Kozdoba · Arjun Nitin Bhagoji · Xiaoxia Wu · Jay Nandy · Michael T Smith · Bingyang Wen · Yuege Xie · Konstantinos Pitas · Suprosanna Shit · Maksym Andriushchenko · Dingli Yu · Gaël Letarte · Misha Khodak · Hussein Mozannar · Chara Podimata · James Foulds · Yizhen Wang · Huishuai Zhang · Ondrej Kuzelka · Alexander Levine · Nan Lu · Zakaria Mhammedi · Paul Viallard · Diana Cai · Lovedeep Gondara · James Lucas · Yasaman Mahdaviyeh · Aristide Baratin · Rishi Bommasani · Alessandro Barp · Andrew Ilyas · Kaiwen Wu · Jens Behrmann · Omar Rivasplata · Amir Nazemi · Aditi Raghunathan · Will Stephenson · Sahil Singla · Akhil Gupta · YooJung Choi · Yannic Kilcher · Clare Lyle · Edoardo Manino · Andrew Bennett · Zhi Xu · Niladri Chatterji · Emre Barut · Flavien Prost · Rodrigo Toro Icarte · Arno Blaas · Chulhee Yun · Sahin Lale · YiDing Jiang · Tharun Kumar Reddy Medini · Ashkan Rezaei · Alexander Meinke · Stephen Mell · Gary Kazantsev · Shivam Garg · Aradhana Sinha · Vishnu Lokhande · Geovani Rizk · Han Zhao · Aditya Kumar Akash · Jikai Hou · Ali Ghodsi · Matthias Hein · Tyler Sypherd · Yichen Yang · Anastasia Pentina · Pierre Gillot · Antoine Ledent · Guy Gur-Ari · Noah MacAulay · Tianzong Zhang -
2019 Poster: Making the Cut: A Bandit-based Approach to Tiered Interviewing »
Candice Schumann · Zhi Lang · Jeffrey Foster · John Dickerson -
2019 Poster: Adversarial training for free! »
Ali Shafahi · Mahyar Najibi · Mohammad Amin Ghiasi · Zheng Xu · John Dickerson · Christoph Studer · Larry Davis · Gavin Taylor · Tom Goldstein -
2015 : Spotlight »
Furong Huang · William Gray Roncal · Tom Goldstein -
2015 : Convolutional Dictionary Learning through Tensor Factorization »
Furong Huang -
2015 : Uncertainty in Dynamic Matching »
John P Dickerson -
2012 Poster: Learning Mixtures of Tree Graphical Models »
Anima Anandkumar · Daniel Hsu · Furong Huang · Sham M Kakade