Research map / Graph learning / Graph algorithms and clustering
Adaptive Softassign via Hadamard-Equipped Sinkhorn
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.
Proposes adaptive softassign that automatically tunes the inflation parameter beta from an error bound, plus Hadamard-equipped Sinkhorn identities for fast, stable recursive computation, yielding an adaptive softassign graph matching algorithm (ASM).
Problem
Softassign-based graph matching is sensitive to the inflation parameter beta, which is currently tuned empirically; large beta is costly and numerically unstable in Sinkhorn.
Approach
Selects beta adaptively by bounding the change between softassign solutions at beta and beta+Δβ, and computes the transition between them recursively via Sinkhorn-Hadamard identities (softassign transition), avoiding overflow/underflow and repeated full Sinkhorn computations.
Key results
- On yeast PPI at 25% noise, ASM reaches 75.1% node accuracy versus 57.6% for GWL and 43.0% for SCG.
- On Facebook at 5% noise, ASM reaches 91.1% node accuracy versus 79.7% for DSPFP and 78.1% for GWL.
- The softassign transition gives a 6.7x speedup at matrix size 2000 for adaptive softassign.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use ASM instead of GWL | Yeast PPI matching · Yeast PPI, 5% noise | Node Acc: 83.7% -> 89.0% | Helped |
| use ASM instead of GWL | Yeast PPI matching · Yeast PPI, 15% noise | Node Acc: 66.3% -> 81.2% | Helped |
| use ASM instead of GWL | Yeast PPI matching · Yeast PPI, 25% noise | Node Acc: 57.6% -> 75.1% | Helped |
| use ASM instead of DSPFP | Facebook matching · Facebook, 5% noise | Node Acc: 79.7% -> 91.1% | Helped |
| use ASM instead of GWL | Facebook matching · Facebook, 15% noise | Node Acc: 68.4% -> 88.4% | Helped |
| use ASM instead of DSPFP | Facebook matching · Facebook, 25% noise | Node Acc: 62.2% -> 85.7% | Helped |
| use ASM instead of AIPFP | 1000-node real-image matching · Leuven | Error (×104): 2.7 -> 2.3 | Helped |
| use ASM instead of SCG | 1000-node real-image matching · ubc | Error (×104): 2.3 -> 2.2 | Helped |
| use ASM instead of SCG | 1000-node real-image matching · trees | Error (×104): 2.5 -> 2.4 | Helped |
| use ASM instead of SCG | 1000-node real-image matching · wall | Error (×104): 2.6 -> 2.5 | Helped |
| add softassign transition (ablation) | Adaptive softassign · Random matrices, matrix size 2000 | speedup ratio: 6.7x | Helped |
Surprising findings
- Adaptive softassign is reported to be roughly tenfold more efficient than GWL on PPI, while on plain graphs ASM is not first-tier in efficiency, which the authors acknowledge.
Limitations
- Efficiency is not first-tier on plain graph matching problems.
- Choice of delta-beta and beta0 relies on heuristics (ln n) and empirical observations.
- Error bound guarantee depends on prior softassign error analysis [32].
Experimental setup
Datasets: yeast PPI network Facebook social network Oxford affine image dataset (Leuven, ubc, trees, wall)
Benchmarks: yeast PPI network matching Facebook social network matching real image graph matching
Metrics: node accuracy matching error running time
Baselines: DSPFP GA AIPFP SCG GWL S-GWL MAGNA++ GRASP
Builds on: softassign projected fixed-point method Sinkhorn algorithm SCG adaptive step size (AIPFP)
Closest papers by meaning
- FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing (NeurIPS 2025 · similarity 0.84)
- Learning Combinatorial Solver for Graph Matching (CVPR 2020 · similarity 0.83)
- Alternating Direction Graph Matching (CVPR 2017 · similarity 0.83)
- SAT-Based Algorithms for Regular Graph Pattern Matching (AAAI 2024 · similarity 0.83)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.82)
- Learning Partial Graph Matching via Optimal Partial Transport (ICLR 2025 · similarity 0.82)
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.