{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:48:58Z","timestamp":1777614538004,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T00:00:00Z","timestamp":1607472000000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2020,12,9]]},"abstract":"<jats:p>In this paper we survey our recent results characterizing various graph neural network (GNN) architectures in terms of their ability to classify nodes over graphs, for classifiers based on unary logical formulas- or queries. We focus on the language FOC2, a well-studied fragment of FO. This choice is motivated by the fact that FOC2 is related to theWeisfeiler-Lehman (WL) test for checking graph isomorphism, which has the same ability as GNNs for distinguishing nodes on graphs. We unveil the exact relationship between FOC2 and GNNs in terms of node classification. To tackle this problem, we start by studying a popular basic class of GNNs, which we call AC-GNNs, in which the features of each node in a graph are updated, in successive layers, according only to the features of its neighbors. We prove that the unary FOC2 formulas that can be captured by an AC-GNN are exactly those that can be expressed in its guarded fragment, which in turn corresponds to graded modal logic. This result implies in particular that ACGNNs are too weak to capture all FOC2 formulas. We then seek for what needs to be added to AC-GNNs for capturing all FOC2. We show that it suffices to add readouts layers, which allow updating the node features not only in terms of its neighbors, but also in terms of a global attribute vector. We call GNNs with readouts ACR-GNNs. We also describe experiments that validate our findings by showing that, on synthetic data conforming to FOC2 but not to graded modal logic, AC-GNNs struggle to fit in while ACR-GNNs can generalise even to graphs of sizes not seen during training.<\/jats:p>","DOI":"10.1145\/3442322.3442324","type":"journal-article","created":{"date-parts":[[2020,12,10]],"date-time":"2020-12-10T19:16:52Z","timestamp":1607627812000},"page":"6-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["The Expressive Power of Graph Neural Networks as a Query Language"],"prefix":"10.1145","volume":"49","author":[{"given":"Pablo","family":"Barcel\u00f3","sequence":"first","affiliation":[{"name":"Pontificia Universidad Catolica de Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Egor V.","family":"Kostylev","sequence":"additional","affiliation":[{"name":"University of Oxford"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mika\u00ebl","family":"Monet","sequence":"additional","affiliation":[{"name":"IMFD Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorge","family":"P\u00e9rez","sequence":"additional","affiliation":[{"name":"University of Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan L.","family":"Reutter","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Catolica de Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan-Pablo","family":"Silva","sequence":"additional","affiliation":[{"name":"DCC, UChile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,12,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Approximation ratios of graph neural networks for combinatorial problems.  Approximation ratios of graph neural networks for combinatorial problems."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/885746"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-2464(07)80016-4"},{"key":"e_1_2_1_4_1","volume-title":"International Conference on Learning Representations","author":"Barcel\u00f3 P.","year":"2019","unstructured":"P. Barcel\u00f3 , E. V. Kostylev , M. Monet , J. P\u00e9rez , J. Reutter , and J. P. Silva . The logical expressiveness of graph neural networks . In International Conference on Learning Representations , 2019 . P. Barcel\u00f3, E. V. Kostylev, M. Monet, J. P\u00e9rez, J. Reutter, and J. P. Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2019."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_2_1_6_1","volume-title":"Relational inductive biases, deep learning, and graph networks. CoRR, abs\/1806.01261","author":"Battaglia P. W.","year":"2018","unstructured":"P. W. Battaglia , J. B. Hamrick , V. Bapst , A. Sanchez-Gonzalez , V. F. Zambaldi , M. Malinowski , A. Tacchetti , D. Raposo , A. Santoro , R. Faulkner , \u00c7. G\u00fcl\u00e7ehre, H. F. Song , A. J. Ballard , J. Gilmer , G. E. Dahl , A. Vaswani , K. R. Allen , C. Nash , V. Langston , C. Dyer , N. Heess , D. Wierstra , P. Kohli , M. Botvinick , O. Vinyals , Y. Li , and 3https:\/\/imfd.cl\/en\/ SIGMOD Record , June 2020 ( Vol . 49, No. 2) 15 R. Pascanu . Relational inductive biases, deep learning, and graph networks. CoRR, abs\/1806.01261 , 2018 . P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. F. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, \u00c7. G\u00fcl\u00e7ehre, H. F. Song, A. J. Ballard, J. Gilmer, G. E. Dahl, A. Vaswani, K. R. Allen, C. Nash, V. Langston, C. Dyer, N. Heess, D. Wierstra, P. Kohli, M. Botvinick, O. Vinyals, Y. Li, and 3https:\/\/imfd.cl\/en\/ SIGMOD Record, June 2020 (Vol. 49, No. 2) 15 R. Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs\/1806.01261, 2018."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/897035"},{"key":"e_1_2_1_8_1","volume-title":"Are powerful graph neural nets necessary? A dissection on graph classification. CoRR, abs\/1905.04579","author":"Chen T.","year":"2019","unstructured":"T. Chen , S. Bian , and Y. Sun . Are powerful graph neural nets necessary? A dissection on graph classification. CoRR, abs\/1905.04579 , 2019 . T. Chen, S. Bian, and Y. Sun. Are powerful graph neural nets necessary? A dissection on graph classification. CoRR, abs\/1905.04579, 2019."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1005245900406"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00028"},{"key":"e_1_2_1_11_1","volume-title":"Fast graph representation learning with PyTorch Geometric. CoRR, abs\/1903.02428","author":"Fey M.","year":"2019","unstructured":"M. Fey and J. E. Lenssen . Fast graph representation learning with PyTorch Geometric. CoRR, abs\/1903.02428 , 2019 . M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. CoRR, abs\/1903.02428, 2019."},{"key":"e_1_2_1_12_1","volume-title":"Generalization and representational limits of graph neural networks. arXiv preprint arXiv:2002.06157","author":"Garg V. K.","year":"2020","unstructured":"V. K. Garg , S. Jegelka , and T. Jaakkola . Generalization and representational limits of graph neural networks. arXiv preprint arXiv:2002.06157 , 2020 . V. K. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. arXiv preprint arXiv:2002.06157, 2020."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305381.3305512"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294869"},{"key":"e_1_2_1_15_1","volume-title":"Graph star net for generalized multi-task learning. arXiv preprint arXiv:1906.12330","author":"Haonan L.","year":"2019","unstructured":"L. Haonan , S. H. Huang , T. Ye , and G. Xiuyan . Graph star net for generalized multi-task learning. arXiv preprint arXiv:1906.12330 , 2019 . L. Haonan, S. H. Huang, T. Ye, and G. Xiuyan. Graph star net for generalized multi-task learning. arXiv preprint arXiv:1906.12330, 2019."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0202-3"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 5th International Conference on Learning Representations, ICLR 2017","author":"Kipf T. N.","year":"2017","unstructured":"T. N. Kipf and M. Welling . Semi-supervised classification with graph convolutional networks . In Proceedings of the 5th International Conference on Learning Representations, ICLR 2017 , Toulon, France, April 24--26 , 2017 , 2017. T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24--26, 2017, 2017."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 7th International Conference on Learning Representations, ICLR 2019","author":"Koul A.","year":"2019","unstructured":"A. Koul , S. Greydanus , and A. Fern . Learning finite state representations of recurrent policy networks . In Proceedings of the 7th International Conference on Learning Representations, ICLR 2019 , New Orleans, LA, USA, May 6--9 , 2019 , 2019. A. Koul, S. Greydanus, and A. Fern. Learning finite state representations of recurrent policy networks. In Proceedings of the 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6--9, 2019, 2019."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/647851.737389"},{"key":"e_1_2_1_20_1","volume-title":"Provably powerful graph networks","author":"Maron H.","year":"2019","unstructured":"H. Maron , H. Ben-Hamu , H. Serviansky , and Y. Lipman . Provably powerful graph networks , 2019 . H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks, 2019."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci049613b"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/541177"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"e_1_2_1_24_1","volume-title":"OWL 2 Web ontology language profiles","author":"Motik B.","year":"2012","unstructured":"B. Motik , B. Cuenca Grau , I. Horrocks , Z. Wu , A. Fokoue , and C. Lutz . OWL 2 Web ontology language profiles ( second edition). W3C recommendation, W3C, 2012 . B. Motik, B. Cuenca Grau, I. Horrocks, Z. Wu, A. Fokoue, and C. Lutz. OWL 2 Web ontology language profiles (second edition). W3C recommendation, W3C, 2012."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30487-4_25"},{"key":"e_1_2_1_26_1","volume-title":"Graded modal logic and counting bisimulation. https:\/\/www2.mathematik. tu-darmstadt.de\/~otto\/papers\/cml19.pdf","author":"Otto M.","year":"2019","unstructured":"M. Otto . Graded modal logic and counting bisimulation. https:\/\/www2.mathematik. tu-darmstadt.de\/~otto\/papers\/cml19.pdf , 2019 . M. Otto. Graded modal logic and counting bisimulation. https:\/\/www2.mathematik. tu-darmstadt.de\/~otto\/papers\/cml19.pdf, 2019."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2556013"},{"key":"e_1_2_1_28_1","volume-title":"Random features strengthen graph neural networks. arXiv preprint arXiv:2002.03155","author":"Sato R.","year":"2020","unstructured":"R. Sato , M. Yamada , and H. Kashima . Random features strengthen graph neural networks. arXiv preprint arXiv:2002.03155 , 2020 . R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. arXiv preprint arXiv:2002.03155, 2020."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"e_1_2_1_30_1","first-page":"593","volume-title":"Proceedings of The Semantic Web - 15th International Conference, ESWC 2018","author":"Schlichtkrull M. S.","year":"2018","unstructured":"M. S. Schlichtkrull , T. N. Kipf , P. Bloem , R. van den Berg, I. Titov, and M. Welling. Modeling relational data with graph convolutional networks . In Proceedings of The Semantic Web - 15th International Conference, ESWC 2018 , Heraklion, Crete, Greece, June 3--7 , 2018 , pages 593 -- 607 , 2018. M. S. Schlichtkrull, T. N. Kipf, P. Bloem, R. van den Berg, I. Titov, and M. Welling. Modeling relational data with graph convolutional networks. In Proceedings of The Semantic Web - 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3--7, 2018, pages 593--607, 2018."},{"key":"e_1_2_1_31_1","volume-title":"OWL 2 Web ontology language document overview","author":"W3C OWL Working Group","year":"2012","unstructured":"W3C OWL Working Group . OWL 2 Web ontology language document overview ( second edition). W3C recommendation, W3C, 2012 . W3C OWL Working Group. OWL 2 Web ontology language document overview (second edition). W3C recommendation, W3C, 2012."},{"issue":"9","key":"e_1_2_1_32_1","first-page":"12","article-title":"A Reduction of a graph to a canonical form and an algebra arising during this reduction","volume":"2","author":"Weisfeiler B. Y.","year":"1968","unstructured":"B. Y. Weisfeiler and A. A. Leman . A Reduction of a graph to a canonical form and an algebra arising during this reduction . Nauchno-Technicheskaya Informatsia , 2 ( 9 ): 12 -- 16 , 1968 . Translated from Russian. B. Y. Weisfeiler and A. A. Leman. A Reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia, 2(9):12--16, 1968. Translated from Russian.","journal-title":"Nauchno-Technicheskaya Informatsia"},{"key":"e_1_2_1_33_1","first-page":"5244","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","author":"Weiss G.","year":"2018","unstructured":"G. Weiss , Y. Goldberg , and E. Yahav . Extracting automata from recurrent neural networks using queries and counterexamples . In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan , Stockholm, Sweden, July 10--15 , 2018 , pages 5244 -- 5253 , 2018. G. Weiss, Y. Goldberg, and E. Yahav. Extracting automata from recurrent neural networks using queries and counterexamples. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10--15, 2018, pages 5244--5253, 2018."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 7th International Conference on Learning Representations, ICLR 2019","author":"Xu K.","year":"2019","unstructured":"K. Xu , W. Hu , J. Leskovec , and S. Jegelka . How Powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations, ICLR 2019 , New Orleans, LA, USA, May 6--9 , 2019 , 2019. K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How Powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6--9, 2019, 2019."},{"key":"e_1_2_1_35_1","first-page":"7134","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019","author":"You J.","year":"2019","unstructured":"J. You , R. Ying , and J. Leskovec . Position-aware graph neural networks . In Proceedings of the 36th International Conference on Machine Learning, ICML 2019 , Long Beach, California, USA, June 9--15 , 2019 , pages 7134 -- 7143 , 2019. J. You, R. Ying, and J. Leskovec. Position-aware graph neural networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, Long Beach, California, USA, June 9--15, 2019, pages 7134--7143, 2019."},{"key":"e_1_2_1_36_1","volume-title":"Predicting multicellular function through multi-layer tissue networks. CoRR, abs\/1707.04638","author":"Zitnik M.","year":"2017","unstructured":"M. Zitnik and J. Leskovec . Predicting multicellular function through multi-layer tissue networks. CoRR, abs\/1707.04638 , 2017 . M. Zitnik and J. Leskovec. Predicting multicellular function through multi-layer tissue networks. CoRR, abs\/1707.04638, 2017."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442322.3442324","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442322.3442324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:15Z","timestamp":1750193295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442322.3442324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,9]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,12,9]]}},"alternative-id":["10.1145\/3442322.3442324"],"URL":"https:\/\/doi.org\/10.1145\/3442322.3442324","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2020,12,9]]},"assertion":[{"value":"2020-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}