TY - GEN
T1 - Correcting the Output of Approximate Graph Matching Algorithms
AU - Lubars, Joseph
AU - Srikant, R.
N1 - Funding Information:
Research supported by NSF Grant 479752-239015-191100.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/10/8
Y1 - 2018/10/8
N2 - Approximate graph matching refers to the problem of finding the best correspondence between the node labels of two correlated graphs. The problem has been applied to a number of domains, including social network de-anonymization. Recently, a number of algorithms have been proposed for seeded graph matching, which uses a few seed matches between two graphs to determine the remaining correspondence. We adapt the ideas from seeded algorithms to develop a graph matching correction algorithm, which takes a partially correct correspondence as input and returns an improved correspondence. We show that this algorithm can correct all errors in graph matching for stochastic block model graphs with high probability. Finally, we apply our algorithm as a post-processing step for other approximate graph matching algorithms to significantly improve the performance of state-of-the-art algorithms for seedless graph matching.
AB - Approximate graph matching refers to the problem of finding the best correspondence between the node labels of two correlated graphs. The problem has been applied to a number of domains, including social network de-anonymization. Recently, a number of algorithms have been proposed for seeded graph matching, which uses a few seed matches between two graphs to determine the remaining correspondence. We adapt the ideas from seeded algorithms to develop a graph matching correction algorithm, which takes a partially correct correspondence as input and returns an improved correspondence. We show that this algorithm can correct all errors in graph matching for stochastic block model graphs with high probability. Finally, we apply our algorithm as a post-processing step for other approximate graph matching algorithms to significantly improve the performance of state-of-the-art algorithms for seedless graph matching.
UR - http://www.scopus.com/inward/record.url?scp=85056184503&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85056184503&partnerID=8YFLogxK
U2 - 10.1109/INFOCOM.2018.8486238
DO - 10.1109/INFOCOM.2018.8486238
M3 - Conference contribution
AN - SCOPUS:85056184503
T3 - Proceedings - IEEE INFOCOM
SP - 1745
EP - 1753
BT - INFOCOM 2018 - IEEE Conference on Computer Communications
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE Conference on Computer Communications, INFOCOM 2018
Y2 - 15 April 2018 through 19 April 2018
ER -