{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:33:51Z","timestamp":1725496431619},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>\n            Hypothesis testing is a statistical method used to draw conclusions about populations from sample data, typically represented in tables. With the prevalence of graph representations in real-life applications, hypothesis testing on graphs is gaining importance. In this work, we formalize node, edge, and path hypotheses on attributed graphs. We develop a sampling-based hypothesis testing framework, which can accommodate existing hypothesis-agnostic graph sampling methods. To achieve accurate and time-efficient sampling, we then propose a Path-Hypothesis-Aware SamplEr, PHASE, an\n            <jats:italic>m<\/jats:italic>\n            -dimensional random walk that accounts for the paths specified in the hypothesis. We further optimize its time efficiency and propose PHASE\n            <jats:sub>opt<\/jats:sub>\n            . Experiments on three real datasets demonstrate the ability of our framework to leverage common graph sampling methods for hypothesis testing, and the superiority of hypothesis-aware sampling methods in terms of accuracy and time efficiency.\n          <\/jats:p>","DOI":"10.14778\/3681954.3681993","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"3192-3200","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Sampling-Based Framework for Hypothesis Testing on Large Attributed Graphs"],"prefix":"10.14778","volume":"17","author":[{"given":"Yun","family":"Wang","sequence":"first","affiliation":[{"name":"The University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chrysanthi","family":"Kosyfaki","sequence":"additional","affiliation":[{"name":"The University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sihem","family":"Amer-Yahia","sequence":"additional","affiliation":[{"name":"CNRS, Univ. Grenoble Aples"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2015. Yelp Dataset. https:\/\/www.yelp.com\/dataset."},{"key":"e_1_2_1_2_1","volume-title":"Huberman","author":"Adamic Lada A.","year":"2001","unstructured":"Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, and Bernardo A. Huberman. 2001. Search in Power-Law Networks. CoRR cs.NI\/0103016 (2001)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Ery Arias-Castro and Nicolas Verzelen. 2014. Community detection in dense random networks. (2014).","DOI":"10.1214\/14-AOS1208"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356182"},{"key":"e_1_2_1_5_1","volume-title":"Bickel and Purnamrita Sarkar","author":"Peter","year":"2013","unstructured":"Peter J. Bickel and Purnamrita Sarkar. 2013. Hypothesis Testing for Automated Community Detection in Networks. CoRR abs\/1311.2694 (2013)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/00031305.1976.10479149"},{"key":"e_1_2_1_7_1","unstructured":"William Gemmell Cochran. 1977. Sampling techniques. john wiley & sons."},{"key":"e_1_2_1_8_1","volume-title":"Hypothesis testing in animal social networks. Trends in ecology & evolution 26, 10","author":"Croft Darren P","year":"2011","unstructured":"Darren P Croft, Joah R Madden, Daniel W Franks, and Richard James. 2011. Hypothesis testing in animal social networks. Trends in ecology & evolution 26, 10 (2011), 502--507."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT","volume":"65","author":"Ghoshdastidar Debarghya","year":"2017","unstructured":"Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, and Ulrike von Luxburg. 2017. Two-Sample Tests for Large Random Graphs Using Network Statistics. In Proceedings of the 30th Conference on Learning Theory, COLT, Amsterdam, The Netherlands, 7--10 July (Proceedings of Machine Learning Research), Vol. 65. PMLR, 954--977."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Debarghya Ghoshdastidar Maurilio Gutzeit Alexandra Carpentier and Ulrike Von Luxburg. 2020. Two-sample hypothesis testing for inhomogeneous random graphs. (2020).","DOI":"10.1214\/19-AOS1884"},{"key":"e_1_2_1_11_1","volume-title":"Practical Methods for Graph Two-Sample Testing. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Ghoshdastidar Debarghya","year":"2018","unstructured":"Debarghya Ghoshdastidar and Ulrike von Luxburg. 2018. Practical Methods for Graph Two-Sample Testing. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3--8, 2018, Montr\u00e9al, Canada. 3019--3028."},{"key":"e_1_2_1_12_1","volume-title":"Wilson","author":"Gibbs Connor P.","year":"2022","unstructured":"Connor P. Gibbs, Bailey K. Fosdick, and James D. Wilson. 2022. ECoHeN: A Hypothesis Testing Framework for Extracting Communities from Heterogeneous Networks. CoRR abs\/2212.10513 (2022)."},{"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":"Snowball sampling. The annals of mathematical statistics","author":"Goodman Leo A","year":"1961","unstructured":"Leo A Goodman. 1961. Snowball sampling. The annals of mathematical statistics (1961), 148--170."},{"key":"e_1_2_1_15_1","article-title":"The MovieLens Datasets","volume":"5","author":"Maxwell Harper F.","year":"2016","unstructured":"F. Maxwell Harper and Joseph A. Konstan. 2016. The MovieLens Datasets: History and Context. ACM Trans. Interact. Intell. Syst. 5, 4 (2016), 19:1--19:19.","journal-title":"History and Context. ACM Trans. Interact. Intell. Syst."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.124"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1198\/016214507000000446"},{"key":"e_1_2_1_18_1","volume-title":"Percus","author":"Krishnamurthy Vaishnavi","year":"2005","unstructured":"Vaishnavi Krishnamurthy, Michalis Faloutsos, Marek Chrobak, Li Lao, Jun-Hong Cui, and Allon G. Percus. 2005. Reducing Large Internet Topologies for Faster Simulations. In NETWORKING: Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communication Systems, 4th International IFIP-TC6 Networking Conference, Waterloo, Canada, May 2--6, Proceedings (Lecture Notes in Computer Science), Vol. 3462. Springer, 328--341."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254795"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"volume-title":"35th IEEE International Conference on Data Engineering, ICDE","author":"Li Yongkun","key":"e_1_2_1_21_1","unstructured":"Yongkun Li, Zhiyong Wu, Shuai Lin, Hong Xie, Min Lv, Yinlong Xu, and John C. S. Lui. 2019. Walking with Perception: Efficient Random Walk Sampling via Common Neighbor Awareness. In 35th IEEE International Conference on Data Engineering, ICDE, Macao, China, April 8--11. IEEE, 962--973."},{"volume-title":"Proceedings of the 19th International Conference on World Wide Web, WWW","author":"Arun","key":"e_1_2_1_22_1","unstructured":"Arun S. Maiya and Tanya Y. Berger-Wolf. 2010. Sampling community structure. In Proceedings of the 19th International Conference on World Wide Web, WWW, Raleigh, North Carolina, USA, April 26--30. ACM, 701--710."},{"key":"e_1_2_1_23_1","volume-title":"Large sample estimation and hypothesis testing. Handbook of econometrics 4","author":"Newey Whitney K","year":"1994","unstructured":"Whitney K Newey and Daniel McFadden. 1994. Large sample estimation and hypothesis testing. Handbook of econometrics 4 (1994), 2111--2245."},{"volume-title":"Breakthroughs in statistics: Methodology and distribution","author":"Neyman Jerzy","key":"e_1_2_1_24_1","unstructured":"Jerzy Neyman. 1992. On the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection. In Breakthroughs in statistics: Methodology and distribution. Springer, 123--150."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0527-4"},{"key":"e_1_2_1_26_1","volume-title":"Effectively Visualizing Large Networks Through Sampling. In 16th IEEE Visualization Conference, IEEE Vis 2005, Minneapolis, MN, USA, October 23--28, 2005, Proceedings. IEEE Computer Society, 375--382","author":"Rafiei Davood","year":"2005","unstructured":"Davood Rafiei and Stephen Curial. 2005. Effectively Visualizing Large Networks Through Sampling. In 16th IEEE Visualization Conference, IEEE Vis 2005, Minneapolis, MN, USA, October 23--28, 2005, Proceedings. IEEE Computer Society, 375--382."},{"key":"e_1_2_1_27_1","volume-title":"Sampling social networks using shortest paths. Physica A: Statistical Mechanics and its Applications 424","author":"Rezvanian Alireza","year":"2015","unstructured":"Alireza Rezvanian and Mohammad Reza Meybodi. 2015. Sampling social networks using shortest paths. Physica A: Statistical Mechanics and its Applications 424 (2015), 254--268."},{"volume-title":"Proceedings of the 10th ACM SIGCOMM Internet Measurement Conference, IMC","author":"Bruno","key":"e_1_2_1_28_1","unstructured":"Bruno F. Ribeiro and Donald F. Towsley. 2010. Estimating and sampling graphs with multidimensional random walks. In Proceedings of the 10th ACM SIGCOMM Internet Measurement Conference, IMC, Melbourne, Australia - November 1--3. ACM, 390--403."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0501179102"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.2001730"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402008"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2016.1193505"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/13645579.2014.953316"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2016.2598867"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1111\/biom.12633"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1006642108"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3681993","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:38:28Z","timestamp":1725475108000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3681993"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":36,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3681993"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3681993","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}