{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:10Z","timestamp":1740122410400,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T00:00:00Z","timestamp":1723507200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T00:00:00Z","timestamp":1723507200000},"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":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Label propagation is frequently encountered in machine learning and data mining applications on graphs, either as a standalone problem or as part of node classification. Many label propagation algorithms utilize random walks (or network propagation), which provide limited ability to take into account negatively-labeled nodes (i.e., nodes that are known to be not associated with the label of interest). Specialized algorithms to incorporate negatively-labeled nodes generally focus on learning or readjusting the edge weights to drive walks away from negatively-labeled nodes and toward positively-labeled nodes. This approach has several disadvantages, as it increases the number of parameters to be learned, and does not necessarily drive the walk away from regions of the network that are rich in negatively-labeled nodes. We reformulate random walk with restarts and network propagation to enable \u201cvariable restarts\", that is the increased likelihood of restarting at a positively-labeled node when a negatively-labeled node is encountered. Based on this reformulation, we develop <jats:sc>CusTaRd<\/jats:sc>, an algorithm that effectively combines variable restart probabilities and edge re-weighting to avoid negatively-labeled nodes. To assess the performance of <jats:sc>CusTaRd<\/jats:sc>, we perform comprehensive experiments on network datasets commonly used in benchmarking label propagation and node classification algorithms. Our results show that <jats:sc>CusTaRd<\/jats:sc> consistently outperforms competing algorithms that learn edge weights or restart profiles, and that negatives close to positive examples are generally more informative than more distant negatives.<\/jats:p>","DOI":"10.1007\/s10618-024-01065-4","type":"journal-article","created":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T19:02:21Z","timestamp":1723575741000},"page":"4024-4039","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Random walks with variable restarts for negative-example-informed label propagation"],"prefix":"10.1007","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8924-8111","authenticated-orcid":false,"given":"Sean","family":"Maxwell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mehmet","family":"Koyut\u00fcrk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,13]]},"reference":[{"key":"1065_CR1","doi-asserted-by":"crossref","unstructured":"Adamic LA, Glance N (2005) The political blogosphere and the 2004 us election: divided they blog. In: Proceedings of the 3rd international workshop on Link discovery, pp 36\u201343","DOI":"10.1145\/1134271.1134277"},{"key":"1065_CR2","doi-asserted-by":"publisher","unstructured":"Backstrom L, Leskovec J (2011) Supervised random walks: predicting and recommending links in social networks. In: Proceedings of the Fourth ACM international conference on web search and data mining, WSDM \u201911, New York. Association for Computing Machinery, pp 635\u2013644. ISBN 9781450304931. https:\/\/doi.org\/10.1145\/1935826.1935914","DOI":"10.1145\/1935826.1935914"},{"issue":"17","key":"1065_CR3","doi-asserted-by":"publisher","first-page":"e98","DOI":"10.1093\/nar\/gkaa639","volume":"48","author":"G Barel","year":"2020","unstructured":"Barel G, Herwig R (2020) Netcore: a network propagation approach using node coreness. Nucl Acids Res 48(17):e98\u2013e98","journal-title":"Nucl Acids Res"},{"key":"1065_CR4","doi-asserted-by":"publisher","unstructured":"Berberidis D, Nikolakopoulos A, Giannakis G (2018) Random walks with restarts for graph-based classification: teleportation tuning and sampling design. In: 2018 IEEE international conference on acoustics, speech, and signal processing, ICASSP 2018\u2014proceedings, volume 2018-April of ICASSP, IEEE international conference on acoustics, speech and signal processing-proceedings. Institute of Electrical and Electronics Engineers Inc., pp 2811\u20132815. ISBN 9781538646588. https:\/\/doi.org\/10.1109\/ICASSP.2018.8461548","DOI":"10.1109\/ICASSP.2018.8461548"},{"issue":"9","key":"1065_CR5","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1038\/nrg.2017.38","volume":"18","author":"L Cowen","year":"2017","unstructured":"Cowen L, Ideker T, Raphael BJ, Sharan R (2017) Network propagation: a universal amplifier of genetic associations. Nat Rev Genet 18(9):551\u2013562","journal-title":"Nat Rev Genet"},{"key":"1065_CR6","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.patrec.2014.01.001.","volume":"42","author":"B Fu","year":"2014","unstructured":"Fu B, Wang Z, Xu G, Cao L (2014) Multi-label learning based on iterative label propagation over graph. Pattern Recogn Lett 42:85\u201390. https:\/\/doi.org\/10.1016\/j.patrec.2014.01.001.","journal-title":"Pattern Recogn Lett"},{"key":"1065_CR7","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2019.122058","volume":"534","author":"SE Garza","year":"2019","unstructured":"Garza SE, Schaeffer SE (2019) Community detection with the label propagation algorithm: a survey. Physica A Stat Mech Appl 534:122058","journal-title":"Physica A Stat Mech Appl"},{"key":"1065_CR8","doi-asserted-by":"publisher","unstructured":"Getoor L (2005) Link-based Classification. Springer, London, pp 189\u2013207. ISBN: 978-1-84628-284-3, https:\/\/doi.org\/10.1007\/1-84628-284-5_7","DOI":"10.1007\/1-84628-284-5_7"},{"key":"1065_CR9","unstructured":"Huang Q, He H, Singh A, Lim S-N, Benson AR (2021) Combining label propagation and simple models out-performs graph neural networks. In: ICLR"},{"key":"1065_CR10","doi-asserted-by":"crossref","unstructured":"Hwang T, Kuang R (2010) A heterogeneous label propagation algorithm for disease gene discovery. In: Proceedings of the 2010 SIAM international conference on data mining. SIAM, pp 583\u2013594","DOI":"10.1137\/1.9781611972801.51"},{"issue":"3","key":"1065_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0213857","volume":"14","author":"W Jin","year":"2019","unstructured":"Jin W, Jung J, Kang U (2019) Supervised and extended restart in random walks for ranking and link prediction in networks. PLOS ONE 14(3):1\u201323. https:\/\/doi.org\/10.1371\/journal.pone.0213857","journal-title":"PLOS ONE"},{"key":"1065_CR12","doi-asserted-by":"crossref","unstructured":"Klicpera J, Bojchevski A, G\u00fcnnemann S (2019) Predict then propagate: graph neural networks meet personalized pagerank. In: ICLR","DOI":"10.1145\/3394486.3403296"},{"key":"1065_CR13","doi-asserted-by":"publisher","unstructured":"Li L, Yao Y, Tang J, Fan W, Tong H (2016) Quint: on query-specific optimal networks. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, KDD \u201916, New York. Association for Computing Machinery, pp 985\u2013994. ISBN 9781450342322. https:\/\/doi.org\/10.1145\/2939672.2939768","DOI":"10.1145\/2939672.2939768"},{"key":"1065_CR14","doi-asserted-by":"crossref","unstructured":"Li Q, Han Z, Wu X-M (2018) Deeper insights into graph convolutional networks for semi-supervised learning. In: Thirty-second AAAI conference on artificial intelligence","DOI":"10.1609\/aaai.v32i1.11604"},{"key":"1065_CR15","doi-asserted-by":"crossref","unstructured":"Liao Y, Yuan S, Chen J, Wu Q, Li B (2016) Joint classification with heterogeneous labels using random walk with dynamic label propagation. In: Bailey J, Khan L, Washio T, Dobbie G, Huang JZ, Wang R (eds) Advances in knowledge discovery and data mining. Springer, Cham, pp 3\u201313. ISBN: 978-3-319-31753-3","DOI":"10.1007\/978-3-319-31753-3_1"},{"key":"1065_CR16","unstructured":"Pan J-Y, Yang H-J, Faloutsos C, Duygulu P, Automatic multimedia cross-modal correlation discovery. KDD \u201904. Association for Computing Machinery, New York, pp 653\u2013658. ISBN: 1581138881"},{"key":"1065_CR17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106","volume":"76","author":"UN Raghavan","year":"2007","unstructured":"Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106","journal-title":"Phys Rev E"},{"key":"1065_CR18","unstructured":"Rozemberczki B, Allen C, Sarkar R (2019) Multi-scale attributed node embedding"},{"key":"1065_CR19","doi-asserted-by":"crossref","unstructured":"Sen P, Namata G, Bilgic M, Getoor L, Gallagher B, Eliassi-Rad T (2008) Collective classification in network data. Technical report, University of Maryland, College Park and Lawrence Livermore National Laboratory. https:\/\/drum.lib.umd.edu\/handle\/1903\/7546","DOI":"10.1609\/aimag.v29i3.2157"},{"key":"1065_CR20","doi-asserted-by":"crossref","unstructured":"Shi W, Chen J, Feng F, Zhang J, Wu J, Gao C, He X (2023) On the theories behind hard negative sampling for recommendation","DOI":"10.1145\/3543507.3583223"},{"key":"1065_CR21","unstructured":"Wagner T, Guha S, Kasiviswanathan S, Mishra N (2018) Semi-supervised learning on data streams via temporal label propagation. In: Dy J, Krause A (eds) Proceedings of the 35th international conference on machine learning, volume\u00a080 of proceedings of machine learning research. PMLR, pp 5095\u20135104. https:\/\/proceedings.mlr.press\/v80\/wagner18a.html"},{"key":"1065_CR22","doi-asserted-by":"crossref","unstructured":"Wang B, Jia J, Gong NZ (2021) Semi-supervised node classification on graphs: Markov random fields versus graph neural networks. In: Proceedings of the AAAI conference on artificial intelligence, vol 35, pp 10093\u201310101","DOI":"10.1609\/aaai.v35i11.17211"},{"issue":"1","key":"1065_CR23","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 (2020) Microsoft academic graph: when experts are not enough. Quant Sci Stud 1(1):396\u2013413. https:\/\/doi.org\/10.1162\/qss_a_00021","journal-title":"Quant Sci Stud"},{"key":"1065_CR24","doi-asserted-by":"crossref","unstructured":"Xie G, Huang B, Sun Y, Wu C, Han Y (2021) Rwsf-blp: a novel lncrna-disease association prediction model using random walk-based multi-similarity fusion and bidirectional label propagation. Mol Genet Genom 1\u201311","DOI":"10.1007\/s00438-021-01764-3"},{"key":"1065_CR25","doi-asserted-by":"publisher","first-page":"1123","DOI":"10.1016\/j.amc.2015.09.057","volume":"273","author":"P Xie","year":"2016","unstructured":"Xie P, Zhang Z, Comellas F (2016) On the spectrum of the normalized Laplacian of iterated triangulations of graphs. Appl Math Comput 273:1123\u20131129. https:\/\/doi.org\/10.1016\/j.amc.2015.09.057","journal-title":"Appl Math Comput"},{"key":"1065_CR26","unstructured":"Zhou D, Bousquet O, Lal TN, Weston J, Sch\u00f6lkopf B (2004) Learning with local and global consistency. In: Advances in neural information processing systems, pp 321\u2013328"},{"issue":"2","key":"1065_CR27","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1109\/TCSVT.2016.2598671","volume":"28","author":"O Zoidi","year":"2018","unstructured":"Zoidi O, Tefas A, Nikolaidis N, Pitas I (2018) Positive and negative label propagations. IEEE Trans Circuits Syst Video Technol 28(2):342\u2013355. https:\/\/doi.org\/10.1109\/TCSVT.2016.2598671","journal-title":"IEEE Trans Circuits Syst Video Technol"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-024-01065-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-024-01065-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-024-01065-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T09:12:14Z","timestamp":1730106734000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-024-01065-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,13]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["1065"],"URL":"https:\/\/doi.org\/10.1007\/s10618-024-01065-4","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"type":"print","value":"1384-5810"},{"type":"electronic","value":"1573-756X"}],"subject":[],"published":{"date-parts":[[2024,8,13]]},"assertion":[{"value":"17 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}