|
Abstract:
|
Graph matching (GM) algorithms impact many areas such as machine learning, pattern recognition, neuroscience, and biology. GM seeks to align the vertex sets of two graphs to best preserve the edge structure. One of the most scalable approximate GM algorithms, the percolation algorithm propagates the prior information from a set of true correspondences and matches two graphs incrementally. We propose the soft percolation algorithm that allows for more promising matches to replace the existing ones, thus eliminating snowballing of errors. Extensions can be made to matching graphs of different orders with centered padding schemes. We demonstrate the effectiveness of our algorithm,conduct an analysis of the efficiency, and investigate the computation trade-offs among the FAQ, percolation and soft percolation algorithms via simulation and real data experiments using the iGraphMatch R package, a centralized repository developed for GM.
|
