{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:41:49Z","timestamp":1770903709008,"version":"3.50.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T00:00:00Z","timestamp":1618704000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,8,31]]},"abstract":"<jats:p>\n            This article introduces a novel task-independent sampler for attributed networks. The problem is important because while data mining tasks on network content are common, sampling on internet-scale networks is costly. Link-trace samplers such as Snowball sampling, Forest Fire, Random Walk, and Metropolis\u2013Hastings Random Walk are widely used for sampling from networks. The design of these attribute-agnostic samplers focuses on preserving salient properties of network structure, and are not optimized for tasks on node content. This article has three contributions. First, we propose a task-independent, attribute aware\n            <jats:italic>link-trace<\/jats:italic>\n            sampler grounded in Information Theory. Our sampler greedily adds to the sample the node with the most informative (i.e., surprising) neighborhood. The sampler tends to rapidly explore the attribute space, maximally reducing the surprise of unseen nodes. Second, we prove that content sampling is an NP-hard problem. A well-known algorithm best approximates the optimization solution within 1 \u2212 1\/\n            <jats:italic>e<\/jats:italic>\n            , but requires full access to the entire graph. Third, we show through empirical counterfactual analysis that in many real-world datasets, network structure does not hinder the performance of surprise based link-trace samplers. Experimental results over 18 real-world datasets reveal: surprise-based samplers are sample efficient and outperform the state-of-the-art attribute-agnostic samplers by a wide margin (e.g., 45% performance improvement in clustering tasks).\n          <\/jats:p>","DOI":"10.1145\/3441445","type":"journal-article","created":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T16:05:45Z","timestamp":1618761945000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Attribute-Guided Network Sampling Mechanisms"],"prefix":"10.1145","volume":"15","author":[{"given":"Suhansanu","family":"Kumar","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana-Champaign, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hari","family":"Sundaram","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana-Champaign, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,4,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601438"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09182"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.3390\/a2031031"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00052-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883045"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(03)00012-1"},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"The igraph software package for complex network research. InterJournal","volume":"1695","author":"Csardi Gabor","year":"2006","unstructured":"Gabor Csardi and Tamas Nepusz . 2006 . The igraph software package for complex network research. InterJournal , Complex Systems 1695 , 5 (2006), 1 -- 9 . Gabor Csardi and Tamas Nepusz. 2006. The igraph software package for complex network research. InterJournal, Complex Systems 1695, 5 (2006), 1--9.","journal-title":"Complex Systems"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1065"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2016.09.002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2017.01.004"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 2010 IEEE INFOCOM. 1--9.","author":"Gjoka M.","unstructured":"M. Gjoka , M. Kurant , C. T. Butts , and A. Markopoulou . 2010b. Walking in Facebook: A case study of unbiased sampling of OSNs . In Proceedings of the 2010 IEEE INFOCOM. 1--9. M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou. 2010b. Walking in Facebook: A case study of unbiased sampling of OSNs. In Proceedings of the 2010 IEEE INFOCOM. 1--9."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462078"},{"key":"e_1_2_1_14_1","volume-title":"Butts","author":"Gjoka Minas","year":"2015","unstructured":"Minas Gjoka , Emily Smith , and Carter T . Butts . 2015 . Estimating subgraph frequencies with or without attributes from egocentrically sampled data. arXiv preprint arXiv:1510.08119 (2015). Minas Gjoka, Emily Smith, and Carter T. Butts. 2015. Estimating subgraph frequencies with or without attributes from egocentrically sampled data. arXiv preprint arXiv:1510.08119 (2015)."},{"key":"e_1_2_1_15_1","volume-title":"Grzymala-Busse and Ming Hu","author":"Jerzy","year":"2000","unstructured":"Jerzy W. Grzymala-Busse and Ming Hu . 2000 . A comparison of several approaches to missing attribute values in data mining. In Proceedings of the International Conference on Rough Sets and Current Trends in Computing. Springer , 378--385. Jerzy W. Grzymala-Busse and Ming Hu. 2000. A comparison of several approaches to missing attribute values in data mining. In Proceedings of the International Conference on Rough Sets and Current Trends in Computing. Springer, 378--385."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/3096941"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2008.01.073"},{"key":"e_1_2_1_18_1","volume-title":"A survey and taxonomy of graph sampling. arXiv preprint arXiv:1308.5865","author":"Hu Pili","year":"2013","unstructured":"Pili Hu and Wing Cheong Lau . 2013. A survey and taxonomy of graph sampling. arXiv preprint arXiv:1308.5865 ( 2013 ). Pili Hu and Wing Cheong Lau. 2013. A survey and taxonomy of graph sampling. arXiv preprint arXiv:1308.5865 (2013)."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 1st Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD\u201997)","author":"Huang Zhexue","year":"1997","unstructured":"Zhexue Huang . 1997 . Clustering large data sets with mixed numeric and categorical values . In Proceedings of the 1st Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD\u201997) . Singapore, 21--34. Zhexue Huang. 1997. Clustering large data sets with mixed numeric and categorical values. In Proceedings of the 1st Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD\u201997). Singapore, 21--34."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.124"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 8th IEEE International Conference on Data Mining. 283--292","author":"Hubler C.","unstructured":"C. Hubler , H.-P. Kriegel , K. Borgwardt , and Z. Ghahramani . 2008. Metropolis algorithms for representative subgraph sampling . In Proceedings of the 8th IEEE International Conference on Data Mining. 283--292 . C. Hubler, H.-P. Kriegel, K. Borgwardt, and Z. Ghahramani. 2008. Metropolis algorithms for representative subgraph sampling. In Proceedings of the 8th IEEE International Conference on Data Mining. 283--292."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITC.2010.5608727"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.016118"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the KDD Workshop on ML Meets Fashion.","author":"Jung-Lin Lee Doris","year":"2017","unstructured":"Doris Jung-Lin Lee , Jinda Han , Dana Chambourova , and Ranjitha Kumar . 2017 . Identifying fashion accounts in social networks . In Proceedings of the KDD Workshop on ML Meets Fashion. Doris Jung-Lin Lee, Jinda Han, Dana Chambourova, and Ranjitha Kumar. 2017. Identifying fashion accounts in social networks. In Proceedings of the KDD Workshop on ML Meets Fashion."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20847-8_10"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 105--113","author":"Arun","unstructured":"Arun S. Maiya and Tanya Y. Berger-Wolf. 2011. Benefits of bias: Towards better characterization of network sampling . In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 105--113 . Arun S. Maiya and Tanya Y. Berger-Wolf. 2011. Benefits of bias: Towards better characterization of network sampling. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 105--113."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 25th International Conference on Neural Information Processing Systems.","volume":"2012","author":"Julian","unstructured":"Julian J. McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks . In Proceedings of the 25th International Conference on Neural Information Processing Systems. Vol. 2012 . 548--56. Julian J. McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks. In Proceedings of the 25th International Conference on Neural Information Processing Systems. Vol. 2012. 548--56."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-017-0523-0"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.99.052304"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.67.026126"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2487880"},{"key":"e_1_2_1_38_1","volume-title":"Qualitative Research","author":"Patton Michael Quinn","unstructured":"Michael Quinn Patton . 2005. Qualitative Research . Wiley Online Library . Michael Quinn Patton. 2005. Qualitative Research. Wiley Online Library."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2008.4595271"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 23rd International Conference on World Wide Web. 831--842","author":"Joseph J.","year":"2014","unstructured":"Joseph J. Pfeiffer III, Sebastian Moreno , Timothy La Fond , Jennifer Neville , and Brian Gallagher . 2014 . Attributed graph models: Modeling network structure with correlated attributes . In Proceedings of the 23rd International Conference on World Wide Web. 831--842 . Joseph J. Pfeiffer III, Sebastian Moreno, Timothy La Fond, Jennifer Neville, and Brian Gallagher. 2014. Attributed graph models: Modeling network structure with correlated attributes. In Proceedings of the 23rd International Conference on World Wide Web. 831--842."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the ICML Structured Learning Workshop.","author":"Joseph J.","unstructured":"Joseph J. Pfeiffer III, Jennifer Neville , and Paul N. Bennett . 2013. Combining active sampling with parameter estimation and prediction in single networks . In Proceedings of the ICML Structured Learning Workshop. Joseph J. Pfeiffer III, Jennifer Neville, and Paul N. Bennett. 2013. Combining active sampling with parameter estimation and prediction in single networks. In Proceedings of the ICML Structured Learning Workshop."},{"key":"e_1_2_1_42_1","volume-title":"IEEE VIS Conference (Poster). Citeseer.","author":"Pienta Robert","year":"2015","unstructured":"Robert Pienta , Zhiyuan Lin , Minsuk Kahng , Jilles Vreeken , Partha P. Talukdar , James Abello , Ganesh Parameswaran , and Duen Horng Polo Chau . 2015 . AdaptiveNav: Discovering locally interesting and surprising nodes in large graphs . In IEEE VIS Conference (Poster). Citeseer. Robert Pienta, Zhiyuan Lin, Minsuk Kahng, Jilles Vreeken, Partha P. Talukdar, James Abello, Ganesh Parameswaran, and Duen Horng Polo Chau. 2015. AdaptiveNav: Discovering locally interesting and surprising nodes in large graphs. In IEEE VIS Conference (Poster). Citeseer."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939808"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 26th VLDB Conference. 307--316","author":"Sarawagi Sunita","year":"2000","unstructured":"Sunita Sarawagi . 2000 . User-adaptive exploration of multidimensional data . In Proceedings of the 26th VLDB Conference. 307--316 . Sunita Sarawagi. 2000. User-adaptive exploration of multidimensional data. In Proceedings of the 26th VLDB Conference. 307--316."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the International Scientific Conference and International Workshop Present Day Trends of Innovations.","author":"Takac Lubos","year":"2012","unstructured":"Lubos Takac and Michal Zabovsky . 2012 . Data analysis in public social networks . In Proceedings of the International Scientific Conference and International Workshop Present Day Trends of Innovations. Lubos Takac and Michal Zabovsky. 2012. Data analysis in public social networks. In Proceedings of the International Scientific Conference and International Workshop Present Day Trends of Innovations."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052665"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2006.261842"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.102"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.167"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441445","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3441445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:05Z","timestamp":1750197785000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,18]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8,31]]}},"alternative-id":["10.1145\/3441445"],"URL":"https:\/\/doi.org\/10.1145\/3441445","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,18]]},"assertion":[{"value":"2019-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}