{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T03:04:33Z","timestamp":1777777473693,"version":"3.51.4"},"reference-count":115,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"1","license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"name":"ERC Consolidator","award":["724228 - LEMAN"],"award-info":[{"award-number":["724228 - LEMAN"]}]},{"name":"Department of Computing, Imperial College London"},{"name":"EPSRC Fellowship DEFORM: Large Scale Shape Analysis of Deformable Models of Humans","award":["EP\/S010203\/1"],"award-info":[{"award-number":["EP\/S010203\/1"]}]},{"name":"Google Faculty Award"},{"name":"Google Faculty Award and the Royal Society Wolfson Research Merit Award"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Pattern Anal. Mach. Intell."],"published-print":{"date-parts":[[2023,1,1]]},"DOI":"10.1109\/tpami.2022.3154319","type":"journal-article","created":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T20:32:20Z","timestamp":1645734740000},"page":"657-668","source":"Crossref","is-referenced-by-count":185,"title":["Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting"],"prefix":"10.1109","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8476-4918","authenticated-orcid":false,"given":"Giorgos","family":"Bouritsas","sequence":"first","affiliation":[{"name":"Department of Computing, Imperial College London, London, U.K."}]},{"given":"Fabrizio","family":"Frasca","sequence":"additional","affiliation":[{"name":"Department of Computing, Imperial College London, U.K."}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5222-1740","authenticated-orcid":false,"given":"Stefanos","family":"Zafeiriou","sequence":"additional","affiliation":[{"name":"Department of Computing, Imperial College London, London, U.K."}]},{"given":"Michael M.","family":"Bronstein","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, U.K."}]}],"member":"263","reference":[{"key":"ref39","first-page":"15 868","article-title":"On the equivalence between graph isomorphism testing and function approximation with GNNs","author":"chen","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/294"},{"key":"ref33","article-title":"What graph neural networks cannot learn: Depth vs width","author":"loukas","year":"0","journal-title":"Proc Int Conf Learn Representations"},{"key":"ref32","first-page":"5998","article-title":"Attention is all you need","author":"vaswani","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref31","first-page":"1243","article-title":"Convolutional sequence to sequence learning","volume":"70","author":"gehring","year":"0","journal-title":"Proc Int Conf Mach Learn"},{"key":"ref30","first-page":"2440","article-title":"End-to-end memory networks","author":"sukhbaatar","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976700.38"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/P19-1285"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/N18-2074"},{"key":"ref34","article-title":"A survey on the expressive power of graph neural networks","author":"sato","year":"2020"},{"key":"ref28","first-page":"12","article-title":"The reduction of a graph to canonical form and the algebra which appears therein","volume":"9","author":"weisfeiler","year":"1968","journal-title":"NTI Ser 2"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.2307\/2371086"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1989.1.4.541"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.2307\/202051"},{"key":"ref22","article-title":"Invariant and equivariant graph networks","author":"maron","year":"0","journal-title":"Proc Int Conf Learn Representations"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"ref24","first-page":"2153","article-title":"Provably powerful graph networks","author":"maron","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref23","first-page":"4363","article-title":"On the universality of invariant networks","volume":"97","author":"maron","year":"0","journal-title":"Proc Int Conf Mach Learn"},{"key":"ref26","first-page":"22118","article-title":"Open graph benchmark: Datasets for machine learning on graphs","volume":"33","author":"hu","year":"0"},{"key":"ref101","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11782"},{"key":"ref25","article-title":"Benchmarking graph neural networks","author":"dwivedi","year":"0"},{"key":"ref100","first-page":"1993","article-title":"Diffusion-convolutional neural networks","author":"atwood","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1007\/11557067_14"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth163"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt717"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23219-5_21"},{"key":"ref55","first-page":"337","article-title":"$\\mathrm{Turbo}_\\mathrm{(iso)}$ Turbo ( iso ): Towards ultrafast and robust subgraph isomorphism search in large graph databases","author":"han","year":"0","journal-title":"Proc ACM SIGMOD Int Conf Manage Data"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58961-9_12"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0097896"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1957.7.961"},{"key":"ref4","first-page":"2224","article-title":"Convolutional networks on graphs for learning molecular fingerprints","author":"duvenaud","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0666-6"},{"key":"ref6","article-title":"The chemistry of smell: Learning generalizable perceptual representations of small molecules","author":"sanchez-lengeling","year":"0"},{"key":"ref5","first-page":"1263","article-title":"Neural message passing for quantum chemistry","volume":"70","author":"gilmer","year":"0","journal-title":"Proc Int Conf Mach Learn"},{"key":"ref8","first-page":"4502","article-title":"Interaction networks for learning about objects, relations and physics","author":"battaglia","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref7","first-page":"2693","article-title":"Neural relational inference for interacting systems","volume":"80","author":"kipf","year":"0","journal-title":"Proc Int Conf Mach Learn Proc Mach Learn Res"},{"key":"ref49","first-page":"4663","article-title":"Relational pooling for graph representations","volume":"97","author":"murphy","year":"0","journal-title":"Proc Int Conf Mach Learn"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/ICCVW.2015.112"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"ref48","first-page":"14143","article-title":"Building powerful and equivariant graph neural networks with structural message-passing","author":"vignac","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9029"},{"key":"ref42","first-page":"123","article-title":"Small graphs are reconstructible","volume":"15","author":"mckay","year":"1997","journal-title":"Australas J Combinatorics"},{"key":"ref41","volume":"8","author":"ulam","year":"1960","journal-title":"A Collection of Mathematical Problems"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth436"},{"key":"ref43","article-title":"The weisfeiler-lehman method and graph isomorphism testing","author":"douglas","year":"2011"},{"key":"ref73","first-page":"4465","article-title":"Distance encoding: Design provably more powerful neural networks for graph representation learning","volume":"33","author":"li","year":"0"},{"key":"ref72","first-page":"3636","article-title":"Natural graph networks","volume":"33","author":"haan","year":"0"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167149"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2009.07.019"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57586-5_22"},{"key":"ref74","first-page":"748","article-title":"Directional graph networks","author":"beaini","year":"0","journal-title":"Proc Int Conf Mach Learn"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"ref78","first-page":"40:1","article-title":"Lovász meets weisfeiler and leman","volume":"107","author":"dell","year":"2018","journal-title":"Proc Int Colloq Automata Lang Program"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.2307\/270703"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2006.51"},{"key":"ref62","article-title":"Frequent subgraph mining by walking in order embedding space","author":"ying","year":"0","journal-title":"Proc Int Conf Mach Learn Workshops"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl038"},{"key":"ref63","article-title":"Neural subgraph matching","author":"ying","year":"2020"},{"key":"ref64","first-page":"7090","article-title":"Universal invariant and equivariant graph neural networks","author":"keriven","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref65","article-title":"From graph low-rank global attention to 2-fwl approximation","author":"puny","year":"2020"},{"key":"ref66","first-page":"21824","article-title":"Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings","author":"morris","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref67","first-page":"3419","article-title":"Generalization and representational limits of graph neural networks","volume":"2020","author":"garg","year":"0","journal-title":"Proc Int Conf Mach Learn"},{"key":"ref68","first-page":"4083","article-title":"Approximation ratios of graph neural networks for combinatorial problems","author":"sato","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref2","first-page":"6530","article-title":"Protein interface prediction using graph convolutional networks","author":"fout","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref69","first-page":"82","article-title":"Local and global properties in networks of processors","author":"angluin","year":"0","journal-title":"Proc ACM Symp Theory Comput"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219890"},{"key":"ref95","doi-asserted-by":"publisher","DOI":"10.1088\/2632-2153\/abf5b8"},{"key":"ref109","first-page":"599","article-title":"Breaking the limits of message passing graph neural networks","author":"balcilar","year":"0","journal-title":"Proc Int Conf Mach Learn"},{"key":"ref94","article-title":"Near: Neighborhood edge aggregator for graph classification","author":"kim","year":"2019"},{"key":"ref108","article-title":"Principal neighbourhood aggregation for graph nets","author":"corso","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref93","article-title":"A hierarchy of graph neural networks based on learnable local features","author":"li","year":"2019"},{"key":"ref107","article-title":"Residual gated graph convnets","author":"bresson","year":"2017"},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357880"},{"key":"ref106","article-title":"Graph attention networks","author":"velickovic","year":"0","journal-title":"Proc Int Conf Learn Representations"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1145\/3341161.3342859"},{"key":"ref105","first-page":"1024","article-title":"Inductive representation learning on large graphs","author":"hamilton","year":"2017","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref90","doi-asserted-by":"publisher","DOI":"10.1109\/DSW.2018.8439897"},{"key":"ref104","article-title":"Semi-supervised classification with graph convolutional networks","author":"kipf","year":"0","journal-title":"Proc Int Conf Learn Representations"},{"key":"ref103","first-page":"1204","article-title":"GraphNorm: A principled approach to accelerating graph neural network training","author":"cai","year":"0","journal-title":"Proc Int Conf Mach Learn"},{"key":"ref102","article-title":"Wasserstein embedding for graph learning","author":"kolouri","year":"0","journal-title":"Proc Int Conf Learn Representations"},{"key":"ref111","doi-asserted-by":"publisher","DOI":"10.1021\/acscentsci.7b00572"},{"key":"ref112","first-page":"1945","article-title":"Grammar variational autoencoder","volume":"70","author":"kusner","year":"0","journal-title":"Proc Int Conf Mach Learn ser Proceedings of Machine Learning Research"},{"key":"ref110","article-title":"Hierarchical inter-message passing for learning on molecular graphs","author":"fey","year":"0"},{"key":"ref98","first-page":"2539","article-title":"Weisfeiler-lehman graph kernels","volume":"12","author":"shervashidze","year":"2011","journal-title":"J Mach Learn Res"},{"key":"ref99","first-page":"5724","article-title":"Graph neural tangent kernel: Fusing graph neural networks with graph kernels","author":"du","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref96","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45167-9_11"},{"key":"ref97","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-015-5517-9"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.576"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2019.00731"},{"key":"ref12","article-title":"Directional message passing for molecular graphs","author":"klicpera","year":"0","journal-title":"Proc Int Conf Learn Representations"},{"key":"ref13","article-title":"Gauge equivariant mesh CNNs: Anisotropic convolutions on geometric graphs","author":"haan","year":"0"},{"key":"ref14","first-page":"15 794","article-title":"Generative models for graph-based protein design","author":"ingraham","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93417-4_38"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1038\/srep35098"},{"key":"ref16","article-title":"How powerful are graph neural networks","author":"xu","year":"0","journal-title":"Proc Int Conf Learn Representations"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.4137\/CIN.S680"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"ref84","first-page":"488","article-title":"Efficient graphlet kernels for large graph comparison","volume":"5","author":"shervashidze","year":"2009","journal-title":"Proc Artif Intell Statist"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25027-0_8"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014072"},{"key":"ref19","first-page":"10383","article-title":"Can graph neural networks count substructures","author":"chen","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref114","doi-asserted-by":"publisher","DOI":"10.1021\/ci3001277"},{"key":"ref113","doi-asserted-by":"publisher","DOI":"10.1039\/9781788016841-00228"},{"key":"ref80","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","author":"pr\u017eulj","year":"2007","journal-title":"Bioinformatics"},{"key":"ref115","first-page":"3391","article-title":"Deep sets","author":"zaheer","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref89","doi-asserted-by":"publisher","DOI":"10.1145\/3184558.3186900"},{"key":"ref85","first-page":"255","article-title":"Fast neighborhood subgraph pairwise distance kernel","author":"costa","year":"0","journal-title":"Proc Int Conf Mach Learn"},{"key":"ref86","first-page":"291","article-title":"Subgraph matching kernels for attributed graphs","author":"kriege","year":"0","journal-title":"Proc Int Conf Mach Learn"},{"key":"ref87","first-page":"7306","article-title":"Graph homomorphism convolution","author":"nt","year":"0","journal-title":"Proc Int Conf Mach Learn ser Proceedings of Machine Learning Research"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1109\/BigData47090.2019.9005670"}],"container-title":["IEEE Transactions on Pattern Analysis and Machine Intelligence"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/34\/9970415\/09721082.pdf?arnumber=9721082","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T19:11:46Z","timestamp":1672081906000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9721082\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,1]]},"references-count":115,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.1109\/tpami.2022.3154319","relation":{},"ISSN":["0162-8828","2160-9292","1939-3539"],"issn-type":[{"value":"0162-8828","type":"print"},{"value":"2160-9292","type":"electronic"},{"value":"1939-3539","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,1]]}}}