# GRASP: Graph Alignment through Spectral Signatures

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2021.

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

- [Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport](https://mlsanity.com/paper/2301.12721/) (2023)
- [Spectral Maps for Learning on Subgraphs](https://mlsanity.com/paper/2205.14938/) (2022)
- [CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment](https://mlsanity.com/paper/2406.13216/) (2024)
- [Latent Functional Maps: a spectral framework for representation alignment](https://mlsanity.com/paper/2406.14183/) (2024)
- [EUGENE: Explainable Structure-aware Graph Edit Distance Estimation with Generalized Edit Costs](https://mlsanity.com/paper/2402.05885/) (2024)

## Abstract (arXiv)

What is the best way to match the nodes of two graphs? This graph alignment problem generalizes graph isomorphism and arises in applications from social network analysis to bioinformatics. Some solutions assume that auxiliary information on known matches or node or edge attributes is available, or utilize arbitrary graph features. Such methods fare poorly in the pure form of the problem, in which only graph structures are given. Other proposals translate the problem to one of aligning node embeddings, yet, by doing so, provide only a single-scale view of the graph. In this paper, we transfer the shape-analysis concept of functional maps from the continuous to the discrete case, and treat the graph alignment problem as a special case of the problem of finding a mapping between functions on graphs. We present GRASP, a method that first establishes a correspondence between functions derived from Laplacian matrix eigenvectors, which capture multiscale structural characteristics, and then exploits this correspondence to align nodes. Our experimental study, featuring noise levels higher than anything used in previous studies, shows that GRASP outperforms state-of-the-art methods for graph alignment across noise levels and graph types.