{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T17:15:30Z","timestamp":1778606130314,"version":"3.51.4"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T00:00:00Z","timestamp":1607299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Alibaba Innovative Research (AIR) programme"},{"name":"Campus for Research Excellence and Technological Enterprise (CREATE) programme, National Research Foundation, Prime Minister?s Office, Singapore"},{"DOI":"10.13039\/501100012659","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772082, 61806020, 61702296"],"award-info":[{"award-number":["61772082, 61806020, 61702296"]}],"id":[{"id":"10.13039\/501100012659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Key Research and Development Program of China","award":["2018YFB1402600"],"award-info":[{"award-number":["2018YFB1402600"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,2,28]]},"abstract":"<jats:p>In real-world problems, heterogeneous entities are often related to each other through multiple interactions, forming a Heterogeneous Interaction Graph (HIG). While modeling HIGs to deal with fundamental tasks, graph neural networks present an attractive opportunity that can make full use of the heterogeneity and rich semantic information by aggregating and propagating information from different types of neighborhoods. However, learning on such complex graphs, often with millions or billions of nodes, edges, and various attributes, could suffer from expensive time cost and high memory consumption. In this article, we attempt to accelerate representation learning on large-scale HIGs by adopting the importance sampling of heterogeneous neighborhoods in a batch-wise manner, which naturally fits with most batch-based optimizations. Distinct from traditional homogeneous strategies neglecting semantic types of nodes and edges, to handle the rich heterogeneous semantics within HIGs, we devise both type-dependent and type-fusion samplers where the former respectively samples neighborhoods of each type and the latter jointly samples from candidates of all types. Furthermore, to overcome the imbalance between the down-sampled and the original information, we respectively propose heterogeneous estimators including the self-normalized and the adaptive estimators to improve the robustness of our sampling strategies.<\/jats:p>\n          <jats:p>Finally, we evaluate the performance of our models for node classification and link prediction on five real-world datasets, respectively. The empirical results demonstrate that our approach performs significantly better than other state-of-the-art alternatives, and is able to reduce the number of edges in computation by up to 93%, the memory cost by up to 92% and the time cost by up to 86%.<\/jats:p>","DOI":"10.1145\/3418684","type":"journal-article","created":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T19:04:16Z","timestamp":1607367856000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Accelerating Large-Scale Heterogeneous Interaction Graph Embedding Learning via Importance Sampling"],"prefix":"10.1145","volume":"15","author":[{"given":"Yugang","family":"Ji","sequence":"first","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingyang","family":"Yin","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongxia","family":"Yang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent W.","family":"Zheng","sequence":"additional","affiliation":[{"name":"Advanced Digital Sciences Center, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chuan","family":"Shi","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuan","family":"Fang","sequence":"additional","affiliation":[{"name":"Singapore Management University, Victoria Street, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,12,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Variance reduction in SGD by distributed importance sampling. arXiv preprint arXiv:1511.06481","author":"Alain Guillaume","year":"2015","unstructured":"Guillaume Alain , Alex Lamb , Chinnadhurai Sankar , Aaron Courville , and Yoshua Bengio . 2015. Variance reduction in SGD by distributed importance sampling. arXiv preprint arXiv:1511.06481 ( 2015 ). Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. 2015. Variance reduction in SGD by distributed importance sampling. arXiv preprint arXiv:1511.06481 (2015)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ymeth.2017.06.036"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807452"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330964"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 6th International Conference on Learning Representations.","author":"Chen Jie","year":"2018","unstructured":"Jie Chen , Tengfei Ma , and Cao Xiao . 2018 . FastGCN: Fast learning with graph convolutional networks via importance sampling . In Proceedings of the 6th International Conference on Learning Representations. Retrieved from https:\/\/openreview.net\/forum?id&equals;rytstxWAW. Jie Chen, Tengfei Ma, and Cao Xiao. 2018. FastGCN: Fast learning with graph convolutional networks via importance sampling. In Proceedings of the 6th International Conference on Learning Representations. Retrieved from https:\/\/openreview.net\/forum?id&equals;rytstxWAW."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159695"},{"key":"e_1_2_1_7_1","article-title":"Importance sampling for minibatches","volume":"19","author":"Csiba Dominik","year":"2018","unstructured":"Dominik Csiba and Peter Richt\u00e1rik . 2018 . Importance sampling for minibatches . Journal of Machine Learning Research 19 (2018), 27:1--27:21. Retrieved from http:\/\/jmlr.org\/papers\/v19\/16-241.html. Dominik Csiba and Peter Richt\u00e1rik. 2018. Importance sampling for minibatches. Journal of Machine Learning Research 19 (2018), 27:1--27:21. Retrieved from http:\/\/jmlr.org\/papers\/v19\/16-241.html.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems. 3837--3845","author":"Defferrard Micha\u00ebl","year":"2016","unstructured":"Micha\u00ebl Defferrard , Xavier Bresson , and Pierre Vandergheynst . 2016 . Convolutional neural networks on graphs with fast localized spectral filtering . In Proceedings of the Advances in Neural Information Processing Systems. 3837--3845 . Retrieved from http:\/\/papers.nips.cc\/paper\/6081-convolutional-neural-networks-on-graphs-with-fast-localized-spectral-filtering. Micha\u00ebl Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. In Proceedings of the Advances in Neural Information Processing Systems. 3837--3845. Retrieved from http:\/\/papers.nips.cc\/paper\/6081-convolutional-neural-networks-on-graphs-with-fast-localized-spectral-filtering."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098036"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2015.2432078"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498247"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132953"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems. 5125--5136","author":"Garc\u00eda-Dur\u00e1n Alberto","year":"2017","unstructured":"Alberto Garc\u00eda-Dur\u00e1n and Mathias Niepert . 2017 . Learning graph representations with embedding propagation . In Proceedings of the Advances in Neural Information Processing Systems. 5125--5136 . Retrieved from http:\/\/papers.nips.cc\/paper\/7097-learning-graph-representations-with-embedding-propagation. Alberto Garc\u00eda-Dur\u00e1n and Mathias Niepert. 2017. Learning graph representations with embedding propagation. In Proceedings of the Advances in Neural Information Processing Systems. 5125--5136. Retrieved from http:\/\/papers.nips.cc\/paper\/7097-learning-graph-representations-with-embedding-propagation."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2005.1555942"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems. 1025--1035","author":"Hamilton William L.","year":"2017","unstructured":"William L. Hamilton , Zhitao Ying , and Jure Leskovec . 2017 . Inductive representation learning on large graphs . In Proceedings of the Advances in Neural Information Processing Systems. 1025--1035 . Retrieved from http:\/\/papers.nips.cc\/paper\/6703-inductive-representation-learning-on-large-graphs. William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of the Advances in Neural Information Processing Systems. 1025--1035. Retrieved from http:\/\/papers.nips.cc\/paper\/6703-inductive-representation-learning-on-large-graphs."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-017-0755-3"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the American Medical Informatics Association Annual Symposium.","author":"Hristovski Dimitar","unstructured":"Dimitar Hristovski , Andrej Kastrin , and Thomas C. Rindflesch . 2016. Implementing semantics-based cross-domain collaboration recommendation in biomedicine with a graph database . In Proceedings of the American Medical Informatics Association Annual Symposium. Retrieved from http:\/\/knowledge.amia.org\/amia-63300-1.3360278\/t005-1.3362920\/f005-1.3362921\/2499243-1.3363975\/2499720-1.3363972. Dimitar Hristovski, Andrej Kastrin, and Thomas C. Rindflesch. 2016. Implementing semantics-based cross-domain collaboration recommendation in biomedicine with a graph database. In Proceedings of the American Medical Informatics Association Annual Symposium. Retrieved from http:\/\/knowledge.amia.org\/amia-63300-1.3360278\/t005-1.3362920\/f005-1.3362921\/2499243-1.3363975\/2499720-1.3363972."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems. 4563--4572","author":"Zhang Tong","year":"2018","unstructured":"Wen-bing Huang, Tong Zhang , Yu Rong , and Junzhou Huang . 2018 . Adaptive sampling towards fast graph representation learning . In Proceedings of the Advances in Neural Information Processing Systems. 4563--4572 . Retrieved from http:\/\/papers.nips.cc\/paper\/7707-adaptive-sampling-towards-fast-graph-representation-learning. Wen-bing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. 2018. Adaptive sampling towards fast graph representation learning. In Proceedings of the Advances in Neural Information Processing Systems. 4563--4572. Retrieved from http:\/\/papers.nips.cc\/paper\/7707-adaptive-sampling-towards-fast-graph-representation-learning."},{"key":"e_1_2_1_20_1","volume-title":"A general embedding framework for heterogeneous information learning in large-scale networks. ACM Transactions on Knowledge Discovery from Data 12, 6","author":"Huang Xiao","year":"2018","unstructured":"Xiao Huang , Jundong Li , Na Zou , and Xia Hu. 2018. A general embedding framework for heterogeneous information learning in large-scale networks. ACM Transactions on Knowledge Discovery from Data 12, 6 ( 2018 ), 70:1--70:24. DOI:https:\/\/doi.org\/10.1145\/3241063 10.1145\/3241063 Xiao Huang, Jundong Li, Na Zou, and Xia Hu. 2018. A general embedding framework for heterogeneous information learning in large-scale networks. ACM Transactions on Knowledge Discovery from Data 12, 6 (2018), 70:1--70:24. DOI:https:\/\/doi.org\/10.1145\/3241063"},{"key":"e_1_2_1_21_1","first-page":"259","article-title":"A graph model for E-commerce recommender systems","volume":"55","author":"Huang Zan","year":"2004","unstructured":"Zan Huang , Wingyan Chung , and Hsinchun Chen . 2004 . A graph model for E-commerce recommender systems . Journal of the Association for Information Science and Technology 55 , 3 (2004), 259 -- 274 . DOI:https:\/\/doi.org\/10.1002\/asi.10372 10.1002\/asi.10372 Zan Huang, Wingyan Chung, and Hsinchun Chen. 2004. A graph model for E-commerce recommender systems. Journal of the Association for Information Science and Technology 55, 3 (2004), 259--274. DOI:https:\/\/doi.org\/10.1002\/asi.10372","journal-title":"Journal of the Association for Information Science and Technology"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939815"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 5th International Conference on Learning Representations.","author":"Thomas","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks . In Proceedings of the 5th International Conference on Learning Representations. Retrieved from https:\/\/openreview.net\/forum?id&equals;SJU4ayYgl. Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations. Retrieved from https:\/\/openreview.net\/forum?id&equals;SJU4ayYgl."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3363574"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2016.08.025"},{"key":"e_1_2_1_26_1","unstructured":"Art B. Owen. 2013. Monte Carlo Theory Methods and Examples.  Art B. Owen. 2013. Monte Carlo Theory Methods and Examples."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"e_1_2_1_29_1","volume-title":"Meta-path guided embedding for similarity search in large-scale heterogeneous information networks. CoRR abs\/1610.09769","author":"Shang Jingbo","year":"2016","unstructured":"Jingbo Shang , Meng Qu , Jialu Liu , Lance M. Kaplan , Jiawei Han , and Jian Peng . 2016. Meta-path guided embedding for similarity search in large-scale heterogeneous information networks. CoRR abs\/1610.09769 ( 2016 ). arxiv:1610.09769 http:\/\/arxiv.org\/abs\/1610.09769 Jingbo Shang, Meng Qu, Jialu Liu, Lance M. Kaplan, Jiawei Han, and Jian Peng. 2016. Meta-path guided embedding for similarity search in large-scale heterogeneous information networks. CoRR abs\/1610.09769 (2016). arxiv:1610.09769 http:\/\/arxiv.org\/abs\/1610.09769"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833443"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2598561"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402736"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_2_1_34_1","volume-title":"Graph attention networks. CoRR abs\/1710.10903","author":"Veli\u010dkovi\u0107 Petar","year":"2017","unstructured":"Petar Veli\u010dkovi\u0107 , Guillem Cucurull , Arantxa Casanova , Adriana Romero , Pietro Li\u00f2 , and Yoshua Bengio . 2017. Graph attention networks. CoRR abs\/1710.10903 ( 2017 ). arxiv:1710.10903 http:\/\/arxiv.org\/abs\/1710.10903 Petar Veli\u010dkovi\u0107, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2017. Graph attention networks. CoRR abs\/1710.10903 (2017). arxiv:1710.10903 http:\/\/arxiv.org\/abs\/1710.10903"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 28th International Conference on World Wide Web (WWW'19)","author":"Wang Xiao","year":"2019","unstructured":"Xiao Wang , Houye Ji , Chuan Shi , Bai Wang , Yanfang Ye , Peng Cui , and Philip S. Yu . 2019. Heterogeneous graph attention network . In Proceedings of the 28th International Conference on World Wide Web (WWW'19) , San Francisco, CA, USA , May 13-17, 2019 . ACM, 2022--2032. DOI:https:\/\/doi.org\/10.1145\/3308558.3313562 10.1145\/3308558.3313562 Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S. Yu. 2019. Heterogeneous graph attention network. In Proceedings of the 28th International Conference on World Wide Web (WWW'19), San Francisco, CA, USA, May 13-17, 2019. ACM, 2022--2032. DOI:https:\/\/doi.org\/10.1145\/3308558.3313562"},{"key":"e_1_2_1_36_1","volume-title":"Yu","author":"Wu Zonghan","year":"2019","unstructured":"Zonghan Wu , Shirui Pan , Fengwen Chen , Guodong Long , Chengqi Zhang , and Philip S . Yu . 2019 . A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596 (2019). Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2019. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596 (2019)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052558"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2019.00080"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219890"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery 8 Data Mining. ACM, 793--803","author":"Zhang Chuxu","unstructured":"Chuxu Zhang , Dongjin Song , Chao Huang , Ananthram Swami , and Nitesh V. Chawla . 2019. Heterogeneous graph neural network . In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery 8 Data Mining. ACM, 793--803 . Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V. Chawla. 2019. Heterogeneous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery 8 Data Mining. ACM, 793--803."},{"key":"e_1_2_1_41_1","volume-title":"Personalized recommendation via integrated diffusion on user--item--tag tripartite graphs. Physica A: Statistical Mechanics and its Applications 389, 1","author":"Zhang Zi-Ke","year":"2010","unstructured":"Zi-Ke Zhang , Tao Zhou , and Yi-Cheng Zhang . 2010. Personalized recommendation via integrated diffusion on user--item--tag tripartite graphs. Physica A: Statistical Mechanics and its Applications 389, 1 ( 2010 ), 179--186. Zi-Ke Zhang, Tao Zhou, and Yi-Cheng Zhang. 2010. Personalized recommendation via integrated diffusion on user--item--tag tripartite graphs. Physica A: Statistical Mechanics and its Applications 389, 1 (2010), 179--186."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00198"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems. 11247--11256","author":"Zou Difan","year":"2019","unstructured":"Difan Zou , Ziniu Hu , Yewen Wang , Song Jiang , Yizhou Sun , and Quanquan Gu . 2019 . Layer-dependent importance sampling for training deep and large graph convolutional networks . In Proceedings of the Advances in Neural Information Processing Systems. 11247--11256 . Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. 2019. Layer-dependent importance sampling for training deep and large graph convolutional networks. In Proceedings of the Advances in Neural Information Processing Systems. 11247--11256."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418684","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3418684","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:28Z","timestamp":1750197748000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418684"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,7]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2,28]]}},"alternative-id":["10.1145\/3418684"],"URL":"https:\/\/doi.org\/10.1145\/3418684","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,7]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}