# CAPER: Coarsen, Align, Project, Refine - A General Multilevel Framework for Network Alignment

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 22 references that are in the map.
- First posted on arXiv 23 Aug 2022.

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

- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding](https://mlsanity.com/paper/1910.02370/) (2019)
- [REGAL: Representation Learning-based Graph Alignment](https://mlsanity.com/paper/1802.06257/) (2018)
- [MILE: A Multi-Level Framework for Scalable Graph Embedding](https://mlsanity.com/paper/1802.09612/) (2018)
- [KerGM: Kernelized Graph Matching](https://mlsanity.com/paper/1911.11120/) (2019)
- [G-CREWE: Graph CompREssion With Embedding for Network Alignment](https://mlsanity.com/paper/2007.16208/) (2020)
- [Refining Network Alignment to Improve Matched Neighborhood Consistency](https://mlsanity.com/paper/2101.08808/) (2021)

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

- [AlignGraph: A Group of Generative Models for Graphs](https://mlsanity.com/paper/2301.11273/) (2023)

## Abstract (arXiv)

Network alignment, or the task of finding corresponding nodes in different networks, is an important problem formulation in many application domains. We propose CAPER, a multilevel alignment framework that Coarsens the input graphs, Aligns the coarsened graphs, Projects the alignment solution to finer levels and Refines the alignment solution. We show that CAPER can improve upon many different existing network alignment algorithms by enforcing alignment consistency across multiple graph resolutions: nodes matched at finer levels should also be matched at coarser levels. CAPER also accelerates the use of slower network alignment methods, at the modest cost of linear-time coarsening and refinement steps, by allowing them to be run on smaller coarsened versions of the input graphs. Experiments show that CAPER can improve upon diverse network alignment methods by an average of 33% in accuracy and/or an order of magnitude faster in runtime.