# Towards Effective and Efficient Graph Alignment without Supervision

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 60 references that are in the map.
- First posted on arXiv 9 Mar 2026.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion](https://mlsanity.com/paper/2301.09474/) (2023)
- [REGAL: Representation Learning-based Graph Alignment](https://mlsanity.com/paper/1802.06257/) (2018)
- [SelfKG: Self-Supervised Entity Alignment in Knowledge Graphs](https://mlsanity.com/paper/2203.01044/) (2022)
- [From Alignment to Assignment: Frustratingly Simple Unsupervised Entity Alignment](https://mlsanity.com/paper/2109.02363/) (2021)
- [Unsupervised Knowledge Graph Alignment by Probabilistic Reasoning and Semantic Embedding](https://mlsanity.com/paper/2105.05596/) (2021)
- [LightEA: A Scalable, Robust, and Interpretable Entity Alignment Framework via Three-view Label Propagation](https://mlsanity.com/paper/2210.10436/) (2022)
- [A Fused Gromov-Wasserstein Framework for Unsupervised Knowledge Graph Entity Alignment](https://mlsanity.com/paper/2305.06574/) (2023)
- [Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport](https://mlsanity.com/paper/2301.12721/) (2023)
- [Spectral Alignment of Graphs](https://mlsanity.com/paper/1602.04181/) (2016)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [Interactive Contrastive Learning for Self-supervised Entity Alignment](https://mlsanity.com/paper/2201.06225/) (2022)
- [CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment](https://mlsanity.com/paper/2406.13216/) (2024)

## Abstract (arXiv)

Unsupervised graph alignment aims to find the node correspondence across different graphs without any anchor node pairs. Despite the recent efforts utilizing deep learning-based techniques, such as the embedding and optimal transport (OT)-based approaches, we observe their limitations in terms of model accuracy-efficiency tradeoff. By focusing on the exploitation of local and global graph information, we formalize them as the ``local representation, global alignment'' paradigm, and present a new ``global representation and alignment'' paradigm to resolve the mismatch between the two phases in the alignment process. We then propose underlineGlobal representation and underlineoptimal transport-underlinebased underlineAlignment (textttGlobAlign), and its variant, textttGlobAlign-E, for better underlineEfficiency. Our methods are equipped with the global attention mechanism and a hierarchical cross-graph transport cost, able to capture long-range and implicit node dependencies beyond the local graph structure. Furthermore, textttGlobAlign-E successfully closes the time complexity gap between representative embedding and OT-based methods, reducing OT's cubic complexity to quadratic terms. Through extensive experiments, our methods demonstrate superior performance, with up to a 20% accuracy improvement over the best competitor. Meanwhile, textttGlobAlign-E achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods.