{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T22:09:19Z","timestamp":1768342159661,"version":"3.49.0"},"reference-count":40,"publisher":"SAGE Publications","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IDA"],"published-print":{"date-parts":[[2023,11,20]]},"abstract":"<jats:p>Graph Convolutional Network (GCN) is an important method for learning graph representations of nodes. For large-scale graphs, the GCN could meet with the neighborhood expansion phenomenon, which makes the model complexity high and the training time long. An efficient solution is to adopt graph sampling techniques, such as node sampling and random walk sampling. However, the existing sampling methods still suffer from aggregating too many neighbor nodes and ignoring node feature information. Therefore, in this paper, we propose a new subgraph sampling method, namely, Similarity-Aware Random Walk (SARW), for GCN with large-scale graphs. A novel similarity index between two adjacent nodes is proposed, describing the relationship of nodes with their neighbors. Then, we design a sampling probability expression between adjacent nodes using node feature information, degree information, neighbor set information, etc. Moreover, we prove the unbiasedness of the SARW-based GCN model for node representations. The simplified version of SARW (SSARW) has a much smaller variance, which indicates the effectiveness of our subgraph sampling method in large-scale graphs for GCN learning. Experiments on six datasets show our method achieves superior performance over the state-of-the-art graph sampling approaches for the large-scale graph node classification task.<\/jats:p>","DOI":"10.3233\/ida-227085","type":"journal-article","created":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T15:20:25Z","timestamp":1698420025000},"page":"1615-1636","source":"Crossref","is-referenced-by-count":1,"title":["SARW: Similarity-Aware Random Walk for GCN"],"prefix":"10.1177","volume":"27","author":[{"given":"Linlin","family":"Hou","sequence":"first","affiliation":[{"name":"Zhejiang Laboratory, Hangzhou, Zhejiang, China"},{"name":"Center for Applied Mathematics, Tianjin University, Tianjin, China"}]},{"given":"Haixiang","family":"Zhang","sequence":"additional","affiliation":[{"name":"Center for Applied Mathematics, Tianjin University, Tianjin, China"}]},{"given":"Qing-Hu","family":"Hou","sequence":"additional","affiliation":[{"name":"Center for Applied Mathematics, Tianjin University, Tianjin, China"}]},{"given":"Alan J.X.","family":"Guo","sequence":"additional","affiliation":[{"name":"Center for Applied Mathematics, Tianjin University, Tianjin, China"}]},{"given":"Ou","family":"Wu","sequence":"additional","affiliation":[{"name":"Center for Applied Mathematics, Tianjin University, Tianjin, China"}]},{"given":"Ting","family":"Yu","sequence":"additional","affiliation":[{"name":"Zhejiang Laboratory, Hangzhou, Zhejiang, China"}]},{"given":"Ji","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Southern Queensland, Australia"}]}],"member":"179","reference":[{"key":"10.3233\/IDA-227085_ref1","doi-asserted-by":"crossref","unstructured":"Y. Zhou, H. Zheng, X. Huang, S. Hao, D. Li and J. Zhao, Graph neural networks: Taxonomy, advances, and trends, ACM Trans. Intell. Syst. Technol. 13(1) (2022).","DOI":"10.1145\/3495161"},{"key":"10.3233\/IDA-227085_ref2","unstructured":"D. Kim and R.o.K. Alice Oh KAIST, How to Find Your Friendly Neighborhood: Graph Attention Design with Self-supervision, in: ICLR, 2021."},{"key":"10.3233\/IDA-227085_ref7","doi-asserted-by":"crossref","first-page":"107643","DOI":"10.1016\/j.knosys.2021.107643","article-title":"Aspect-based sentiment analysis via affective knowledge enhanced graph convolutional networks","volume":"235","author":"Liang","year":"2022","journal-title":"Knowledge-Based Systems"},{"key":"10.3233\/IDA-227085_ref9","doi-asserted-by":"crossref","unstructured":"Z. Wang, Z. Wei, Y. Li, W. Kuang and B. Ding, Graph Neural Networks with Node-Wise Architecture, in: KDD, Association for Computing Machinery, 2022, pp.\u00a01949\u20131958.","DOI":"10.1145\/3534678.3539387"},{"key":"10.3233\/IDA-227085_ref10","unstructured":"F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu and K. Weinberger, Simplifying Graph Convolutional Networks, in: ICML, 2019, pp.\u00a06861\u20136871."},{"key":"10.3233\/IDA-227085_ref11","doi-asserted-by":"crossref","unstructured":"H. Park and J. Neville, Exploiting Interaction Links for Node Classification with Deep Graph Neural Networks, in: IJCAI, 2019, pp.\u00a03223\u20133230.","DOI":"10.24963\/ijcai.2019\/447"},{"key":"10.3233\/IDA-227085_ref12","unstructured":"T.N. Kipf and M. Welling, Semi-Supervised Classification with Graph Convolutional Networks, in: ICLR, 2017."},{"issue":"10","key":"10.3233\/IDA-227085_ref13","doi-asserted-by":"crossref","first-page":"2541","DOI":"10.1109\/TPDS.2021.3065737","article-title":"Efficient Data Loader for Fast Sampling-Based GNN Training on Large Graphs","volume":"32","author":"Bai","year":"2021","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"issue":"2","key":"10.3233\/IDA-227085_ref14","doi-asserted-by":"crossref","first-page":"1698","DOI":"10.1109\/TVCG.2020.3030428","article-title":"Preserving minority structures in graph sampling","volume":"27","author":"Zhao","year":"2021","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"10.3233\/IDA-227085_ref16","unstructured":"J. Chen, J. Zhu and L. Song, Stochastic Training of Graph Convolutional Networks with Variance Reduction, in: ICML, Vol. 80, 2018, pp.\u00a0942\u2013950."},{"key":"10.3233\/IDA-227085_ref17","unstructured":"D. Zou, Z. Hu, Y. Wang, S. Jiang, Y. Sun and Q. Gu, Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks, in: NIPS, 2019."},{"key":"10.3233\/IDA-227085_ref18","doi-asserted-by":"crossref","unstructured":"W. Chiang, X. Liu, S. Si, Y. Li, S. Bengio and C. Hsieh, Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks, in: KDD, 2019.","DOI":"10.1145\/3292500.3330925"},{"key":"10.3233\/IDA-227085_ref20","unstructured":"H. Zeng, H. Zhou, A. Srivastava, R. Kannan and V. Prasanna, GraphSAINT: Graph sampling based inductive learning method, in: ICLR, 2020."},{"key":"10.3233\/IDA-227085_ref22","doi-asserted-by":"crossref","unstructured":"L. Yang, Z. Liu, Y. Dou, J. Ma and P.S. Yu, ConsisRec: Enhancing GNN for Social Recommendation via Consistent Neighbor Aggregation, in: SIGIR, Association for Computing Machinery, 2021, pp.\u00a02141\u20132145.","DOI":"10.1145\/3404835.3463028"},{"key":"10.3233\/IDA-227085_ref24","doi-asserted-by":"crossref","unstructured":"A. Pal, C. Eksombatchai, Y. Zhou, B. Zhao, C. Rosenberg and J. Leskovec, PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest, in: KDD, 2020, pp.\u00a02311\u20132320.","DOI":"10.1145\/3394486.3403280"},{"key":"10.3233\/IDA-227085_ref25","doi-asserted-by":"crossref","unstructured":"C. Gao, X. Wang, X. He and Y. Li, Graph Neural Networks for Recommender System, in: WSDM, 2022, pp.\u00a01623\u20131625.","DOI":"10.1145\/3488560.3501396"},{"key":"10.3233\/IDA-227085_ref26","doi-asserted-by":"crossref","unstructured":"X. Liu, X. You, X. Zhang, J. Wu and P. Lv, Tensor Graph Convolutional Networks for Text Classification, in: AAAI, 2020, pp.\u00a08409\u20138416.","DOI":"10.1609\/aaai.v34i05.6359"},{"key":"10.3233\/IDA-227085_ref27","doi-asserted-by":"crossref","first-page":"105443","DOI":"10.1016\/j.knosys.2019.105443","article-title":"Modeling sentiment dependencies with graph convolutional networks for aspect-level sentiment classification","volume":"193","author":"Zhao","year":"2020","journal-title":"Knowledge-Based Systems"},{"key":"10.3233\/IDA-227085_ref28","doi-asserted-by":"crossref","unstructured":"G. Nikolentzos and M. Vazirgiannis, Random Walk Graph Neural Networks, in: NeurIPS, 2020, pp.\u00a016211\u201316222.","DOI":"10.1016\/j.neunet.2020.07.008"},{"key":"10.3233\/IDA-227085_ref29","unstructured":"H. Pei, B. Wei, K.C.-C. Chang, Y. Lei and B. Yang, Geom-GCN: Geometric Graph Convolutional Networks, in: ICLR, 2020."},{"key":"10.3233\/IDA-227085_ref31","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.comcom.2021.12.015","article-title":"Graph-based deep learning for communication networks: A survey","volume":"185","author":"Jiang","year":"2022","journal-title":"Computer Communications"},{"key":"10.3233\/IDA-227085_ref32","unstructured":"Z. Chen, L. Li and J. Bruna, Supervised Community Detection with Line Graph Neural Networks, in: ICLR, 2020."},{"issue":"9","key":"10.3233\/IDA-227085_ref33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3477141","article-title":"Computing graph neural networks: A survey from algorithms to accelerators","volume":"54","author":"Abadal","year":"2021","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"10.3233\/IDA-227085_ref34","unstructured":"K. Xu, W. Hu, J. Leskovec and S. Jegelka, How Powerful are Graph Neural Networks, in: ICLR, 2019."},{"key":"10.3233\/IDA-227085_ref35","unstructured":"J. Bruna, W. Zaremba, A. Szlam and Y. LeCun, Spectral networks and deep locally connected networks on graphs, in: ICLR, 2014."},{"key":"10.3233\/IDA-227085_ref36","doi-asserted-by":"crossref","unstructured":"X. Hou, J. Huang, G. Wang, P. Qi, X. He and B. Zhou, Selective Attention Based Graph Convolutional Networks for Aspect-Level Sentiment Classification, in: Proceedings of the Fifteenth Workshop on Graph-Based Methods for Natural Language Processing (TextGraphs-15), 2021, pp.\u00a083\u201393.","DOI":"10.18653\/v1\/2021.textgraphs-1.8"},{"key":"10.3233\/IDA-227085_ref37","doi-asserted-by":"crossref","unstructured":"X. Wang, X. He, Y. Cao, M. Liu and T.-S. Chua, KGAT: Knowledge Graph Attention Network for Recommendation, in: KDD, 2019, pp.\u00a0950\u2013958.","DOI":"10.1145\/3292500.3330989"},{"key":"10.3233\/IDA-227085_ref38","unstructured":"A. Hasanzadeh, E. Hajiramezanali, S. Boluki, M. Zhou, N. Duffield, K. Narayanan and X. Qian, Bayesian graph neural networks with adaptive connection sampling, in: International Conference on Machine Learning, PMLR, 2020, pp.\u00a04094\u20134104."},{"key":"10.3233\/IDA-227085_ref39","doi-asserted-by":"crossref","unstructured":"W. Cong, R. Forsati, M. Kandemir and M. Mahdavi, Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks, in: KDD, 2020, pp.\u00a01393\u20131403.","DOI":"10.1145\/3394486.3403192"},{"key":"10.3233\/IDA-227085_ref40","doi-asserted-by":"crossref","unstructured":"R. Ying, R. He, K. Chen, P. Eksombatchai, W.L. Hamilton and J. Leskovec, Graph Convolutional Neural Networks for Web-Scale Recommender Systems, in: KDD, 2018, pp.\u00a0974\u2013983.","DOI":"10.1145\/3219819.3219890"},{"key":"10.3233\/IDA-227085_ref41","unstructured":"W. Huang, T. Zhang, Y. Rong and J. Huang, Adaptive Sampling towards Fast Graph Representation Learning, in: NIPS, 2018, pp.\u00a04563\u20134572."},{"key":"10.3233\/IDA-227085_ref42","unstructured":"W.L. Hamilton, R. Ying and J. Leskovec, Inductive Representation Learning on Large Graphs, in: NIPS, 2017, pp.\u00a01025\u20131035."},{"key":"10.3233\/IDA-227085_ref43","unstructured":"J. Chen, T. Ma and C. Xiao, FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling, in: ICLR, 2018."},{"key":"10.3233\/IDA-227085_ref44","doi-asserted-by":"crossref","unstructured":"H. Zeng, H. Zhou, A. Srivastava, R. Kannan and V. Prasanna, Accurate, efficient and scalable graph embedding, in: 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2019, pp.\u00a0462\u2013471.","DOI":"10.1109\/IPDPS.2019.00056"},{"key":"10.3233\/IDA-227085_ref45","doi-asserted-by":"crossref","unstructured":"X. Wang, P. Cui, J. Wang, J. Pei, W. Zhu and S. Yang, Community Preserving Network Embedding, in: AAAI, 2017, pp.\u00a0203\u2013209.","DOI":"10.1609\/aaai.v31i1.10488"},{"key":"10.3233\/IDA-227085_ref46","doi-asserted-by":"crossref","unstructured":"L. Xu, X. Wei, J. Cao and P.S. Yu, Embedding Identity and Interest for Social Networks, in: WWW, 2017, pp.\u00a0859\u2013860.","DOI":"10.1145\/3041021.3054268"},{"key":"10.3233\/IDA-227085_ref47","doi-asserted-by":"crossref","unstructured":"Y. Li, Z. Wu, S. Lin, H. Xie, M. Lv, Y. Xu and J.C.s. Lui, Walking with Perception: Efficient Random Walk Sampling via Common Neighbor Awareness, in: ICDE, 2019, pp.\u00a0962\u2013973.","DOI":"10.1109\/ICDE.2019.00090"},{"key":"10.3233\/IDA-227085_ref48","doi-asserted-by":"crossref","unstructured":"C.-H. Lee, X. Xu and D.Y. Eun, Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling, in: SIGMETRICS, 2012, pp.\u00a0319\u2013330.","DOI":"10.1145\/2318857.2254795"},{"key":"10.3233\/IDA-227085_ref49","unstructured":"R.-H. Li, J.X. Yu, L. Qin, R. Mao and T. Jin, On random walk based graph sampling, in: ICDE, 2015, pp.\u00a0927\u2013938."},{"key":"10.3233\/IDA-227085_ref50","unstructured":"L. Lov\u00e1sz and P. Erdos, Random walks on graphs: A survey, Combinatorics 2 (1993)."}],"container-title":["Intelligent Data Analysis"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/IDA-227085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,11]],"date-time":"2025-03-11T07:14:06Z","timestamp":1741677246000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/IDA-227085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,20]]},"references-count":40,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.3233\/ida-227085","relation":{},"ISSN":["1088-467X","1571-4128"],"issn-type":[{"value":"1088-467X","type":"print"},{"value":"1571-4128","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,20]]}}}