{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T01:55:26Z","timestamp":1782611726402,"version":"3.54.5"},"reference-count":90,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T00:00:00Z","timestamp":1725926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We describe and study a transport-based procedure called network optimal transition coupling (NetOTC) for the comparison and alignment of two networks. The networks of interest may be directed or undirected, weighted or unweighted, and may have distinct vertex sets of different sizes. Given two networks and a cost function relating their vertices, NetOTC finds a transition coupling of their associated random walks having minimum expected cost. The minimizing cost quantifies the difference between the networks, while the optimal transport plan itself provides alignments of both the vertices and the edges of the two networks. Coupling of the full random walks, rather than their marginal distributions, ensures that NetOTC captures local and global information about the networks and preserves edges. NetOTC has no free parameters and does not rely on randomization. We investigate a number of theoretical properties of NetOTC and present experiments establishing its empirical performance.<\/jats:p>","DOI":"10.1093\/jrsssb\/qkae085","type":"journal-article","created":{"date-parts":[[2024,7,29]],"date-time":"2024-07-29T21:01:32Z","timestamp":1722286892000},"page":"186-210","source":"Crossref","is-referenced-by-count":1,"title":["Alignment and comparison of directed networks via transition couplings of random walks"],"prefix":"10.1093","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-8794-963X","authenticated-orcid":false,"given":"Bongsoo","family":"Yi","sequence":"first","affiliation":[{"name":"Department of Statistics and Operations Research, University of North Carolina at Chapel Hill , Chapel Hill, NC ,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kevin","family":"O\u2019Connor","sequence":"additional","affiliation":[{"name":"Department of Statistics and Operations Research, University of North Carolina at Chapel Hill , Chapel Hill, NC ,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9665-126X","authenticated-orcid":false,"given":"Kevin","family":"McGoff","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of North Carolina at Charlotte , Charlotte, NC ,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9973-9248","authenticated-orcid":false,"given":"Andrew B","family":"Nobel","sequence":"additional","affiliation":[{"name":"Department of Statistics and Operations Research, University of North Carolina at Chapel Hill , Chapel Hill, NC ,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2024,9,10]]},"reference":[{"key":"2025090920021790700_qkae085-B1","first-page":"1","article-title":"Community detection and stochastic block models: Recent developments","volume":"18","author":"Abbe","year":"2018","journal-title":"Journal of Machine Learning Research"},{"key":"2025090920021790700_qkae085-B2","author":"Abbe","year":"2015"},{"key":"2025090920021790700_qkae085-B3","author":"Babai","year":"2016"},{"key":"2025090920021790700_qkae085-B4","author":"Barak","year":"2019"},{"key":"2025090920021790700_qkae085-B5","author":"Barbe","year":"2020"},{"issue":"6","key":"2025090920021790700_qkae085-B6","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1162\/089976603321780317","article-title":"Laplacian eigenmaps for dimensionality reduction and data representation","volume":"15","author":"Belkin","year":"2003","journal-title":"Neural Computation"},{"key":"2025090920021790700_qkae085-B7","doi-asserted-by":"crossref","DOI":"10.1017\/9781108755528","volume-title":"Foundations of data science","author":"Blum","year":"2020"},{"key":"2025090920021790700_qkae085-B8","author":"Brug\u00e8re","year":"2024"},{"key":"2025090920021790700_qkae085-B9","author":"Chen","year":"2020"},{"key":"2025090920021790700_qkae085-B10","author":"Chen","year":"2022"},{"key":"2025090920021790700_qkae085-B11","author":"Chen","year":"2023"},{"key":"2025090920021790700_qkae085-B12","author":"Cho","year":"2010"},{"issue":"10","key":"2025090920021790700_qkae085-B13","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","article-title":"A (sub)graph isomorphism algorithm for matching large graphs","volume":"26","author":"Cordella","year":"2004","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2025090920021790700_qkae085-B14","author":"Cour","year":"2007"},{"key":"2025090920021790700_qkae085-B15","author":"Cullina","year":"2019"},{"issue":"1","key":"2025090920021790700_qkae085-B17","doi-asserted-by":"publisher","first-page":"121","DOI":"10.3934\/dcds.2006.15.121","article-title":"An introduction to joinings in ergodic theory","volume":"15","author":"De La Rue","year":"2006","journal-title":"Discrete and Continuous Dynamical Systems"},{"issue":"2","key":"2025090920021790700_qkae085-B16","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1021\/jm00106a046","article-title":"Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity","volume":"34","author":"Debnath","year":"1991","journal-title":"Journal of Medicinal Chemistry"},{"issue":"1-2","key":"2025090920021790700_qkae085-B18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s00440-020-00997-4","article-title":"Efficient random graph matching via degree profiles","volume":"179","author":"Ding","year":"2020","journal-title":"Probability Theory and Related Fields"},{"key":"2025090920021790700_qkae085-B19","author":"Dong","year":"2020"},{"issue":"3\u20134","key":"2025090920021790700_qkae085-B20","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF02834757","article-title":"The d\u00af-distance between two Markov processes cannot always be attained by a Markov joining","volume":"24","author":"Ellis","year":"1976","journal-title":"Israel Journal of Mathematics"},{"key":"2025090920021790700_qkae085-B21","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1090\/tran\/1978-241-00","article-title":"Distances between two-state Markov processes attainable by Markov joinings","volume":"241","author":"Ellis","year":"1978","journal-title":"Transactions of the American Mathematical Society"},{"key":"2025090920021790700_qkae085-B22","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1214\/aop\/1176994718","article-title":"Conditions for attaining d\u00af by a Markovian joining","volume":"8","author":"Ellis","year":"1980","journal-title":"The Annals of Probability"},{"issue":"2","key":"2025090920021790700_qkae085-B23","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1214\/aop\/1176994784","article-title":"On Kamae\u2019s conjecture concerning the d-distance between two-state Markov processes","volume":"8","author":"Ellis","year":"1980","journal-title":"The Annals of Probability"},{"issue":"4","key":"2025090920021790700_qkae085-B24","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1109\/TCBB.2015.2474391","article-title":"Global alignment of protein-protein interaction networks: A survey","volume":"13","author":"Elmsallati","year":"2016","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"2025090920021790700_qkae085-B25","author":"Engel","year":"2021"},{"key":"2025090920021790700_qkae085-B26","author":"Enqvist","year":"2009"},{"issue":"4","key":"2025090920021790700_qkae085-B27","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s00191-009-0160-x","article-title":"The evolution of the world trade web: A weighted-network analysis","volume":"20","author":"Fagiolo","year":"2010","journal-title":"Journal of Evolutionary Economics"},{"issue":"3","key":"2025090920021790700_qkae085-B28","doi-asserted-by":"publisher","first-page":"1182","DOI":"10.1109\/TNSE.6488902","article-title":"Spectral alignment of graphs","volume":"7","author":"Feizi","year":"2020","journal-title":"IEEE Transactions on Network Science and Engineering"},{"key":"2025090920021790700_qkae085-B29","volume-title":"Computers and intractability; A guide to the theory of NP-completeness","author":"Garey","year":"1990"},{"key":"2025090920021790700_qkae085-B30","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/101","volume-title":"Ergodic theory via joinings","author":"Glasner","year":"2003"},{"issue":"4","key":"2025090920021790700_qkae085-B31","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1109\/34.491619","article-title":"A graduated assignment algorithm for graph matching","volume":"18","author":"Gold","year":"1996","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2025090920021790700_qkae085-B32","author":"Grover","year":"2016"},{"key":"2025090920021790700_qkae085-B33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-031-01588-5","article-title":"Graph representation learning","volume":"14","author":"Hamilton","year":"2020","journal-title":"Synthesis Lectures on Artificial Intelligence and Machine Learning"},{"issue":"2","key":"2025090920021790700_qkae085-B34","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","article-title":"Stochastic blockmodels: First steps","volume":"5","author":"Holland","year":"1983","journal-title":"Social Networks"},{"key":"2025090920021790700_qkae085-B35","volume-title":"Dynamic programming and Markov processes","author":"Howard","year":"1960"},{"issue":"5","key":"2025090920021790700_qkae085-B36","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1111\/jomf.2014.76.issue-5","article-title":"A social network comparison of low-income black and white newlywed couples","volume":"76","author":"Jackson","year":"2014","journal-title":"Journal of Marriage and Family"},{"key":"2025090920021790700_qkae085-B37","author":"Jiang","year":"2017"},{"issue":"8","key":"2025090920021790700_qkae085-B38","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1089\/cmb.2009.0136","article-title":"Fast and accurate alignment of multiple protein networks","volume":"16","author":"Kalaev","year":"2008","journal-title":"Journal of Computational Biology : A Journal of Computational Molecular Cell Biology"},{"issue":"20","key":"2025090920021790700_qkae085-B39","doi-asserted-by":"publisher","first-page":"11394","DOI":"10.1073\/pnas.1534710100","article-title":"Conserved pathways within bacteria and yeast as revealed by global protein network alignment","volume":"100","author":"Kelley","year":"2003","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"key":"2025090920021790700_qkae085-B40","author":"Kersting","year":"2016"},{"issue":"S1","key":"2025090920021790700_qkae085-B41","doi-asserted-by":"publisher","first-page":"S59","DOI":"10.1186\/1471-2105-10-S1-S59","article-title":"A new graph-based method for pairwise global network alignment","volume":"10","author":"Klau","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2025090920021790700_qkae085-B42","author":"Korula","year":"2014"},{"key":"2025090920021790700_qkae085-B43","author":"Kriege","year":"2018"},{"issue":"50","key":"2025090920021790700_qkae085-B44","doi-asserted-by":"publisher","first-page":"1341","DOI":"10.1098\/rsif.2010.0063","article-title":"Topological network alignment uncovers biological function and phylogeny","volume":"7","author":"Kuchaiev","year":"2010","journal-title":"Journal of The Royal Society Interface"},{"issue":"10","key":"2025090920021790700_qkae085-B45","doi-asserted-by":"publisher","first-page":"1390","DOI":"10.1093\/bioinformatics\/btr127","article-title":"Integrative network alignment reveals large regions of global network similarity in yeast and human","volume":"27","author":"Kuchaiev","year":"2011","journal-title":"Bioinformatics"},{"issue":"3","key":"2025090920021790700_qkae085-B46","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1080\/07362994.2017.1422747","article-title":"Causal transport plans and their Monge-Kantorovich problems","volume":"36","author":"Lassalle","year":"2013","journal-title":"Stochastic Analysis and Applications"},{"issue":"1","key":"2025090920021790700_qkae085-B47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41109-019-0232-2","article-title":"A review of stochastic block models and extensions for graph clustering","volume":"4","author":"Lee","year":"2019","journal-title":"Applied Network Science"},{"key":"2025090920021790700_qkae085-B48","author":"Leordeanu","year":"2005"},{"key":"2025090920021790700_qkae085-B49","author":"Leordeanu","year":"2009"},{"key":"2025090920021790700_qkae085-B50","doi-asserted-by":"crossref","DOI":"10.1090\/mbk\/107","volume-title":"Markov chains and mixing times","author":"Levin","year":"2017"},{"key":"2025090920021790700_qkae085-B51","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511626302","volume-title":"An introduction to symbolic dynamics and coding","author":"Lind","year":"1995"},{"issue":"2","key":"2025090920021790700_qkae085-B52","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1016\/j.ejor.2005.09.032","article-title":"A survey of the quadratic assignment problem","volume":"176","author":"Loiola","year":"2007","journal-title":"European Journal of Operational Research"},{"key":"2025090920021790700_qkae085-B53","first-page":"3513","article-title":"Seeded graph matching for correlated Erd\u00f6s-R\u00e9nyi graphs","volume":"15","author":"Lyzinski","year":"2014","journal-title":"Journal of Machine Learning Research"},{"key":"2025090920021790700_qkae085-B54","doi-asserted-by":"publisher","first-page":"2647","DOI":"10.1016\/j.csbj.2020.09.011","article-title":"A review of protein\u2013protein interaction network alignment: From pathway comparison to global alignment","volume":"18","author":"Ma","year":"2020","journal-title":"Computational and Structural Biotechnology Journal"},{"key":"2025090920021790700_qkae085-B55","author":"Maretic","year":"2019"},{"key":"2025090920021790700_qkae085-B56","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1109\/TSIPN.2022.3169632","article-title":"Wasserstein-based graph alignment","volume":"8","author":"Maretic","year":"2022","journal-title":"IEEE Transactions on Signal and Information Processing over Networks"},{"key":"2025090920021790700_qkae085-B57","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","article-title":"Practical graph isomorphism, ii","volume":"60","author":"McKay","year":"2014","journal-title":"Journal of Symbolic Computation"},{"issue":"4","key":"2025090920021790700_qkae085-B58","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s10208-011-9093-5","article-title":"Gromov\u2013Wasserstein distances and the metric approach to object matching","volume":"11","author":"M\u00e9moli","year":"2011","journal-title":"Foundations of Computational Mathematics"},{"issue":"S6","key":"2025090920021790700_qkae085-B59","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1186\/s12859-017-1635-7","article-title":"An extensive assessment of network alignment algorithms for comparison of brain connectomes","volume":"18","author":"Milano","year":"2017","journal-title":"BMC Bioinformatics"},{"key":"2025090920021790700_qkae085-B60","author":"Mislove","year":"2007"},{"key":"2025090920021790700_qkae085-B61","first-page":"1","article-title":"Optimal transport for stationary Markov chains via policy iteration","volume":"23","author":"O\u2019Connor","year":"2022","journal-title":"Journal of Machine Learning Research"},{"issue":"2","key":"2025090920021790700_qkae085-B62","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iaae006","article-title":"Estimation of stationary optimal transport plans","volume":"13","author":"O\u2019Connor","year":"2024","journal-title":"Information and Inference: A Journal of the IMA"},{"key":"2025090920021790700_qkae085-B63","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1214\/aop\/1176997024","article-title":"An application of ergodic theory to probability theory","volume":"1","author":"Ornstein","year":"1973","journal-title":"The Annals of Probability"},{"key":"2025090920021790700_qkae085-B64","author":"Perozzi","year":"2014"},{"key":"2025090920021790700_qkae085-B65","doi-asserted-by":"crossref","DOI":"10.1561\/9781680835519","volume-title":"Computational optimal transport","author":"Peyr\u00e9","year":"2019"},{"key":"2025090920021790700_qkae085-B66","author":"Peyr\u00e9","year":"2016"},{"issue":"7\u20138","key":"2025090920021790700_qkae085-B67","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1016\/j.disc.2005.11.059","article-title":"Graph factors and factorization: 1985\u20132003: A survey","volume":"307","author":"Plummer","year":"2007","journal-title":"Discrete Mathematics"},{"key":"2025090920021790700_qkae085-B68","author":"Riesen","year":"2008"},{"key":"2025090920021790700_qkae085-B69","author":"Schellewald","year":"2005"},{"issue":"35","key":"2025090920021790700_qkae085-B70","doi-asserted-by":"publisher","first-page":"12763","DOI":"10.1073\/pnas.0806627105","article-title":"Global alignment of multiple protein interaction networks with application to functional orthology detection","volume":"105","author":"Singh","year":"2008","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2025090920021790700_qkae085-B71","author":"Song","year":"2016"},{"issue":"6","key":"2025090920021790700_qkae085-B72","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.1021\/ci034143r","article-title":"Spline-fitting with a genetic algorithm: A method for developing classification structure- activity relationships","volume":"43","author":"Sutherland","year":"2003","journal-title":"Journal of Chemical Information and Computer Sciences"},{"key":"2025090920021790700_qkae085-B73","author":"Titouan","year":"2019"},{"key":"2025090920021790700_qkae085-B74","author":"Toivonen","year":"2011"},{"key":"2025090920021790700_qkae085-B75","volume-title":"Solving Markov random fields using semi definite programming","author":"Torr","year":"2003"},{"issue":"11","key":"2025090920021790700_qkae085-B76","doi-asserted-by":"publisher","first-page":"1526","DOI":"10.1109\/TPAMI.2004.95","article-title":"A POCS-based graph matching algorithm","volume":"26","author":"van Wyk","year":"2004","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"9","key":"2025090920021790700_qkae085-B77","doi-asserted-by":"publisher","first-page":"212","DOI":"10.3390\/a13090212","article-title":"Fused Gromov-Wasserstein distance for structured objects","volume":"13","author":"Vayer","year":"2020","journal-title":"Algorithms"},{"key":"2025090920021790700_qkae085-B78","author":"Vayer","year":"2019"},{"key":"2025090920021790700_qkae085-B79","volume-title":"Optimal transport: Old and new","author":"Villani","year":"2008"},{"key":"2025090920021790700_qkae085-B80","first-page":"1201","article-title":"Graph kernels","volume":"11","author":"Vishwanathan","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"2025090920021790700_qkae085-B81","author":"Xu","year":"2019"},{"key":"2025090920021790700_qkae085-B82","author":"Xu","year":"2019"},{"key":"2025090920021790700_qkae085-B83","doi-asserted-by":"publisher","author":"Yan","year":"2016","DOI":"10.1145\/2911996.2912035"},{"key":"2025090920021790700_qkae085-B84","author":"Yan","year":"2008"},{"key":"2025090920021790700_qkae085-B85","author":"Yartseva","year":"2013"},{"key":"2025090920021790700_qkae085-B86","author":"Yu","year":"2018"},{"issue":"4","key":"2025090920021790700_qkae085-B87","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1016\/j.neuroimage.2010.06.041","article-title":"Network-based statistic: Identifying differences in brain networks","volume":"53","author":"Zalesky","year":"2010","journal-title":"Neuroimage"},{"issue":"12","key":"2025090920021790700_qkae085-B88","doi-asserted-by":"publisher","first-page":"2227","DOI":"10.1109\/TPAMI.2008.245","article-title":"A path following algorithm for the graph matching problem","volume":"31","author":"Zaslavskiy","year":"2009","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"2","key":"2025090920021790700_qkae085-B89","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s101140000049","article-title":"Existence and application of optimal Markovian coupling with respect to non-negative lower semi-continuous functions","volume":"16","author":"Zhang","year":"2000","journal-title":"Acta Mathematica Sinica"},{"issue":"9","key":"2025090920021790700_qkae085-B90","doi-asserted-by":"publisher","first-page":"1774","DOI":"10.1109\/TPAMI.2015.2501802","article-title":"Factorized graph matching","volume":"38","author":"Zhou","year":"2016","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/87\/1\/186\/59075278\/qkae085.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/87\/1\/186\/59075278\/qkae085.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T00:02:26Z","timestamp":1757462546000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/87\/1\/186\/7754547"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,10]]},"references-count":90,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,9,10]]},"published-print":{"date-parts":[[2025,2,10]]}},"URL":"https:\/\/doi.org\/10.1093\/jrsssb\/qkae085","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,2]]},"published":{"date-parts":[[2024,9,10]]}}}