Research map / Graph learning / Graph algorithms and clustering
Graph Matching: Relax at Your Own Risk
Vince Lyzinski, Donniell E. Fishkind, Marcelo Fiori, Joshua T Vogelstein, Carey E. Priebe, Guillermo Sapiro
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| initialize FAQ at the convex optimum D* instead of the barycenter J | FAQ · KKI-NKI | vertices correctly matched: 38 -> 63 | Improved |
| initialize FAQ at the convex optimum D* instead of the barycenter J | FAQ · Wikipedia (fr-en) | vertices correctly matched: 30 -> 477 | Improved |
| initialize FAQ at the convex optimum D* instead of the barycenter J | FAQ · C. elegans | vertices correctly matched: 1 -> 5 | Improved |
| initialize FAQ at D* instead of the barycenter J | FAQ · KKI-NKI | ||A'P-PB||_F: 93895.21 -> 83642.64 | Improved |
| run indefinite FAQ from D* instead of projecting the convex solution (P_c) | convex relaxation · KKI-NKI | vertices correctly matched: 41 -> 63 | Improved |
| run indefinite FAQ from D* instead of projecting the convex solution (P_c) | convex relaxation · Wikipedia (fr-en) | vertices correctly matched: 97 -> 477 | Improved |
| use FAQ:D* instead of PATH | PATH · KKI-NKI | vertices correctly matched: 1 -> 63 | Improved |
| use FAQ:D* instead of GLAG | GLAG · Wikipedia (fr-en) | vertices correctly matched: 181 -> 477 | Improved |
| use FAQ:D* instead of GLAG | GLAG · C. elegans | ||A'P-PB||_F: 145.53 -> 127.50 | Improved |
| initialize FAQ at D* in power law graphs (vs convex projection, PATH, GLAG) | FAQ · power law random graphs (150 vertices) | success rate recovering P* | Improved |
| initialize FAQ at D* in bounded-degree graphs | FAQ · bounded degree graphs (max degree 4) | success rate recovering P* | Improved |
| initialize FAQ at the true permutation P* (oracle) vs D* | FAQ · bounded degree graphs, p=0 | success rate recovering P* | Improved |
Closest papers by meaning
- A Convex Relaxation for Multi-Graph Matching (CVPR 2019 · similarity 0.92)
- Graph Matching with Partially-Correct Seeds (JMLR 2021 · similarity 0.90)
- Learning Partial Graph Matching via Optimal Partial Transport (ICLR 2025 · similarity 0.89)
- Graph Alignment via Birkhoff Relaxation (NeurIPS 2025 · similarity 0.88)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.88)
- FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing (NeurIPS 2025 · similarity 0.87)
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.
