# REGAL: Representation Learning-based Graph Alignment

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2018.

## Built on by (most cited first, 30 of 40)

- [Hierarchical Multi-Marginal Optimal Transport for Network Alignment](https://mlsanity.com/paper/2310.04470/) (2023)
- [Simplicial Complex Representation Learning](https://mlsanity.com/paper/2103.04046/) (2021)
- [Generalizable Cross-Graph Embedding for GNN-based Congestion Prediction](https://mlsanity.com/paper/2111.05941/) (2021)
- [Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport](https://mlsanity.com/paper/2301.12721/) (2023)
- [Graph Mixup with Soft Alignments](https://mlsanity.com/paper/2306.06788/) (2023)
- [Domain-adaptive Message Passing Graph Neural Network](https://mlsanity.com/paper/2308.16470/) (2023)
- [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)
- [Node Proximity Is All You Need: Unified Structural and Positional Node and Graph Embedding](https://mlsanity.com/paper/2102.13582/) (2021)
- [Spectral Augmentations for Graph Contrastive Learning](https://mlsanity.com/paper/2302.02909/) (2023)
- [WL-Align: Weisfeiler-Lehman Relabeling for Aligning Users across Networks via Regularized Representation Learning](https://mlsanity.com/paper/2212.14182/) (2022)
- [A Survey on Role-Oriented Network Embedding](https://mlsanity.com/paper/2107.08379/) (2021)
- [On the Power of Gradual Network Alignment Using Dual-Perception Similarities](https://mlsanity.com/paper/2201.10945/) (2022)
- [Learning Structure-Semantic Evolution Trajectories for Graph Domain Adaptation](https://mlsanity.com/paper/2602.10506/) (2026)
- [Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning](https://mlsanity.com/paper/2102.10169/) (2021)
- [Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels](https://mlsanity.com/paper/2208.08638/) (2022)
- [Grad-Align+: Empowering Gradual Network Alignment Using Attribute Augmentation](https://mlsanity.com/paper/2208.11025/) (2022)
- [Towards Higher-order Topological Consistency for Unsupervised Network Alignment](https://mlsanity.com/paper/2208.12463/) (2022)
- [Towards Improving Embedding Based Models of Social Network Alignment via Pseudo Anchors](https://mlsanity.com/paper/2111.11335/) (2021)
- [Zoo Guide to Network Embedding](https://mlsanity.com/paper/2305.03474/) (2023)
- [CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment](https://mlsanity.com/paper/2406.13216/) (2024)
- [Efficient Network Embedding by Approximate Equitable Partitions](https://mlsanity.com/paper/2409.10160/) (2024)
- [Inference Attacks Against Graph Generative Diffusion Models](https://mlsanity.com/paper/2601.03701/) (2026)
- [Interactive Visual Pattern Search on Graph Data via Graph Representation Learning](https://mlsanity.com/paper/2202.09459/) (2022)
- [FadMan: Federated Anomaly Detection across Multiple Attributed Networks](https://mlsanity.com/paper/2205.14196/) (2022)
- [Image Keypoint Matching using Graph Neural Networks](https://mlsanity.com/paper/2205.14275/) (2022)
- [Digraphwave: Scalable Extraction of Structural Node Embeddings via Diffusion on Directed Graphs](https://mlsanity.com/paper/2207.10149/) (2022)
- [CAPER: Coarsen, Align, Project, Refine - A General Multilevel Framework for Network Alignment](https://mlsanity.com/paper/2208.10682/) (2022)
- [Centrality-Based Node Feature Augmentation for Robust Network Alignment](https://mlsanity.com/paper/2304.12751/) (2023)
- [A Hidden Challenge of Link Prediction: Which Pairs to Check?](https://mlsanity.com/paper/2102.07878/) (2021)

## Abstract (arXiv)

Problems involving multiple networks are prevalent in many scientific and other domains. In particular, network alignment, or the task of identifying corresponding nodes in different networks, has applications across the social and natural sciences. Motivated by recent advancements in node representation learning for single-graph tasks, we propose REGAL (REpresentation learning-based Graph ALignment), a framework that leverages the power of automatically-learned node representations to match nodes across different graphs. Within REGAL we devise xNetMF, an elegant and principled node embedding formulation that uniquely generalizes to multi-network problems. Our results demonstrate the utility and promise of unsupervised representation learning-based network alignment in terms of both speed and accuracy. REGAL runs up to 30x faster in the representation learning stage than comparable methods, outperforms existing network alignment methods by 20 to 30% accuracy on average, and scales to networks with millions of nodes each.