{"ID":2840207,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.14862","arxiv_id":"2511.14862","title":"Optimal graph joining with applications to isomorphism detection and identification","abstract":"We introduce an optimal transport based approach for comparing undirected graphs with non-negative edge weights and general vertex labels, and we study connections between the resulting linear program and the graph isomorphism problem. Our approach is based on the notion of a joining of two graphs $G$ and $H$, which is a product graph that preserves their marginal structure. Given $G$ and $H$ and a vertex-based cost function $c$, the optimal graph joining (OGJ) problem finds a joining of $G$ and $H$ minimizing degree weighted cost. The OGJ problem can be written as a linear program with a convex polyhedral solution set. We establish several basic properties of the OGJ problem, and present theoretical results connecting the OGJ problem to the graph isomorphism problem. In particular, we examine a variety of conditions on graph families that are sufficient to ensure that for every pair of graphs $G$ and $H$ in the family (i) $G$ and $H$ are isomorphic if and only if their optimal joining cost is zero, and (ii) if $G$ and $H$ are isomorphic, the the extreme points of the solution set of the OGJ problem are deterministic joinings corresponding to the isomorphisms from $G$ to $H$.","short_abstract":"We introduce an optimal transport based approach for comparing undirected graphs with non-negative edge weights and general vertex labels, and we study connections between the resulting linear program and the graph isomorphism problem. Our approach is based on the notion of a joining of two graphs $G$ and $H$, which is...","url_abs":"https://arxiv.org/abs/2511.14862","url_pdf":"https://arxiv.org/pdf/2511.14862v1","authors":"[\"Phuong N. Hoàng\",\"Kevin McGoff\",\"Andrew B. Nobel\",\"Yang Xiang\",\"Bongsoo Yi\"]","published":"2025-11-18T19:21:25Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"math.OC\",\"math.PR\"]","methods":"[]","has_code":false}