Research map / Learning theory and algorithms / Optimal transport
Hierarchical Multi-Marginal Optimal Transport for Network Alignment
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 HOT, a hierarchical multi-marginal optimal transport framework for aligning multiple networks, combining FGW-barycenter cluster-level alignment with a multi-marginal FGW node-level alignment solved by a proximal point method.
Problem
Multi-network alignment (finding node correspondences across K networks) is hard due to a lack of high-order discrepancy measures and an exponentially growing solution space.
Approach
Generalizes the fused Gromov-Wasserstein distance to a multi-marginal setting (MFGW) with a position-aware RWR-based cost tensor, and decomposes the problem hierarchically via FGW barycenter clusters so node-level MFGW subproblems are small; a proximal point method with KL regularization and Sinkhorn inner solves gives convergence to a local optimum.
Key results
- HOT outperforms the best consistency-based method by at least 55.3% in PH@10 and 51.9% in HH@10 on plain networks.
- HOT outperforms the best embedding-based method by at least 4.0% in PH@10 and 12.0% in HH@10 on plain networks.
- HOT achieves up to 360x speedup and 1000x memory reduction compared with the non-hierarchical solution when scaling number of graphs K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HOT instead of the best embedding-based competitor | Multi-network alignment · Plain networks | High-order Hits@10: 12.0% | Helped |
| Use HOT instead of the best OT-based competitor | Multi-network alignment · Plain networks | High-order Hits@10: 15.8% | Helped |
| Increase the number of clusters M (ablation) | HOT · ACM(A)-500 and DBLP(A)-500 | High-order Hits@10 | Mixed |
| Vary restart probability β (ablation) | HOT · DBLP(A)-500 | Pairwise Hits@10 | No clear effect |
| Increase α toward 1 (ablation) | HOT · DBLP(A)-500 | Pairwise Hits@10 | Hurt |
Surprising findings
- Pairwise FGW distances underestimate the joint MFGW distance: MFGW is lower bounded by the sum of all pairwise FGW distances.
Limitations
- Complexity remains exponential in the number of graphs K for node-level alignment.
- Only two levels (cluster and node) are considered; multi-level hierarchy is future work.
- Baselines with dense alignment tensors run out of memory for K>=5 or networks above 2000 nodes, so comparisons at scale are limited.
Experimental setup
Datasets: Douban ER DBLP ACM
Benchmarks: Douban-230 ER-500 DBLP-500 DBLP-1000 ACM(A)-1000 DBLP(A)-1000
Metrics: pairwise Hits@K high-order Hits@K MRR running time memory cost
Baselines: IsoRank FINAL MOANA SYTE CrossMNA NetTrans NeXtAlign Grad-Align GW FGW LOT S-GWL
Builds on: fused Gromov-Wasserstein distance multi-marginal optimal transport unified random walk with restart S-GWL Sinkhorn algorithm
Closest papers by meaning
- PLANETALIGN: A Comprehensive Python Library for Benchmarking Network Alignment (ICLR 2026 · similarity 0.88)
- Hypergraph Learning for Unsupervised Graph Alignment via Optimal Transport (AAAI 2025 · similarity 0.86)
- Chaining 2-FWL GNNs for Combinatorial Graph Alignment (NeurIPS 2026 · similarity 0.85)
- Hierarchical Refinement: Optimal Transport to Infinity and Beyond (ICML 2025 · similarity 0.85)
- Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · similarity 0.85)
- Transfer Learning on Edge Connecting Probability Estimation Under Graphon Model (NeurIPS 2025 · similarity 0.84)
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.