# Rethinking Efficiency and Redundancy in Training Large-scale Graphs

arXiv: https://arxiv.org/abs/2209.00800 · HTML: https://mlsanity.com/paper/2209.00800/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 59 references that are in the map.
- First posted on arXiv 2 Sep 2022.

## Builds on (most cited first, 30 of 36)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks](https://mlsanity.com/paper/2005.11650/) (2020)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [Data Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2006.06830/) (2020)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning](https://mlsanity.com/paper/2103.00113/) (2021)
- [Learning to Drop: Robust Graph Neural Network via Topological Denoising](https://mlsanity.com/paper/2011.07057/) (2020)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Bayesian Graph Neural Networks with Adaptive Connection Sampling](https://mlsanity.com/paper/2006.04064/) (2020)
- [Computing Graph Neural Networks: A Survey from Algorithms to Accelerators](https://mlsanity.com/paper/2010.00130/) (2020)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks](https://mlsanity.com/paper/2006.13866/) (2020)
- [Sampling methods for efficient training of graph convolutional networks: A survey](https://mlsanity.com/paper/2103.05872/) (2021)
- [Accurate, Efficient and Scalable Graph Embedding](https://mlsanity.com/paper/1810.11899/) (2018)
- [Bandit Samplers for Training Graph Neural Networks](https://mlsanity.com/paper/2006.05806/) (2020)
- [Understanding GNN Computational Graph: A Coordinated Computation, IO, and Memory Perspective](https://mlsanity.com/paper/2110.09524/) (2021)

## Built on by (most cited first, 1 of 1)

- [On Pitfalls of textitRemOve-And-Retrain: Data Processing Inequality Perspective](https://mlsanity.com/paper/2304.13836/) (2023)

## Abstract (arXiv)

Large-scale graphs are ubiquitous in real-world scenarios and can be trained by Graph Neural Networks (GNNs) to generate representation for downstream tasks. Given the abundant information and complex topology of a large-scale graph, we argue that redundancy exists in such graphs and will degrade the training efficiency. Unfortunately, the model scalability severely restricts the efficiency of training large-scale graphs via vanilla GNNs. Despite recent advances in sampling-based training methods, sampling-based GNNs generally overlook the redundancy issue. It still takes intolerable time to train these models on large-scale graphs. Thereby, we propose to drop redundancy and improve efficiency of training large-scale graphs with GNNs, by rethinking the inherent characteristics in a graph. In this paper, we pioneer to propose a once-for-all method, termed DropReef, to drop the redundancy in large-scale graphs. Specifically, we first conduct preliminary experiments to explore potential redundancy in large-scale graphs. Next, we present a metric to quantify the neighbor heterophily of all nodes in a graph. Based on both experimental and theoretical analysis, we reveal the redundancy in a large-scale graph, i.e., nodes with high neighbor heterophily and a great number of neighbors. Then, we propose DropReef to detect and drop the redundancy in large-scale graphs once and for all, helping reduce the training time while ensuring no sacrifice in the model accuracy. To demonstrate the effectiveness of DropReef, we apply it to recent state-of-the-art sampling-based GNNs for training large-scale graphs, owing to the high precision of such models. With DropReef leveraged, the training efficiency of models can be greatly promoted. DropReef is highly compatible and is offline performed, benefiting the state-of-the-art sampling-based GNNs in the present and future to a significant extent.