{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T23:01:07Z","timestamp":1754262067561,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":119,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,18]],"date-time":"2023-06-18T00:00:00Z","timestamp":1687046400000},"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":[],"published-print":{"date-parts":[[2023,6,18]]},"DOI":"10.1145\/3584372.3589936","type":"proceedings-article","created":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T22:21:22Z","timestamp":1685744482000},"page":"373-379","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Query Language Perspective on Graph Learning"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8967-2473","authenticated-orcid":false,"given":"Floris","family":"Geerts","sequence":"first","affiliation":[{"name":"University of Antwerp, Antwerp, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2023,6,18]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Anders Aamand Justin Y Chen Piotr Indyk Shyam Narayanan Ronitt Rubinfeld Nicholas Schiefer Sandeep Silwal and Tal Wagner. 2022. Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_2_1","volume-title":"The Surprising Power of Graph Neural Networks with Random Node Initialization. In Joint Conference on Artificial Intelligence. 2112--2118","author":"Abboud Ralph","year":"2021","unstructured":"Ralph Abboud, .Ismail. Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. 2021. The Surprising Power of Graph Neural Networks with Random Node Initialization. In Joint Conference on Artificial Intelligence. 2112--2118."},{"key":"e_1_3_2_1_3_1","volume-title":"Characterizing the Expressive Power of Invariant and Equivariant Graph Neural Networks. In International Conference on Learning Representations.","author":"Azizian Wa\u00efss","year":"2021","unstructured":"Wa\u00efss Azizian and Marc Lelarge. 2021. Characterizing the Expressive Power of Invariant and Equivariant Graph Neural Networks. In International Conference on Learning Representations."},{"volume-title":"Breaking the Limits of Message Passing Graph Neural Networks. In International Conference on Machine Learning. 599--608","author":"Balcilar Muhammet","key":"e_1_3_2_1_4_1","unstructured":"Muhammet Balcilar, Pierre H\u00e9 roux, Benoit Ga\u00fc z\u00e8 re, Pascal Vasseur, S\u00e9 bastien Adam, and Paul Honeine. 2021a. Breaking the Limits of Message Passing Graph Neural Networks. In International Conference on Machine Learning. 599--608."},{"volume-title":"International Conference on Learning Representations.","author":"Balcilar Muhammet","key":"e_1_3_2_1_5_1","unstructured":"Muhammet Balcilar, Guillaume Renton, Pierre H\u00e9 roux, Benoit Ga\u00fc z\u00e8 re, S\u00e9 bastien Adam, and Paul Honeine. 2021b. Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_6_1","volume-title":"Weisfeiler and Leman Go Relational. In The First Learning on Graphs Conference.","author":"Pablo Barcel\u00f3","year":"2022","unstructured":"Pablo Barcel\u00f3 , Mikhail Galkin, Christopher Morris, and Miguel Romero Orth. 2022. Weisfeiler and Leman Go Relational. In The First Learning on Graphs Conference."},{"key":"e_1_3_2_1_7_1","unstructured":"Pablo Barcel\u00f3 Floris Geerts Juan L. Reutter and Maksimilian Ryschkov. 2021. Graph Neural Networks with Local Graph Parameters. In Advances in Neural Information Processing Systems. 25280--25293."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.09.003"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442322.3442324"},{"key":"e_1_3_2_1_10_1","volume-title":"The Logical Expressiveness of Graph Neural Networks. In International Conference on Learning Representations.","author":"Pablo Barcel\u00f3","year":"2020","unstructured":"Pablo Barcel\u00f3 , Egor V. Kostylev, Mika\u00eb l Monet, Jorge P\u00e9 rez, Juan L. Reutter, and Juan Pablo Silva. 2020b. The Logical Expressiveness of Graph Neural Networks. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_11_1","volume-title":"Directional Graph Networks. In International Conference on Machine Learning. 748--758","author":"Beaini Dominique","year":"2021","unstructured":"Dominique Beaini, Saro Passaro, Vincent L\u00e9 tourneau, William L. Hamilton, Gabriele Corso, and Pietro Li\u00f3. 2021. Directional Graph Networks. In International Conference on Machine Learning. 748--758."},{"key":"e_1_3_2_1_12_1","volume-title":"Equivariant Subgraph Aggregation Networks. In International Conference on Learning Representations.","author":"Bevilacqua Beatrice","year":"2022","unstructured":"Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. 2022. Equivariant Subgraph Aggregation Networks. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_13_1","volume-title":"Pietro Li\u00f2, Guido Mont\u00fa far, and Michael M. Bronstein.","author":"Bodnar Cristian","year":"2021","unstructured":"Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Li\u00f2, Guido Mont\u00fa far, and Michael M. Bronstein. 2021a. Weisfeiler and Lehman Go Cellular: CW Networks. In Advances in Neural Information Processing Systems. 2625--2640."},{"volume-title":"Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks. In International Conference on Machine Learning. 1026--1037","author":"Bodnar Cristian","key":"e_1_3_2_1_14_1","unstructured":"Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F. Mont\u00fa far, Pietro Li\u00f3 , and Michael M. Bronstein. 2021b. Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks. In International Conference on Machine Learning. 1026--1037."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000076"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti1007"},{"key":"e_1_3_2_1_17_1","volume-title":"Bronstein","author":"Bouritsas Giorgos","year":"2020","unstructured":"Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. 2020. Improving graph neural network expressivity via subgraph isomorphism counting. (2020). arxiv: 2006.09252"},{"key":"e_1_3_2_1_18_1","volume-title":"On the Expressive Power of Query Languages for Matrices. In International Conference on Database Theory. 10:1--10:17","author":"Brijder Robert","year":"2018","unstructured":"Robert Brijder, Floris Geerts, Jan Van den Bussche, and Timmy Weerwag. 2018. On the Expressive Power of Query Languages for Matrices. In International Conference on Database Theory. 10:1--10:17."},{"key":"e_1_3_2_1_19_1","volume-title":"Jan Van den Bussche, and Timmy Weerwag","author":"Brijder Robert","year":"2019","unstructured":"Robert Brijder, Floris Geerts, Jan Van den Bussche, and Timmy Weerwag. 2019. On the Expressive Power of Query Languages for Matrices. ACM TODS, Vol. 44, 4 (2019), 15:1--15:31."},{"key":"e_1_3_2_1_20_1","volume-title":"Spectral Networks and Deep Locally Connected Networks on Graphs. In International Conference on Learning Representation.","author":"Bruna Joan","year":"2014","unstructured":"Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2014. Spectral Networks and Deep Locally Connected Networks on Graphs. In International Conference on Learning Representation."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_1_22_1","unstructured":"Zhengdao Chen Soledad Villar Lei Chen and Joan Bruna. 2019. On the Equivalence Between Graph Isomorphism Testing and Function Approximation With GNNs. In Advances in Neural Information Processing Systems. 15868--15876."},{"key":"e_1_3_2_1_23_1","unstructured":"Gabriele Corso Luca Cavalleri Dominique Beaini Pietro Li\u00f2 and Petar Velivckovi\u0107. 2020. Principal Neighbourhood Aggregation for Graph Nets. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_24_1","volume-title":"Fast Neighborhood Subgraph Pairwise Distance Kernel. In International Conference on Machine Learning. 255--262","author":"Costa Fabrizio","year":"2010","unstructured":"Fabrizio Costa and Kurt De Grave. 2010. Fast Neighborhood Subgraph Pairwise Distance Kernel. In International Conference on Machine Learning. 255--262."},{"key":"e_1_3_2_1_25_1","unstructured":"Leonardo Cotta Christopher Morris and Bruno Ribeiro. 2021. Reconstruction for Powerful Graph Representations. In Advances in Neural Information Processing Systems. 1713--1726."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02551274"},{"key":"e_1_3_2_1_27_1","volume-title":"Coloring Graph Neural Networks for Node Disambiguation. In International Joint Conference on Artificial Intelligence. 2126--2132","author":"Dasoulas George","year":"2020","unstructured":"George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. 2020. Coloring Graph Neural Networks for Node Disambiguation. In International Joint Conference on Artificial Intelligence. 2126--2132."},{"key":"e_1_3_2_1_28_1","unstructured":"Micha\u00eb l Defferrard Xavier Bresson and Pierre Vandergheynst. 2016. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances in Neural Information Processing Systems. 3837--3845."},{"key":"e_1_3_2_1_29_1","volume-title":"Ruosong Wang, and Keyulu Xu.","author":"Du Simon S.","year":"2019","unstructured":"Simon S. Du, Kangcheng Hou, Ruslan Salakhutdinov, Barnab\u00e1 s P\u00f3 czos, Ruosong Wang, and Keyulu Xu. 2019. Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels. In Advances in Neural Information Processing Systems. 5724--5734."},{"key":"e_1_3_2_1_30_1","volume-title":"Timothy Hirzel, Al\u00e1 n Aspuru-Guzik, and Ryan P. Adams.","author":"Duvenaud David","year":"2015","unstructured":"David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraguirre, Rafael G\u00f3 mez-Bombarelli, Timothy Hirzel, Al\u00e1 n Aspuru-Guzik, and Ryan P. Adams. 2015. Convolutional Networks on Graphs for Learning Molecular Fingerprints. In Advances in Neural Information Processing Systems. 2224--2232."},{"key":"e_1_3_2_1_31_1","unstructured":"Pascal Mattia Esser Leena C. Vankadara and Debarghya Ghoshdastidar. 2021. Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks. In Advances in Neural Information Processing Systems. 27043--27056."},{"key":"e_1_3_2_1_32_1","unstructured":"Jiarui Feng Yixin Chen Fuhai Li Anindya Sarkar and Muhan Zhang. 2022. How Powerful are K-hop Message Passing Graph Neural Networks. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_33_1","unstructured":"Fabrizio Frasca Beatrice Bevilacqua Michael M. Bronstein and Haggai Maron. 2022. Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries. (2022)."},{"key":"e_1_3_2_1_34_1","volume-title":"Optimal Assignment Kernels for Attributed Molecular Graphs. In International Conference on Machine Learning. 225--232","author":"Holger Fr\u00f6","year":"2005","unstructured":"Holger Fr\u00f6 hlich, J\u00f6 rg K. Wegner, Florian Sieker, and Andreas Zell. 2005. Optimal Assignment Kernels for Attributed Molecular Graphs. In International Conference on Machine Learning. 225--232."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2018.2887403"},{"volume-title":"Generalization and Representational Limits of Graph Neural Networks. In International Conference on Machine Learning. 3419--3430","author":"Garg Vikas K.","key":"e_1_3_2_1_36_1","unstructured":"Vikas K. Garg, Stefanie Jegelka, and Tommi S. Jaakkola. 2020. Generalization and Representational Limits of Graph Neural Networks. In International Conference on Machine Learning. 3419--3430."},{"key":"e_1_3_2_1_37_1","volume-title":"On Graph Kernels: Hardness Results and Efficient Alternatives. In Conference on Computational Learning Theory. 129--143","author":"Thomas","year":"2003","unstructured":"Thomas G\"a rtner, Peter A. Flach, and Stefan Wrobel. 2003. On Graph Kernels: Hardness Results and Efficient Alternatives. In Conference on Computational Learning Theory. 129--143."},{"key":"e_1_3_2_1_38_1","volume-title":"On the Expressive Power of Linear Algebra on Graphs. In International Conference on Database Theory. 7:1--7:19","author":"Geerts Floris","year":"2019","unstructured":"Floris Geerts. 2019. On the Expressive Power of Linear Algebra on Graphs. In International Conference on Database Theory. 7:1--7:19."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-09990-9"},{"volume-title":"International Conference on Machine Learning. 3640--3649","author":"Geerts Floris","key":"e_1_3_2_1_40_1","unstructured":"Floris Geerts, Filip Mazowiecki, and Guillermo A. P\u00e9 rez. 2021a. Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework. In International Conference on Machine Learning. 3640--3649."},{"key":"e_1_3_2_1_41_1","volume-title":"Expressive Power of Linear Algebra Query Languages. In Symposium on Principles of Database Systems.","author":"Geerts Floris","year":"2021","unstructured":"Floris Geerts, Thomas Mu noz, Cristian Riveros, and Domagoj Vrgovc. 2021b. Expressive Power of Linear Algebra Query Languages. In Symposium on Principles of Database Systems."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503780.3503782"},{"volume-title":"Expressiveness and Approximation Properties of Graph Neural Networks. In International Conference on Learning Representations.","author":"Geerts Floris","key":"e_1_3_2_1_43_1","unstructured":"Floris Geerts and Juan L. Reutter. 2022. Expressiveness and Approximation Properties of Graph Neural Networks. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-11321-5_2"},{"volume-title":"Neural Message Passing for Quantum Chemistry. In International Conference on Machine Learning. 1263--1272","author":"Gilmer Justin","key":"e_1_3_2_1_45_1","unstructured":"Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural Message Passing for Quantum Chemistry. In International Conference on Machine Learning. 1263--1272."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387641"},{"key":"e_1_3_2_1_47_1","volume-title":"The Logic of Graph Neural Networks. In Symposium on Logic in Computer Science. 1--17","author":"Grohe Martin","year":"2021","unstructured":"Martin Grohe. 2021. The Logic of Graph Neural Networks. In Symposium on Logic in Computer Science. 1--17."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Martin Grohe. 2023. The Descriptive Complexity of Graph Neural Networks. (2023). arxiv: 2303.04613","DOI":"10.1109\/LICS56636.2023.10175735"},{"volume-title":"Graph Representation Learning","author":"Hamilton William L.","key":"e_1_3_2_1_49_1","unstructured":"William L. Hamilton. 2020. Graph Representation Learning. Morgan & Claypool Publishers."},{"key":"e_1_3_2_1_50_1","unstructured":"William L. Hamilton Zhitao Ying and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems. 1024--1034."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502100"},{"volume-title":"Topological Graph Neural Networks. In International Conference on Learning Representations.","author":"Horn Max","key":"e_1_3_2_1_52_1","unstructured":"Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten M. Borgwardt. 2022. Topological Graph Neural Networks. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0893-6080(91)90009-T"},{"key":"e_1_3_2_1_54_1","unstructured":"Yinan Huang Xingang Peng Jianzhu Ma and Muhan Zhang. 2023. Boosting the Cycle Counting Power of Graph Neural Networks with I(^mbox2 )-GNNs. (2023)."},{"key":"e_1_3_2_1_55_1","volume-title":"LaraDB: A Minimalist Kernel for Linear and Relational Algebra Computation. In ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond. 2:1--2:10","author":"Hutchison Dylan","year":"2017","unstructured":"Dylan Hutchison, Bill Howe, and Dan Suciu. 2017. LaraDB: A Minimalist Kernel for Linear and Relational Algebra Computation. In ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond. 2:1--2:10."},{"key":"e_1_3_2_1_56_1","unstructured":"Stefanie Jegelka. 2022. Theory of Graph Neural Networks: Representation and Learning. (2022). arxiv: 2204.07697"},{"key":"e_1_3_2_1_57_1","volume-title":"Fast Random Walk Graph Kernel. In SIAM International Conference on Data Mining. 828--838","author":"Kang U","year":"2012","unstructured":"U Kang, Hanghang Tong, and Jimeng Sun. 2012. Fast Random Walk Graph Kernel. In SIAM International Conference on Data Mining. 828--838."},{"key":"e_1_3_2_1_58_1","volume-title":"Marginalized Kernels Between Labeled Graphs. In International Conference on Machine Learning. 321--328","author":"Kashima Hisashi","year":"2003","unstructured":"Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. 2003. Marginalized Kernels Between Labeled Graphs. In International Conference on Machine Learning. 321--328."},{"key":"e_1_3_2_1_59_1","unstructured":"Nicolas Keriven and Gabriel Peyr\u00e9. 2019. Universal Invariant and Equivariant Graph Neural Networks. In Advances in Neural Information Processing Systems. 7090--7099."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3426865"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"volume-title":"Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations.","author":"Thomas","key":"e_1_3_2_1_62_1","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_63_1","unstructured":"Risi Kondor and Horace Pan. 2016. The Multiscale Laplacian Graph Kernel. In Advances in Neural Information Processing Systems. 2982--2990."},{"key":"e_1_3_2_1_64_1","volume-title":"Wilson","author":"Kriege Nils M.","year":"2016","unstructured":"Nils M. Kriege, Pierre-Louis Giscard, and Richard C. Wilson. 2016. On Valid Optimal Assignment Kernels and Applications to Graph Classification. In Advances in Neural Information Processing Systems. 1615--1623."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41109-019-0195-3"},{"volume-title":"Subgraph Matching Kernels for Attributed Graphs. In International Conference on Machine Learning.","author":"Nils","key":"e_1_3_2_1_66_1","unstructured":"Nils M. Kriege and Petra Mutzel. 2012. Subgraph Matching Kernels for Attributed Graphs. In International Conference on Machine Learning."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-6080(05)80131-5"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2018.2879624"},{"key":"e_1_3_2_1_69_1","volume-title":"Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning. In Advances in Neural Information Processing Systems.","author":"Li Pan","year":"2020","unstructured":"Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. 2020. Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning. In Advances in Neural Information Processing Systems."},{"volume-title":"International Conference on Learning Representations.","author":"Liao Renjie","key":"e_1_3_2_1_70_1","unstructured":"Renjie Liao, Raquel Urtasun, and Richard S. Zemel. 2021. A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00736-3"},{"volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","key":"e_1_3_2_1_72_1","unstructured":"Leonid Libkin. 2004. Elements of Finite Model Theory. Springer."},{"volume-title":"Deep Learning on Graphs","author":"Ma Yao","key":"e_1_3_2_1_73_1","unstructured":"Yao Ma and Jiliang Tang. 2021. Deep Learning on Graphs. Cambridge University Press."},{"key":"e_1_3_2_1_74_1","unstructured":"Takanori Maehara and Hoang NT. 2019. A Simple Proof of the Universality of Invariant\/Equivariant Graph Neural Networks. (2019). arxiv: 1910.03802"},{"key":"e_1_3_2_1_75_1","unstructured":"Haggai Maron Heli Ben-Hamu Hadar Serviansky and Yaron Lipman. 2019a. Provably Powerful Graph Networks. In Advances in Neural Information Processing Systems. 2153--2164."},{"key":"e_1_3_2_1_76_1","volume-title":"On the Universality of Invariant Networks. In International Conference on Machine Learning. 4363--4371","author":"Maron Haggai","year":"2019","unstructured":"Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. 2019b. On the Universality of Invariant Networks. In International Conference on Machine Learning. 4363--4371."},{"key":"e_1_3_2_1_77_1","volume-title":"Benedikt Schesch, and Roger Wattenhofer.","author":"Martinkus Karolis","year":"2022","unstructured":"Karolis Martinkus, P\u00e1 l Andr\u00e1 s Papp, Benedikt Schesch, and Roger Wattenhofer. 2022. Agent-based Graph Neural Networks. (2022). showeprint[arXiv]2206.11010"},{"key":"e_1_3_2_1_78_1","unstructured":"Sohir Maskey Ron Levie Yunseok Lee and Gitta Kutyniok. 2022. Generalization Analysis of Message Passing Neural Networks on Large Random Graphs. In Advances in Neural Information Processing Systems."},{"volume-title":"Foundations of Machine Learning","author":"Mohri Mehryar","key":"e_1_3_2_1_79_1","unstructured":"Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. 2018. Foundations of Machine Learning. MIT Press."},{"volume-title":"Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs. In IEEE Conference on Computer Vision and Pattern Recognition. 5425--5434","author":"Monti Federico","key":"e_1_3_2_1_80_1","unstructured":"Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodol\u00e0, Jan Svoboda, and Michael M. Bronstein. 2017. Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs. In IEEE Conference on Computer Vision and Pattern Recognition. 5425--5434."},{"key":"e_1_3_2_1_81_1","volume-title":"WL meet VC.","author":"Morris Christopher","year":"2023","unstructured":"Christopher Morris, Floris Geerts, Jan T\u00f6nshoff, and Martin Grohe. 2023. WL meet VC. (2023). arxiv: 2301.11039"},{"key":"e_1_3_2_1_82_1","volume-title":"Glocalized Weisfeiler-Lehman Kernels: Global-Local Feature Maps of Graphs. In IEEE International Conference on Data Mining. 327--336","author":"Morris Christopher","year":"2017","unstructured":"Christopher Morris, Kristian Kersting, and Petra Mutzel. 2017. Glocalized Weisfeiler-Lehman Kernels: Global-Local Feature Maps of Graphs. In IEEE International Conference on Data Mining. 327--336."},{"key":"e_1_3_2_1_83_1","volume-title":"Borgwardt","author":"Morris Christopher","year":"2021","unstructured":"Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten M. Borgwardt. 2021. Weisfeiler and Leman go Machine Learning: The Story so far. (2021). showeprint[arXiv]2112.09992"},{"key":"e_1_3_2_1_84_1","volume-title":"International Conference on Machine Learning. 16017--16042","author":"Morris Christopher","year":"2022","unstructured":"Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. 2022. SpeqNets: Sparsity-aware permutation-equivariant graph networks. In International Conference on Machine Learning. 16017--16042."},{"key":"e_1_3_2_1_85_1","unstructured":"Christopher Morris Gaurav Rattan and Petra Mutzel. 2020. Weisfeiler and Leman Go Sparse: Towards Higher-Order Graph Embeddings. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_86_1","volume-title":"Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. In AAAI Conference on Artificial Intelligence. 4602--4609","author":"Morris Christopher","year":"2019","unstructured":"Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. In AAAI Conference on Artificial Intelligence. 4602--4609."},{"key":"e_1_3_2_1_87_1","volume-title":"Relational Pooling for Graph Representations. In International Conference on Machine Learning. 4663--4673","author":"Murphy Ryan L.","year":"2019","unstructured":"Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak A. Rao, and Bruno Ribeiro. 2019. Relational Pooling for Graph Representations. In International Conference on Machine Learning. 4663--4673."},{"key":"e_1_3_2_1_88_1","volume-title":"Graph Homomorphism Convolution. In International Conference on Machine Learning. 7306--7316","author":"Nguyen Hoang","year":"2020","unstructured":"Hoang Nguyen and Takanori Maehara. 2020. Graph Homomorphism Convolution. In International Conference on Machine Learning. 7306--7316."},{"key":"e_1_3_2_1_89_1","volume-title":"Matching Node Embeddings for Graph Similarity. In AAAI Conference on Artificial Intelligence. 2429--2435","author":"Nikolentzos Giannis","year":"2017","unstructured":"Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. 2017. Matching Node Embeddings for Graph Similarity. In AAAI Conference on Artificial Intelligence. 2429--2435."},{"key":"e_1_3_2_1_90_1","unstructured":"P\u00e1 l Andr\u00e1 s Papp Karolis Martinkus Lukas Faber and Roger Wattenhofer. 2021. DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_91_1","volume-title":"International Conference on Machine Learning. 17323--17345","author":"Papp P\u00e1","year":"2022","unstructured":"P\u00e1 l Andr\u00e1 s Papp and Roger Wattenhofer. 2022. A Theoretical Comparison of Graph Neural Network Extensions. In International Conference on Machine Learning. 17323--17345."},{"key":"e_1_3_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1006\/jath.1994.1080"},{"key":"e_1_3_2_1_93_1","volume-title":"Haggai Maron, and Yaron Lipman.","author":"Puny Omri","year":"2023","unstructured":"Omri Puny, Derek Lim, Bobak Toussi Kiani, Haggai Maron, and Yaron Lipman. 2023. Equivariant Polynomials for Graph Neural Networks. (2023). arxiv: 2302.11556"},{"key":"e_1_3_2_1_94_1","unstructured":"Chendi Qian Gaurav Rattan Floris Geerts Christopher Morris and Mathias Niepert. 2022. Ordered Subgraph Aggregation Networks. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_95_1","volume-title":"Jan T\u00f6 nshoff, and Martin Grohe","author":"Rosenbluth Eran","year":"2023","unstructured":"Eran Rosenbluth, Jan T\u00f6 nshoff, and Martin Grohe. 2023. Some Might Say All You Need Is Sum. (2023). arxiv: 2302.11603"},{"key":"e_1_3_2_1_96_1","volume-title":"Random Features Strengthen Graph Neural Networks. In SIAM International Conference on Data Mining. 333--341","author":"Sato Ryoma","year":"2021","unstructured":"Ryoma Sato, Makoto Yamada, and Hisashi Kashima. 2021. Random Features Strengthen Graph Neural Networks. In SIAM International Conference on Data Mining. 333--341."},{"key":"e_1_3_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"e_1_3_2_1_98_1","volume-title":"Ah Chung Tsoi, and Markus Hagenbuchner","author":"Scarselli Franco","year":"2018","unstructured":"Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. 2018. The Vapnik-Chervonenkis Dimension of Graph and Recursive Neural Networks. Neural Networks (2018), 248--259."},{"volume-title":"Understanding Machine Learning: From Theory to Algorithms","author":"Shalev-Shwartz Shai","key":"e_1_3_2_1_99_1","unstructured":"Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_100_1","unstructured":"N. Shervashidze P. Schweitzer E. J. van Leeuwen K. Mehlhorn and K. M. Borgwardt. 2011. Weisfeiler-Lehman Graph Kernels. Journal of Machine Learning Research (2011) 2539--2561."},{"volume-title":"Efficient Graphlet Kernels for Large Graph Comparison. In International Conference on Artificial Intelligence and Statistics. 488--495","author":"Shervashidze Nino","key":"e_1_3_2_1_101_1","unstructured":"Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. 2009. Efficient Graphlet Kernels for Large Graph Comparison. In International Conference on Artificial Intelligence and Statistics. 488--495."},{"key":"e_1_3_2_1_102_1","volume-title":"Borgwardt","author":"Sugiyama Mahito","year":"2015","unstructured":"Mahito Sugiyama and Karsten M. Borgwardt. 2015. Halting in Random Walk Kernels. In Advances in Neural Information Processing Systems. 1639--1647."},{"key":"e_1_3_2_1_103_1","unstructured":"Rajat Talak Siyi Hu Lisa Peng and Luca Carlone. 2021. Neural Trees for Learning on Graphs. In Advances in Neural Information Processing Systems. 26395--26408."},{"key":"e_1_3_2_1_104_1","volume-title":"Autobahn: Automorphism-based Graph Neural Nets. In Advances in Neural Information Processing Systems. 29922--29934.","author":"Thiede Erik H.","year":"2021","unstructured":"Erik H. Thiede, Wenda Zhou, and Risi Kondor. 2021. Autobahn: Automorphism-based Graph Neural Nets. In Advances in Neural Information Processing Systems. 29922--29934."},{"key":"e_1_3_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.5555\/1113097.1113101"},{"key":"e_1_3_2_1_106_1","unstructured":"Jan T\u00f6 nshoff Martin Ritzert Hinrikus Wolf and Martin Grohe. 2021. Graph Learning with 1D Convolutions on Random Walks. (2021). showeprint[arXiv]2102.08786"},{"key":"e_1_3_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.5555\/211359"},{"key":"e_1_3_2_1_108_1","volume-title":"Graph Attention Networks. In International Conference on Learning Representations.","author":"Petar Velivckovi\u0107","year":"2018","unstructured":"Petar Velivckovi\u0107 , Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2 , and Yoshua Bengio. 2018. Graph Attention Networks. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_109_1","volume-title":"Stability and Generalization of Graph Convolutional Neural Networks. In International Conference on Knowledge Discovery & Data Mining. 1539--1548","author":"Verma Saurabh","year":"2019","unstructured":"Saurabh Verma and Zhi-Li Zhang. 2019. Stability and Generalization of Graph Convolutional Neural Networks. In International Conference on Knowledge Discovery & Data Mining. 1539--1548."},{"key":"e_1_3_2_1_110_1","unstructured":"Cl\u00e9 ment Vignac Andreas Loukas and Pascal Frossard. 2020. Building powerful and equivariant graph neural networks with structural message-passing. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_111_1","volume-title":"International Conference on Learning Representations.","author":"Wijesinghe Asiri","year":"2022","unstructured":"Asiri Wijesinghe and Qing Wang. 2022. A New Perspective on \"How Graph Neural Networks Go Beyond Weisfeiler-Lehman?\". In International Conference on Learning Representations."},{"key":"e_1_3_2_1_112_1","doi-asserted-by":"crossref","unstructured":"Lingfei Wu Peng Cui Jian Pei and Liang Zhao (Eds.). 2022. Graph Neural Networks: Foundations Frontiers and Applications. Springer.","DOI":"10.1007\/978-981-16-6054-2_13"},{"key":"e_1_3_2_1_113_1","volume-title":"International Conference on Learning Representations.","author":"Xu Keyulu","year":"2019","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_114_1","volume-title":"Tensor Programs IIb: Architectural Universality Of Neural Tangent Kernel Training Dynamics. In International Conference on Machine Learning. 11762--11772","author":"Yang Greg","year":"2021","unstructured":"Greg Yang and Etai Littwin. 2021. Tensor Programs IIb: Architectural Universality Of Neural Tangent Kernel Training Dynamics. In International Conference on Machine Learning. 11762--11772."},{"key":"e_1_3_2_1_115_1","volume-title":"Identity-aware Graph Neural Networks. In AAAI Conference on Artificial Intelligence. 10737--10745","author":"You Jiaxuan","year":"2021","unstructured":"Jiaxuan You, Jonathan Gomes-Selman, Rex Ying, and Jure Leskovec. 2021. Identity-aware Graph Neural Networks. In AAAI Conference on Artificial Intelligence. 10737--10745."},{"key":"e_1_3_2_1_116_1","unstructured":"Bohang Zhang Guhao Feng Yiheng Du Di He and Liwei Wang. 2023 a. A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests. (2023). arxiv: 2302.07090"},{"key":"e_1_3_2_1_117_1","unstructured":"Bohang Zhang Shengjie Luo Liwei Wang and Di He. 2023 b. Rethinking the Expressive Power of GNNs via Graph Biconnectivity. (2023). showeprint[arXiv]2301.09505"},{"key":"e_1_3_2_1_118_1","unstructured":"Muhan Zhang and Pan Li. 2021. Nested Graph Neural Networks. In Advances in Neural Information Processing Systems. 15734--15747."},{"key":"e_1_3_2_1_119_1","volume-title":"International Conference on Learning Representations. io","author":"Zhao Lingxiao","year":"2022","unstructured":"Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. 2022. From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness. In International Conference on Learning Representations. io"}],"event":{"name":"SIGMOD\/PODS '23: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Seattle WA USA","acronym":"SIGMOD\/PODS '23"},"container-title":["Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3589936","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3589936","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:29Z","timestamp":1750178789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3589936"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,18]]},"references-count":119,"alternative-id":["10.1145\/3584372.3589936","10.1145\/3584372"],"URL":"https:\/\/doi.org\/10.1145\/3584372.3589936","relation":{},"subject":[],"published":{"date-parts":[[2023,6,18]]},"assertion":[{"value":"2023-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}