{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T15:14:26Z","timestamp":1775229266584,"version":"3.50.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"AI Singapore Programme","award":["AISG2-RP-2020-01"],"award-info":[{"award-number":["AISG2-RP-2020-01"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Graph convolutional networks (GCNs) are promising for graph learning tasks. For privacy-preserving graph learning tasks involving distributed graph datasets, federated learning (FL)-based GCN (FedGCN) training is required. An important open challenge for FedGCN is scaling to large graphs, which typically incurs 1) high computation overhead for handling the explosively-increasing number of neighbors, and 2) high communication overhead of training GCNs involving multiple FL clients. Thus, neighbor sampling is being studied to enhance the scalability of FedGCNs. Existing FedGCN training techniques with neighbor sampling often produce extremely large communication and computation overhead and inaccurate node embeddings, leading to poor model performance. To bridge this gap, we propose the &lt;u&gt;Fed&lt;\/u&gt;erated &lt;u&gt;A&lt;\/u&gt;daptive &lt;u&gt;A&lt;\/u&gt;ttention-based &lt;u&gt;S&lt;\/u&gt;ampling (FedAAS) approach. It achieves substantial cost savings by efficiently leveraging historical embedding estimators and focusing the limited communication resources on transmitting the most influential neighbor node embeddings across FL clients. We further design an adaptive embedding synchronization scheme to optimize the efficiency and accuracy of FedAAS on large-scale datasets. Theoretical analysis shows that the approximation error induced by the staleness of historical embedding is upper bounded, and the model is guaranteed to converge in an efficient manner. Extensive experimental evaluation against four state-of-the-art baselines on six real-world graph datasets show that FedAAS achieves up to 5.12% higher test accuracy, while saving communication and computation costs by 95.11% and 94.76%, respectively.<\/jats:p>","DOI":"10.1145\/3654947","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-24","source":"Crossref","is-referenced-by-count":1,"title":["Historical Embedding-Guided Efficient Large-Scale Federated Graph Learning"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3592-4153","authenticated-orcid":false,"given":"Anran","family":"Li","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5585-9897","authenticated-orcid":false,"given":"Yuanyuan","family":"Chen","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8316-1894","authenticated-orcid":false,"given":"Jian","family":"Zhang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8982-1483","authenticated-orcid":false,"given":"Mingfei","family":"Cheng","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5784-770X","authenticated-orcid":false,"given":"Yihao","family":"Huang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1515-3558","authenticated-orcid":false,"given":"Yueming","family":"Wu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6062-207X","authenticated-orcid":false,"given":"Anh Tuan","family":"Luu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6893-8650","authenticated-orcid":false,"given":"Han","family":"Yu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3125565"},{"key":"e_1_2_2_2_1","volume-title":"Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247","author":"Chen Jie","year":"2018","unstructured":"Jie Chen, Tengfei Ma, and Cao Xiao. 2018. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247 (2018)."},{"key":"e_1_2_2_3_1","volume-title":"Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv:1710.10568","author":"Chen Jianfei","year":"2017","unstructured":"Jianfei Chen, Jun Zhu, and Le Song. 2017. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv:1710.10568 (2017)."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330925"},{"key":"e_1_2_2_5_1","volume-title":"International conference on machine learning. PMLR, 1106--1114","author":"Dai Hanjun","year":"2018","unstructured":"Hanjun Dai, Zornitsa Kozareva, Bo Dai, Alex Smola, and Le Song. 2018. Learning steady-states of iterative algorithms over graphs. In International conference on machine learning. PMLR, 1106--1114."},{"key":"e_1_2_2_6_1","volume-title":"GraphFed: A Personalized Subgraph Federated Learning Framework for Non-IID Graphs. In 2023 IEEE 20th International Conference on Mobile Ad Hoc and Smart Systems (MASS). IEEE, 227--233","author":"Deng Pan","year":"2023","unstructured":"Pan Deng, Xuefeng Liu, Jianwei Niu, and Chunming Hu. 2023. GraphFed: A Personalized Subgraph Federated Learning Framework for Non-IID Graphs. In 2023 IEEE 20th International Conference on Mobile Ad Hoc and Smart Systems (MASS). IEEE, 227--233."},{"key":"e_1_2_2_7_1","volume-title":"Federated Graph Learning with Periodic Neighbour Sampling. In 2022 IEEE\/ACM 30th International Symposium on Quality of Service (IWQoS). IEEE, 1--10","author":"Du Bingqian","year":"2022","unstructured":"Bingqian Du and Chuan Wu. 2022. Federated Graph Learning with Periodic Neighbour Sampling. In 2022 IEEE\/ACM 30th International Symposium on Quality of Service (IWQoS). IEEE, 1--10."},{"key":"e_1_2_2_8_1","first-page":"1","article-title":"Benchmarking graph neural networks","volume":"24","author":"Dwivedi Vijay Prakash","year":"2023","unstructured":"Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2023. Benchmarking graph neural networks. Journal of Machine Learning Research 24, 43 (2023), 1--48.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_9_1","volume-title":"Thomas Laurent, Yoshua Bengio, and Xavier Bresson.","author":"Dwivedi Vijay Prakash","year":"2021","unstructured":"Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2021. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875 (2021)."},{"key":"e_1_2_2_10_1","first-page":"22326","article-title":"Long range graph benchmark","volume":"35","author":"Dwivedi Vijay Prakash","year":"2022","unstructured":"Vijay Prakash Dwivedi, Ladislav Ramp\u00e1?ek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. 2022. Long range graph benchmark. Advances in Neural Information Processing Systems 35 (2022), 22326--22340.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3467895"},{"key":"e_1_2_2_12_1","volume-title":"Lenssen","author":"Fey Matthias","year":"2019","unstructured":"Matthias Fey and Jan E. Lenssen. 2019. Fast Graph Representation Learning with PyTorch Geometric. In ICLRWorkshop on Representation Learning on Graphs and Manifolds."},{"key":"e_1_2_2_13_1","volume-title":"International Conference on Machine Learning. PMLR, 3294--3304","author":"Fey Matthias","year":"2021","unstructured":"Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec. 2021. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In International Conference on Machine Learning. PMLR, 3294--3304."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/120880811"},{"key":"e_1_2_2_15_1","volume-title":"International conference on machine learning. PMLR, 1263--1272","author":"Gilmer Justin","year":"2017","unstructured":"Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural message passing for quantum chemistry. In International conference on machine learning. PMLR, 1263--1272."},{"key":"e_1_2_2_16_1","volume-title":"Inductive representation learning on large graphs. Advances in neural information processing systems 30","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017)."},{"key":"e_1_2_2_17_1","volume-title":"Federated learning for mobile keyboard prediction. DeepAI","author":"Hard Andrew","year":"2018","unstructured":"Andrew Hard, Kanishka Rao, Rajiv Mathews, and Ramaswamy. 2018. Federated learning for mobile keyboard prediction. DeepAI (2018)."},{"key":"e_1_2_2_18_1","volume-title":"Fedgraphnn: A federated learning system and benchmark for graph neural networks. arXiv preprint arXiv:2104.07145","author":"He Chaoyang","year":"2021","unstructured":"Chaoyang He, Keshav Balasubramanian, Emir Ceyani, Carl Yang, Han Xie, Lichao Sun, Lifang He, Liangwei Yang, Philip S Yu, Yu Rong, et al. 2021. Fedgraphnn: A federated learning system and benchmark for graph neural networks. arXiv preprint arXiv:2104.07145 (2021)."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3182542"},{"key":"e_1_2_2_20_1","volume-title":"Adaptive sampling towards fast graph representation learning. Advances in neural information processing systems 31","author":"Huang Wenbing","year":"2018","unstructured":"Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. 2018. Adaptive sampling towards fast graph representation learning. Advances in neural information processing systems 31 (2018)."},{"key":"e_1_2_2_21_1","volume-title":"International conference on machine learning. PMLR, 2525--2534","author":"Katharopoulos Angelos","year":"2018","unstructured":"Angelos Katharopoulos and Fran\u00e7ois Fleuret. 2018. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning. PMLR, 2525--2534."},{"key":"e_1_2_2_22_1","volume-title":"Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980","author":"Kingma Diederik P","year":"2014","unstructured":"Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)."},{"key":"e_1_2_2_23_1","volume-title":"Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907","author":"Kipf Thomas N","year":"2016","unstructured":"Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_2_25_1","volume-title":"Efficient Federated-Learning Model Debugging. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 372--383","author":"Li Anran","year":"2021","unstructured":"Anran Li, Lan Zhang, Junhao Wang, Juntao Tan, Feng Han, Yaxuan Qin, Nikolaos M Freris, and Xiang-Yang Li. 2021. Efficient Federated-Learning Model Debugging. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 372--383."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00077"},{"key":"e_1_2_2_27_1","volume-title":"Federated graph neural networks: Overview, techniques and challenges. arXiv preprint arXiv:2202.07256","author":"Liu Rui","year":"2022","unstructured":"Rui Liu, Pengwei Xing, Zichao Deng, Anran Li, Cuntai Guan, and Han Yu. 2022. Federated graph neural networks: Overview, techniques and challenges. arXiv preprint arXiv:2202.07256 (2022)."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/JAS.2021.1004311"},{"key":"e_1_2_2_29_1","unstructured":"Brendan McMahan Eider Moore and Ramage. 2017. Communication-efficient learning of deep networks from decentralized data. In ICML."},{"key":"e_1_2_2_30_1","volume-title":"FedWalk: Communication Efficient Federated Unsupervised Node Embedding with Differential Privacy. arXiv preprint arXiv:2205.15896","author":"Pan Qiying","year":"2022","unstructured":"Qiying Pan and Yifei Zhu. 2022. FedWalk: Communication Efficient Federated Unsupervised Node Embedding with Differential Privacy. arXiv preprint arXiv:2205.15896 (2022)."},{"key":"e_1_2_2_31_1","volume-title":"Learn locally, correct globally: A distributed algorithm for training graph neural networks. arXiv preprint arXiv:2111.08202","author":"Ramezani Morteza","year":"2021","unstructured":"Morteza Ramezani, Weilin Cong, Mahmut T Kandemir, and Anand Sivasubramaniam. 2021. Learn locally, correct globally: A distributed algorithm for training graph neural networks. arXiv preprint arXiv:2111.08202 (2021)."},{"key":"e_1_2_2_32_1","first-page":"14501","article-title":"Recipe for a general, powerful, scalable graph transformer","volume":"35","author":"Ladislav","year":"2022","unstructured":"Ladislav Ramp\u00e1?ek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. 2022. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems 35 (2022), 14501--14515.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_33_1","first-page":"12559","article-title":"Self-supervised graph transformer on large-scale molecular data","volume":"33","author":"Rong Yu","year":"2020","unstructured":"Yu Rong, Yatao Bian, Tingyang Xu,Weiyang Xie, YingWei,Wenbing Huang, and Junzhou Huang. 2020. Self-supervised graph transformer on large-scale molecular data. Advances in Neural Information Processing Systems 33 (2020), 12559--12571.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_34_1","volume-title":"Collective classification in network data. AI magazine 29, 3","author":"Sen Prithviraj","year":"2008","unstructured":"Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine 29, 3 (2008), 93--93."},{"key":"e_1_2_2_35_1","volume-title":"Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868","author":"Shchur Oleksandr","year":"2018","unstructured":"Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan G\u00fcnnemann. 2018. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 (2018)."},{"key":"e_1_2_2_36_1","volume-title":"Graph convolutional networks for computational drug development and discovery. Briefings in bioinformatics 21, 3","author":"Sun Mengying","year":"2020","unstructured":"Mengying Sun, Sendong Zhao, Olivier Elemento, Jiayu Zhou, and Fei Wang. 2020. Graph convolutional networks for computational drug development and discovery. Briefings in bioinformatics 21, 3 (2020), 919--935."},{"key":"e_1_2_2_37_1","volume-title":"Federated Learning on Non-IID Graphs via Structural Knowledge Sharing. arXiv preprint arXiv:2211.13009","author":"Tan Yue","year":"2022","unstructured":"Yue Tan, Yixin Liu, Guodong Long, Jing Jiang, Qinghua Lu, and Chengqi Zhang. 2022. Federated Learning on Non-IID Graphs via Structural Knowledge Sharing. arXiv preprint arXiv:2211.13009 (2022)."},{"key":"e_1_2_2_38_1","volume-title":"Attention is all you need. Advances in neural information processing systems 30","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in neural information processing systems 30 (2017)."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380186"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v28i1.8870"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219890"},{"key":"e_1_2_2_42_1","volume-title":"International conference on machine learning. PMLR, 7252--7261","author":"Yurochkin Mikhail","year":"2019","unstructured":"Mikhail Yurochkin, Mayank Agarwal, Nghia Hoang, and Yasaman Khazaeni. 2019. Bayesian nonparametric federated learning of neural networks. In International conference on machine learning. PMLR, 7252--7261."},{"key":"e_1_2_2_43_1","volume-title":"Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931","author":"Zeng Hanqing","year":"2019","unstructured":"Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2019. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931 (2019)."},{"key":"e_1_2_2_44_1","volume-title":"Federated Graph Learning--A Position Paper. arXiv preprint arXiv:2105.11099","author":"Zhang Huanding","year":"2021","unstructured":"Huanding Zhang, Tao Shen, Fei Wu, Mingyang Yin, Hongxia Yang, and Chao Wu. 2021. Federated Graph Learning--A Position Paper. arXiv preprint arXiv:2105.11099 (2021)."},{"key":"e_1_2_2_45_1","first-page":"6671","article-title":"Subgraph federated learning with missing neighbor generation","volume":"34","author":"Zhang Ke","year":"2021","unstructured":"Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. 2021. Subgraph federated learning with missing neighbor generation. Advances in Neural Information Processing Systems 34 (2021), 6671--6682.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_46_1","volume-title":"FedEgo: Privacy-preserving Personalized Federated Graph Learning with Ego-graphs. arXiv preprint arXiv:2208.13685","author":"Zhang Taolin","year":"2022","unstructured":"Taolin Zhang, Chuan Chen, Yaomin Chang, Lin Shu, and Zibin Zheng. 2022. FedEgo: Privacy-preserving Personalized Federated Graph Learning with Ego-graphs. arXiv preprint arXiv:2208.13685 (2022)."},{"key":"e_1_2_2_47_1","volume-title":"Layer-dependent importance sampling for training deep and large graph convolutional networks. Advances in neural information processing systems 32","author":"Zou Difan","year":"2019","unstructured":"Difan Zou, Ziniu Hu, Song Jiang, Yizhou Sun, and Quanquan Gu. 2019. Layer-dependent importance sampling for training deep and large graph convolutional networks. Advances in neural information processing systems 32 (2019)."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654947","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654947","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:38:20Z","timestamp":1755787100000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654947"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654947"],"URL":"https:\/\/doi.org\/10.1145\/3654947","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}