PaperlayerView exact revision on arXiv

Source-linked AI summary

The Gromov-Wasserstein distance between networks and stable network invariants

Samir Chowdhury, Facundo Mémoli

arXiv:1808.04337v2cs.DMmath.MG

TL;DR

Comparing directed, weighted networks calls for a distance that accommodates asymmetry and node significance. The paper develops a network Gromov–Wasserstein distance and optimal-transport invariants that lower-bound it; its lower-bound theory includes a real-line formulation with closed-form solutions. The framework is illustrated on simulated networks and real bilateral migration data.

  • Problem

    The paper addresses how to compare directed, weighted networks, including data that are asymmetric and may have significant substructures or outliers.

    Source: §1.1 · p. 2

  • Method

    The paper defines a network Gromov–Wasserstein distance and develops optimal-transport network invariants that yield lower bounds, with the TLB computed via real-line optimal transport.

    Source: §1.2 · p. 3, §3 · p. 10, §3.1 · p. 12

  • Results

    The TLB equals its real-line version, so the relevant optimal-transport problems have closed-form solutions; the network invariants provide readily computable lower bounds on the distance.

    Source: §3.1 · p. 12, §5 · p. 20

  • Takeaways & Limitations

    The paper illustrates its constructions on simulated networks and real global bilateral migration data, whose patterns suggest migration changes over time within each gender.

    Source: §4.2 · p. 17, §4.5 · p. 19

    Real-world network datasets may have incomplete edge weights and require preprocessing to fit the framework.

    Source: §2.1 · p. 4

Abstract

from arXiv · show

We define a metric---the network Gromov-Wasserstein distance---on weighted, directed networks that is sensitive to the presence of outliers. In addition to proving its theoretical properties, we supply network invariants based on optimal transport that approximate this distance by means of lower bounds. We test these methods on a range of simulated network datasets and on a dataset of real-world global bilateral migration. For our simulations, we define a network generative model based on the stochastic block model. This may be of independent interest for benchmarking purposes.

1 Introduction

The paper targets comparison of directed, weighted networks by aligning weighted edges while accounting for node significance, including asymmetric data that need not be metric spaces. It develops a network Gromov–Wasserstein framework and stable optimal-transport invariants, then illustrates them on simulated and real networks.

1.1 Motivation and related literature

  • The comparison problem seeks an alignment of weighted edges while simultaneously matching nodes with similar significance, addressing directed and weighted networks that may be asymmetric.Optimal transport uses a probability measure that users can adjust to emphasize relevant substructures and smooth out outliers.Source: §1.1 · pp. 2–3
  • The paper treats networks that need not be metric spaces, extending earlier work on arbitrary matrices from finite networks to a continuous setting.It presents itself as a theoretical complement to.Source: §1.1 · p. 3

1.2 Contributions

  • The framework extends network Gromov–Wasserstein theory to Polish spaces with measurable integrable weights, and its network invariants provide lower bounds computable with at most linear programming.The experiments focus particularly on the Third Lower Bound (TLB).Source: §1.2 · p. 3
  • Strengthened lower-bound inequalities make the TLB computable through optimal-transport problems over R with closed-form solutions.The paper also defines a network Gromov–Prokhorov distance and sublevel/superlevel size functions, which satisfy interleaving stability and distinguish spheres of different dimensions.Source: §1.2 · pp. 3–4

1.3 Organization of the paper

  • The introduction also outlines the paper’s organization and notation, with distances in §2, invariants and stability in §3, and experiments in §4.The experiments illustrate the constructions on simulated and real highly asymmetric networks.Source: §1.3 · p. 4, §1.2 · p. 4

2 The structure of measure networks

This section develops transport-based distances for measure networks, including their pseudometric properties and related interval and Gromov–Prokhorov constructions. It examines the Gromov–Prokhorov triangle inequality via glued couplings and introduces a lemma relating the Gromov–Prokhorov and Gromov–Wasserstein distances.

2.1 Networks and isomorphism

  • A measure network is a Polish space with a fully supported probability measure and bounded measurable edge weights; finite cases are directed weighted graphs with node significance values.Strong isomorphism preserves edge weights under a Borel bijection, while weak isomorphism uses compatible maps from a common probability space.Source: §2.1 · pp. 4–5
  • Real-world networks with undefined edge weights require preprocessing to fit the framework, although some networks are complete by construction.Gene regulatory networks inferred from gene expression are given as an example of complete-by-construction edge weights.Source: §2.1 · p. 4

2.2 Couplings and the distortion functional

  • A coupling has the networks’ measures as marginals, and its distortion measures the p-norm discrepancy between their edge weights under paired samples.The distance is defined by minimizing this distortion over all couplings.Source: §2.2 · p. 6, §2.1 · p. 6

2.3 Optimality of couplings in the network setting

  • For every p ∈ [1, ∞], an optimal coupling minimizing the distortion exists between any two measure networks.For finite p, distortion is continuous on the coupling set; for p = ∞, it is lower semicontinuous.Source: §2.3 · pp. 7–8

2.4 The network Gromov-Wasserstein distance

  • For each p ∈ [1, ∞], dN,p is a pseudometric on N; for networks X and Y in N, dN,p(X,Y) = 0 if and only if X ∼=w Y.Source: §2.4 · pp. 8–9

2.5 Additional constructions

  • The section introduces an alternative network distance modeled on Gromov–Prokhorov distance, which provides lower bounds on dN,∞ between spheres.It also connects the framework to parametrizations and Gromov’s box distance.Source: §2.5 · p. 9

2.5.1 Interval representation

  • Parametrizing a network on [0, 1] preserves its weak-isomorphism class and represents it as a measurable integrable function on the unit square; normalized centered weights yield a graphon.This representation also permits a network version of Gromov’s box distance, though computing it involves difficult combinatorial problems.Source: §2.5.1 · p. 9

2.5.2 The network Gromov-Prokhorov distance

  • The network Gromov–Prokhorov distance is stated to be a pseudometric on the collection of measure networks.Its definition uses a coupling-based comparison of edge weights.Source: §2.5.2 · p. 10
  • The triangle-inequality argument glues couplings and shows that a violation set for X and Z is contained in the union of the X–Y and Y–Z violation sets.This containment bounds the measure of the X–Z violation set by the sum of the other two.Source: §2.5.2 · p. 10
  • Lemma 21 is introduced as stating a relation between the Gromov-Prokhorov and Gromov-Wasserstein distances, but its statement is not supplied.The passage says the lemma follows by unpacking the definitions of the two distances.Source: §2.5.2 · p. 10

3 Invariants and lower bounds

This section develops stable invariants and sphere-profile constructions that give lower bounds on network distances, and applies them to comparisons between spheres, including a stronger bound for one pair.

3.1 A hierarchy of lower bounds for dN,p

  • The size_p invariant compresses a network to one real number, is exactly and cheaply computable, and provides a quantitatively stable coarse first comparison.Source: §3.1 · pp. 11–12
  • The FLB, SLB, and TLB bounds equal their real-line pushforwards, with TLB computation reducible to a closed-form one-dimensional optimal-transport problem.Source: §3.1 · p. 12
  • The FLB and TLB arise as Lipschitz-stability bounds for invariants encoding distributions of node eccentricities and distributions of neighborhood profiles.Source: §3.1 · pp. 11–12

3.2 Interleaving stable invariants

  • The sublevel-size function is a network invariant with interleaving stability.Source: §3.2 · pp. 14–15
  • Although size1 cannot distinguish spheres, the full t-indexed subSize1,t functions do, as shown by explicit sphere formulas.Source: §3.2 · p. 14

3.2.1 Lower bounds for spheres

  • The authors apply Theorem 32 to derive lower bounds on d_GPN,0(Sn, Sm), whose explicit value was unknown even for S1 and S2.Source: §3.2.1 · p. 15
  • For spheres, profiles fp(t) = subSizep,t(Sn) and gp(t) = subSizep,t(Sm) give dN,0(Sn, Sm) ≥ dI(fp, gp).The profiles are defined for t ∈ [0, π].Source: §3.2.1 · pp. 15–16
  • Setting h ≡ 0 identifies dI(fp, h) and dI(gp, h) with the respective sizep values, yielding a sizep bound; other h choices can improve it.Specifically, the passage gives dI(fp, h) = sizep(Sn) and dI(gp, h) = sizep(Sm).Source: §3.2.1 · p. 16
  • The explicit formula of Proposition 31 is used to computationally obtain lower bounds.The passage also begins describing Matlab simulations, but supplies no complete simulation result.Source: §3.2.1 · p. 16
  • dN,∞(S1, S2) ≥ 0.17, versus the prior [M´em11, Remark 5.16] bound dN,2(S1, S2) ≥ 0.0503, a threefold improvement.The comparison uses dN,∞ ≥ dN,2 to carry the prior bound over to dN,∞.Source: §3.2.1 · p. 16

4 Experiments

The experiments apply (R-TLB) to simulated stochastic block model (SBM) networks and real migration networks. The comparisons illustrate how it reflects community structure, edge weights, and temporal and gender patterns, while the network SBM supplies a generative model for testing.

4.1 Computational aspects

  • For asymmetric networks of several hundred nodes, (R-TLB) is computable exactly in under a minute, though computing the real-line OT problems remains the bottleneck.The paper reports ERGW as orders of magnitude faster in comparable demonstrations, but notes its numerical infeasibility issues.Source: §4.1 · p. 16

4.2 The network stochastic block model

  • The proposed network SBM composes Gaussian distributions to generate random networks and can be adapted to other distributions.The experiments use this model to create networks with controlled community structure and edge-weight patterns.Source: §4.2 · p. 17, §4.3 · p. 18, §4.4 · p. 18

4.3 Experiment: SBMs from cycle networks.

  • In the cycle-based SBM experiment, classes 1 and 3 are similar despite different node counts, while the other classes are well-separated.Class 2 differs in edge weights, class 4 in community count, and class 5 in its proportion of negative edge weights.Source: §4.3 · p. 18, Figure 5 · p. 18

4.4 Experiment: Two-community SBMs with sliding means

  • On normalized two-community Gaussian-mixture SBMs, (R-TLB) performs reasonably well, with a dissimilarity gradient consistent with sliding means.Normalization puts edge weights in [−1, 1], a setting in which the authors expect simpler invariants such as size to likely fail.Source: §4.4 · pp. 18–19, Figure 5 · p. 18

4.5 Experiment: Real migration networks

  • Across 10 migration networks, (R-TLB) reveals temporal shifts, gender-linked clustering within periods, and similar male and female migration rates in 2000.The data cover male and female populations across five decades, with 225 country or administrative-region nodes per network.Source: §4.5 · p. 19

5 Discussion

The paper establishes the network GW distance as a pseudometric for directed, weighted networks and presents OT-based invariants that give readily computable lower bounds. Its experiments use a new SBM network model as well as simulated and real networks.

5 Discussion

  • The network GW distance is a valid pseudometric on directed, weighted networks, with a metric structure arising from the GW formulation.The authors emphasize that this structure on the space of networks is not inherited from a metric on the underlying spaces.Source: §5 · p. 20
  • OT-based network invariants provide lower bounds on the GW distance that are readily computable using at most linear programming.The paper tests these methods across a range of network datasets.Source: §5 · p. 20
  • The proposed network SBM may provide useful benchmarks for future network-method applications.Source: §5 · p. 20

A Computation via entropic regularization

This appendix discusses entropic regularization (ER) approaches for approximating a local minimum of the GW objective. It identifies numerical instability as a practical concern when network edge weights vary widely.

A Computation via entropic regularization

A.1 Numerical stability of entropic regularization

The appendix describes Sinkhorn scaling and stabilization strategies for entropic OT, whose kernel can become numerically unstable at large regularization parameters or across widely varying network edge weights. Log-domain initialization can help, but may not keep all kernel entries within machine limits.

A.1 Numerical stability of entropic regularization

  • Sinkhorn approximates the regularized OT solution by iteratively scaling the kernel K = e^(−λM) to match the two measures' row and column sums.The solution has the form diag(a)K diag(b).Source: §A.1 · p. 22
  • Large λ can drive kernel entries below machine precision and scaling updates to overflow, despite Sinkhorn's theoretical need for a positive kernel.The appendix gives e^−1000 as an example Matlab treats as zero, even with λ = 200 and Mij = 50.Source: §A.1 · p. 22
  • Wide edge-weight ranges within and across networks make kernel initialization especially difficult in network applications.The migration data vary greatly between countries and years.Source: §A.1 · p. 22
  • Log-domain initialization translates cost values before exponentiation, but may still fail to keep every kernel entry between machine precision and the machine limit.When the spread in min(M) and max(M) is too large, one recourse is changing λ; pair-specific λ values may be related to a global value by geometric rescaling for p = 2.Source: §A.1 · p. 23

A.1.1 Sturm’s cosine rule construction

The construction places the two networks on geodesic rays from the zero network, using size-based scalings to define reference networks. A resulting quantity depends on the reference networks, not on the chosen scaling parameters.

A.1.1 Sturm’s cosine rule construction

  • Sturm’s cosine-rule structure expresses the comparison using squared edge weights and their cross-product term.The passage explains the squared-difference expansion and identifies the resulting structure as Sturm’s cosine rule.Source: §A.1.1 · p. 24
  • The networks are represented as 2s- and 2t-scalings of reference networks on geodesic rays from the zero network.The rays are defined by scalar multiples of the edge-weight functions, with s and t set from the networks’ squared sizes.Source: §A.1.1 · p. 24
  • The resulting quantity depends only on the reference networks and is independent of the scaling parameters s and t.Source: §A.1.1 · p. 24

A.1.2 Interpretation of λ and rescaling

A weight-dependent entropic regularization parameter can be interpreted through rescaling the networks’ edge weights. These rescalings remain on geodesics connecting the original networks to the zero-network basepoint.

A.1.2 Interpretation of λ and rescaling

  • When e^(-λ*M) falls below machine precision, rescaling the cost matrix can match the kernel obtained with λXY.The stated condition is that e^(-λXY*M) remains above machine precision; M* = (λXY/λ*)M gives e^(-λ*M*) = e^(-λXY*M).Source: §A.1.2 · p. 24
  • For a cost matrix formed from the edge-weight product, rescaling the weights produces the corresponding rescaled cost matrix.The passage gives M = ωXωY and M* = (λXY/λ*)M as the example.Source: §A.1.2 · p. 24
  • The rescaled networks lie on geodesics connecting the original networks to the zero-network basepoint.Figure 7 depicts the interaction between the regularization parameter and these rescalings.Source: §A.1.2 · p. 24, Figure 7 · p. 25

Related papers

Loading 1808.04337v2…