Feng Shi and Ziheng Xu, UCLA, presenting on July 22, 2020 at 11:00 a.m. and 7:00 p.m. ET)
As a fundamental problem in pattern recognition, graph matching has applications in a variety of fields, especially for computer vision. The utilization of graph matching in video analytics include (but not limited) scene understanding, object keypoints matching, checking the availability of scene generation, etc.. The graph similarity (or matching) problem attempts to find node correspondences between graphs. Traditionally, obtaining an exact solution with heuristic algorithms is NP-hard and spends long latency; recently, the research employing deep graph architectures has been proposed in finding an approximate solution, which leverages the speed and accuracy. Previous works in such research mainly focused on using localized node embeddings to obtain an approximate node alignment. However, investigating only local features cannot reflect the whole structure; the overall graph topology plays a vital role in determining the edge alignment between graphs. Diffusion wavelets, which depict the probability distributions of graph signals over a graph, are powerful tools to assist in the graph topology exploration. In this work, we present WaveSim, a light-weight deep graph matching framework incorporating graph diffusion wavelets to calculate the diffusion distance. We also mathematically prove that it is possible to transform a Quadratic Assignment Programming (QAP) problem with high-order combinatorial nature into a lower dimension problem. Experiments show that WaveSim achieves remarkable and robust performances, and can be extended to matching problems with large graphs.
