Online Program Home
My Program

Abstract Details

Activity Number: 574 - Recent Advances in Software
Type: Contributed
Date/Time: Wednesday, July 31, 2019 : 2:00 PM to 3:50 PM
Sponsor: Section on Statistical Computing
Abstract #306505
Title: Graph Matching Algorithms Using the IGraphMatch R Package
Author(s): Zihuan Qiao* and Daniel L Sussman
Companies: and Boston University
Keywords: graph matching; R package; computational trade-offs

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.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2019 program