{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:31:58Z","timestamp":1750307518671,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,11,1]],"date-time":"2009-11-01T00:00:00Z","timestamp":1257033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["#0746930#0438866"],"award-info":[{"award-number":["#0746930#0438866"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["#W911NF0710428"],"award-info":[{"award-number":["#W911NF0710428"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2009,11]]},"abstract":"<jats:p>\n            Information diffusion, viral marketing, graph-based semi-supervised learning, and collective classification all attempt to model and exploit the relationships among nodes in a network to improve the performance of node labeling algorithms. However, sometimes the advantage of exploiting the relationships can become a disadvantage. Simple models like label propagation and iterative classification can aggravate a misclassification by propagating mistakes in the network, while more complex models that define and optimize a global objective function, such as Markov random fields and graph mincuts, can misclassify a set of nodes jointly. This problem can be mitigated if the classification system is allowed to ask for the correct labels for a few of the nodes during inference. However, determining the optimal set of labels to acquire is intractable under relatively general assumptions, which forces us to resort to approximate and heuristic techniques. We describe three such techniques in this article. The first one is based on directly approximating the value of the objective function of label acquisition and greedily acquiring the label that provides the most improvement. The second technique is a simple technique based on the analogy we draw between viral marketing and label acquisition. Finally, we propose a method, which we refer to as\n            <jats:italic>reflect and correct<\/jats:italic>\n            , that can learn and predict when the classification system is likely to make mistakes and suggests acquisitions to correct those mistakes. We empirically show on a variety of synthetic and real-world datasets that the reflect and correct method significantly outperforms the other two techniques, as well as other approaches based on network structural measures such as node degree and network clustering.\n          <\/jats:p>","DOI":"10.1145\/1631162.1631168","type":"journal-article","created":{"date-parts":[[2009,12,8]],"date-time":"2009-12-08T20:53:14Z","timestamp":1260305594000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Reflect and correct"],"prefix":"10.1145","volume":"3","author":[{"given":"Mustafa","family":"Bilgic","sequence":"first","affiliation":[{"name":"University of Maryland at College Park, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lise","family":"Getoor","sequence":"additional","affiliation":[{"name":"University of Maryland at College Park, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,12,4]]},"reference":[{"volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence. 1225--1230","author":"Bilgic M.","key":"e_1_2_1_1_1","unstructured":"Bilgic , M. and Getoor , L . 2007. VOILA: Efficient feature-value acquisition for classification . In Proceedings of the AAAI Conference on Artificial Intelligence. 1225--1230 . Bilgic, M. and Getoor, L. 2007. VOILA: Efficient feature-value acquisition for classification. In Proceedings of the AAAI Conference on Artificial Intelligence. 1225--1230."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401901"},{"volume-title":"Proceedings of the International Conference on Machine Learning. 19--26","author":"Blum A.","key":"e_1_2_1_3_1","unstructured":"Blum , A. and Chawla , S . 2001. Learning from labeled and unlabeled data using graph mincuts . In Proceedings of the International Conference on Machine Learning. 19--26 . Blum, A. and Chawla, S. 2001. Learning from labeled and unlabeled data using graph mincuts. In Proceedings of the International Conference on Machine Learning. 19--26."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276332"},{"key":"e_1_2_1_5_1","volume-title":"Eds","author":"Chapelle O.","year":"2006","unstructured":"Chapelle , O. , Sch\u00f6lkopf , B. , and Zien , A. , Eds . 2006 . Semi-Supervised Learning. MIT Press , Cambridge, MA. Chapelle, O., Sch\u00f6lkopf, B., and Zien, A., Eds. 2006. Semi-Supervised Learning. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022673506211"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622737.1622744"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007330508534"},{"key":"e_1_2_1_9_1","first-page":"679","article-title":"Learning probabilistic models of link structure","volume":"3","author":"Getoor L.","year":"2002","unstructured":"Getoor , L. , Friedman , N. , Koller , D. , and Taskar , B. 2002 . Learning probabilistic models of link structure . J. Mach. Learn. Res. 3 , 679 -- 707 . Getoor, L., Friedman, N., Koller, D., and Taskar, B. 2002. Learning probabilistic models of link structure. J. Mach. Learn. Res. 3, 679--707.","journal-title":"J. Mach. Learn. Res."},{"volume-title":"Proceedings of the IJCAI Workshop on Text Learning: Beyond Supervision. ACM","author":"Getoor L.","key":"e_1_2_1_10_1","unstructured":"Getoor , L. , Segal , E. , Taskar , B. , and Koller , D . 2001. Probabilistic models of text and link structure for hypertext classification . In Proceedings of the IJCAI Workshop on Text Learning: Beyond Supervision. ACM , New York, 24--29. Getoor, L., Segal, E., Taskar, B., and Koller, D. 2001. Probabilistic models of text and link structure for hypertext classification. In Proceedings of the IJCAI Workshop on Text Learning: Beyond Supervision. ACM, New York, 24--29."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/276675.276685"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Gilks W. R. Richardson S. and Spiegelhalter D. J. 1996. Markov Chain Monte Carlo in Practice. Interdisciplinary Statistics. Chapman&amp;Hall\/CRC.  Gilks W. R. Richardson S. and Spiegelhalter D. J. 1996. Markov Chain Monte Carlo in Practice. Interdisciplinary Statistics. Chapman&amp;Hall\/CRC.","DOI":"10.1201\/b14835"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1966.300074"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014125"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007665907178"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence. 1339--1345","author":"Krause A.","key":"e_1_2_1_17_1","unstructured":"Krause , A. and Guestrin , C . 2005. Optimal nonmyopic value of information in graphical models\u2014efficient algorithms and theoretical limits . In Proceedings of the International Joint Conference on Artificial Intelligence. 1339--1345 . Krause, A. and Guestrin, C. 2005. Optimal nonmyopic value of information in graphical models\u2014efficient algorithms and theoretical limits. In Proceedings of the International Joint Conference on Artificial Intelligence. 1339--1345."},{"volume-title":"Proceedings of the International Conference on Machine Learning. 282--289","author":"Lafferty J. D.","key":"e_1_2_1_18_1","unstructured":"Lafferty , J. D. , McCallum , A. , and Pereira , F. C. N. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data . In Proceedings of the International Conference on Machine Learning. 282--289 . Lafferty, J. D., McCallum, A., and Pereira, F. C. N. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the International Conference on Machine Learning. 282--289."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1232722.1232727"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"volume-title":"Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval. ACM","author":"Lewis D. D.","key":"e_1_2_1_21_1","unstructured":"Lewis , D. D. and Gale , W. A . 1994. A sequential algorithm for training text classifiers . In Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval. ACM , New York, 3--12. Lewis, D. D. and Gale, W. A. 1994. A sequential algorithm for training text classifiers. In Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, New York, 3--12."},{"volume-title":"Proceedings of the International Conference on Machine Learning. 496--503","author":"Lu Q.","key":"e_1_2_1_22_1","unstructured":"Lu , Q. and Getoor , L . 2003a. Link based classification . In Proceedings of the International Conference on Machine Learning. 496--503 . Lu, Q. and Getoor, L. 2003a. Link based classification. In Proceedings of the International Conference on Machine Learning. 496--503."},{"volume-title":"Proceedings of the ICML Workshop on the Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining.","author":"Lu Q.","key":"e_1_2_1_23_1","unstructured":"Lu , Q. and Getoor , L . 2003b. Link-based classification using labeled and unlabeled data . In Proceedings of the ICML Workshop on the Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining. Lu, Q. and Getoor, L. 2003b. Link-based classification using labeled and unlabeled data. In Proceedings of the ICML Workshop on the Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining."},{"volume-title":"Proceedings of the ACM Workshop on Multi-Relational Data Mining. ACM","author":"Macskassy S.","key":"e_1_2_1_24_1","unstructured":"Macskassy , S. and Provost , F . 2003. A simple relational classifier . In Proceedings of the ACM Workshop on Multi-Relational Data Mining. ACM , New York. Macskassy, S. and Provost, F. 2003. A simple relational classifier. In Proceedings of the ACM Workshop on Multi-Relational Data Mining. ACM, New York."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1248659.1248693"},{"volume-title":"Proceedings of the International Conference on Machine Learning. 350--358","author":"McCallum A.","key":"e_1_2_1_26_1","unstructured":"McCallum , A. and Nigam , K . 1998. Employing EM and pool-based active learning for text classification . In Proceedings of the International Conference on Machine Learning. 350--358 . McCallum, A. and Nigam, K. 1998. Employing EM and pool-based active learning for text classification. In Proceedings of the International Conference on Machine Learning. 350--358."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009953814988"},{"volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence. 596--601","author":"McDowell L.","key":"e_1_2_1_28_1","unstructured":"McDowell , L. , Gupta , K. M. , and Aha , D. W . 2007. Cautious inference in collective classification . In Proceedings of the AAAI Conference on Artificial Intelligence. 596--601 . McDowell, L., Gupta, K. M., and Aha, D. W. 2007. Cautious inference in collective classification. In Proceedings of the AAAI Conference on Artificial Intelligence. 596--601."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015330.1015385"},{"volume-title":"Proceedings of the SRL Workshop in AAAI.","author":"Neville J.","key":"e_1_2_1_30_1","unstructured":"Neville , J. and Jensen , D . 2000. Iterative classification in relational data . In Proceedings of the SRL Workshop in AAAI. Neville, J. and Jensen, D. 2000. Iterative classification in relational data. In Proceedings of the SRL Workshop in AAAI."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.67.026126"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1282100.1282172"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2007.41"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the International Conference on Machine Learning. 441--448","author":"Roy N.","year":"2001","unstructured":"Roy , N. and McCallum , A. 2001 . Toward optimal active learning through sampling estimation of error reduction . In Proceedings of the International Conference on Machine Learning. 441--448 . Roy, N. and McCallum, A. 2001. Toward optimal active learning through sampling estimation of error reduction. In Proceedings of the International Conference on Machine Learning. 441--448."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000011806.12374.c3"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v29i3.2157"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/130385.130417"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143946"},{"volume-title":"Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence. 485--492","author":"Taskar B.","key":"e_1_2_1_41_1","unstructured":"Taskar , B. , Abbeel , P. , and Koller , D . 2002. Discriminative probabilistic models for relational data . In Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence. 485--492 . Taskar, B., Abbeel, P., and Koller, D. 2002. Discriminative probabilistic models for relational data. In Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence. 485--492."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1162\/153244302760185243"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.148"},{"key":"e_1_2_1_44_1","unstructured":"Yedidia J. Freeman W. T. and Weiss Y. 2000. Generalized belief propagation. In Neural Information Processing Systems. 689--695.  Yedidia J. Freeman W. T. and Weiss Y. 2000. Generalized belief propagation. In Neural Information Processing Systems. 689--695."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502540"},{"key":"e_1_2_1_46_1","volume-title":"Tech. Rep. CMU-CALD-02-107","author":"Zhu X.","year":"2002","unstructured":"Zhu , X. and Ghahramani , Z . 2002 . Learning from labeled and unlabeled data with label propagation. Tech. Rep. CMU-CALD-02-107 , Carnegie Mellon University . Zhu, X. and Ghahramani, Z. 2002. Learning from labeled and unlabeled data with label propagation. Tech. Rep. CMU-CALD-02-107, Carnegie Mellon University."},{"volume-title":"Proceedings of the International Conference on Machine Learning. 912--919","author":"Zhu X.","key":"e_1_2_1_47_1","unstructured":"Zhu , X. , Ghahramani , Z. , and Lafferty , J. D . 2003. Semi-supervised learning using gaussian fields and harmonic functions . In Proceedings of the International Conference on Machine Learning. 912--919 . Zhu, X., Ghahramani, Z., and Lafferty, J. D. 2003. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the International Conference on Machine Learning. 912--919."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1631162.1631168","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1631162.1631168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:18:13Z","timestamp":1750249093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1631162.1631168"}},"subtitle":["A misclassification prediction approach to active inference"],"short-title":[],"issued":{"date-parts":[[2009,11]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["10.1145\/1631162.1631168"],"URL":"https:\/\/doi.org\/10.1145\/1631162.1631168","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2009,11]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}