Optimal graph joining with applications to isomorphism detection and identification
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908663274274816 |
|---|---|
| author | Hoàng, Phuong N. McGoff, Kevin Nobel, Andrew B. Xiang, Yang Yi, Bongsoo |
| author_facet | Hoàng, Phuong N. McGoff, Kevin Nobel, Andrew B. Xiang, Yang Yi, Bongsoo |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14862 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal graph joining with applications to isomorphism detection and identification Hoàng, Phuong N. McGoff, Kevin Nobel, Andrew B. Xiang, Yang Yi, Bongsoo Combinatorics Optimization and Control Probability 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$. |
| title | Optimal graph joining with applications to isomorphism detection and identification |
| topic | Combinatorics Optimization and Control Probability |
| url | https://arxiv.org/abs/2511.14862 |