Early-Bird GCNs: Graph-Network Co-optimization towards More Efficient GCN Training and Inference via Drawing Early-Bird Lottery Tickets
Early-Bird GCNs: Graph-Network Co-optimization towards More Efficient GCN Training and Inference via Drawing Early-Bird Lottery Tickets
复制标题
DOI：
10.1609/aaai.v36i8.20873
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Haoran You;Zhihan Lu;Zijian Zhou;Y. Fu;Yingyan Lin
中科院分区：
文献类型：
--
作者：
Haoran You;Zhihan Lu;Zijian Zhou;Y. Fu;Yingyan Lin
图卷积网络（GCN）已经成为最先进的深度学习模型，用于图上的表示学习。然而，在大型图数据集上训练和推理GCN仍然是众所周知的挑战，这限制了它们在大型现实世界图中的应用，并阻碍了对更深入和更复杂的GCN图的探索。这是因为随着图形大小的增长，节点特征的绝对数量和大型邻接矩阵很容易使所需的内存和数据移动激增。为了解决上述挑战，我们探索了在稀疏化GCN图时绘制彩票的可能性，即，极大地缩小邻接矩阵的子图仍然能够实现与其全图相当或甚至更好的精度。具体来说，我们第一次发现存在的图形早鸟（GEB）票出现在非常早期的阶段时，稀疏GCN图，并提出了一个简单而有效的检测器，自动识别这种GEB票的出现。此外，我们提倡图-模型协同优化，并开发了一个通用高效的GCN早期训练框架，称为GEBT，它可以通过以下方式显着提高GCN训练的效率：（1）在GCN图和模型之间绘制联合早期票;（2）同时实现GCN图和模型的稀疏化。在各种GCN模型和数据集上的实验一致地验证了我们的GEB发现和我们的GEBT的有效性，例如，我们的GEBT实现了高达80.2% ~ 85.6%和84.6% ~ 87.5%的GCN训练和推理成本的节省，同时提供了与最先进的方法相比相当甚至更好的准确性。我们的源代码和补充附录可以在https://github.com/RICE-EIC/Early-Bird-GCN上找到。
Graph Convolutional Networks (GCNs) have emerged as the state-of-the-art deep learning model for representation learning on graphs. However, it remains notoriously challenging to train and inference GCNs over large graph datasets, limiting their application to large real-world graphs and hindering the exploration of deeper and more sophisticated GCN graphs. This is because as the graph size grows, the sheer number of node features and the large adjacency matrix can easily explode the required memory and data movements. To tackle the aforementioned challenges, we explore the possibility of drawing lottery tickets when sparsifying GCN graphs, i.e., subgraphs that largely shrink the adjacency matrix yet are capable of achieving accuracy comparable to or even better than their full graphs. Specifically, we for the first time discover the existence of graph early-bird (GEB) tickets that emerge at the very early stage when sparsifying GCN graphs, and propose a simple yet effective detector to automatically identify the emergence of such GEB tickets. Furthermore, we advocate graph-model co-optimization and develop a generic efficient GCN early-bird training framework dubbed GEBT that can significantly boost the efficiency of GCN training by (1) drawing joint early-bird tickets between the GCN graphs and models and (2) enabling simultaneously sparsification of both the GCN graphs and models. Experiments on various GCN models and datasets consistently validate our GEB finding and the effectiveness of our GEBT, e.g., our GEBT achieves up to 80.2% ~ 85.6% and 84.6% ~ 87.5% savings of GCN training and inference costs while offering a comparable or even better accuracy as compared to state-of-the-art methods. Our source code and supplementary appendix are available at https://github.com/RICE-EIC/Early-Bird-GCN.