Optimal Graph Joining with Applications to Isomorphism Detection and Identification
Phuong N. Hoàng* and Kevin McGoff and Andrew B. Nobel and Yang Xiang and Bongsoo Yi · 2025
Read Optimal Graph Joining with Applications to Isomorphism Detection and Identification by Phuong N. Hoàng* and Kevin McGoff and Andrew B. Nobel and Yang Xiang and Bongsoo Yi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14862.txt.
Introduction
Phuong N. Hoàng, Kevin McGoff, and three co-authors propose a transport-based way to compare networks. Their joining of two graphs glues them into one product graph that keeps each graph's degree structure intact. The cheapest joining, under a cost for matching vertex labels, gives a distance-like score between the two networks.
That best joining problem turns out to be a linear program with a well-shaped solution set. The authors prove basic properties and tie the problem to the famous graph isomorphism question, working out when families of graphs can be told apart this way. The method offers a principled tool for fingerprinting networks in chemistry, biology, and security.
Catalog record
| CREATOR | Phuong N. Hoàng* and Kevin McGoff and Andrew B. Nobel and Yang Xiang and Bongsoo Yi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 172 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-14862