Spar-GW: Efficient Gromov-Wasserstein Distance Approximation for Structured Data

A paper from Huazhong University of Science and Technology proposes the Spar-GW method for approximating the Gromov-Wasserstein distance, a metric for structured data like point clouds and graphs. The method reduces computational complexity from O(n^4) to O(n^(2+δ)) for an arbitrary small δ>0. The work includes theoretical convergence guarantees and experimental validation on synthetic and real-world tasks.

Use Cases

• Matching point clouds based on the Gromov-Wasserstein distance framework described.
• Aligning graph-structured data using the proposed importance sparsification method.
• Approximating variants of GW distance, such as entropic or unbalanced GW distance, as mentioned in the description.
• Benchmarking computational efficiency for metric-measure space comparisons in synthetic tasks.

Strengths

• The proposed Spar-GW method reduces computational complexity from O(n^4) to O(n^(2+δ)) for an arbitrary small δ>0.
• Method is applicable to GW distance with arbitrary ground cost and can be extended to variants like entropic and unbalanced GW distance.
• Theoretical convergence and consistency are established under mild regularity conditions.

Limitations

• Row count and dataset size are unknown, which may limit suitability assessment.
• Column-level documentation is absent; field semantics must be inferred after download.
• Last update date is unknown; freshness unverified.

Provenance

Source

Huazhong University of Science and Technology

Collection Method

Proposed as a novel importance sparsification method in an academic paper.