# CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 89 references that are in the map.
- First posted on arXiv 19 Jun 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [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)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Predicting multicellular function through multi-layer tissue networks](https://mlsanity.com/paper/1707.04638/) (2017)
- [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)
- [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)
- [REGAL: Representation Learning-based Graph Alignment](https://mlsanity.com/paper/1802.06257/) (2018)
- [A Benchmark and Comprehensive Survey on Knowledge Graph Entity Alignment via Representation Learning](https://mlsanity.com/paper/2103.15059/) (2021)
- [Entity Alignment with Noisy Annotations from Large Language Models](https://mlsanity.com/paper/2405.16806/) (2024)
- [A Fused Gromov-Wasserstein Framework for Unsupervised Knowledge Graph Entity Alignment](https://mlsanity.com/paper/2305.06574/) (2023)
- [A Solution for Multi-Alignment by Transformation Synchronisation](https://mlsanity.com/paper/1410.8546/) (2014)
- [Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport](https://mlsanity.com/paper/2301.12721/) (2023)
- [Unlocking the Power of Large Language Models for Entity Alignment](https://mlsanity.com/paper/2402.15048/) (2024)
- [A Comparative Study of Graph Matching Algorithms in Computer Vision](https://mlsanity.com/paper/2207.00291/) (2022)
- [Spectral Alignment of Graphs](https://mlsanity.com/paper/1602.04181/) (2016)
- [WL-Align: Weisfeiler-Lehman Relabeling for Aligning Users across Networks via Regularized Representation Learning](https://mlsanity.com/paper/2212.14182/) (2022)
- [GRASP: Graph Alignment through Spectral Signatures](https://mlsanity.com/paper/2106.05729/) (2021)
- [Domain-adversarial Network Alignment](https://mlsanity.com/paper/1908.05429/) (2019)
- [Towards Higher-order Topological Consistency for Unsupervised Network Alignment](https://mlsanity.com/paper/2208.12463/) (2022)

## Built on by (most cited first, 2 of 2)

- [Towards Effective and Efficient Graph Alignment without Supervision](https://mlsanity.com/paper/2603.08526/) (2026)
- [Scalable Optimal Transport Algorithm for Network Alignment](https://mlsanity.com/paper/2607.11952/) (2026)

## Abstract (arXiv)

Unsupervised graph alignment finds the node correspondence between a pair of attributed graphs by only exploiting graph structure and node features. One category of recent studies first computes the node representation and then matches nodes with the largest embedding-based similarity, while the other category reduces the problem to optimal transport (OT) via Gromov-Wasserstein learning. However, it remains largely unexplored in the model expressiveness, as well as how theoretical expressivity impacts prediction accuracy. We investigate the model expressiveness from two aspects. First, we characterize the model's discriminative power in distinguishing matched and unmatched node pairs across two graphs. Second, we study the model's capability of guaranteeing node matching properties such as one-to-one matching and mutual alignment. Motivated by our theoretical analysis, we put forward a hybrid approach named CombAlign with stronger expressive power. Specifically, we enable cross-dimensional feature interaction for OT-based learning and propose an embedding-based method inspired by the Weisfeiler-Lehman test. We also apply non-uniform marginals obtained from the embedding-based modules to OT as priors for more expressiveness. Based on that, we propose a traditional algorithm-based refinement, which combines our OT and embedding-based predictions using the ensemble learning strategy and reduces the problem to maximum weight matching. With carefully designed edge weights, we ensure those matching properties and further enhance prediction accuracy. By extensive experiments, we demonstrate a significant improvement of 14.5% in alignment accuracy compared to state-of-the-art approaches and confirm the soundness of our theoretical analysis.