Solutions of the Graph Matching Problem Using Graph Signals

The problem of graph matching involves finding a node correspondence between two unlabeled graphs with known topologies, which has applications in various fields such as social network analysis and species identification. In this paper, we tackle this problem without prior knowledge of the underlying graphs and using only observations of graph signals. We assume that these signals are generated by applying graph filters to graph signal excitations. We construct sample covariance matrices from the graph signals and match the nodes based on the selected eigenvectors of the sample covariance matrices. Numerical results demonstrate that our proposed algorithm outperforms the existing method that matches two estimated underlying graphs learned from the graph signals.