{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:35:53Z","timestamp":1758274553219,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,4,3]],"date-time":"2018-04-03T00:00:00Z","timestamp":1522713600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["1841\/14"],"award-info":[{"award-number":["1841\/14"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2018,4,3]]},"abstract":"<jats:p>\n            Graph-based semi-supervised learning (SSL) algorithms predict labels for all nodes based on provided labels of a small set of seed nodes. Classic methods capture the graph structure through some underlying diffusion process that propagates through the graph edges. Spectral diffusion, which includes personalized page rank and label propagation, propagates through random walks. Social diffusion propagates through shortest paths. These diffusions are\n            <jats:italic>linear<\/jats:italic>\n            in the sense of not distinguishing between contributions of few \"strong\" relations or many \"weak\" relations.\n          <\/jats:p>\n          <jats:p>Recent methods such as node embeddings and graph convolutional networks (GCN) attained significant gains in quality for SSL tasks. These methods vary on how the graph structure, seed label information, and other features are used, but do share a common thread of nonlinearity that suppresses weak relations and reenforces stronger ones.<\/jats:p>\n          <jats:p>\n            Aiming for quality gain with more scalable methods, we revisit classic linear diffusion methods and place them in a self-training framework. The resulting\n            <jats:italic>bootstrapped diffusions<\/jats:italic>\n            are nonlinear in that they re-enforce stronger relations, as with the more complex methods. Surprisingly, we observe that SSL with bootstrapped diffusions not only significantly improves over the respective non-bootstrapped baselines but also outperform state-of-the-art SSL methods. Moreover, since the self-training wrapper retains the scalability of the base method, we obtain both higher quality and better scalability.\n          <\/jats:p>","DOI":"10.1145\/3179413","type":"journal-article","created":{"date-parts":[[2018,4,4]],"date-time":"2018-04-04T12:11:45Z","timestamp":1522843905000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Bootstrapped Graph Diffusions"],"prefix":"10.1145","volume":"2","author":[{"given":"Buchnik","family":"Eliav","sequence":"first","affiliation":[{"name":"Tel Aviv University and Google Research, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edith","family":"Cohen","sequence":"additional","affiliation":[{"name":"Google Research and Tel Aviv University, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,4,3]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1162\/0891201041850876"},{"unstructured":"J. Atwood and D. Towsley. 2016. Diffusion-Convolutional Neural Networks. In NIPS.   J. Atwood and D. Towsley. 2016. Diffusion-Convolutional Neural Networks. In NIPS.","key":"e_1_2_1_2_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.17730\/humo.7.3.f4033344851gl053"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/j.jet.2005.10.003"},{"unstructured":"A. Blum and S. Chawla. 2001. Learning from Labeled and Unlabeled Data Using Graph Mincuts ICML.   A. Blum and S. Chawla. 2001. Learning from Labeled and Unlabeled Data Using Graph Mincuts ICML.","key":"e_1_2_1_5_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/1015330.1015429"},{"doi-asserted-by":"crossref","unstructured":"J. Carlson A. Betteridge B. Kisiel B. Settles E. R. Hruschka Jr. and T. M. Mitchell. 2010. Toward an Architecture for Never-ending Language Learning AAAI.   J. Carlson A. Betteridge B. Kisiel B. Settles E. R. Hruschka Jr. and T. M. Mitchell. 2010. Toward an Architecture for Never-ending Language Learning AAAI.","key":"e_1_2_1_7_1","DOI":"10.1609\/aaai.v24i1.7519"},{"doi-asserted-by":"crossref","unstructured":"O. Chapelle B. Sch\u00f6lkopf and A. Zien. 2006. Semi-supervised learning. MIT Press.   O. Chapelle B. Sch\u00f6lkopf and A. Zien. 2006. Semi-supervised learning. MIT Press.","key":"e_1_2_1_8_1","DOI":"10.7551\/mitpress\/9780262033589.001.0001"},{"volume-title":"Spectral Graph Theory","author":"Chung F. R. K.","unstructured":"F. R. K. Chung . 1997. Spectral Graph Theory . American Mathematical Society . F. R. K. Chung. 1997. Spectral Graph Theory. American Mathematical Society.","key":"e_1_2_1_9_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_2_1_11_1","volume-title":"Semi-Supervised Learning on Graphs through Reach and Distance Diffusion. CoRR","author":"Cohen E.","year":"2016","unstructured":"E. Cohen . 2016. Semi-Supervised Learning on Graphs through Reach and Distance Diffusion. CoRR Vol. abs\/ 1603 .09064 ( 2016 ). http:\/\/arxiv.org\/abs\/1603.09064 E. Cohen. 2016. Semi-Supervised Learning on Graphs through Reach and Distance Diffusion. CoRR Vol. abs\/1603.09064 (2016). http:\/\/arxiv.org\/abs\/1603.09064"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/2512938.2512944"},{"key":"e_1_2_1_13_1","volume-title":"Networks: Computation and Maximization. Technical Report cs.SI\/1410.6976. arXiv","author":"Cohen E.","year":"2015","unstructured":"E. Cohen , D. Delling , T. Pajor , and R. F. Werneck . 2015 . Distance-Based Influence in Networks: Computation and Maximization. Technical Report cs.SI\/1410.6976. arXiv . http:\/\/arxiv.org\/abs\/1410.06976 E. Cohen, D. Delling, T. Pajor, and R. F. Werneck. 2015. Distance-Based Influence in Networks: Computation and Maximization. Technical Report cs.SI\/1410.6976. arXiv. http:\/\/arxiv.org\/abs\/1410.06976"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1016\/j.jcss.2006.10.016"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.5555\/373515.373517"},{"unstructured":"M. Defferrard X. Bresson and P. Vandergheynst. 2016. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering NIPS.   M. Defferrard X. Bresson and P. Vandergheynst. 2016. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering NIPS.","key":"e_1_2_1_16_1"},{"unstructured":"N. Du L. Song M. Gomez-Rodriguez and H. Zha. 2013. Scalable Influence Estimation in Continuous-Time Diffusion Networks. NIPS.   N. Du L. Song M. Gomez-Rodriguez and H. Zha. 2013. Scalable Influence Estimation in Continuous-Time Diffusion Networks. NIPS.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","volume-title":"Centrality in social networks: Conceptual clarification. Social Networks","author":"Freeman L. C.","year":"1979","unstructured":"L. C. Freeman . 1979. Centrality in social networks: Conceptual clarification. Social Networks Vol. 1 ( 1979 ). L. C. Freeman. 1979. Centrality in social networks: Conceptual clarification. Social Networks Vol. 1 (1979)."},{"doi-asserted-by":"crossref","unstructured":"M. Gomez-Rodriguez J. Leskovec and A. Krause. 2010. Inferring Networks of Diffusion and Influence. In KDD.  M. Gomez-Rodriguez J. Leskovec and A. Krause. 2010. Inferring Networks of Diffusion and Influence. In KDD.","key":"e_1_2_1_19_1","DOI":"10.1145\/1835804.1835933"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_21_1","volume-title":"Deep Convolutional Networks on Graph-Structured Data. CoRR","author":"Henaff M.","year":"2015","unstructured":"M. Henaff , J. Bruna , and Y. LeCun . 2015. Deep Convolutional Networks on Graph-Structured Data. CoRR Vol. abs\/ 1506 .05163 ( 2015 ). http:\/\/arxiv.org\/abs\/1506.05163 M. Henaff, J. Bruna, and Y. LeCun. 2015. Deep Convolutional Networks on Graph-Structured Data. CoRR Vol. abs\/1506.05163 (2015). http:\/\/arxiv.org\/abs\/1506.05163"},{"unstructured":"T. Joachims. 1999. Transductive Inference for Text Classification Using Support Vector Machines ICML.   T. Joachims. 1999. Transductive Inference for Text Classification Using Support Vector Machines ICML.","key":"e_1_2_1_22_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/956750.956769"},{"unstructured":"T. N. Kipf and M. Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks ICLR.  T. N. Kipf and M. Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks ICLR.","key":"e_1_2_1_24_1"},{"unstructured":"F. Lin and W. W. Cohen. 2008. The MultiRank Bootstrap Algorithm: Self-Supervised Political Blog Classification and Ranking Using Semi-Supervised Link Classification ICWSM.  F. Lin and W. W. Cohen. 2008. The MultiRank Bootstrap Algorithm: Self-Supervised Political Blog Classification and Ranking Using Semi-Supervised Link Classification ICWSM.","key":"e_1_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/1807167.1807184"},{"unstructured":"T. Mikolov I. Sutskever K. Chen G. S. Corrado and J. Dean. 2013. Distributed Representations of Words and Phrases and their Compositionality NIPS.   T. Mikolov I. Sutskever K. Chen G. S. Corrado and J. Dean. 2013. Distributed Representations of Words and Phrases and their Compositionality NIPS.","key":"e_1_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/1298306.1298311"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/2939672.2939782"},{"unstructured":"T. Opsahl F. Agneessens and J. Skvoretz. 2010. Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks Vol. 32 (2010). http:\/\/toreopsahl.com\/2010\/03\/20\/  T. Opsahl F. Agneessens and J. Skvoretz. 2010. Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks Vol. 32 (2010). http:\/\/toreopsahl.com\/2010\/03\/20\/","key":"e_1_2_1_30_1"},{"unstructured":"L. Page S. Brin R. Motwani and T. Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford InfoLab.  L. Page S. Brin R. Motwani and T. Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford InfoLab.","key":"e_1_2_1_31_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/2623330.2623732"},{"unstructured":"S. Ravi and Q. Diao. 2016. Large-Scale Semi-Supervised Learning Using Streaming Approximation AISTATS.  S. Ravi and Q. Diao. 2016. Large-Scale Semi-Supervised Learning Using Streaming Approximation AISTATS.","key":"e_1_2_1_33_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1007\/BF02289527"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1109\/TIT.1965.1053799"},{"doi-asserted-by":"crossref","unstructured":"P. Sen G. Namata M. Bilgic L. Getoor B. Gallagher and T. Eliassi-Rad. 2008. Collective classification in network data. AI Magazine (2008).  P. Sen G. Namata M. Bilgic L. Getoor B. Gallagher and T. Eliassi-Rad. 2008. Collective classification in network data. AI Magazine (2008).","key":"e_1_2_1_36_1","DOI":"10.1609\/aimag.v29i3.2157"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1137\/080744888"},{"doi-asserted-by":"crossref","unstructured":"A. Subramanya and P. P. Talukdar. 2014. Graph-based semi-supervised learning. Morgan & Claypool.   A. Subramanya and P. P. Talukdar. 2014. Graph-based semi-supervised learning. Morgan & Claypool.","key":"e_1_2_1_38_1","DOI":"10.1007\/978-3-031-01571-7"},{"unstructured":"M. Whitney and A. Sarkar. 2012. Bootstrapping via Graph Propagation. In ACL.   M. Whitney and A. Sarkar. 2012. Bootstrapping via Graph Propagation. In ACL.","key":"e_1_2_1_39_1"},{"unstructured":"Z. Yang W. W. Cohen and R. Salakhutdinov. 2016. Revisiting Semi-Supervised Learning with Graph Embeddings ICML. JMLR.org.   Z. Yang W. W. Cohen and R. Salakhutdinov. 2016. Revisiting Semi-Supervised Learning with Graph Embeddings ICML. JMLR.org.","key":"e_1_2_1_40_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.3115\/981658.981684"},{"unstructured":"D. Zhou O. Bousquet T. Lal J. Weston and B. Sch\u00f6lkopf. 2004. Learning with Local and Global Consistency. In NIPS.   D. Zhou O. Bousquet T. Lal J. Weston and B. Sch\u00f6lkopf. 2004. Learning with Local and Global Consistency. In NIPS.","key":"e_1_2_1_42_1"},{"unstructured":"X. Zhu and Z. Ghahramani. 2002. Learning from labeled and unlabeled data with label propagation. (2002). http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.14.3864  X. Zhu and Z. Ghahramani. 2002. Learning from labeled and unlabeled data with label propagation. (2002). http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.14.3864","key":"e_1_2_1_43_1"},{"unstructured":"X. Zhu Z. Ghahramani and J. Laffery. 2003. Semi-supervised learning using Gaussian fields and harmonic functions ICML.   X. Zhu Z. Ghahramani and J. Laffery. 2003. Semi-supervised learning using Gaussian fields and harmonic functions ICML.","key":"e_1_2_1_44_1"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3179413","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3179413","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:18Z","timestamp":1750208898000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3179413"}},"subtitle":["Exposing the Power of Nonlinearity"],"short-title":[],"issued":{"date-parts":[[2018,4,3]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,4,3]]}},"alternative-id":["10.1145\/3179413"],"URL":"https:\/\/doi.org\/10.1145\/3179413","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2018,4,3]]},"assertion":[{"value":"2018-04-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}