{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:00:19Z","timestamp":1740182419830,"version":"3.37.3"},"reference-count":56,"publisher":"IOP Publishing","issue":"3","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":29,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"tdm","delay-in-days":29,"URL":"https:\/\/iopscience.iop.org\/info\/page\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62172341"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["iopscience.iop.org"],"crossmark-restriction":false},"short-container-title":["Mach. Learn.: Sci. Technol."],"published-print":{"date-parts":[[2024,9,1]]},"abstract":"Abstract<\/jats:title>\n The graph isomorphism, as a key task in graph data analysis, is of great significance for the understanding, feature extraction, and pattern recognition of graph data. The best performance of traditional methods is the quasi-polynomial time complexity, which is infeasible for huge graphs. This paper aims to propose a lightweight graph network to resolve the problem of isomorphism in huge graphs. We propose a partitioning algorithm with linear time complexity based on isomorphic necessary condition to handle network graphs that cannot be fully computed by a single computer. We use anti-weight convolution analysis and skip connections to obtain a more stable representation with fewer layers and parameters. We implement simulations on personal computer (PC) with graphs consisting of hundred millions of edges, demonstrating the identification performance (\n \n \n \n ><\/mml:mo>\n \n \n 98<\/mml:mn>\n %<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:inline-formula>) and time efficiency.<\/jats:p>","DOI":"10.1088\/2632-2153\/ad7d5f","type":"journal-article","created":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T22:58:12Z","timestamp":1726786692000},"page":"035084","update-policy":"https:\/\/doi.org\/10.1088\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Portable network resolving huge-graph isomorphism problem"],"prefix":"10.1088","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-0065-7750","authenticated-orcid":true,"given":"Xin","family":"An","sequence":"first","affiliation":[]},{"given":"Ling-Fang","family":"Li","sequence":"additional","affiliation":[]},{"given":"Xue","family":"Yang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1287-4437","authenticated-orcid":true,"given":"Ming-Xing","family":"Luo","sequence":"additional","affiliation":[]}],"member":"266","published-online":{"date-parts":[[2024,9,30]]},"reference":[{"key":"mlstad7d5fbib1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1038\/s41586-023-06221-2","article-title":"Scientific discovery in the age of artificial intelligence","volume":"620","author":"Wang","year":"2023","journal-title":"Nature"},{"article-title":"ChemBERTa: large-scale self-supervised pretraining for molecular property prediction","year":"2020","author":"Chithrananda","key":"mlstad7d5fbib2"},{"key":"mlstad7d5fbib3","first-page":"pp 2674","article-title":"SelfAugment: automatic augmentation policies for self-supervised learning","author":"Reed","year":"2021"},{"key":"mlstad7d5fbib4","doi-asserted-by":"publisher","first-page":"23414","DOI":"10.1002\/anie.201909989","article-title":"Autonomous discovery in the chemical sciences part II: outlook","volume":"59","author":"Coley","year":"2020","journal-title":"Angew. Chem., Int. Ed."},{"key":"mlstad7d5fbib5","doi-asserted-by":"publisher","first-page":"5714","DOI":"10.1021\/acs.jcim.0c00174","article-title":"The synthesizability of molecules proposed by generative models","volume":"60","author":"Gao","year":"2020","journal-title":"J. Chem. Inf. Model."},{"key":"mlstad7d5fbib6","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1038\/s41586-021-03819-2","article-title":"Highly accurate protein structure prediction with AlphaFold","volume":"596","author":"Jumper","year":"2021","journal-title":"Nature"},{"key":"mlstad7d5fbib7","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.143001","article-title":"Deep potential molecular dynamics: a scalable model with the accuracy of quantum mechanics","volume":"120","author":"Zhang","year":"2018","journal-title":"Phys. Rev. Lett."},{"key":"mlstad7d5fbib8","first-page":"pp 85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"mlstad7d5fbib9","first-page":"pp 684","article-title":"Graph isomorphism in quasipolynomial time","author":"Babai","year":"2016"},{"article-title":"How powerful are graph neural networks?","year":"2019","author":"Xu","key":"mlstad7d5fbib10"},{"key":"mlstad7d5fbib11","first-page":"pp 4602","article-title":"Weisfeiler and Leman go neural: higher-order graph neural networks","volume":"vol 33","author":"Morris","year":"2019"},{"key":"mlstad7d5fbib12","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2023.121280","article-title":"Graph isomorphism U-Net","volume":"236","author":"Amouzad","year":"2024","journal-title":"Expert Syst. Appl."},{"key":"mlstad7d5fbib13","article-title":"Fine-grained expressivity of graph neural networks","volume":"vol 36","author":"B\u00f6ker","year":"2024"},{"key":"mlstad7d5fbib14","first-page":"pp 4845","article-title":"Learning to count isomorphisms with graph neural networks","volume":"vol 37","author":"Yu","year":"2023"},{"article-title":"Graph attention networks","year":"2018","author":"Velickovic","key":"mlstad7d5fbib15"},{"key":"mlstad7d5fbib16","first-page":"pp 7134","article-title":"Position-aware graph neural networks","author":"You","year":"2019"},{"key":"mlstad7d5fbib17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/TNN.2008.2005605","article-title":"The graph neural network model","volume":"20","author":"Scarselli","year":"2008","journal-title":"IEEE Trans. Neural Netw."},{"key":"mlstad7d5fbib18","first-page":"p 30","article-title":"Inductive representation learning on large graphs","author":"Hamilton","year":"2017"},{"key":"mlstad7d5fbib19","first-page":"pp 1263","article-title":"Neural message passing for quantum chemistry","author":"Gilmer","year":"2017"},{"key":"mlstad7d5fbib20","first-page":"p 28","article-title":"Convolutional networks on graphs for learning molecular fingerprints","author":"Duvenaud","year":"2015"},{"key":"mlstad7d5fbib21","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1109\/MSP.2017.2693418","article-title":"Geometric deep learning: going beyond Euclidean data","volume":"34","author":"Bronstein","year":"2017","journal-title":"IEEE Signal Process. Mag."},{"key":"mlstad7d5fbib22","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1109\/TPAMI.2022.3154319","article-title":"Improving graph neural network expressivity via subgraph isomorphism counting","volume":"45","author":"Bouritsas","year":"2022","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"mlstad7d5fbib23","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/swf.30","article-title":"Web dynamics","volume":"2","author":"Levene","year":"2001","journal-title":"Softw. Focus"},{"key":"mlstad7d5fbib24","doi-asserted-by":"publisher","first-page":"7693","DOI":"10.1109\/TKDE.2022.3201243","article-title":"Adversarial attack and defense on graph data: a survey","volume":"35","author":"Sun","year":"2022","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"mlstad7d5fbib25","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/321556.321562","article-title":"An efficient algorithm for graph isomorphism","volume":"17","author":"Corneil","year":"1970","journal-title":"J. ACM"},{"key":"mlstad7d5fbib26","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1126\/science.126.3278.814","article-title":"Finding chemical records by digital computers","volume":"126","author":"Ray","year":"1957","journal-title":"Science"},{"key":"mlstad7d5fbib27","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1021\/c160017a018","article-title":"The generation of a unique machine description for chemical structures-a technique developed at chemical abstracts service","volume":"5","author":"Morgan","year":"1965","journal-title":"J. Chem. Doc."},{"key":"mlstad7d5fbib28","first-page":"12","article-title":"A reduction of a graph to a canonical form and an algebra arising during this reduction (in Russian)","volume":"2","author":"Leman","year":"1968","journal-title":"Nauchno-Tekh. Inf."},{"key":"mlstad7d5fbib29","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1137\/22M1514076","article-title":"Isomorphism testing parameterized by genus and beyond","volume":"38","author":"Neuen","year":"2024","journal-title":"SIAM J. Discrete Math."},{"key":"mlstad7d5fbib30","first-page":"pp 157","article-title":"Faster canonical forms for strongly regular graphs","author":"Babai","year":"2013"},{"key":"mlstad7d5fbib31","first-page":"pp 1395","article-title":"Code equivalence and group isomorphism","author":"Babai","year":"2011"},{"key":"mlstad7d5fbib32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3543686","article-title":"Planar graph isomorphism is in log-space","volume":"14","author":"Datta","year":"2022","journal-title":"ACM Trans. Comput. Theory"},{"key":"mlstad7d5fbib33","first-page":"pp 2220","article-title":"Rethinking pooling in graph neural networks","volume":"vol 33","author":"Mesquita","year":"2020"},{"key":"mlstad7d5fbib34","first-page":"pp 5470","article-title":"ASAP: adaptive structure aware pooling for learning hierarchical graph representations","volume":"vol 34","author":"Ranjan","year":"2020"},{"key":"mlstad7d5fbib35","first-page":"pp 3734","article-title":"Self-attention graph pooling","author":"Lee","year":"2019"},{"article-title":"Semi-supervised classification with graph convolutional networks","year":"2017","author":"Kipf","key":"mlstad7d5fbib36"},{"article-title":"Graph attention networks","year":"2018","author":"Velickovic","key":"mlstad7d5fbib37"},{"article-title":"How attentive are graph attention networks?","year":"2022","author":"Brody","key":"mlstad7d5fbib38"},{"article-title":"How to find your friendly neighborhood: graph attention design with self-supervision","year":"2021","author":"Kim","key":"mlstad7d5fbib39"},{"key":"mlstad7d5fbib40","first-page":"pp 7594","article-title":"Graph convolutional networks with dual message passing for subgraph isomorphism counting and matching","volume":"vol 36","author":"Liu","year":"2022"},{"article-title":"Anti-symmetric DGN: a stable architecture for deep graph networks","year":"2023","author":"Gravina","key":"mlstad7d5fbib41"},{"key":"mlstad7d5fbib42","first-page":"pp 4438","article-title":"An end-to-end deep learning architecture for graph classification","volume":"vol 32","author":"Zhang","year":"2018"},{"key":"mlstad7d5fbib43","first-page":"pp 1365","article-title":"Deep graph kernels","author":"Yanardag","year":"2015"},{"key":"mlstad7d5fbib44","first-page":"pp 73","article-title":"Siamese neural networks: an overview","author":"Chicco","year":"2021"},{"key":"mlstad7d5fbib45","first-page":"pp 3438","article-title":"Measuring and relieving the over-smoothing problem for graph neural networks from the topological view","volume":"vol 34","author":"Chen","year":"2020"},{"key":"mlstad7d5fbib46","first-page":"pp 2083","article-title":"Graph U-Nets","author":"Gao","year":"2019"},{"key":"mlstad7d5fbib47","doi-asserted-by":"publisher","first-page":"2539","DOI":"10.5555\/1953048.2078187","article-title":"Weisfeiler-Lehman graph kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"mlstad7d5fbib48","first-page":"pp 2001","article-title":"Diffusion-convolutional neural networks","volume":"vol 29","author":"Atwood","year":"2016"},{"key":"mlstad7d5fbib49","first-page":"pp 2186","article-title":"Anonymous walk embeddings","author":"Ivanov","year":"2018"},{"key":"mlstad7d5fbib50","doi-asserted-by":"publisher","first-page":"2697","DOI":"10.1021\/acs.jcim.0c01489","article-title":"XGraphBoost: extracting graph neural network-based features for a better prediction of molecular properties","volume":"61","author":"Deng","year":"2021","journal-title":"J. Chem. Inf. Model."},{"article-title":"Boost then convolve: gradient boosting meets graph neural networks","year":"2021","author":"Sand Prokhorenkova","key":"mlstad7d5fbib51"},{"key":"mlstad7d5fbib52","first-page":"pp 1988","article-title":"Unsupervised inductive graph-level representation learning via graph-graph proximity","author":"Bai","year":"2019"},{"key":"mlstad7d5fbib53","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1961189.1961199","article-title":"LIBSVM: a library for support vector machines","volume":"2","author":"Chang","year":"2011","journal-title":"ACM Trans. Intel. Syst. Technol."},{"key":"mlstad7d5fbib54","first-page":"pp 2014","article-title":"Learning convolutional neural networks for graphs","author":"Niepert","year":"2016"},{"key":"mlstad7d5fbib55","first-page":"pp 40","article-title":"Revisiting semi-supervised learning with graph embeddings","author":"Yang","year":"2016"},{"key":"mlstad7d5fbib56","first-page":"pp 22118","article-title":"Open graph benchmark: datasets for machine learning on graphs","volume":"vol 33","author":"Hu","year":"2020"}],"container-title":["Machine Learning: Science and Technology"],"original-title":[],"link":[{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ad7d5f","content-type":"text\/html","content-version":"am","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ad7d5f\/pdf","content-type":"application\/pdf","content-version":"am","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ad7d5f","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ad7d5f\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ad7d5f\/pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ad7d5f\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ad7d5f\/pdf","content-type":"application\/pdf","content-version":"am","intended-application":"similarity-checking"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ad7d5f\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T12:37:07Z","timestamp":1727699827000},"score":1,"resource":{"primary":{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ad7d5f"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,1]]},"references-count":56,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2024,9,30]]},"published-print":{"date-parts":[[2024,9,1]]}},"URL":"https:\/\/doi.org\/10.1088\/2632-2153\/ad7d5f","relation":{},"ISSN":["2632-2153"],"issn-type":[{"type":"electronic","value":"2632-2153"}],"subject":[],"published":{"date-parts":[[2024,9,1]]},"assertion":[{"value":"Portable network resolving huge-graph isomorphism problem","name":"article_title","label":"Article Title"},{"value":"Machine Learning: Science and Technology","name":"journal_title","label":"Journal Title"},{"value":"paper","name":"article_type","label":"Article Type"},{"value":"\u00a9 2024 The Author(s). Published by IOP Publishing Ltd","name":"copyright_information","label":"Copyright Information"},{"value":"2024-06-02","name":"date_received","label":"Date Received","group":{"name":"publication_dates","label":"Publication dates"}},{"value":"2024-09-19","name":"date_accepted","label":"Date Accepted","group":{"name":"publication_dates","label":"Publication dates"}},{"value":"2024-09-30","name":"date_epub","label":"Online publication date","group":{"name":"publication_dates","label":"Publication dates"}}]}}