nucleation

LIT-1822: The Gromov–Wasserstein distance between networks and stable network invariants

1 min read

Properties5
StatusActive — read in full 2026-10-29 (NOTE-1330), from the arXiv v2; worth reading as the clean statement of what a Gromov–Wasserstein comparison of directed weighted networks can and cannot see: it is a pseudometric on any bounded weights, zero exactly at weak isomorphism, and its cheap invariants are lower bounds that can all vanish for networks apart.
Version2
Tagsnetwork-science, mathematics
Cited as “paper” byNOTE-1330 — Chowdhury & Mémoli — Network Gromov–Wasserstein
Cited as “source” byTHEORY-1130 — The Gromov–Wasserstein distance, half the least Lp distortion of a coupling, is a pseudometric on all networks with a probability measure on the nodes and any bounded edge weights, symmetric or not, and it is zero exactly when the two networks are weakly isomorphic, images of one network under maps that preserve weights and measures; so it compares only what the weight function and node measure record, THEORY-1152 — Between two weighted directed networks with node measures, the Gromov–Wasserstein distance is bounded below by a hierarchy of invariants, each in an in-going and an out-going version, and the strongest of them, a transport problem whose costs are themselves transport problems, equals a transport problem whose costs are one-dimensional Wasserstein distances between the nodes' weight profiles, so it is computed in closed form; the bounds are one-sided, and two networks can agree on all of them while being at positive distance

Graph View

Chowdhury, S., & Mémoli, F. (2019). The Gromov–Wasserstein distance between networks and stable network invariants. Information and Inference, 8(4), 757–787.

Read in full in NOTE-1330.

Key takeaways

  • The distance is defined for any bounded weights; its metric properties come from couplings, not from the networks (THEORY-1130).
  • Zero distance means weak isomorphism of the recorded weights and node measures, nothing about what the record omits; missing weights must be imputed first, and the node measure is the user’s.
  • The cheap invariants are lower bounds only (THEORY-1152); networks can agree on all of them and be apart.

Why this is here

A7: influence, authority and obligation are directed, so their comparison needs a directed distance. Its sharper use is CLAIM-448’s: two recorded networks can align well while the organizations behind them differ, because a legibility regime decides what enters the record (CASE-124).

The reading supports both uses. The paper supplies the directed distance, with in- and out-going invariants. For CLAIM-448, Theorem 18 states exactly what the distance is blind to, and the paper’s own experiments use a lower bound whose agreement is weaker evidence still (NOTE-1330).

Backlinks