# Scalable Optimal Transport Algorithm for Network Alignment

arXiv: https://arxiv.org/abs/2607.11952 · HTML: https://mlsanity.com/paper/2607.11952/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 11 Jul 2026.

## Builds on (most cited first, 14 of 14)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Graph Optimal Transport for Cross-Domain Alignment](https://mlsanity.com/paper/2006.14744/) (2020)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [GE-SpMM: General-purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networks](https://mlsanity.com/paper/2007.03179/) (2020)
- [REGAL: Representation Learning-based Graph Alignment](https://mlsanity.com/paper/1802.06257/) (2018)
- [AceKG: A Large-scale Knowledge Graph for Academic Data Mining](https://mlsanity.com/paper/1807.08484/) (2018)
- [Design Principles for Sparse Matrix Multiplication on the GPU](https://mlsanity.com/paper/1803.08601/) (2018)
- [Joint Optimal Transport and Embedding for Network Alignment](https://mlsanity.com/paper/2502.19334/) (2025)
- [PLANETALIGN: A Comprehensive Python Library for Benchmarking Network Alignment](https://mlsanity.com/paper/2505.21366/) (2025)
- [Graph Matching via Optimal Transport](https://mlsanity.com/paper/2111.05366/) (2021)
- [CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment](https://mlsanity.com/paper/2406.13216/) (2024)
- [Sparsity-Aware Roofline Models for Sparse Matrix-Matrix Multiplication](https://mlsanity.com/paper/2604.06637/) (2026)
- [AvAtar: Learning to Align via Active Optimal Transport](https://mlsanity.com/paper/2605.24395/) (2026)

## Abstract (arXiv)

Network alignment identifies node correspondences across different networks and is a fundamental primitive in many data science applications, including social network analysis, fraud detection, and knowledge graph integration. However, state-of-the-art network alignment methods often achieve high accuracy by repeatedly constructing and updating dense matrices, sacrificing scalability in the process. To address this scalability limitation without compromising alignment accuracy, we present FastAlign, a scalable, sparsity-aware framework for optimal transport-based network alignment. Rather than introducing a new alignment model, FastAlign preserves the original OT formulation and reinterprets its computation as a set of recurring mixed sparse-dense operations. FastAlign combines sparsity-aware graph computation with domain-specific kernel fusion, including a custom SpMM kernel. Our results show that FastAlign achieves alignment quality comparable to state-of-the-art OT-based methods while substantially reducing end-to-end runtime up to 3.89x-9.45x on CPU and 2.24x-32.54x on GPU.