research-article

Open access

Nimble GNN Embedding with Tensor-Train Decomposition

Authors:

Christos Faloutsos,

George Karypis,

Richard VuducAuthors Info & Claims

KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Pages 2327 - 2335

https://doi.org/10.1145/3534678.3539423

Published: 14 August 2022 Publication History

Abstract

This paper describes a new method for representing embedding tables of graph neural networks (GNNs) more compactly via tensor-train (TT) decomposition. We consider the scenario where (a) the graph data that lack node features, thereby requiring the learning of embeddings during training; and (b) we wish to exploit GPU platforms, where smaller tables are needed to reduce host-to-GPU communication even for large-memory GPUs. The use of TT enables a compact parameterization of the embedding, rendering it small enough to fit entirely on modern GPUs even for massive graphs. When combined with judicious schemes for initialization and hierarchical graph partitioning, this approach can reduce the size of node embedding vectors by 1,659 times to 81,362 times on large publicly available benchmark datasets, achieving comparable or better accuracy and significant speedups on multi-GPU systems. In some cases, our model without explicit node features on input can even match the accuracy of models that use node features.

References

[1]

Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data. 1247--1250.

Digital Library

[2]

Nadav Cohen, Or Sharir, and Amnon Shashua. 2016. On the expressive power of deep learning: A tensor analysis. In Conference on learning theory. PMLR, 698--728.

[3]

Timur Garipov, Dmitry Podoprikhin, Alexander Novikov, and Dmitry Vetrov. 2016. Ultimate tensorization: compressing convolutional and fc layers alike. arXiv preprint arXiv:1611.03214 (2016).

[4]

Benjamin Ghaemmaghami, Zihao Deng, Benjamin Cho, Leo Orshansky, Ashish Kumar Singh, Mattan Erez, and Michael Orshansky. 2020. Training with multi-layer embeddings for model reduction. arXiv preprint arXiv:2006.05623 (2020).

[5]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017).

[6]

Oleksii Hrinchuk, Valentin Khrulkov, Leyla Mirvakhabova, Elena Orlova, and Ivan Oseledets. 2019. Tensorized embedding layers for efficient model compression. arXiv preprint arXiv:1901.10787 (2019).

[7]

Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv preprint arXiv:2005.00687 (2020).

[8]

Wei Hu, Lechao Xiao, and Jeffrey Pennington. 2020. Provable benefit of orthogonal initialization in optimizing deep linear networks. arXiv preprint arXiv:2001.05992 (2020).

[9]

Maria Kalantzi and George Karypis. 2021. Position-based Hash Embeddings For Scaling Graph Neural Networks. In 2021 IEEE International Conference on Big Data (Big Data). IEEE, 779--789.

[10]

Wang-Cheng Kang, Derek Zhiyuan Cheng, Tiansheng Yao, Xinyang Yi, Ting Chen, Lichan Hong, and Ed H Chi. 2020. Deep hash embedding for large-vocab categorical feature representations. arXiv e-prints (2020), arXiv--2010.

[11]

George Karypis and Vipin Kumar. 1997. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. (1997).

[12]

Thomas N Kipf and MaxWelling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).

[13]

Christos Louizos, Max Welling, and Diederik P Kingma. 2017. Learning sparse neural networks through L_0 regularization. arXiv preprint arXiv:1712.01312 (2017).

[14]

Miller McPherson, Lynn Smith-Lovin, and James M. Cook. 2001. Birds of a feather: homophily in social networks. Annual Review of Sociology 27 (August 2001), 415--444. https://doi.org/10.1146/annurev.soc.27.1.415

[15]

Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. 2016. Pruning convolutional neural networks for resource efficient inference. arXiv preprint arXiv:1611.06440 (2016).

[16]

Ivan V Oseledets. 2011. Tensor-train decomposition. SIAM Journal on Scientific Computing 33, 5 (2011), 2295--2317.

Digital Library

[17]

Joan Serrà and Alexandros Karatzoglou. 2017. Getting deep recommenders fit: Bloom embeddings for sparse binary input/output networks. In Proceedings of the Eleventh ACM Conference on Recommender Systems. 279--287.

Digital Library

[18]

Hao-Jun Michael Shi, Dheevatsa Mudigere, Maxim Naumov, and Jiyan Yang. 2020. Compositional embeddings using complementary partitions for memory-efficient recommendation systems. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 165--175.

[19]

Dan Tito Svenstrup, Jonas Hansen, and Ole Winther. 2017. Hash embeddings for efficient word representations. Advances in neural information processing systems 30 (2017).

[20]

Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903 (2017).

[21]

Pauli Virtanen, Ralf Gommers, and et al. 2020. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods 17 (2020), 261--272. https://doi.org/10.1038/s41592-019-0686-2

[22]

Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. 2019. Deep Graph Library: Towards Efficient and Scalable Deep Learning on Graphs. (2019).

[23]

Wenqi Wang, Yifan Sun, Brian Eriksson, Wenlin Wang, and Vaneet Aggarwal. 2018. Wide compression: Tensor ring nets. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 9329--9338.

[24]

Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. 2009. Feature hashing for large scale multitask learning. In Proceedings of the 26th annual international conference on machine learning. 1113--1120.

Digital Library

[25]

Chunxing Yin, Bilge Acun, Carole-Jean Wu, and Xing Liu. 2021. TT-rec: Tensor train compression for deep learning recommendation models. Proceedings of Machine Learning and Systems 3 (2021), 448--462.

[26]

Weijie Zhao, Deping Xie, Ronglai Jia, Yulei Qian, Ruiquan Ding, Mingming Sun, and Ping Li. 2020. Distributed hierarchical gpu parameter server for massive scale deep learning ads systems. Proceedings of Machine Learning and Systems 2 (2020), 412--428.

[27]

Da Zheng, Chao Ma, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song, Quan Gan, Zheng Zhang, and George Karypis. 2020. Distdgl: distributed graph neural network training for billion-scale graphs. In 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3). IEEE, 36--44.

[28]

Michael Zhu and Suyog Gupta. 2017. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint arXiv:1710.01878 (2017).

Cited By

Gupta VChen XHuang RMeng FChen JYan YSerra ESpezzano F(2024)GraphScale: A Framework to Enable Machine Learning over Billion-node GraphsProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3680021(4514-4521)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3680021
Kwon TKo JJung JJang JShin K(2024)Compact lossy compression of tensors via neural tensor-train decompositionKnowledge and Information Systems10.1007/s10115-024-02252-xOnline publication date: 14-Oct-2024
https://doi.org/10.1007/s10115-024-02252-x
Gong YYin MHuang LXiao JSui YDeng CYuan BSolihin YHeinrich M(2023)ETTE: Efficient Tensor-Train-based Computing Engine for Deep Neural NetworksProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589103(1-13)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589103
Show More Cited By

Index Terms

Nimble GNN Embedding with Tensor-Train Decomposition
1. Computing methodologies
  1. Machine learning

Recommendations

Auto-Divide GNN: Accelerating GNN Training with Subgraph Division
Euro-Par 2023: Parallel Processing
Abstract
Graph Neural Networks (GNNs) have gained considerable attention in recent years for their exceptional performance on graph-structured data. Sampling-based GNN training is the most common method used for training GNNs on large-scale graphs, and it ...
Dual-image reversible data hiding method using maximum embedding ability of each pixel
Abstract
Compared to conventional reversible data hiding (RDH) methods, dual-image RDH methods have greater embedding capacity, better stego image quality and higher security. Among existing dual-image RDH methods, three methods of Lu et al., ...
HongTu: Scalable Full-Graph GNN Training on Multiple GPUs
PACMMOD

Full-graph training on graph neural networks (GNN) has emerged as a promising training method for its effectiveness. Full-graph training requires extensive memory and computation resources. To accelerate this training process, researchers have proposed ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 2022

5033 pages

ISBN:9781450393850

DOI:10.1145/3534678

General Chairs:
Aidong Zhang
University of Virginia
,
Huzefa Rangwala
Amazon/George Mason University

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 August 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD '22

Sponsor:

KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 14 - 18, 2022

Washington DC, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
890
Total Downloads

Downloads (Last 12 months)235
Downloads (Last 6 weeks)33

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gupta VChen XHuang RMeng FChen JYan YSerra ESpezzano F(2024)GraphScale: A Framework to Enable Machine Learning over Billion-node GraphsProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3680021(4514-4521)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3680021
Kwon TKo JJung JJang JShin K(2024)Compact lossy compression of tensors via neural tensor-train decompositionKnowledge and Information Systems10.1007/s10115-024-02252-xOnline publication date: 14-Oct-2024
https://doi.org/10.1007/s10115-024-02252-x
Gong YYin MHuang LXiao JSui YDeng CYuan BSolihin YHeinrich M(2023)ETTE: Efficient Tensor-Train-based Computing Engine for Deep Neural NetworksProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589103(1-13)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589103
Liang XChen TNguyen QLi JYin H(2023)Learning Compact Compositional Embeddings via Regularized Pruning for Recommendation2023 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM58522.2023.00047(378-387)Online publication date: 1-Dec-2023
https://doi.org/10.1109/ICDM58522.2023.00047
Kwon TKo JJung JShin K(2023)TensorCodec: Compact Lossy Compression of Tensors without Strong Data Assumptions2023 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM58522.2023.00032(229-238)Online publication date: 1-Dec-2023
https://doi.org/10.1109/ICDM58522.2023.00032

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents