Research map / Point clouds / Point cloud classification
Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies the Procrustes-Wasserstein planted model (unknown orthogonal transform plus relabeling of Gaussian point clouds), gives information-theoretic recovery results in high and low dimensions under an L2 transport-cost metric, and proposes the Ping-Pong alternating algorithm initialized by Frank-Wolfe relaxed QAP.
Problem
Recovering the unknown relabeling and orthogonal transformation that align two noisy high-dimensional point clouds (Procrustes-Wasserstein), equivalently geometric graph alignment, in the unsupervised setting.
Approach
Uses the euclidean transport cost (instead of overlap) as the performance metric, derives information-theoretic recovery conditions in both d>>log n and d<<log n regimes, and proposes an alternating Ping-Pong algorithm (SVD for orthogonal step, LAP for permutation step) initialized by Frank-Wolfe on a convex relaxation, with one-step recovery guarantees.
Key results
- In high dimensions (d >= 2 log n), the ML estimator achieves overlap >= 1 - max(60 sigma^2, c d/n, c log n/(d log d)) w.h.p., so almost exact recovery when sigma -> 0.
- In low dimensions, estimators achieve c^2/(2d) <= delta and l2(Q)/(2d) <= delta when sigma <= C delta^2 d^{-1/2} and log n >= C d log(1/delta), i.e. sigma can be O(1) in transport-cost sense versus sigma = o(n^{-1/d}) for overlap.
- Experiments show Ping-Pong most globally outperforms the mini-batch Procrustes-Wasserstein algorithm in overlap accuracy across d, n, sigma settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Ping-Pong's greedy alternating minimization instead of projected gradient steps | Frank-Wolfe-initialized alignment algorithm · Procrustes-Wasserstein experiments | overlap | Helped |
Surprising findings
- Under the transport-cost metric, low-dimensional recovery is possible with noise sigma that does not vanish with n, whereas overlap recovery requires sigma decreasing polynomially in n.
Limitations
- One-step analysis only; no contraction/convergence proof for the full iterative algorithm.
- Low-dimensional guarantees for the conic alignment estimator are not computationally efficient.
- Experiments limited to synthetic data with small n and d.
Experimental setup
Datasets: synthetic Gaussian point clouds from planted model
Benchmarks: synthetic planted Gaussian model
Metrics: overlap L2 transport cost c^2 Frobenius error for Q
Baselines: Relaxed QAP via Frank-Wolfe Grave et al. mini-batch Procrustes-Wasserstein algorithm
Builds on: Procrustes problem (Schönemann) Umeyama algorithm Frank-Wolfe algorithm
Closest papers by meaning
- Fast Alignment of Embeddings: Computational Guarantees for Anisotropic Procrustes-Wasserstein (NeurIPS 2026 · similarity 0.92)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.87)
- Weighted Embeddings for Low-Dimensional Graph Representation (AAAI 2025 · similarity 0.86)
- Node Similarities under Random Projections: Limits and Pathological Cases (ICLR 2025 · similarity 0.86)
- Hypergraph Learning for Unsupervised Graph Alignment via Optimal Transport (AAAI 2025 · similarity 0.86)
- Fast Wasserstein rates for estimating probability distributions of probabilistic graphical models (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.