{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T03:00:13Z","timestamp":1768014013209,"version":"3.49.0"},"reference-count":137,"publisher":"SAGE Publications","issue":"3-4","license":[{"start":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T00:00:00Z","timestamp":1680652800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"name":"United States National Science Foundation","award":["Grant #1900888 and Grant #1900765"],"award-info":[{"award-number":["Grant #1900888 and Grant #1900765"]}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p> The convergence of extremely high levels of hardware concurrency and the effective overlap of computation and communication in asynchronous executions has resulted in increasing nondeterminism in High-Performance Computing (HPC) applications. Nondeterminism can manifest at multiple levels: from low-level communication primitives to libraries to application-level functions. No matter its source, nondeterminism can drastically increase the cost of result reproducibility, debugging workflows, testing parallel programs, or ensuring fault-tolerance. Nondeterministic executions of HPC applications can be modeled as event graphs, and the applications\u2019 nondeterministic behavior can be understood and, in some cases, mitigated using graph comparison algorithms. However, a connection between graph comparison algorithms and approaches to understanding nondeterminism in HPC still needs to be established. This survey article moves the first steps toward establishing a connection between graph comparison algorithms and nondeterminism in HPC with its three contributions: it provides a survey of different graph comparison algorithms and a timeline for each category\u2019s significant works; it discusses how existing graph comparison methods do not fully support properties needed to understand nondeterministic patterns in HPC applications; and it presents the open challenges that should be addressed to leverage the power of graph comparisons for the study of nondeterminism in HPC applications. <\/jats:p>","DOI":"10.1177\/10943420231166610","type":"journal-article","created":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T15:58:11Z","timestamp":1680710291000},"page":"306-327","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Survey of Graph Comparison Methods with Applications to Nondeterminism in High-Performance Computing"],"prefix":"10.1177","volume":"37","author":[{"given":"Sanjukta","family":"Bhowmick","sequence":"first","affiliation":[{"name":"University of Northern Texas, Denton, TX, USA"}]},{"given":"Patrick","family":"Bell","sequence":"additional","affiliation":[{"name":"University of Tennessee Knoxville College of Engineering, Knoxville, TN, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0031-6377","authenticated-orcid":false,"given":"Michela","family":"Taufer","sequence":"additional","affiliation":[{"name":"University of Tennessee Knoxville College of Engineering, Knoxville, TN, USA"}]}],"member":"179","published-online":{"date-parts":[[2023,4,5]]},"reference":[{"key":"bibr1-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2016.60"},{"key":"bibr2-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2020.106715"},{"key":"bibr3-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/2532352.2532357"},{"key":"bibr4-10943420231166610","doi-asserted-by":"publisher","DOI":"10.5936\/csbj.201302004"},{"key":"bibr5-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu447"},{"key":"bibr6-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180216"},{"key":"bibr7-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt713"},{"key":"bibr8-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-19212-9_2"},{"key":"bibr9-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363957"},{"key":"bibr10-10943420231166610","unstructured":"Babai L (1979) Monte-Carlo algorithms in graph isomorphism testing. Universit\u00e9 Tde Montr\u00e9al Technical Report. DMS (79-10)."},{"key":"bibr11-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"bibr12-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpa.2021.100151"},{"key":"bibr13-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3548607"},{"key":"bibr14-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975321.38"},{"key":"bibr15-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68942-3_9"},{"key":"bibr16-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1155\/2012\/713587"},{"key":"bibr17-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-S7-S13"},{"key":"bibr18-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1561\/2200000076"},{"key":"bibr19-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.132"},{"key":"bibr20-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.281"},{"key":"bibr21-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3439724"},{"key":"bibr22-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxr071"},{"key":"bibr23-10943420231166610","volume-title":"A Heuristic for Reducing Fill-In in Sparse Matrix Factorization","author":"Bui TN","year":"1993"},{"key":"bibr24-10943420231166610","doi-asserted-by":"crossref","unstructured":"Bulu\u00e7 A, Meyerhenke H, Safro I, et al. (2016) Recent Advances in Graph Partitioning. Springer International Publishing, pp. 117\u2013158.","DOI":"10.1007\/978-3-319-49487-6_4"},{"key":"bibr25-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2015.34"},{"issue":"1","key":"bibr26-10943420231166610","volume":"5","author":"Chapp D","year":"2018","journal-title":"Supercomputing Frontiers and Innovations"},{"key":"bibr27-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3081530"},{"key":"bibr28-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539100"},{"key":"bibr29-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412136"},{"key":"bibr30-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132904"},{"key":"bibr31-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3126908.3126936"},{"key":"bibr32-10943420231166610","volume-title":"Proceedings of the 4th Workshop on Determinism and Correctness in Parallel Programming (WoDet)","author":"Chiang WF","year":"2013"},{"key":"bibr33-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0038107"},{"key":"bibr34-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"bibr35-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"bibr36-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.05.001"},{"key":"bibr37-10943420231166610","volume-title":"Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining","author":"Dehaspe L","year":"1998"},{"key":"bibr38-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482418"},{"key":"bibr39-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2018.2808529"},{"key":"bibr40-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24855-9_20"},{"key":"bibr41-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1142\/9789812777638_0014"},{"key":"bibr42-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78839-3_19"},{"key":"bibr43-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1101\/gr.5235706"},{"key":"bibr44-10943420231166610","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner T, Flach P, Wrobel S (2003) On graph kernels: Hardness results and efficient alternatives. Learning Theory and Kernel Machines. Springer, pp. 129\u2013143.","DOI":"10.1007\/978-3-540-45167-9_11"},{"key":"bibr45-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144504444711"},{"key":"bibr46-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461800"},{"key":"bibr47-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/1866210.1866211"},{"key":"bibr48-10943420231166610","doi-asserted-by":"crossref","unstructured":"Gopalakrishnan G, Hovland PD, Iancu C, et al. (2017) Report of the HPC Correctness Summit, 2017, Washington, DC. CoRR abs\/1705. 07478.","DOI":"10.2172\/1470989"},{"key":"bibr49-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3372123"},{"issue":"3","key":"bibr50-10943420231166610","first-page":"472","volume":"19","author":"Guzzi PH","year":"2018","journal-title":"Briefings in Bioinformatics"},{"key":"bibr51-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091085"},{"key":"bibr52-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271788"},{"key":"bibr53-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3520484"},{"key":"bibr54-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.30"},{"key":"bibr55-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803896"},{"key":"bibr56-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/2464576.2464600"},{"key":"bibr57-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45372-5_2"},{"key":"bibr58-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/31.1743"},{"key":"bibr59-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888912000331"},{"key":"bibr60-10943420231166610","first-page":"694","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Johansson F","year":"2014"},{"key":"bibr61-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091052"},{"key":"bibr62-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btm630"},{"key":"bibr63-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"bibr64-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkh411"},{"key":"bibr65-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.8"},{"key":"bibr66-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1137\/13090729X"},{"key":"bibr67-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.152"},{"key":"bibr68-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.18"},{"key":"bibr69-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1992.222990"},{"key":"bibr70-10943420231166610","volume-title":"Event Graph Analysis for Debugging Massively Parallel Programs","author":"Kranzlm\u00fcller D","year":"2000"},{"key":"bibr71-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1007\/s41109-019-0195-3"},{"key":"bibr72-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2010.0063"},{"key":"bibr73-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487592"},{"key":"bibr74-10943420231166610","unstructured":"Liu L, Cheung WK, Li X, et al. (2016) Aligning users across social networks using network embedding Ijcai, pp. 1774\u20131780."},{"key":"bibr75-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_21"},{"key":"bibr76-10943420231166610","volume-title":"Neural Subgraph Matching","author":"Lou Z","year":"2020"},{"key":"bibr77-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"bibr78-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"bibr79-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.39"},{"key":"bibr80-10943420231166610","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9486.003.0010"},{"key":"bibr81-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1016\/j.csbj.2020.09.011"},{"key":"bibr82-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2020.2985838"},{"key":"bibr83-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1038\/srep04547"},{"key":"bibr84-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359633"},{"key":"bibr85-10943420231166610","volume-title":"Practical Graph Isomorphism","author":"McKay BD","year":"1981"},{"key":"bibr86-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"bibr87-10943420231166610","volume-title":"IGLOO: Integrating Global and Local Biological Network Alignment","author":"Meng L","year":"2016"},{"key":"bibr88-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btw348"},{"key":"bibr89-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1142\/S0219525915500046"},{"key":"bibr90-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654096"},{"key":"bibr91-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1021\/c160017a018"},{"key":"bibr92-10943420231166610","volume-title":"VELOC: VEry Low Overhead Checkpointing in the Age of Exascale","author":"Nicolae B","year":"2021"},{"key":"bibr93-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1007\/s13174-010-0003-x"},{"key":"bibr94-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629593"},{"key":"bibr95-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851179"},{"key":"bibr96-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/2925426.2926264"},{"key":"bibr97-10943420231166610","doi-asserted-by":"publisher","DOI":"10.3390\/app8020230"},{"key":"bibr98-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411924"},{"key":"bibr99-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2019.2892959"},{"key":"bibr100-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2019.00162"},{"key":"bibr101-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00024"},{"key":"bibr102-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0067995"},{"key":"bibr103-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1983.6313167"},{"key":"bibr104-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1038\/srep35098"},{"key":"bibr105-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807642"},{"key":"bibr106-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018767"},{"key":"bibr107-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2011.62"},{"issue":"9","key":"bibr108-10943420231166610","volume":"12","author":"Shervashidze N","year":"2011","journal-title":"Journal of Machine Learning Research"},{"key":"bibr109-10943420231166610","first-page":"488","volume-title":"Artificial Intelligence and Statistics","author":"Shervashidze N","year":"2009"},{"key":"bibr110-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00104"},{"key":"bibr111-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2013.30"},{"key":"bibr112-10943420231166610","first-page":"1639","volume":"28","author":"Sugiyama M","year":"2015","journal-title":"Advances in Neural Information Processing Systems"},{"key":"bibr113-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v28i1.8720"},{"key":"bibr114-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1155\/2013\/670623"},{"key":"bibr115-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"bibr116-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04921-1_4"},{"key":"bibr117-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx246"},{"key":"bibr118-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3388440.3414205"},{"key":"bibr119-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv161"},{"key":"bibr120-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1016\/0893-6080(88)90016-0"},{"key":"bibr121-10943420231166610","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D18-1032"},{"issue":"9","key":"bibr122-10943420231166610","first-page":"12","volume":"2","author":"Weisfeiler B","year":"1968","journal-title":"Nauchno-Technicheskaya Informatsia"},{"key":"bibr123-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2972-8_4"},{"key":"bibr124-10943420231166610","volume-title":"Structural Simulation Toolkit (SST) DUMPI Trace Library","author":"Wilke J"},{"key":"bibr125-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.03.011"},{"key":"bibr126-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091043"},{"key":"bibr127-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476214"},{"key":"bibr128-10943420231166610","unstructured":"Xu L, Wang W, Alvarez M, et al. (2014) Parallelization of shortest path graph kernels on multi-core cpus and gpus. In: Proceedings of the Programmability Issues for Heterogeneous Multicores (MultiProg)."},{"key":"bibr129-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/1504176.1504213"},{"key":"bibr130-10943420231166610","first-page":"721","volume-title":"Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM)","author":"Yan X","year":"2002"},{"key":"bibr131-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783417"},{"key":"bibr132-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.114"},{"key":"bibr133-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939766"},{"key":"bibr134-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313484"},{"key":"bibr135-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.160"},{"key":"bibr136-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.67"},{"key":"bibr137-10943420231166610","doi-asserted-by":"publisher","DOI":"10.1145\/1830252.1830274"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/10943420231166610","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/10943420231166610","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/10943420231166610","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T19:42:03Z","timestamp":1740858123000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/10943420231166610"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,5]]},"references-count":137,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.1177\/10943420231166610"],"URL":"https:\/\/doi.org\/10.1177\/10943420231166610","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,5]]}}}