nucleation

LIT-1813: Optimal Transport for structured data with application on graphs

1 min read

Properties5
StatusActive — read in full 2026-10-29 (NOTE-1328), from arXiv v3; worth reading for the metric and interpolation theorems of fused Gromov–Wasserstein, from which it follows that anchors as features break exactly the structural symmetries that move them.
Version2
Tagsmathematics, network-science, anthology-candidate
Cited as “paper” byNOTE-1328 — Vayer et al. — Fused Gromov–Wasserstein
Cited as “source” byTHEORY-1129 — Anchors entered as node features in fused Gromov–Wasserstein break a structural tie only when they move under it: with α strictly between 0 and 1, the zero-cost matchings of a structure with itself are exactly its automorphisms that fix every anchor, so a 6-cycle has 12 with no anchor, 2 with one anchor, 1 with two adjacent anchors and still 2 with two antipodal ones, and whether a set of anchors identifies the correspondence can be decided from the structure before any fit, THEORY-1156 — The fused Gromov–Wasserstein discrepancy between two attributed graphs, a single coupling that pays (1 − α) for moving node features and α for distorting pairwise structure, tends to the Wasserstein distance between the features as α → 0 and to the Gromov–Wasserstein distance between the structures as α → 1, lies above their α-weighted mixture, and for q = 1, α strictly between 0 and 1 and distance-matrix structures is a metric that vanishes exactly when a bijection of the nodes preserves weights, features and structure together

Graph View

Vayer, T., Chapel, L., Flamary, R., Tavenard, R., & Courty, N. (2019). Optimal transport for structured data with application on graphs. ICML 2019, PMLR 97, 6275–6284.

Why this is here

A6 thought it “probably the most practical model for CASE-055”: independently validated anchor matches break the symmetries pure GW cannot, and the weight between structure and anchors is a scientific parameter to vary, not a hyperparameter to tune. An arm of CASE-185.

The reading (NOTE-1328) confirms the first point with a condition: anchors break a symmetry only if it moves them, so anchors placed on an axis of symmetry leave the tie (THEORY-1129). The paper itself treats α as a cross-validated hyperparameter and proves only its endpoint limits; the exact FGW value is concave in α, which suits reading α as a parameter to vary.

Backlinks