Publications

We propose a novel graph matching algorithm that uses ideas from graph signal processing to match vertices of graphs using alternative graph representations. Specifically, we consider a multi-scale heat diffusion on the graphs to create multiple weighted graph representations that incorporate both direct adjacencies as well as local structures induced from the heat diffusion. Then a multi-objective optimization method is used to match vertices across all pairs of graph representations simultaneously. We show that our proposed algorithm performs significantly better than the algorithm that only uses the adjacency matrices, especially when the number of known latent alignments between vertices (seeds) is small. We test the algorithm on a set of graphs and show that at the low seed level, the proposed algorithm performs at least 15–35% better than the traditional graph matching algorithm.

In this white paper we propose a new method which exploits tools from graph signal processing to solve the graph matching problem, the problem of estimating the correspondence between the vertex sets of two graphs. We recast the graph matching problem as matching multiple similarity matrices where the similarities are computed between filtered signals unique to eachnode. Using appropriate graph filters, these similarity matrices can emphasize long or short range behavior and the method will implicitly search for similarities between the graphs and at multiple scales. Our method shows substantial improvementsover standard methods which use the raw adjacency matrices, especially in low-information environments.