# Blind Graph Matching Using Graph Signals

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2023.

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

- [Recovering Missing Node Features with Local Structure-based Embeddings](https://mlsanity.com/paper/2309.09068/) (2023)
- [Disentangled Structural and Featural Representation for Task-Agnostic Graph Valuation](https://mlsanity.com/paper/2408.12659/) (2024)
- [Shuffled Linear Regression via Spectral Matching](https://mlsanity.com/paper/2410.00078/) (2024)

## Abstract (arXiv)

Classical graph matching aims to find a node correspondence between two unlabeled graphs of known topologies. This problem has a wide range of applications, from matching identities in social networks to identifying similar biological network functions across species. However, when the underlying graphs are unknown, the use of conventional graph matching methods requires inferring the graph topologies first, a process that is highly sensitive to observation errors. In this paper, we tackle the blind graph matching problem with unknown underlying graphs directly using observations of graph signals, which are generated from graph filters applied to graph signal excitations. We propose to construct sample covariance matrices from the observed signals and match the nodes based on the selected sample eigenvectors. Our analysis shows that the blind matching outcome converges to the result obtained with known graph topologies when the signal sampling size is large and the signal noise is small. Numerical results showcase the performance improvement of the proposed algorithm compared to matching two estimated underlying graphs learned from the graph signals.