{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T16:39:27Z","timestamp":1746549567498},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T00:00:00Z","timestamp":1721606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T00:00:00Z","timestamp":1721606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Active learning for graph neural networks (GNNs) aims to select <jats:italic>B<\/jats:italic> nodes to label for the best possible GNN performance. Carefully selected labeled nodes can help improve GNN performance and hence motivates a line of research works. Unfortunately, existing methods still provide inferior GNN performance or cannot scale to large networks.Motivated by these limitations, in this paper, we present <jats:italic>FICOM<\/jats:italic>, an effective and scalable GNN active learning framework. Firstly, we formulate the node selection as an optimization problem where we consider the importance of a node from (i) the importance of a node during the feature propagation with a connection to the personalized PageRank (PPR), and (ii) the diversity of a node brings in the embedding space generated by feature propagation. We show that the defined problem is submodular, and a greedy solution can provide a <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1-1\/e)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mi>e<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximate solution.However, a standard greedy solution requires getting the node with the maximum marginal gain of the objective score in each iteration, which incurs a prohibitive running cost and cannot scale to large datasets. As our main contribution, we present FICOM, an efficient and scalable solution that provides <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1-1\/e)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mi>e<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation guarantee and scales to graphs with millions of nodes on a single machine. The main idea is that we adaptively maintain the lower- and upper-bound of the marginal gain for each node <jats:italic>v<\/jats:italic>. In each iteration, we can first derive a small subset of candidate nodes and then compute the exact score for this subset of candidate nodes so that we can find the node with the maximum marginal gain efficiently. Extensive experiments on six benchmark datasets using four GNNs, including GCN, SGC, APPNP, and GCNII, show that our FICOM consistently outperforms existing active learning approaches on semi-supervised node classification tasks using different GNNs. Moreover, our solution can finish within 5\u00a0h on a million-node graph.<\/jats:p>","DOI":"10.1007\/s00778-024-00870-z","type":"journal-article","created":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T18:02:12Z","timestamp":1721671332000},"page":"1723-1742","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["FICOM: an effective and scalable active learning framework for GNNs on semi-supervised node classification"],"prefix":"10.1007","volume":"33","author":[{"given":"Xingyi","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinchao","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fangyuan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sibo","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,22]]},"reference":[{"key":"870_CR1","unstructured":"Bhatia, K., Dahiya, K., Jain, H., Kar, P., Mittal, A., Prabhu, Y., Varma, M.: The extreme classification repository: Multi-label datasets and code (2016) http:\/\/manikvarma.org\/downloads\/XC\/XMLRepository.html"},{"key":"870_CR2","doi-asserted-by":"crossref","unstructured":"Bojchevski, A., Klicpera, J., Perozzi, B., Kapoor, A., Blais, M., R\u00f3zemberczki, B., Lukasik, M., G\u00fcnnemann, S.: Scaling graph neural networks with approximate pagerank. In: SIGKDD, pp. 2464\u20132473 (2020)","DOI":"10.1145\/3394486.3403296"},{"key":"870_CR3","unstructured":"Brinker, K.: Incorporating diversity in active learning with support vector machines. In: ICML, pp. 59\u201366 (2003)"},{"key":"870_CR4","unstructured":"Cai, H., Zheng, V.W., Chang, K.C.C.: Active learning for graph embedding. CoRRabs\/1705.05085 (2017)"},{"key":"870_CR5","unstructured":"Chen, M., Wei, Z., Huang, Z., Ding, B., Li, Y.: Simple and deep graph convolutional networks. In: ICML, pp. 1725\u20131735 (2020)"},{"key":"870_CR6","unstructured":"Chien, E., Peng, J., Li, P., Milenkovic, O.: Adaptive universal generalized pagerank graph neural network. In: ICLR (2021)"},{"key":"870_CR7","doi-asserted-by":"crossref","unstructured":"Cohen, E., Kaplan, H.: Summarizing data using bottom-k sketches. In: PODC, pp. 225\u2013234 (2007)","DOI":"10.1145\/1281100.1281133"},{"key":"870_CR8","unstructured":"Cong, W., Ramezani, M., Mahdavi, M.: On provable benefits of depth in training graph convolutional networks. In: NeurIPS, pp. 9936\u20139949 (2021)"},{"issue":"8","key":"870_CR9","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G Cornuejols","year":"1977","unstructured":"Cornuejols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manage. Sci. 23(8), 789\u2013810 (1977)","journal-title":"Manage. Sci."},{"key":"870_CR10","doi-asserted-by":"crossref","unstructured":"Du, X., Zhang, X., Wang, S., Huang, Z.: Efficient tree-svd for subset node embedding over large dynamic graphs. PACMMOD 1(1), 96:1\u201396:26 (2023)","DOI":"10.1145\/3588950"},{"key":"870_CR11","doi-asserted-by":"crossref","unstructured":"Gao, L., Yang, H., Zhou, C., Wu, J., Pan, S., Hu, Y.: Active discriminative network representation learning. In: IJCAI, pp. 2142\u20132148 (2018)","DOI":"10.24963\/ijcai.2018\/296"},{"key":"870_CR12","unstructured":"Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural message passing for quantum chemistry. In: ICML, pp. 1263\u20131272 (2017)"},{"key":"870_CR13","unstructured":"Hamilton, W.L., Ying, R., Leskovec, J.: Inductive representation learning on large graphs. In: NeurIPS (2017)"},{"issue":"9","key":"870_CR14","first-page":"1668","volume":"14","author":"G Hou","year":"2021","unstructured":"Hou, G., Chen, X., Wang, S., Wei, Z.: Massively parallel algorithms for personalized pagerank. PVLDB 14(9), 1668\u20131680 (2021)","journal-title":"PVLDB"},{"issue":"1","key":"870_CR15","first-page":"25:1","volume":"1","author":"G Hou","year":"2023","unstructured":"Hou, G., Guo, Q., Zhang, F., Wang, S., Wei, Z.: Personalized pagerank on evolving graphs with an incremental index-update scheme. PACMMOD 1(1), 25:1-25:26 (2023)","journal-title":"PACMMOD"},{"key":"870_CR16","first-page":"10174","volume":"33","author":"S Hu","year":"2020","unstructured":"Hu, S., Xiong, Z., Qu, M., Yuan, X., C\u00f4t\u00e9, M.A., Liu, Z., Tang, J.: Graph policy network for transferable active learning on graphs. NeurIPS 33, 10174\u201310185 (2020)","journal-title":"NeurIPS"},{"key":"870_CR17","unstructured":"Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., Leskovec, J.: Open graph benchmark: Datasets for machine learning on graphs. In: NeurIPS, pp. 22,118\u201322,133 (2020)"},{"key":"870_CR18","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: SIGKDD, pp. 137\u2013146 (2003)","DOI":"10.1145\/956750.956769"},{"key":"870_CR19","unstructured":"Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: ICLR (2017)"},{"key":"870_CR20","doi-asserted-by":"crossref","unstructured":"Klicpera, J., Bojchevski, A., G\u00fcnnemann, S.: Predict then propagate: Graph neural networks meet personalized pagerank. In: ICLR (2019)","DOI":"10.1145\/3394486.3403296"},{"key":"870_CR21","first-page":"05485","volume":"1911","author":"J Klicpera","year":"2019","unstructured":"Klicpera, J., Wei\u00dfenberger, S., G\u00fcnnemann, S.: Diffusion improves graph learning. CoRR 1911, 05485 (2019)","journal-title":"CoRR"},{"key":"870_CR22","doi-asserted-by":"crossref","unstructured":"Li, Q., Han, Z., Wu, X.M.: Deeper insights into graph convolutional networks for semi-supervised learning. In: AAAI (2018)","DOI":"10.1609\/aaai.v32i1.11604"},{"issue":"10","key":"870_CR23","first-page":"1897","volume":"32","author":"S Luo","year":"2019","unstructured":"Luo, S., Xiao, X., Lin, W., Kao, B.: Baton: batch one-hop personalized pageranks with efficiency and accuracy. TKDE 32(10), 1897\u20131908 (2019)","journal-title":"TKDE"},{"key":"870_CR24","unstructured":"Ming, C., Zhewei, W., Bolin, D., LiYaliang, Ye, Y., Xiaoyong, D., Ji-Rong, W.: Scalable graph neural networks via bidirectional propagation. In: NeurIPS (2020)"},{"key":"870_CR25","doi-asserted-by":"crossref","unstructured":"Mo, D., Luo, S.: Agenda: Robust personalized pageranks in evolving graphs. In: CIKM, pp. 1315\u20131324 (2021)","DOI":"10.1145\/3459637.3482317"},{"key":"870_CR26","unstructured":"Namata, G., London, B., Getoor, L., Huang, B.: Query-driven active surveying for collective classification. In: MLG (2012)"},{"issue":"1","key":"870_CR27","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"870_CR28","unstructured":"Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: bringing order to the web (1999)"},{"key":"870_CR29","unstructured":"Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., Chintala, S.: Pytorch: An imperative style, high-performance deep learning library. In: NeurIPS (2019)"},{"issue":"3","key":"870_CR30","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1609\/aimag.v29i3.2157","volume":"29","author":"P Sen","year":"2008","unstructured":"Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., Eliassi-Rad, T.: Collective classification in network data. AI magazine 29(3), 93\u201393 (2008)","journal-title":"AI magazine"},{"key":"870_CR31","unstructured":"Settles, B.: Active learning literature survey (2009)"},{"key":"870_CR32","doi-asserted-by":"crossref","unstructured":"Settles, B., Craven, M.: An analysis of active learning strategies for sequence labeling tasks. In: EMNLP, pp. 1070\u20131079 (2008)","DOI":"10.3115\/1613715.1613855"},{"key":"870_CR33","doi-asserted-by":"crossref","unstructured":"Tang, F., Liu, Q., Zhu, H., Chen, E., Zhu, F.: Diversified social influence maximization. In: ASONAM, pp. 455\u2013459 (2014)","DOI":"10.1109\/ASONAM.2014.6921625"},{"key":"870_CR34","doi-asserted-by":"crossref","unstructured":"Tang, M., Luo, X., Roukos, S.: Active learning for statistical natural language parsing. In: ACL, pp. 120\u2013127 (2002)","DOI":"10.3115\/1073083.1073105"},{"key":"870_CR35","doi-asserted-by":"crossref","unstructured":"Wang, H., He, M., Wei, Z., Wang, S., Yuan, Y., Du, X., Wen, J.R.: Approximate graph propagation. In: SIGKDD, pp. 1686\u20131696 (2021)","DOI":"10.1145\/3447548.3467243"},{"key":"870_CR36","unstructured":"Wang, H., Leskovec, J.: Unifying graph convolutional neural networks and label propagation. CoRR arXiv:2002.06755 (2020)"},{"issue":"1","key":"870_CR37","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1162\/qss_a_00021","volume":"1","author":"K Wang","year":"2020","unstructured":"Wang, K., Shen, Z., Huang, C., Wu, C.H., Dong, Y., Kanakia, A.: Microsoft academic graph: when experts are not enough. Quant. Sci. Stud. 1(1), 396\u2013413 (2020)","journal-title":"Quant. Sci. Stud."},{"issue":"6","key":"870_CR38","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1007\/s00778-019-00576-7","volume":"28","author":"R Wang","year":"2019","unstructured":"Wang, R., Wang, S., Zhou, X.: Parallelizing approximate single-source personalized pagerank queries on shared memory. VLDBJ 28(6), 923\u2013940 (2019)","journal-title":"VLDBJ"},{"issue":"3","key":"870_CR39","first-page":"205","volume":"10","author":"S Wang","year":"2016","unstructured":"Wang, S., Tang, Y., Xiao, X., Yang, Y., Li, Z.: Hubppr: effective indexing for approximate personalized pagerank. PVLDB 10(3), 205\u2013216 (2016)","journal-title":"PVLDB"},{"key":"870_CR40","doi-asserted-by":"crossref","unstructured":"Wang, S., Tao, Y.: Efficient algorithms for finding approximate heavy hitters in personalized pageranks. In: SIGMOD, pp. 1113\u20131127 (2018)","DOI":"10.1145\/3183713.3196919"},{"issue":"4","key":"870_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3360902","volume":"44","author":"S Wang","year":"2019","unstructured":"Wang, S., Yang, R., Wang, R., Xiao, X., Wei, Z., Lin, W., Yang, Y., Tang, N.: Efficient algorithms for approximate single-source personalized pagerank queries. TODS 44(4), 1\u201337 (2019)","journal-title":"TODS"},{"key":"870_CR42","doi-asserted-by":"crossref","unstructured":"Wang, S., Yang, R., Xiao, X., Wei, Z., Yang, Y.: Fora: Simple and effective approximate single-source personalized pagerank. In: SIGKDD, pp. 505\u2013514 (2017)","DOI":"10.1145\/3097983.3098072"},{"key":"870_CR43","doi-asserted-by":"crossref","unstructured":"Wei, Z., He, X., Xiao, X., Wang, S., Shang, S., Wen, J.: Topppr: Top-k personalized pagerank queries with precision guarantees on large graphs. In: SIGMOD, pp. 441\u2013456 (2018)","DOI":"10.1145\/3183713.3196920"},{"key":"870_CR44","unstructured":"Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., Weinberger, K.: Simplifying graph convolutional networks. In: ICML, pp. 6861\u20136871 (2019)"},{"key":"870_CR45","doi-asserted-by":"crossref","unstructured":"Wu, H., Gan, J., Wei, Z., Zhang, R.: Unifying the global and local approaches: an efficient power iteration with forward push. In: SIGMOD 2021, pp. 1996\u20132008 (2021)","DOI":"10.1145\/3448016.3457298"},{"key":"870_CR46","unstructured":"Wu, Y., Xu, Y., Singh, A., Yang, Y., Dubrawski, A.: Active learning graph neural networks via node feature propagation. In: NeurIPS Workshop (2019)"},{"key":"870_CR47","doi-asserted-by":"crossref","unstructured":"Xie, K., Dong, X., Zhang, Y., Zhang, X., Guo, Q., Wang, S.: Learning-based attribute-augmented proximity matrix factorization for attributed network embedding. TKDE (2024)","DOI":"10.1109\/TKDE.2024.3385847"},{"key":"870_CR48","unstructured":"Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.i., Jegelka, S.: Representation learning on graphs with jumping knowledge networks. In: ICML, pp. 5453\u20135462 (2018)"},{"issue":"5","key":"870_CR49","first-page":"670","volume":"13","author":"R Yang","year":"2020","unstructured":"Yang, R., Shi, J., Xiao, X., Yang, Y., Bhowmick, S.S.: Homogeneous network embedding for massive graphs via reweighted personalized pagerank. PVLDB 13(5), 670\u2013683 (2020)","journal-title":"PVLDB"},{"issue":"2","key":"870_CR50","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s11263-014-0781-x","volume":"113","author":"Y Yang","year":"2015","unstructured":"Yang, Y., Ma, Z., Nie, F., Chang, X., Hauptmann, A.G.: Multi-class active learning by uncertainty sampling with diversity maximization. IJCV 113(2), 113\u2013127 (2015)","journal-title":"IJCV"},{"key":"870_CR51","doi-asserted-by":"crossref","unstructured":"Yin, Y., Wei, Z.: Scalable graph embeddings via sparse transpose proximities. In: SIGKDD, pp. 1429\u20131437 (2019)","DOI":"10.1145\/3292500.3330860"},{"key":"870_CR52","unstructured":"Zeng, H., Zhou, H., Srivastava, A., Kannan, R., Prasanna, V.: GraphSAINT: Graph sampling based inductive learning method. In: ICLR (2020)"},{"key":"870_CR53","doi-asserted-by":"crossref","unstructured":"Zhang, W., Shen, Y., Li, Y., Chen, L., Yang, Z., Cui, B.: Alg: Fast and accurate active learning framework for graph convolutional networks. In: SIGMOD, pp. 2366\u20132374 (2021)","DOI":"10.1145\/3448016.3457325"},{"key":"870_CR54","doi-asserted-by":"crossref","unstructured":"Zhang, W., Yang, Z., Wang, Y., Shen, Y., Li, Y., Wang, L., Cui, B.: Grain: improving data efficiency of graph neural networks via diversified influence maximization. PVLDB 14(11), 2473\u20132482 (2021)","DOI":"10.14778\/3476249.3476295"},{"key":"870_CR55","doi-asserted-by":"crossref","unstructured":"Zhang, X., Weng, Z., Wang, S.: Towards deeper understanding of ppr-based embedding approaches: a topological perspective. In: TheWebConf, pp. 969\u2013979 (2024)","DOI":"10.1145\/3589334.3645663"},{"key":"870_CR56","doi-asserted-by":"crossref","unstructured":"Zhang, X., Xie, K., Wang, S., Huang, Z.: Learning based proximity matrix factorization for node embedding. In: SIGKDD, pp. 2243\u20132253 (2021)","DOI":"10.1145\/3447548.3467296"},{"key":"870_CR57","doi-asserted-by":"crossref","unstructured":"Zhang, X., Xu, S., Lin, W., Wang, S.: Constrained social community recommendation. In: SIGKDD, pp. 5586\u20135596 (2023)","DOI":"10.1145\/3580305.3599793"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-024-00870-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-024-00870-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-024-00870-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T12:08:30Z","timestamp":1723896510000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-024-00870-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,22]]},"references-count":57,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["870"],"URL":"https:\/\/doi.org\/10.1007\/s00778-024-00870-z","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2024,7,22]]},"assertion":[{"value":"24 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}