{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T04:19:15Z","timestamp":1784607555178,"version":"3.55.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T00:00:00Z","timestamp":1623888000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T00:00:00Z","timestamp":1623888000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740850"],"award-info":[{"award-number":["CCF-1740850"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1703331"],"award-info":[{"award-number":["IIS-1703331"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Statistical relational learning (SRL) and graph neural networks (GNNs) are two powerful approaches for learning and inference over graphs. Typically, they are evaluated in terms of simple metrics such as accuracy over individual node labels. Complex<jats:italic>aggregate graph queries<\/jats:italic>(AGQ) involving multiple nodes, edges, and labels are common in the graph mining community and are used to estimate important network properties such as social cohesion and influence. While graph mining algorithms support AGQs, they typically do not take into account uncertainty, or when they do, make simplifying assumptions and do not build full probabilistic models. In this paper, we examine the performance of SRL and GNNs on AGQs over graphs with partially observed node labels. We show that, not surprisingly, inferring the unobserved node labels as a first step and then evaluating the queries on the fully observed graph can lead to sub-optimal estimates, and that a better approach is to compute these queries as an expectation under the joint distribution. We propose a sampling framework to tractably compute the expected values of AGQs. Motivated by the analysis of subgroup cohesion in social networks, we propose a suite of AGQs that estimate the community structure in graphs. In our empirical evaluation, we show that by estimating these queries as an expectation, SRL-based approaches yield up to a 50-fold reduction in average error when compared to existing GNN-based approaches.<\/jats:p>","DOI":"10.1007\/s10994-021-06007-5","type":"journal-article","created":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T19:02:50Z","timestamp":1623956570000},"page":"1847-1866","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A comparison of statistical relational learning and graph neural networks for aggregate graph queries"],"prefix":"10.1007","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4075-1664","authenticated-orcid":false,"given":"Varun","family":"Embar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sriram","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lise","family":"Getoor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"6007_CR1","first-page":"1","volume":"18","author":"E Abbe","year":"2018","unstructured":"Abbe, E. (2018). Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18, 1\u201386.","journal-title":"Journal of Machine Learning Research"},{"key":"6007_CR2","first-page":"1","volume":"18","author":"SH Bach","year":"2017","unstructured":"Bach, S. H., Broecheler, M., Huang, B., & Getoor, L. (2017). Hinge-loss Markov random fields and probabilistic soft logic. Journal of Machine Learning Research, 18, 1\u201367.","journal-title":"Journal of Machine Learning Research"},{"key":"6007_CR3","unstructured":"Broecheler, M., & Getoor, L. (2010). Computing marginal distributions over continuous Markov networks for statistical relational learning. In NeuRIPS."},{"key":"6007_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"TN Bui","year":"1987","unstructured":"Bui, T. N., Chaudhuri, S., Leighton, F. T., & Sipser, M. (1987). Graph bisection algorithms with good average case behavior. Combinatorica, 7, 171\u2013191.","journal-title":"Combinatorica"},{"key":"6007_CR5","doi-asserted-by":"crossref","unstructured":"Chin, A., Chen, Y., Altenburger, K. M., & Ugander, J. (2019). Decoupled smoothing on graphs. In WWW.","DOI":"10.1145\/3308558.3313748"},{"key":"6007_CR6","doi-asserted-by":"publisher","DOI":"10.1002\/0470073047","volume-title":"Mining graph data","author":"DJ Cook","year":"2006","unstructured":"Cook, D. J., & Holder, L. B. (2006). Mining graph data. Wiley."},{"key":"6007_CR7","doi-asserted-by":"crossref","unstructured":"Dandekar, P., Goel, A., & Lee, D. (2012). Biased assimilation, homophily, and the dynamics of polarization. In WINE.","DOI":"10.1007\/978-3-642-35311-6_47"},{"key":"6007_CR8","doi-asserted-by":"crossref","unstructured":"De Raedt, L., Duman\u010di\u0107, S., Manhaeve, R., & Marra, G. (2020). From statistical relational to neuro-symbolic artificial intelligence. In: IJCAI.","DOI":"10.24963\/ijcai.2020\/688"},{"key":"6007_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-01574-8","volume-title":"Statistical relational artificial intelligence: Logic, probability, and computation","author":"L De Raedt","year":"2016","unstructured":"De Raedt, L., Kersting, K., & Natarajan, S. (2016). Statistical relational artificial intelligence: Logic, probability, and computation. Morgan & Claypool Publishers."},{"key":"6007_CR10","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10994-015-5494-z","volume":"100","author":"L De Raedt","year":"2015","unstructured":"De Raedt, L., & Kimmig, A. (2015). Probabilistic (logic) programming concepts. Machine Learning, 100, 5\u201347.","journal-title":"Machine Learning"},{"key":"6007_CR11","doi-asserted-by":"crossref","unstructured":"Dunne, C., & Shneiderman, B. (2013). Motif simplification: Improving network visualization readability with fan, connector, and clique glyphs. In CHI.","DOI":"10.1145\/2470654.2466444"},{"key":"6007_CR12","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/7432.001.0001","volume-title":"Introduction to Statistical Relational Learning","author":"L Getoor","year":"2007","unstructured":"Getoor, L., & Taskar, B. (2007). Introduction to Statistical Relational Learning. The MIT Press."},{"key":"6007_CR13","doi-asserted-by":"publisher","DOI":"10.1201\/b14835","volume-title":"Markov chain Monte Carlo in practice","author":"WR Gilks","year":"1995","unstructured":"Gilks, W. R., Richardson, S., & Spiegelhalter, D. (1995). Markov chain Monte Carlo in practice. Chapman and Hall\/CRC."},{"key":"6007_CR14","unstructured":"Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural message passing for quantum chemistry. In ICML."},{"key":"6007_CR15","unstructured":"Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive representation learning on large graphs. In NeuRIPS."},{"key":"6007_CR16","doi-asserted-by":"crossref","unstructured":"Harsha Vardhan, L., Jia, G., & Kok, S. (2020). Probabilistic logic graph attention networks for reasoning. In WWW companion.","DOI":"10.1145\/3366424.3391265"},{"key":"6007_CR17","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","volume":"5","author":"PW Holland","year":"1983","unstructured":"Holland, P. W., Laskey, K. B., & Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social Networks, 5, 109\u2013137.","journal-title":"Social Networks"},{"key":"6007_CR18","volume-title":"An introduction to Statistical Relational Learning","author":"K Kersting","year":"2007","unstructured":"Kersting, K., & De Raedt, L. (2007). Bayesian logic programming: Theory and tool. In L. Getoor & B. Taskar (Eds.), An introduction to Statistical Relational Learning. MIT Press."},{"key":"6007_CR19","unstructured":"Kipf, T. N., & Welling, M. (2017). Kipf and Max Welling. In ICLR: Semi-supervised classification with graph convolutional networks."},{"key":"6007_CR20","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1145\/3186727","volume":"51","author":"Y Liu","year":"2018","unstructured":"Liu, Y., Safavi, T., Dighe, A., & Koutra, D. (2018). Graph summarization methods and applications: A survey. ACM Computing Surveys (CSUR), 51, 62\u201396.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"6007_CR21","first-page":"254","volume":"32","author":"S Muggleton","year":"1996","unstructured":"Muggleton, S., et al. (1996). Stochastic logic programs. Advances in Inductive Logic Programming, 32, 254\u2013264.","journal-title":"Advances in Inductive Logic Programming"},{"key":"6007_CR22","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-94-011-5014-9_12","volume-title":"Learning in graphical models","author":"RM Neal","year":"1998","unstructured":"Neal, R. M., & Hinton, G. E. (1998). A view of the Em algorithm that justifies incremental, sparse, and other variants. In M. I. Jordan (Ed.), Learning in graphical models (pp. 355\u2013368). Springer."},{"key":"6007_CR23","unstructured":"Neville, J., & Jensen, D. (2002). Iterative classification in relational data. In AAAI workshop on learning statistical models from relational data."},{"key":"6007_CR24","first-page":"373","volume":"4","author":"F Niu","year":"2011","unstructured":"Niu, F., R\u00e9, C., Doan, A. H., & Shavlik, J. (2011). Tuffy: Scaling up statistical inference in Markov logic networks using an rdbms. International Journal on Very Large Data Bases, 4, 373\u2013384.","journal-title":"International Journal on Very Large Data Bases"},{"key":"6007_CR25","doi-asserted-by":"crossref","unstructured":"Pham, T., Tran, T., Phung, D., & Venkatesh, S. (2017). Column networks for collective classification. In AAAI.","DOI":"10.1609\/aaai.v31i1.10851"},{"key":"6007_CR26","unstructured":"Poon, H., & Domingos, P. (2006). Sound and efficient inference with probabilistic and deterministic dependencies. In AAAI."},{"key":"6007_CR27","unstructured":"Qu, M., Bengio, Y., & Tang, J. (2019). Gmnn: Graph Markov neural networks. In ICML."},{"key":"6007_CR28","unstructured":"Qu, M., & Tang, J. (2019). Probabilistic logic neural networks for reasoning. In NeuRIPS."},{"key":"6007_CR29","unstructured":"Qiang, Q., Liu, S., Jensen, C. S., Zhu, F., & Faloutsos, C. (2014). Interestingness-driven diffusion process summarization in dynamic networks. In ECML."},{"key":"6007_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139058452","volume-title":"Mining of massive datasets","author":"A Rajaraman","year":"2011","unstructured":"Rajaraman, A., & Ullman, J. D. (2011). Mining of massive datasets. Cambridge University Press."},{"key":"6007_CR31","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/s10994-006-5833-1","volume":"62","author":"M Richardson","year":"2006","unstructured":"Richardson, M., & Domingos, P. (2006). Markov logic networks. Machine Learning, 62, 107\u2013136.","journal-title":"Machine Learning"},{"key":"6007_CR32","doi-asserted-by":"crossref","unstructured":"Schlichtkrull, M., Kipf, T. N., Bloem, P., Van Den Berg, R., Titov, I., & Welling, M. (2018). Modeling relational data with graph convolutional networks. In ESWC","DOI":"10.1007\/978-3-319-93417-4_38"},{"key":"6007_CR33","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1177\/0038038588022001007","volume":"22","author":"J Scott","year":"1988","unstructured":"Scott, J. (1988). Social network analysis. Sociology, 22, 109\u2013127.","journal-title":"Sociology"},{"key":"6007_CR34","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1609\/aimag.v29i3.2157","volume":"29","author":"P Sen","year":"2008","unstructured":"Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., & Eliassi-Rad, T. (2008). Collective classification in network data. AI Magazine, 29, 93\u201393.","journal-title":"AI Magazine"},{"key":"6007_CR35","doi-asserted-by":"publisher","first-page":"3417","DOI":"10.1109\/TKDE.2015.2453957","volume":"27","author":"L Shi","year":"2015","unstructured":"Shi, L., Tong, H., Tang, J., & Lin, C. (2015). Vegas: Visual influence graph summarization on citation networks. IEEE Transactions on Knowledge and Data Engineering, 27, 3417\u20133431.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"6007_CR36","unstructured":"Veli\u010dkovi\u0107, P., Cucurull, G., Casanova, A., Romero, A., Li\u00f2, P., & Bengio, Y. (2018). Graph attention networks. In: ICLR."},{"key":"6007_CR37","unstructured":"Venugopal, D., Sarkhel, S., & Gogate, V. (2016). Magician: Scalable inference and learning in Markov logic using approximate symmetries. Technical report, UofM, Memphis."},{"key":"6007_CR38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478","volume-title":"Social Network Analysis: Methods and Applications","author":"S Wasserman","year":"1994","unstructured":"Wasserman, S., & Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge University Press."},{"key":"6007_CR39","doi-asserted-by":"crossref","unstructured":"Wu, Y., Zhong, Z., Xiong, W., & Jing, N. (2014). Graph summarization for attributed graphs. In ISEEE.","DOI":"10.1109\/InfoSEEE.2014.6948163"},{"key":"6007_CR40","unstructured":"Zhang, Y., Chen, X., Yang, Y., Ramamurthy, A., Li, B., Qi, Y., & Song, L. (2020). Efficient probabilistic logic reasoning with graph neural networks."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06007-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-06007-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06007-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T14:45:34Z","timestamp":1672497934000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-06007-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,17]]},"references-count":40,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["6007"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-06007-5","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,17]]},"assertion":[{"value":"20 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}